[Dominators] check indirect branches of callbr

[nickdesaulniers]

Summary

This will be necessary to support outputs from asm goto along indirect
edges.

Test via:

$ pushd llvm/build; ninja IRTests; popd
$ ./llvm/build/unittests/IR/IRTests \
  --gtest_filter=DominatorTree.CallBrDomination

Also, return nullptr in Instruction::getInsertionPointAfterDef for
CallBrInst as was recommened in
https://reviews.llvm.org/D135997#3991427. The following phab review was
folded into this commit: https://reviews.llvm.org/D140166

Link: Link: https://discourse.llvm.org/t/rfc-syncing-asm-goto-with-outputs-with-gcc/65453/8

[nickdesaulniers]

• remove stale comment

[nickdesaulniers]

• fix up tests

[nikic]

llvm/lib/IR/Dominators.cpp

196–197

Is it possible to just drop the callbr handling entirely? I'd expect it to be covered by the normal code now.

[nickdesaulniers]

• drop CallBr special cases (no longer necessary), remove printf from test

[efriedma]

LGTM, but you might need to wait to land this until after the corresponding backend changes have landed to avoid regressions. (Optimizations could introduce uses in non-default destinations.)

[nikic]

This also needs a LangRef update.

[nickdesaulniers]

Thanks for the reviews! I plan to build up a series and don't intend to land any until all are working. (Maybe I could have waited before pestering reviewers)

This also needs a LangRef update.

Will do.

[nikic]

After this change, https://github.com/llvm/llvm-project/blob/cca01df291300fb06879fca5113bc71567c64738/llvm/lib/IR/Instruction.cpp#L129 will have to be adjusted for the new semantics. The function should return nullptr for callbr, because there no longer exists any insert point after the callbr. I think callers should deal with this gracefully, but it will probably regress some optimizations.

[nickdesaulniers]

Ready for review:

1. https://reviews.llvm.org/D135997
2. https://reviews.llvm.org/D140166
3. https://reviews.llvm.org/D139861
4. https://reviews.llvm.org/D139872
5. https://reviews.llvm.org/D139883
6. https://reviews.llvm.org/D139970
7. https://reviews.llvm.org/D140160
8. https://reviews.llvm.org/D137113
9. https://reviews.llvm.org/D136497

[void]

One small nit. Otherwise LGTM.

llvm/test/Verifier/callbr.ll

59–60

Could you add some "CHECK"s here? Or a comment like below (;; No issue!).

[nickdesaulniers]

• add no issue comment to test

[nickdesaulniers]

• rebase, format

[void]

Could you investigate the build failures?

[nickdesaulniers]

In D135997#4060429, @void wrote:

Could you investigate the build failures?

@ychen any idea how my patch could be tripping this presubmit failure? I have no idea.

[nickdesaulniers]

In D135997#4060429, @void wrote:

Could you investigate the build failures?

Looks like just a bad spot I picked for my previous rebase. Just need to re-rebase.

[nickdesaulniers]

• rebase (prior test failures were simply bad luck rebasing to a broken SHA)

[nickdesaulniers]

• rebase

[nickdesaulniers]

• final rebase, merge D140166, update commit message

llvm/include/llvm/IR/Dominators.h

public:
   /// Return true if value Def dominates use U, in the sense that Def is
   /// available at U, and could be substituted as the used value without
   /// violating the SSA dominance requirement.
   ///
   /// In particular, it is worth noting that:
   ///  * Non-instruction Defs dominate everything.
   ///  * Def does not dominate a use in Def itself (outside of degenerate cases
   ///    like unreachable code or trivial phi cycles).
-  ///  * Invoke/callbr Defs only dominate uses in their default destination.
+  ///  * Invoke Defs only dominate uses in their default destination.
   bool dominates(const Value *Def, const Use &U) const;
   /// Return true if value Def dominates all possible uses inside instruction
   /// User. Same comments as for the Use-based API apply.
   bool dominates(const Value *Def, const Instruction *User) const;
 
   /// Returns true if Def would dominate a use in any instruction in BB.
   /// If Def is an instruction in BB, then Def does not dominate BB.
   ///

llvm/lib/IR/Dominators.cpp

bool DominatorTree::dominates(const Instruction *Def,
 
   // Invoke results are only usable in the normal destination, not in the
   // exceptional destination.
   if (const auto *II = dyn_cast<InvokeInst>(Def)) {
     BasicBlock *NormalDest = II->getNormalDest();
     BasicBlockEdge E(DefBB, NormalDest);
     return dominates(E, UseBB);
   }
 
-  // Callbr results are similarly only usable in the default destination.
-  if (const auto *CBI = dyn_cast<CallBrInst>(Def)) {
-    BasicBlock *NormalDest = CBI->getDefaultDest();
-    BasicBlockEdge E(DefBB, NormalDest);
-    return dominates(E, UseBB);
-  }
-
   return dominates(DefBB, UseBB);
 }
 
 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
                               const BasicBlock *UseBB) const {
   // If the BB the edge ends in doesn't dominate the use BB, then the
   // edge also doesn't.
   const BasicBlock *Start = BBE.getStart();
   const BasicBlock *End = BBE.getEnd();
bool DominatorTree::dominates(const Value *DefV, const Use &U) const {
   // their own block, except possibly a phi, so we don't need to
   // walk the block in any case.
   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
     BasicBlock *NormalDest = II->getNormalDest();
     BasicBlockEdge E(DefBB, NormalDest);
     return dominates(E, U);
   }
 
-  // Callbr results are similarly only usable in the default destination.
-  if (const auto *CBI = dyn_cast<CallBrInst>(Def)) {
-    BasicBlock *NormalDest = CBI->getDefaultDest();
-    BasicBlockEdge E(DefBB, NormalDest);
-    return dominates(E, U);
-  }
-
   // If the def and use are in different blocks, do a simple CFG dominator
   // tree query.
   if (DefBB != UseBB)
     return dominates(DefBB, UseBB);
 
   // Ok, def and use are in the same block. If the def is an invoke, it
   // doesn't dominate anything in the block. If it's a PHI, it dominates
   // everything in the block.

llvm/lib/IR/Instruction.cpp

Instruction *Instruction::getInsertionPointAfterDef() {
   BasicBlock::iterator InsertPt;
   if (auto *PN = dyn_cast<PHINode>(this)) {
     InsertBB = PN->getParent();
     InsertPt = InsertBB->getFirstInsertionPt();
   } else if (auto *II = dyn_cast<InvokeInst>(this)) {
     InsertBB = II->getNormalDest();
     InsertPt = InsertBB->getFirstInsertionPt();
   } else if (auto *CB = dyn_cast<CallBrInst>(this)) {
-    InsertBB = CB->getDefaultDest();
-    InsertPt = InsertBB->getFirstInsertionPt();
+    // Def is available in multiple successors, there's no single dominating
+    // insertion point.
+    return nullptr;
   } else {
     assert(!isTerminator() && "Only invoke/callbr terminators return value");
     InsertBB = getParent();
     InsertPt = std::next(getIterator());
   }
 
   // catchswitch blocks don't have any legal insertion point (because they
   // are both an exception pad and a terminator).

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombinerImpl::visitCallBase(CallBase &Call) {
   }
   default: { break; }
   }
 
   return Changed ? &Call : nullptr;
 }
 
 /// If the callee is a constexpr cast of a function, attempt to move the cast to
-/// the arguments of the call/callbr/invoke.
+/// the arguments of the call/invoke.
+/// CallBrInst is not supported.
 bool InstCombinerImpl::transformConstExprCastCall(CallBase &Call) {
   auto *Callee =
       dyn_cast<Function>(Call.getCalledOperand()->stripPointerCasts());
   if (!Callee)
     return false;
 
+  assert(!isa<CallBrInst>(Call) &&
+         "CallBr's don't have a single point after a def to insert at");
+
   // If this is a call to a thunk function, don't remove the cast. Thunks are
   // used to transparently forward all incoming parameters and outgoing return
   // values, so it's important to leave the cast in place.
   if (Callee->hasFnAttribute("thunk"))
     return false;
 
   // If this is a musttail call, the callee's prototype must match the caller's
   // prototype with the exception of pointee types. The code below doesn't
if (OldRetTy != NewRetTy) {
     }
 
     if (!CallerPAL.isEmpty() && !Caller->use_empty()) {
       AttrBuilder RAttrs(FT->getContext(), CallerPAL.getRetAttrs());
       if (RAttrs.overlaps(AttributeFuncs::typeIncompatible(NewRetTy)))
         return false;   // Attribute not compatible with transformed value.
     }
 
-    // If the callbase is an invoke/callbr instruction, and the return value is
+    // If the callbase is an invoke instruction, and the return value is
     // used by a PHI node in a successor, we cannot change the return type of
     // the call because there is no place to put the cast instruction (without
     // breaking the critical edge).  Bail out in this case.
     if (!Caller->use_empty()) {
       BasicBlock *PhisNotSupportedBlock = nullptr;
       if (auto *II = dyn_cast<InvokeInst>(Caller))
         PhisNotSupportedBlock = II->getNormalDest();
-      if (auto *CB = dyn_cast<CallBrInst>(Caller))
-        PhisNotSupportedBlock = CB->getDefaultDest();
       if (PhisNotSupportedBlock)
         for (User *U : Caller->users())
           if (PHINode *PN = dyn_cast<PHINode>(U))
             if (PN->getParent() == PhisNotSupportedBlock)
               return false;
     }
   }
 
bool InstCombinerImpl::transformConstExprCastCall(CallBase &Call) {
 
   SmallVector<OperandBundleDef, 1> OpBundles;
   Call.getOperandBundlesAsDefs(OpBundles);
 
   CallBase *NewCall;
   if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
     NewCall = Builder.CreateInvoke(Callee, II->getNormalDest(),
                                    II->getUnwindDest(), Args, OpBundles);
-  } else if (CallBrInst *CBI = dyn_cast<CallBrInst>(Caller)) {
-    NewCall = Builder.CreateCallBr(Callee, CBI->getDefaultDest(),
-                                   CBI->getIndirectDests(), Args, OpBundles);
   } else {
     NewCall = Builder.CreateCall(Callee, Args, OpBundles);
     cast<CallInst>(NewCall)->setTailCallKind(
         cast<CallInst>(Caller)->getTailCallKind());
   }
   NewCall->takeName(Caller);
   NewCall->setCallingConv(Call.getCallingConv());
   NewCall->setAttributes(NewCallerPAL);

llvm/test/Transforms/Coroutines/coro-debug.ll

 ; Check that the dbg.declare intrinsic of invoke instruction is hanled correctly.
 ; CHECK: %[[ALLOCATED_STORAGE:.+]] = invoke i8* @allocate()
 ; CHECK-NEXT: to label %[[NORMAL_DEST:.+]] unwind
 ; CHECK: [[NORMAL_DEST]]
 ; CHECK-NEXT: call void @llvm.dbg.declare(metadata i8* %[[ALLOCATED_STORAGE]]
 ; CHECK: %[[CALLBR_RES:.+]] = callbr i32 asm
 ; CHECK-NEXT: to label %[[DEFAULT_DEST:.+]] [label
 ; CHECK: [[DEFAULT_DEST]]:
-; CHECK-NEXT: call void @llvm.dbg.declare(metadata i32 %[[CALLBR_RES]]
+; CHECK-NOT: {{.*}}:
+; CHECK: call void @llvm.dbg.declare(metadata i32 %[[CALLBR_RES]]
 ; CHECK: define internal fastcc void @f.destroy(%f.Frame* noundef nonnull align 8 dereferenceable(40) %FramePtr) #0 personality i32 0 !dbg ![[DESTROY:[0-9]+]]
 ; CHECK: define internal fastcc void @f.cleanup(%f.Frame* noundef nonnull align 8 dereferenceable(40) %FramePtr) #0 personality i32 0 !dbg ![[CLEANUP:[0-9]+]]
 
 ; CHECK: ![[ORIG]] = distinct !DISubprogram(name: "f", linkageName: "flink"
 
 ; CHECK: ![[RESUME]] = distinct !DISubprogram(name: "f", linkageName: "flink"
 ; CHECK: ![[RESUME_COROHDL]] = !DILocalVariable(name: "coro_hdl", scope: ![[RESUME]]
 ; CHECK: ![[RESUME_X]] = !DILocalVariable(name: "x", arg: 1, scope: ![[RESUME]]
 ; CHECK: ![[RESUME_DIRECT]] = !DILocalVariable(name: "direct_mem", scope: ![[RESUME]]
 ; CHECK: ![[RESUME_CONST]] = !DILocalVariable(name: "direct_const", scope: ![[RESUME]]
 ; CHECK: ![[RESUME_DIRECT_VALUE]] = !DILocalVariable(name: "direct_value", scope: ![[RESUME]]
 
 ; CHECK: ![[DESTROY]] = distinct !DISubprogram(name: "f", linkageName: "flink"
 
 ; CHECK: ![[CLEANUP]] = distinct !DISubprogram(name: "f", linkageName: "flink"

llvm/test/Transforms/InstCombine/freeze.ll

 
 define i32 @freeze_callbr_use_after_phi(i1 %c) {
 ; CHECK-LABEL: @freeze_callbr_use_after_phi(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = callbr i32 asm sideeffect "", "=r"() #[[ATTR1:[0-9]+]]
 ; CHECK-NEXT:    to label [[CALLBR_CONT:%.*]] []
 ; CHECK:       callbr.cont:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ 0, [[CALLBR_CONT]] ]
+; CHECK-NEXT:    call void @use_i32(i32 [[X]])
 ; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
 ; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
-; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    call void @use_i32(i32 [[PHI]])
 ; CHECK-NEXT:    br label [[CALLBR_CONT]]
 ;
 entry:
   %x = callbr i32 asm sideeffect "", "=r"()
   to label %callbr.cont []
 
 callbr.cont:

llvm/test/Transforms/Reassociate/callbr.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=reassociate < %s | FileCheck %s
 
 define i32 @test(i1 %b) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:    [[RES:%.*]] = callbr i32 asm "", "=r,!i"()
 ; CHECK-NEXT:    to label [[NORMAL:%.*]] [label %abnormal]
 ; CHECK:       normal:
-; CHECK-NEXT:    [[FACTOR:%.*]] = mul i32 [[RES]], -2
-; CHECK-NEXT:    [[SUB2:%.*]] = add i32 [[FACTOR]], 5
+; CHECK-NEXT:    [[RES_NEG:%.*]] = sub i32 0, [[RES]]
+; CHECK-NEXT:    [[SUB1:%.*]] = add i32 [[RES_NEG]], 5
+; CHECK-NEXT:    [[RES_NEG1:%.*]] = sub i32 0, [[RES]]
+; CHECK-NEXT:    [[SUB2:%.*]] = add i32 [[SUB1]], [[RES_NEG1]]
 ; CHECK-NEXT:    ret i32 [[SUB2]]
 ; CHECK:       abnormal:
 ; CHECK-NEXT:    ret i32 0
 ;
   %res = callbr i32 asm "", "=r,!i"()
   to label %normal [label %abnormal]
 
 normal:
   %sub1 = sub nsw i32 5, %res
   %sub2 = sub nsw i32 %sub1, %res
   ret i32 %sub2
 
 abnormal:
   ret i32 0
 }

llvm/test/Verifier/callbr.ll

define void @callbr_without_label_constraint() {
   callbr void asm sideeffect "#callbr_without_label_constraint", ""()
   to label %1 [label %2]
 1:
   ret void
 2:
   ret void
 }
 
-;; Ensure you cannot use the return value of a callbr in indirect targets.
-; CHECK: Instruction does not dominate all uses!
-; CHECK-NEXT: #test4
+;; Ensure you can use the return value of a callbr in indirect targets.
+;; No issue!
 define i32 @test4(i1 %var) {
 entry:
   %ret = callbr i32 asm sideeffect "#test4", "=r,!i"() to label %normal [label %abnormal]
 
 normal:
   ret i32 0
 
 abnormal:
   ret i32 %ret
 }

llvm/test/Verifier/dominates.ll

next:
   %y = phi i32 [ 0, %entry ]
   %x = phi i32 [ %y, %entry ]
   ret void
 ; CHECK: Instruction does not dominate all uses!
 ; CHECK-NEXT:  %y = phi i32 [ 0, %entry ]
 ; CHECK-NEXT:  %x = phi i32 [ %y, %entry ]
 }
 
+;; No issue!
 define i32 @f6(i32 %x) {
 bb0:
   %y1 = callbr i32 asm "", "=r,!i"() to label %bb1 [label %bb2]
 bb1:
   ret i32 0
 bb2:
   ret i32 %y1
-; CHECK: Instruction does not dominate all uses!
-; CHECK-NEXT:  %y1 = callbr i32 asm "", "=r,!i"()
-; CHECK-NEXT:        to label %bb1 [label %bb2]
-; CHECK-NEXT:  ret i32 %y1
 }

llvm/unittests/IR/DominatorTreeTest.cpp

runWithDomTree(*M, "f",
     EXPECT_TRUE(DT->dominates(C, I));
 
     const Use &U = I->getOperandUse(0);
     EXPECT_TRUE(DT->dominates(A, U));
     EXPECT_TRUE(DT->dominates(G, U));
     EXPECT_TRUE(DT->dominates(C, U));
   });
 }
+TEST(DominatorTree, CallBrDomination) {
+  StringRef ModuleString = R"(
+define void @x() {
+  %y = alloca i32
+  %w = callbr i32 asm "", "=r,!i"()
+          to label %asm.fallthrough [label %z]
+
+asm.fallthrough:
+  br label %cleanup
+
+z:
+  store i32 %w, ptr %y
+  br label %cleanup
+
+cleanup:
+  ret void
+})";
+
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  runWithDomTree(
+      *M, "x", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
+        Function::iterator FI = F.begin();
+
+        BasicBlock *Entry = &*FI++;
+        BasicBlock *ASMFallthrough = &*FI++;
+        BasicBlock *Z = &*FI++;
+
+        EXPECT_TRUE(DT->dominates(Entry, ASMFallthrough));
+        EXPECT_TRUE(DT->dominates(Entry, Z));
+
+        BasicBlock::iterator BBI = Entry->begin();
+        ++BBI;
+        Instruction &I = *BBI;
+        EXPECT_TRUE(isa<CallBrInst>(I));
+        EXPECT_TRUE(isa<Value>(I));
+        for (const User *U : I.users()) {
+          EXPECT_TRUE(isa<Instruction>(U));
+          EXPECT_TRUE(DT->dominates(cast<Value>(&I), cast<Instruction>(U)));
+        }
+      });
+}