[BasicBlockUtils] Allow critical edge splitting with callbr terminators

[nikic]

Summary

After D129205, we support SplitBlockPredecessors() for predecessors with callbr terminators. This means that it is now also safe to invoke critical edge splitting for an edge coming from a callbr terminator. Remove checks in various passes that were protecting against that.

[nathanchance]

My set of Linux kernel build and QEMU boot tests did not notice any issues with this change.

llvm/lib/Transforms/Scalar/GVN.cpp

for (BasicBlock *Pred : predecessors(LoadBB)) {
     if (Pred->getTerminator()->getNumSuccessors() != 1) {
       if (isa<IndirectBrInst>(Pred->getTerminator())) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
                    << Pred->getName() << "': " << *Load << '\n');
         return false;
       }
 
-      // FIXME: Can we support the fallthrough edge?
-      if (isa<CallBrInst>(Pred->getTerminator())) {
-        LLVM_DEBUG(
-            dbgs() << "COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"
-                   << Pred->getName() << "': " << *Load << '\n');
-        return false;
-      }
-
       if (LoadBB->isEHPad()) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
                    << Pred->getName() << "': " << *Load << '\n');
         return false;
       }
 
       // Do not split backedge as it will break the canonical loop form.
if (!isSafeToSpeculativelyExecute(CurInst)) {
       if (ICF->isDominatedByICFIFromSameBlock(CurInst))
         return false;
     }
 
     // Don't do PRE across indirect branch.
     if (isa<IndirectBrInst>(PREPred->getTerminator()))
       return false;
 
-    // Don't do PRE across callbr.
-    // FIXME: Can we do this across the fallthrough edge?
-    if (isa<CallBrInst>(PREPred->getTerminator()))
-      return false;
-
     // We can't do PRE safely on a critical edge, so instead we schedule
     // the edge to be split and perform the PRE the next time we iterate
     // on the function.
     unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
     if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
       toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
       return false;
     }

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 }
 
 unsigned
 llvm::SplitAllCriticalEdges(Function &F,
                             const CriticalEdgeSplittingOptions &Options) {
   unsigned NumBroken = 0;
   for (BasicBlock &BB : F) {
     Instruction *TI = BB.getTerminator();
-    if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI) &&
-        !isa<CallBrInst>(TI))
+    if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
         if (SplitCriticalEdge(TI, i, Options))
           ++NumBroken;
   }
   return NumBroken;
 }
 
 static BasicBlock *SplitBlockImpl(BasicBlock *Old, Instruction *SplitPt,

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp

llvm::SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum,
   if (Options.IgnoreUnreachableDests &&
       isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
     return nullptr;
 
   auto *LI = Options.LI;
   SmallVector<BasicBlock *, 4> LoopPreds;
   // Check if extra modifications will be required to preserve loop-simplify
   // form after splitting. If it would require splitting blocks with IndirectBr
-  // or CallBr terminators, bail out if preserving loop-simplify form is
-  // requested.
+  // terminators, bail out if preserving loop-simplify form is requested.
   if (LI) {
     if (Loop *TIL = LI->getLoopFor(TIBB)) {
 
       // The only way that we can break LoopSimplify form by splitting a
       // critical edge is if after the split there exists some edge from TIL to
       // DestBB *and* the only edge into DestBB from outside of TIL is that of
       // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
       // is the new exit block and it has no non-loop predecessors. If the
if (Loop *TIL = LI->getLoopFor(TIBB)) {
           LoopPreds.clear();
           break;
         }
         LoopPreds.push_back(P);
       }
       // Loop-simplify form can be preserved, if we can split all in-loop
       // predecessors.
       if (any_of(LoopPreds, [](BasicBlock *Pred) {
-            const Instruction *T = Pred->getTerminator();
-            if (const auto *CBR = dyn_cast<CallBrInst>(T))
-              return CBR->getDefaultDest() != Pred;
-            return isa<IndirectBrInst>(T);
+            return isa<IndirectBrInst>(Pred->getTerminator());
           })) {
         if (Options.PreserveLoopSimplify)
           return nullptr;
         LoopPreds.clear();
       }
     }
   }
 

llvm/test/Transforms/GVN/callbr-loadpre-critedge.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -gvn -S | FileCheck %s
 
 ; This test checks that we don't hang trying to split a critical edge in loadpre
 ; when the control flow uses a callbr instruction.
 
 %struct.pluto = type <{ i8, i8 }>
 
 define void @widget(%struct.pluto** %tmp1) {
 ; CHECK-LABEL: @widget(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    callbr void asm sideeffect "", "i,i"(i8* blockaddress(@widget, [[BB5:%.*]]), i8* blockaddress(@widget, [[BB8:%.*]]))
-; CHECK-NEXT:    to label [[BB4:%.*]] [label [[BB5]], label %bb8]
+; CHECK-NEXT:    callbr void asm sideeffect "", "i,i"(i8* blockaddress(@widget, [[BB5:%.*]]), i8* blockaddress(@widget, [[BB_BB8_CRIT_EDGE:%.*]]))
+; CHECK-NEXT:    to label [[BB4:%.*]] [label [[BB5]], label %bb.bb8_crit_edge]
+; CHECK:       bb.bb8_crit_edge:
+; CHECK-NEXT:    [[TMP10_PRE:%.*]] = load %struct.pluto*, %struct.pluto** [[TMP1:%.*]], align 8
+; CHECK-NEXT:    br label [[BB8:%.*]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb5:
-; CHECK-NEXT:    [[TMP6:%.*]] = load %struct.pluto*, %struct.pluto** [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP6:%.*]] = load %struct.pluto*, %struct.pluto** [[TMP1]], align 8
 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds [[STRUCT_PLUTO:%.*]], %struct.pluto* [[TMP6]], i64 0, i32 1
 ; CHECK-NEXT:    br label [[BB8]]
 ; CHECK:       bb8:
-; CHECK-NEXT:    [[TMP9:%.*]] = phi i8* [ [[TMP7]], [[BB5]] ], [ null, [[BB:%.*]] ]
-; CHECK-NEXT:    [[TMP10:%.*]] = load %struct.pluto*, %struct.pluto** [[TMP1]]
+; CHECK-NEXT:    [[TMP10:%.*]] = phi %struct.pluto* [ [[TMP6]], [[BB5]] ], [ [[TMP10_PRE]], [[BB_BB8_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[TMP9:%.*]] = phi i8* [ [[TMP7]], [[BB5]] ], [ null, [[BB_BB8_CRIT_EDGE]] ]
 ; CHECK-NEXT:    [[TMP11:%.*]] = getelementptr inbounds [[STRUCT_PLUTO]], %struct.pluto* [[TMP10]], i64 0, i32 0
-; CHECK-NEXT:    [[TMP12:%.*]] = load i8, i8* [[TMP11]]
+; CHECK-NEXT:    [[TMP12:%.*]] = load i8, i8* [[TMP11]], align 1
 ; CHECK-NEXT:    tail call void @spam(i8* [[TMP9]], i8 [[TMP12]])
 ; CHECK-NEXT:    ret void
 ;
 bb:
   callbr void asm sideeffect "", "i,i"(i8* blockaddress(@widget, %bb5), i8* blockaddress(@widget, %bb8))
   to label %bb4 [label %bb5, label %bb8]
 
 bb4:                                              ; preds = %bb

llvm/test/Transforms/GVN/callbr-scalarpre-critedge.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -gvn -S | FileCheck %s
 
 ; This test checks that we don't hang trying to split a critical edge in scalar
 ; PRE when the control flow uses a callbr instruction.
 
 define void @wombat(i64 %arg, i64* %arg1, i64 %arg2, i32* %arg3) {
 ; CHECK-LABEL: @wombat(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i64 [[ARG2:%.*]], [[ARG:%.*]]
-; CHECK-NEXT:    callbr void asm sideeffect "", "i,i"(i8* blockaddress(@wombat, [[BB7:%.*]]), i8* blockaddress(@wombat, [[BB9:%.*]]))
-; CHECK-NEXT:    to label [[BB6:%.*]] [label [[BB7]], label %bb9]
+; CHECK-NEXT:    callbr void asm sideeffect "", "i,i"(i8* blockaddress(@wombat, [[BB7:%.*]]), i8* blockaddress(@wombat, [[BB_BB9_CRIT_EDGE:%.*]]))
+; CHECK-NEXT:    to label [[BB6:%.*]] [label [[BB7]], label %bb.bb9_crit_edge]
+; CHECK:       bb.bb9_crit_edge:
+; CHECK-NEXT:    [[DOTPRE:%.*]] = trunc i64 [[TMP5]] to i32
+; CHECK-NEXT:    br label [[BB9:%.*]]
 ; CHECK:       bb6:
 ; CHECK-NEXT:    br label [[BB7]]
 ; CHECK:       bb7:
 ; CHECK-NEXT:    [[TMP8:%.*]] = trunc i64 [[TMP5]] to i32
 ; CHECK-NEXT:    tail call void @barney(i32 [[TMP8]])
 ; CHECK-NEXT:    br label [[BB9]]
 ; CHECK:       bb9:
-; CHECK-NEXT:    [[TMP10:%.*]] = trunc i64 [[TMP5]] to i32
-; CHECK-NEXT:    store i32 [[TMP10]], i32* [[ARG3:%.*]]
+; CHECK-NEXT:    [[TMP10_PRE_PHI:%.*]] = phi i32 [ [[DOTPRE]], [[BB_BB9_CRIT_EDGE]] ], [ [[TMP8]], [[BB7]] ]
+; CHECK-NEXT:    store i32 [[TMP10_PRE_PHI]], i32* [[ARG3:%.*]], align 4
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %tmp5 = or i64 %arg2, %arg
   callbr void asm sideeffect "", "i,i"(i8* blockaddress(@wombat, %bb7), i8* blockaddress(@wombat, %bb9))
-          to label %bb6 [label %bb7, label %bb9]
 
 bb6:                                              ; preds = %bb
   br label %bb7
 
 bb7:                                              ; preds = %bb6, %bb
   %tmp8 = trunc i64 %tmp5 to i32
   tail call void @barney(i32 %tmp8)
   br label %bb9
 
 bb9:                                              ; preds = %bb7, %bb
   %tmp10 = trunc i64 %tmp5 to i32
   store i32 %tmp10, i32* %arg3
   ret void
 }
 
 declare void @barney(i32)

llvm/test/Transforms/LoopStrengthReduce/callbr-critical-edge-splitting.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -loop-reduce %s -o - -S | FileCheck %s --check-prefix=LEGACYPM
 ; RUN: opt -passes='loop(loop-reduce)' %s -o - -S | FileCheck %s --check-prefix=NEWPM
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 define dso_local i32 @test1() local_unnamed_addr {
 ; LEGACYPM-LABEL: @test1(
 ; LEGACYPM-NEXT:  entry:
 ; LEGACYPM-NEXT:    br label [[FOR_COND:%.*]]
 ; LEGACYPM:       for.cond:
-; LEGACYPM-NEXT:    callbr void asm sideeffect "", "i,i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@test1, [[COND_TRUE_I:%.*]]), i8* blockaddress(@test1, [[FOR_END:%.*]]))
-; LEGACYPM-NEXT:    to label [[ASM_FALLTHROUGH_I_I:%.*]] [label [[COND_TRUE_I]], label %for.end]
+; LEGACYPM-NEXT:    callbr void asm sideeffect "", "i,i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@test1, [[COND_TRUE_I:%.*]]), i8* blockaddress(@test1, [[FOR_ENDSPLIT:%.*]]))
+; LEGACYPM-NEXT:    to label [[ASM_FALLTHROUGH_I_I:%.*]] [label [[COND_TRUE_I]], label %for.endsplit]
 ; LEGACYPM:       asm.fallthrough.i.i:
 ; LEGACYPM-NEXT:    unreachable
 ; LEGACYPM:       cond.true.i:
 ; LEGACYPM-NEXT:    br label [[DO_BODY_I_I_DO_BODY_I_I_CRIT_EDGE:%.*]]
 ; LEGACYPM:       do.body.i.i.do.body.i.i_crit_edge:
 ; LEGACYPM-NEXT:    [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV_NEXT:%.*]], [[DO_BODY_I_I_DO_BODY_I_I_CRIT_EDGE]] ], [ undef, [[COND_TRUE_I]] ]
 ; LEGACYPM-NEXT:    [[LSR_IV_NEXT]] = add i64 [[LSR_IV]], 1
 ; LEGACYPM-NEXT:    br i1 true, label [[DO_BODY_I_I_RDRAND_INT_EXIT_I_CRIT_EDGE:%.*]], label [[DO_BODY_I_I_DO_BODY_I_I_CRIT_EDGE]]
 ; LEGACYPM:       do.body.i.i.rdrand_int.exit.i_crit_edge:
-; LEGACYPM-NEXT:    br i1 true, label [[FOR_END]], label [[FOR_INC:%.*]]
+; LEGACYPM-NEXT:    br i1 true, label [[DO_BODY_I_I_RDRAND_INT_EXIT_I_CRIT_EDGE_FOR_END_CRIT_EDGE:%.*]], label [[FOR_INC:%.*]]
+; LEGACYPM:       do.body.i.i.rdrand_int.exit.i_crit_edge.for.end_crit_edge:
+; LEGACYPM-NEXT:    br label [[FOR_END:%.*]]
 ; LEGACYPM:       for.inc:
 ; LEGACYPM-NEXT:    br label [[FOR_COND]]
+; LEGACYPM:       for.endsplit:
+; LEGACYPM-NEXT:    br label [[FOR_END]]
 ; LEGACYPM:       for.end:
-; LEGACYPM-NEXT:    [[PGOCOUNT_PROMOTED24:%.*]] = phi i64 [ undef, [[FOR_COND]] ], [ [[LSR_IV_NEXT]], [[DO_BODY_I_I_RDRAND_INT_EXIT_I_CRIT_EDGE]] ]
+; LEGACYPM-NEXT:    [[PGOCOUNT_PROMOTED24:%.*]] = phi i64 [ [[LSR_IV_NEXT]], [[DO_BODY_I_I_RDRAND_INT_EXIT_I_CRIT_EDGE_FOR_END_CRIT_EDGE]] ], [ undef, [[FOR_ENDSPLIT]] ]
 ; LEGACYPM-NEXT:    ret i32 undef
 ;
 ; NEWPM-LABEL: @test1(
 ; NEWPM-NEXT:  entry:
 ; NEWPM-NEXT:    br label [[FOR_COND:%.*]]
 ; NEWPM:       for.cond:
 ; NEWPM-NEXT:    callbr void asm sideeffect "", "i,i,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@test1, [[COND_TRUE_I:%.*]]), i8* blockaddress(@test1, [[FOR_END:%.*]]))
 ; NEWPM-NEXT:    to label [[ASM_FALLTHROUGH_I_I:%.*]] [label [[COND_TRUE_I]], label %for.end]