[LoopInfo] Allow cloning of callbr

[nikic]

Summary

After D129288, callbr is safe to clone without special handling. This permits optimizations like loop unroll and loop unswitch on loops containing callbrs.

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

[nickdesaulniers]

Thanks for fixing this up!

llvm/lib/Analysis/LoopInfo.cpp

bool Loop::isLoopSimplifyForm() const {
   // exits have all their predecessors inside the loop.
   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
 }
 
 // Routines that reform the loop CFG and split edges often fail on indirectbr.
 bool Loop::isSafeToClone() const {
   // Return false if any loop blocks contain indirectbrs, or there are any calls
   // to noduplicate functions.
-  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
-  // operand list to reflect the newly cloned labels.
   for (BasicBlock *BB : this->blocks()) {
-    if (isa<IndirectBrInst>(BB->getTerminator()) ||
-        isa<CallBrInst>(BB->getTerminator()))
+    if (isa<IndirectBrInst>(BB->getTerminator()))
       return false;
 
     for (Instruction &I : *BB)
       if (auto *CB = dyn_cast<CallBase>(&I))
         if (CB->cannotDuplicate())
           return false;
   }
   return true;

llvm/test/Transforms/LoopUnroll/callbr.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -loop-unroll -S %s | FileCheck %s
 
-; Check that the loop body does not get unrolled.  We could modify this test in
-; the future to support loop unrolling callbr's IFF we checked that the callbr
-; operands were unrolled/updated correctly, as today they are not.
+; Check that the loop body containing callbr is correctly unrolled.
 define dso_local void @d() {
 ; CHECK-LABEL: @d(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
-; CHECK:       for.cond.cleanup:
-; CHECK-NEXT:    ret void
 ; CHECK:       for.body:
-; CHECK-NEXT:    [[E_04:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[E_04]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_INC]], label [[IF_THEN:%.*]]
+; CHECK-NEXT:    br i1 true, label [[FOR_INC:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    callbr void asm sideeffect "1: nop\0A\09.quad b, ${0:l}, $$5\0A\09", "!i,~{dirflag},~{fpsr},~{flags}"()
 ; CHECK-NEXT:    to label [[ASM_FALLTHROUGH:%.*]] [label %l_yes]
 ; CHECK:       asm.fallthrough:
 ; CHECK-NEXT:    br label [[L_YES:%.*]]
 ; CHECK:       l_yes:
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @g()
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
-; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[E_04]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 3
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+; CHECK-NEXT:    br i1 false, label [[FOR_INC_1:%.*]], label [[IF_THEN_1:%.*]]
+; CHECK:       if.then.1:
+; CHECK-NEXT:    callbr void asm sideeffect "1: nop\0A\09.quad b, ${0:l}, $$5\0A\09", "!i,~{dirflag},~{fpsr},~{flags}"()
+; CHECK-NEXT:    to label [[ASM_FALLTHROUGH_1:%.*]] [label %l_yes.1]
+; CHECK:       asm.fallthrough.1:
+; CHECK-NEXT:    br label [[L_YES_1:%.*]]
+; CHECK:       l_yes.1:
+; CHECK-NEXT:    [[CALL_1:%.*]] = tail call i32 (...) @g()
+; CHECK-NEXT:    br label [[FOR_INC_1]]
+; CHECK:       for.inc.1:
+; CHECK-NEXT:    br i1 false, label [[FOR_INC_2:%.*]], label [[IF_THEN_2:%.*]]
+; CHECK:       if.then.2:
+; CHECK-NEXT:    callbr void asm sideeffect "1: nop\0A\09.quad b, ${0:l}, $$5\0A\09", "!i,~{dirflag},~{fpsr},~{flags}"()
+; CHECK-NEXT:    to label [[ASM_FALLTHROUGH_2:%.*]] [label %l_yes.2]
+; CHECK:       asm.fallthrough.2:
+; CHECK-NEXT:    br label [[L_YES_2:%.*]]
+; CHECK:       l_yes.2:
+; CHECK-NEXT:    [[CALL_2:%.*]] = tail call i32 (...) @g()
+; CHECK-NEXT:    br label [[FOR_INC_2]]
+; CHECK:       for.inc.2:
+; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.cond.cleanup:                                 ; preds = %for.inc
   ret void
 
 for.body:                                         ; preds = %for.inc, %entry

llvm/test/Transforms/SimpleLoopUnswitch/callbr.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='simple-loop-unswitch<nontrivial>' %s -S | FileCheck %s
 
 declare i1 @foo()
 
 define i32 @mem_cgroup_node_nr_lru_pages(i1 %tree) {
 ; CHECK-LABEL: @mem_cgroup_node_nr_lru_pages(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[TREE:%.*]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK:       entry.split.us:
+; CHECK-NEXT:    br label [[FOR_COND_US:%.*]]
+; CHECK:       for.cond.us:
+; CHECK-NEXT:    br label [[IF_END8_US:%.*]]
+; CHECK:       if.end8.us:
+; CHECK-NEXT:    br label [[FOR_COND_US]]
+; CHECK:       entry.split:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
-; CHECK-NEXT:    br i1 [[TREE:%.*]], label [[IF_END8:%.*]], label [[IF_ELSE:%.*]]
+; CHECK-NEXT:    br label [[IF_ELSE:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    callbr void asm sideeffect ".pushsection __jump_table, \22aw\22 \0A\09.popsection \0A\09", "!i,~{dirflag},~{fpsr},~{flags}"()
-; CHECK-NEXT:    to label [[IF_END8]] [label %for.cond5.preheader]
+; CHECK-NEXT:    to label [[IF_END8:%.*]] [label %for.cond5.preheader]
 ; CHECK:       for.cond5.preheader:
 ; CHECK-NEXT:    br label [[FOR_COND5:%.*]]
 ; CHECK:       for.cond5:
 ; CHECK-NEXT:    [[CALL6:%.*]] = call i1 @foo()
 ; CHECK-NEXT:    br i1 [[CALL6]], label [[IF_END8_LOOPEXIT:%.*]], label [[FOR_COND5]]
 ; CHECK:       if.end8.loopexit:
 ; CHECK-NEXT:    br label [[IF_END8]]
 ; CHECK:       if.end8: