[IR] Treat callbr as special terminator (PR64215)

[nikic]

Summary

isLegalToHoistInto() currently return true for callbr instructions. That means that a callbr with one successor will be considered a proper loop preheader, which may result in instructions that use the callbr return value being hoisted past it.

Fix this by adding callbr to isExceptionTerminator (with a rename to isSpecialTerminator), which also fixes similar assumptions in other places.

Fixes https://github.com/llvm/llvm-project/issues/64215.

[fhahn]

LGTM, thanks!

[nickdesaulniers]

Thanks for the patch!
Any other call sites of Instruction::isExceptionalTerminator() that might need similar touch ups? Perhaps we should just add Instruction::CallBr to isExceptionalTerminator(unsigned OpCode)?

[nickdesaulniers]

llvm/lib/IR/BasicBlock.cpp

399–401

Note: a callbr may produce a value, but that's optional. It's perhaps more common at the moment that callbr does not produce a value.

[nikic]

In D158609#4610264, @nickdesaulniers wrote:

Thanks for the patch!
Any other call sites of Instruction::isExceptionalTerminator() that might need similar touch ups? Perhaps we should just add Instruction::CallBr to isExceptionalTerminator(unsigned OpCode)?

Good point. For example this test crashes jump-threading:

define i32 @test() {
  %x = callbr i32 asm sideeffect "", "=r"()
  to label %bb []

bb:
  ret i32 %x
}

So yeah, I think we should add it and rename the method, though I'm not sure to what.

[nikic]

Rename isExceptionalTerminator -> isSpecialTerminator (special as in has side effect or return value) and add callbr to it. Adjust callers as appropriate.

[nikic]

llvm/lib/Transforms/Coroutines/CoroElide.cpp

230

Context for this change: TIs contains "terminators" that have no successors and are not unreachable. The only such terminator are ret, resume, and (sometimes) cleanupret. The isExceptionalTerminator check excludes resume and cleanupret, so we are left with just ret.

If found it more obvious to just spell that out, because the isExceptionalTerminator check was a bit overly vague here (e.g. things like invoke are not relevant at all).

[nickdesaulniers]

In D158609#4613515, @nikic wrote:

So yeah, I think we should add it and rename the method, though I'm not sure to what.

FWIW, https://repository.tudelft.nl/islandora/object/uuid:a3bea0c0-fc6d-47a1-9b94-bf39df4aff8f?collection=education uses the phrase an "exotic terminator."

[nickdesaulniers]

The presubmit bots seem to be failing due to git clang-format HEAD~ resulting in a difference.

llvm/include/llvm/IR/Instruction.h

public:
   const char *getOpcodeName() const { return getOpcodeName(getOpcode()); }
   bool isTerminator() const { return isTerminator(getOpcode()); }
   bool isUnaryOp() const { return isUnaryOp(getOpcode()); }
   bool isBinaryOp() const { return isBinaryOp(getOpcode()); }
   bool isIntDivRem() const { return isIntDivRem(getOpcode()); }
   bool isShift() const { return isShift(getOpcode()); }
   bool isCast() const { return isCast(getOpcode()); }
   bool isFuncletPad() const { return isFuncletPad(getOpcode()); }
-  bool isExceptionalTerminator() const {
-    return isExceptionalTerminator(getOpcode());
-  }
+  bool isSpecialTerminator() const { return isSpecialTerminator(getOpcode()); }
 
   /// It checks if this instruction is the only user of at least one of
   /// its operands.
   bool isOnlyUserOfAnyOperand();
 
   static const char *getOpcodeName(unsigned Opcode);
 
   static inline bool isTerminator(unsigned Opcode) {
static inline bool isCast(unsigned Opcode) {
     return Opcode >= CastOpsBegin && Opcode < CastOpsEnd;
   }
 
   /// Determine if the Opcode is one of the FuncletPadInst instructions.
   static inline bool isFuncletPad(unsigned Opcode) {
     return Opcode >= FuncletPadOpsBegin && Opcode < FuncletPadOpsEnd;
   }
 
-  /// Returns true if the Opcode is a terminator related to exception handling.
-  static inline bool isExceptionalTerminator(unsigned Opcode) {
+  /// Returns true if the Opcode is a "special" terminator that does more than
+  /// branch to a successor (e.g. have a side effect or return a value).
+  static inline bool isSpecialTerminator(unsigned Opcode) {
     switch (Opcode) {
     case Instruction::CatchSwitch:
     case Instruction::CatchRet:
     case Instruction::CleanupRet:
     case Instruction::Invoke:
     case Instruction::Resume:
+    case Instruction::CallBr:
       return true;
     default:
       return false;
     }
   }
 
   //===--------------------------------------------------------------------===//
   // Metadata manipulation.

llvm/lib/IR/BasicBlock.cpp

bool BasicBlock::isLegalToHoistInto() const {
   auto *Term = getTerminator();
   // No terminator means the block is under construction.
   if (!Term)
     return true;
 
   // If the block has no successors, there can be no instructions to hoist.
   assert(Term->getNumSuccessors() > 0);
 
-  // Instructions should not be hoisted across exception handling boundaries.
-  return !Term->isExceptionalTerminator();
+  // Instructions should not be hoisted across special terminators, which may
+  // have side effects or return values.
+  return !Term->isSpecialTerminator();
 }
 
 bool BasicBlock::isEntryBlock() const {
   const Function *F = getParent();
   assert(F && "Block must have a parent function to use this API");
   return this == &F->getEntryBlock();
 }
 

llvm/lib/Transforms/Coroutines/CoroElide.cpp

if (!Visited.insert(BB).second)
       continue;
 
     // A Path insensitive marker to test whether the coro.begin escapes.
     // It is intentional to make it path insensitive while it may not be
     // precise since we don't want the process to be too slow.
     PotentiallyEscaped |= EscapingBBs.count(BB);
 
     if (TIs.count(BB)) {
-      if (!BB->getTerminator()->isExceptionalTerminator() || PotentiallyEscaped)
+      if (isa<ReturnInst>(BB->getTerminator()) || PotentiallyEscaped)
         return true;
 
       // If the function ends with the exceptional terminator, the memory used
       // by the coroutine frame can be released by stack unwinding
       // automatically. So we can think the coro.begin doesn't escape if it
       // exits the function by exceptional terminator.
 
       continue;

llvm/lib/Transforms/Scalar/GVN.cpp

 ///   SuccBB:
 ///      v2 = load %addr
 ///      ...
 ///
 LoadInst *GVNPass::findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
                                            LoadInst *Load) {
   // For simplicity we handle a Pred has 2 successors only.
   auto *Term = Pred->getTerminator();
-  if (Term->getNumSuccessors() != 2 || Term->isExceptionalTerminator())
+  if (Term->getNumSuccessors() != 2 || Term->isSpecialTerminator())
     return nullptr;
   auto *SuccBB = Term->getSuccessor(0);
   if (SuccBB == LoadBB)
     SuccBB = Term->getSuccessor(1);
   if (!SuccBB->getSinglePredecessor())
     return nullptr;
 
   unsigned int NumInsts = MaxNumInsnsPerBlock;

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 
 /// Merge basic block BB into its sole predecessor if possible.
 bool JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB) {
   BasicBlock *SinglePred = BB->getSinglePredecessor();
   if (!SinglePred)
     return false;
 
   const Instruction *TI = SinglePred->getTerminator();
-  if (TI->isExceptionalTerminator() || TI->getNumSuccessors() != 1 ||
+  if (TI->isSpecialTerminator() || TI->getNumSuccessors() != 1 ||
       SinglePred == BB || hasAddressTakenAndUsed(BB))
     return false;
 
   // If SinglePred was a loop header, BB becomes one.
   if (LoopHeaders.erase(SinglePred))
     LoopHeaders.insert(BB);
 
   LVI->eraseBlock(SinglePred);

llvm/lib/Transforms/Scalar/Sink.cpp

 
 /// IsAcceptableTarget - Return true if it is possible to sink the instruction
 /// in the specified basic block.
 static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo,
                                DominatorTree &DT, LoopInfo &LI) {
   assert(Inst && "Instruction to be sunk is null");
   assert(SuccToSinkTo && "Candidate sink target is null");
 
-  // It's never legal to sink an instruction into a block which terminates in an
-  // EH-pad.
-  if (SuccToSinkTo->getTerminator()->isExceptionalTerminator())
+  // It's never legal to sink an instruction into an EH-pad block.
+  if (SuccToSinkTo->isEHPad())
     return false;
 
   // If the block has multiple predecessors, this would introduce computation
   // on different code paths.  We could split the critical edge, but for now we
   // just punt.
   // FIXME: Split critical edges if not backedges.
   if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) {
     // We cannot sink a load across a critical edge - there may be stores in

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
   BasicBlock *PredBB = BB->getUniquePredecessor();
   if (!PredBB) return false;
 
   // Don't break self-loops.
   if (PredBB == BB) return false;
 
   // Don't break unwinding instructions or terminators with other side-effects.
   Instruction *PTI = PredBB->getTerminator();
-  if (PTI->isExceptionalTerminator() || PTI->mayHaveSideEffects())
+  if (PTI->isSpecialTerminator() || PTI->mayHaveSideEffects())
     return false;
 
   // Can't merge if there are multiple distinct successors.
   if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB)
     return false;
 
   // Currently only allow PredBB to have two predecessors, one being BB.
   // Update BI to branch to BB's only successor instead of BB.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

if (!CI) {
       return;
     }
 
     // Constant condition variables mean the branch can only go a single way.
     Succs[CI->isZero()] = true;
     return;
   }
 
-  // Unwinding instructions successors are always executable.
-  if (TI.isExceptionalTerminator()) {
+  // We cannot analyze special terminators, so consider all successors
+  // executable.
+  if (TI.isSpecialTerminator()) {
     Succs.assign(TI.getNumSuccessors(), true);
     return;
   }
 
   if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
     if (!SI->getNumCases()) {
       Succs[0] = true;
       return;
for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
       }
     }
 
     // If we didn't find our destination in the IBR successor list, then we
     // have undefined behavior. Its ok to assume no successor is executable.
     return;
   }
 
-  // In case of callbr, we pessimistically assume that all successors are
-  // feasible.
-  if (isa<CallBrInst>(&TI)) {
-    Succs.assign(TI.getNumSuccessors(), true);
-    return;
-  }
-
   LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
   llvm_unreachable("SCCP: Don't know how to handle this terminator!");
 }
 
 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 // block to the 'To' basic block is currently feasible.
 bool SCCPInstVisitor::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
   // Check if we've called markEdgeExecutable on the edge yet. (We could

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

getCaseResults(SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest,
 
   // If CaseDest is empty except for some side-effect free instructions through
   // which we can constant-propagate the CaseVal, continue to its successor.
   SmallDenseMap<Value *, Constant *> ConstantPool;
   ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal));
   for (Instruction &I : CaseDest->instructionsWithoutDebug(false)) {
     if (I.isTerminator()) {
       // If the terminator is a simple branch, continue to the next block.
-      if (I.getNumSuccessors() != 1 || I.isExceptionalTerminator())
+      if (I.getNumSuccessors() != 1 || I.isSpecialTerminator())
         return false;
       Pred = CaseDest;
       CaseDest = I.getSuccessor(0);
     } else if (Constant *C = ConstantFold(&I, DL, ConstantPool)) {
       // Instruction is side-effect free and constant.
 
       // If the instruction has uses outside this block or a phi node slot for
       // the block, it is not safe to bypass the instruction since it would then

llvm/test/Transforms/JumpThreading/callbr.ll

bb7:
   br i1 %i9, label %bb11, label %bb10
 
 bb10:
   br label %bb11
 
 bb11:
   ret i1 %i9
 }
+
+define i32 @callbr_no_block_merge() {
+; CHECK-LABEL: @callbr_no_block_merge(
+; CHECK-NEXT:    [[X:%.*]] = callbr i32 asm sideeffect "", "=r"()
+; CHECK-NEXT:    to label [[BB:%.*]] []
+; CHECK:       bb:
+; CHECK-NEXT:    ret i32 [[X]]
+;
+  %x = callbr i32 asm sideeffect "", "=r"()
+  to label %bb []
+
+bb:
+  ret i32 %x
+}

llvm/test/Transforms/LICM/callbr-crash.ll

 cond.true.i:                                      ; preds = %for.cond
   %asmresult1.i.i = extractvalue { i8, i32 } zeroinitializer, 1
   br i1 undef, label %for.end, label %for.cond
 
 for.end:                                          ; preds = %cond.true.i, %for.cond
   %phi = phi i32 [ %asmresult1.i.i, %cond.true.i ], [ undef, %for.cond ]
   ret i32 %phi
 }
+
+declare void @use_i32(i32)
+
+define void @pr64215() {
+; CHECK-LABEL: @pr64215(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[X:%.*]] = callbr i32 asm sideeffect "", "=r"()
+; CHECK-NEXT:    to label [[LOOP_PREHEADER:%.*]] []
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X]], 1
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    call void @use_i32(i32 [[ADD]])
+; CHECK-NEXT:    br label [[LOOP]]
+;
+entry:
+  %x = callbr i32 asm sideeffect "", "=r"()
+  to label %loop []
+
+loop:
+  %add = add i32 %x, 1
+  call void @use_i32(i32 %add)
+  br label %loop
+}