[Verifier] add invariant check for callbr

[nickdesaulniers]

Summary

The list of indirect labels should ALWAYS have their blockaddresses as
argument operands to the callbr (but not necessarily the other way
around). Add an invariant that checks this.

The verifier catches a bad test case that was added recently in r368478.
I think that was a simple mistake, and the test was made less strict in
regards to the precise addresses (as those weren't specifically the
point of the test).

This invariant will be used to find a reported bug.

Link: https://www.spinics.net/lists/arm-kernel/msg753473.html
Link: https://github.com/ClangBuiltLinux/linux/issues/649

[nickdesaulniers]

• rebase on master, run git-clang-format HEAD~

[lebedev.ri]

Is this already documented in LangRef?

llvm/test/CodeGen/AArch64/callbr-asm-obj-file.ll

1–4

Does update_llc_test_checks actually deal with this chaining?
I don't believe it does.

[nickdesaulniers]

In D67196#1658509, @lebedev.ri wrote:

Is this already documented in LangRef?

It is not!
https://llvm.org/docs/LangRef.html#callbr-instruction
Shall I add to that in this patch? (Assuming it's ok to explicitly state such an invariant?)

llvm/test/CodeGen/AArch64/callbr-asm-obj-file.ll

1–4

It does not, hence why I wasn't able to run ./llvm/utils/update_llc_test_checks.py llvm/test/CodeGen/AArch64/callbr-asm-obj-file.lland then observe any changes to the file (other than the header, which I see I committed accidentally). Do you know how I would fix the chaining related issue?

[lebedev.ri]

llvm/test/CodeGen/AArch64/callbr-asm-obj-file.ll

1–4

By manually updating the check lines i suppose. I hate doing that :/

[srhines]

llvm/test/Verifier/callbr.ll

3

Can you add a test case that shows the proper subset behavior (i.e. more blockaddress labels than are handled by the indirect label list)?

Can you also flip the labels in one test case so that you aren't just iterating over the same exact labels in the same exact order in both places (i.e. verify set behavior rather than just simple iteration).

[nickdesaulniers]

• add unit test, add invariant to LangRef, remove "or jump" from LangRef (was never there)

[nickdesaulniers]

• fix my added unit test

[srhines]

LGTM, but please wait for someone more familiar with LangRef policies to review that part.

[nickdesaulniers]

• rebase

[void]

The llvm/test/CodeGen/AArch64/callbr-asm-obj-file.ll change LGTM.

[nickdesaulniers]

Bumping for code review

[void]

LGTMing. Others please comment if you have objections.

llvm/docs/LangRef.rst

 ^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
       <result> = callbr [cconv] [ret attrs] [addrspace(<num>)] <ty>|<fnty> <fnptrval>(<function args>) [fn attrs]
-                    [operand bundles] to label <normal label> or jump [other labels]
+                    [operand bundles] to label <normal label> [other labels]
 
 Overview:
 """""""""
 
 The '``callbr``' instruction causes control to transfer to a specified
 function, with the possibility of control flow transfer to either the
 '``normal``' label or one of the '``other``' labels.
 

 #. '``function args``': argument list whose types match the function
    signature argument types and parameter attributes. All arguments must
    be of :ref:`first class <t_firstclass>` type. If the function signature
    indicates the function accepts a variable number of arguments, the
    extra arguments can be specified.
 #. '``normal label``': the label reached when the called function
    executes a '``ret``' instruction.
 #. '``other labels``': the labels reached when a callee transfers control
-   to a location other than the normal '``normal label``'
+   to a location other than the normal '``normal label``'. The blockaddress
+   constant for these should also be in the list of '``function args``'.
 #. The optional :ref:`function attributes <fnattrs>` list.
 #. The optional :ref:`operand bundles <opbundles>` list.
 
 Semantics:
 """"""""""
 
 This instruction is designed to operate as a standard '``call``'
 instruction in most regards. The primary difference is that it
 establishes an association with additional labels to define where control
 flow goes after the call.
 
 The only use of this today is to implement the "goto" feature of gcc inline
 assembly where additional labels can be provided as locations for the inline
 assembly to jump to.
 
 Example:
 """"""""
 
 .. code-block:: text
 
       callbr void asm "", "r,x"(i32 %x, i8 *blockaddress(@foo, %fail))
-                  to label %normal or jump [label %fail]
+                  to label %normal [label %fail]
 
 .. _i_resume:
 
 '``resume``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""

llvm/lib/IR/Verifier.cpp

void Verifier::visitCallBrInst(CallBrInst &CBI) {
   for (unsigned i = 0, e = CBI.getNumOperands(); i != e; ++i) {
     Assert(i >= CBI.getNumArgOperands() || !isa<BasicBlock>(CBI.getOperand(i)),
            "Using an unescaped label as a callbr argument!", &CBI);
     if (isa<BasicBlock>(CBI.getOperand(i)))
       for (unsigned j = i + 1; j != e; ++j)
         Assert(CBI.getOperand(i) != CBI.getOperand(j),
                "Duplicate callbr destination!", &CBI);
   }
+  {
+    SmallPtrSet<BasicBlock *, 4> ArgBBs;
+    for (Value *V : CBI.args())
+      if (auto *BA = dyn_cast<BlockAddress>(V))
+        ArgBBs.insert(BA->getBasicBlock());
+    for (BasicBlock *BB : CBI.getIndirectDests())
+      Assert(ArgBBs.find(BB) != ArgBBs.end(),
+             "Indirect label missing from arglist.", &CBI);
+  }
 
   visitTerminator(CBI);
 }
 
 void Verifier::visitSelectInst(SelectInst &SI) {
   Assert(!SelectInst::areInvalidOperands(SI.getOperand(0), SI.getOperand(1),
                                          SI.getOperand(2)),
          "Invalid operands for select instruction!", &SI);

llvm/test/CodeGen/AArch64/callbr-asm-obj-file.ll

 ; RUN: llc < %s -mtriple=aarch64-unknown-linux-gnu -filetype=obj -o - \
 ; RUN:  | llvm-objdump -triple aarch64-unknown-linux-gnu -d - \
 ; RUN:  | FileCheck %s
 
 %struct.c = type { i1 (...)* }
 
 @l = common hidden local_unnamed_addr global i32 0, align 4
 
-; CHECK-LABEL: 0000000000000000 test1:
-; CHECK-LABEL: 0000000000000018 $d.1:
-; CHECK-LABEL: 0000000000000020 $x.2:
+; CHECK-LABEL: test1:
+; CHECK-LABEL: $d.1:
+; CHECK-LABEL: $x.2:
 ; CHECK-NEXT:    b #16 <$x.4+0x4>
-; CHECK-LABEL: 000000000000002c $x.4:
+; CHECK-LABEL: $x.4:
 ; CHECK-NEXT:    b #4 <$x.4+0x4>
 ; CHECK-NEXT:    mov w0, wzr
 ; CHECK-NEXT:    ldr x30, [sp], #16
 ; CHECK-NEXT:    ret
 define hidden i32 @test1() {
   %1 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)()
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %3, label %5
7:                                                ; preds = %3, %4, %5
   %8 = phi i32 [ %6, %5 ], [ 0, %4 ], [ 0, %3 ]
   ret i32 %8
 }
 
 declare dso_local i32 @g(...) local_unnamed_addr
 
 declare dso_local i32 @i(...) local_unnamed_addr
 
-; CHECK-LABEL: 000000000000003c test2:
-; CHECK:         bl #0 <test2+0x18>
-; CHECK-LABEL: 0000000000000064 $d.5:
-; CHECK-LABEL: 000000000000006c $x.6:
-; CHECK-NEXT:    b #-24 <test2+0x18>
+; CHECK-LABEL: test2:
+; CHECK:         bl #0 <test2+0x10>
+; CHECK-LABEL: $d.5:
+; CHECK-LABEL: $x.6:
+; CHECK-NEXT:    b #16 <$x.8+0x4>
 define hidden i32 @test2() local_unnamed_addr {
   %1 = load i32, i32* @l, align 4
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %10, label %3
 
 3:                                                ; preds = %0
   %4 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)()
   %5 = icmp eq i32 %4, 0
   br i1 %5, label %6, label %7
 
 6:                                                ; preds = %3
   callbr void asm sideeffect "1: nop\0A\09.quad b\0A\09b ${1:l}\0A\09.quad ${0:c}", "i,X"(i32* null, i8* blockaddress(@test2, %7))
-          to label %10 [label %9]
+          to label %10 [label %7]
 
 7:                                                ; preds = %3
   %8 = tail call i32 bitcast (i32 (...)* @i to i32 ()*)()
   br label %10
 
 9:                                                ; preds = %6
   br label %10
 
 10:                                               ; preds = %7, %0, %6, %9
   ret i32 undef
 }
 
-; CHECK-LABEL: 0000000000000084 test3:
-; CHECK-LABEL: 00000000000000a8 $d.9:
-; CHECK-LABEL: 00000000000000b0 $x.10:
+; CHECK-LABEL: test3:
+; CHECK-LABEL: $d.9:
+; CHECK-LABEL: $x.10:
 ; CHECK-NEXT:    b #20 <$x.12+0x8>
-; CHECK-LABEL: 00000000000000bc $x.12:
+; CHECK-LABEL: $x.12:
 ; CHECK-NEXT:    b #4 <$x.12+0x4>
 ; CHECK-NEXT:    mov w0, wzr
 ; CHECK-NEXT:    ldr x30, [sp], #16
 ; CHECK-NEXT:    ret
 define internal i1 @test3() {
   %1 = tail call i32 bitcast (i32 (...)* @g to i32 ()*)()
   %2 = icmp eq i32 %1, 0
   br i1 %2, label %3, label %5

llvm/test/Verifier/callbr.ll

+; RUN: not opt -S %s -verify 2>&1 | FileCheck %s
+
+; CHECK: Indirect label missing from arglist.
+define void @foo() {
+  ; The %4 in the indirect label list is not found in the blockaddresses in the
+  ; arg list (bad).
+  callbr void asm sideeffect "${0:l} {1:l}", "X,X"(i8* blockaddress(@foo, %3), i8* blockaddress(@foo, %2))
+  to label %1 [label %4, label %2]
+1:
+  ret void
+2:
+  ret void
+3:
+  ret void
+4:
+  ret void
+}
+
+; CHECK-NOT: Indirect label missing from arglist.
+define void @bar() {
+  ; %4 and %2 are both in the indirect label list and the arg list (good).
+  callbr void asm sideeffect "${0:l} ${1:l}", "X,X"(i8* blockaddress(@bar, %4), i8* blockaddress(@bar, %2))
+  to label %1 [label %4, label %2]
+1:
+  ret void
+2:
+  ret void
+3:
+  ret void
+4:
+  ret void
+}
+
+; CHECK-NOT: Indirect label missing from arglist.
+define void @baz() {
+  ; note %2 blockaddress. Such a case is possible when passing the address of
+  ; a label as an input to the inline asm (both address of label and asm goto
+  ; use blockaddress constants; we're testing that the indirect label list from
+  ; the asm goto is in the arg list to the asm).
+  callbr void asm sideeffect "${0:l} ${1:l} ${2:l}", "X,X,X"(i8* blockaddress(@baz, %4), i8* blockaddress(@baz, %2), i8* blockaddress(@baz, %3))
+  to label %1 [label %3, label %4]
+1:
+  ret void
+2:
+  ret void
+3:
+  ret void
+4:
+  ret void
+}