Fix 12513: Loop unrolling breaks with indirect branches.

Take this opportunity to generalize the indirectbr bailout logic for
loop transformations. CFG transformations will never get indirectbr
right, and there's no point trying.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154386 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 4921629a040de72713013f8c8afe9fad7040ff8b..91feaaac038debd4b3ef0b5d0edd3b7d4b38d4e5 100644 (file)
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -594,6 +594,9 @@ public:
   /// normal form.
   bool isLoopSimplifyForm() const;
 
+  /// isSafeToClone - Return true if the loop body is safe to clone in practice.
+  bool isSafeToClone() const;
+
   /// hasDedicatedExits - Return true if no exit block for the loop
   /// has a predecessor that is outside the loop.
   bool hasDedicatedExits() const;

diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 858cc642f41a66bf8f6f2d62443184fea186b9c1..f7a60a1737d4b54474961207c3349c1c05236737 100644 (file)
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -205,6 +205,17 @@ bool Loop::isLoopSimplifyForm() const {
   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
 }
 
+/// isSafeToClone - Return true if the loop body is safe to clone in practice.
+/// 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.
+  for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
+    if (isa<IndirectBrInst>((*I)->getTerminator()))
+      return false;
+  }
+  return true;
+}
+
 /// hasDedicatedExits - Return true if no exit block for the loop
 /// has a predecessor that is outside the loop.
 bool Loop::hasDedicatedExits() const {

diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp
index 1c93a703d6f14b86ca723dfb20a2ba991e2dcef2..ee232687ffde714961efacf39f7299c5a7c0da9c 100644 (file)
--- a/lib/Transforms/Scalar/LoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -192,10 +192,6 @@ namespace {
       loopPreheader = currentLoop->getLoopPreheader();
     }
 
-    /// HasIndirectBrsInPreds - Returns true if there are predecessors, that are
-    /// terminated with indirect branch instruction.
-    bool HasIndirectBrsInPreds(const SmallVectorImpl<BasicBlock *> &ExitBlocks);
-
     /// Split all of the edges from inside the loop to their exit blocks.
     /// Update the appropriate Phi nodes as we do so.
     void SplitExitEdges(Loop *L, const SmallVector<BasicBlock *, 8> &ExitBlocks);
@@ -203,7 +199,7 @@ namespace {
     bool UnswitchIfProfitable(Value *LoopCond, Constant *Val);
     void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
                                   BasicBlock *ExitBlock);
-    bool UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
+    void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L);
 
     void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
                                               Constant *Val, bool isEqual);
@@ -409,6 +405,14 @@ bool LoopUnswitch::processCurrentLoop() {
   if (!loopPreheader)
     return false;
 
+  // Loops with indirectbr cannot be cloned.
+  if (!currentLoop->isSafeToClone())
+    return false;
+
+  // Without dedicated exits, splitting the exit edge may fail.
+  if (!currentLoop->hasDedicatedExits())
+    return false;
+
   LLVMContext &Context = loopHeader->getContext();
 
   // Probably we reach the quota of branches for this loop. If so
@@ -638,7 +642,8 @@ bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) {
   if (OptimizeForSize || F->hasFnAttr(Attribute::OptimizeForSize))
     return false;
 
-  return UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
+  UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
+  return true;
 }
 
 /// CloneLoop - Recursively clone the specified loop and all of its children,
@@ -733,24 +738,6 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond,
   ++NumTrivial;
 }
 
-/// HasIndirectBrsInPreds - Returns true if there are predecessors, that are
-/// terminated with indirect branch instruction.
-bool LoopUnswitch::HasIndirectBrsInPreds(
-     const SmallVectorImpl<BasicBlock *> &ExitBlocks){
-
-  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
-    const BasicBlock *ExitBlock = ExitBlocks[i];
-    for (const_pred_iterator p = pred_begin(ExitBlock), e = pred_end(ExitBlock);
-         p != e; ++p) {
-      // Cannot split an edge from an IndirectBrInst
-      if (isa<IndirectBrInst>((*p)->getTerminator()))
-        return true;
-
-    }
-  }
-  return false;
-}
-
 /// SplitExitEdges - Split all of the edges from inside the loop to their exit
 /// blocks.  Update the appropriate Phi nodes as we do so.
 void LoopUnswitch::SplitExitEdges(Loop *L,
@@ -776,7 +763,7 @@ void LoopUnswitch::SplitExitEdges(Loop *L,
 /// UnswitchNontrivialCondition - We determined that the loop is profitable
 /// to unswitch when LIC equal Val.  Split it into loop versions and test the
 /// condition outside of either loop.  Return the loops created as Out1/Out2.
-bool LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
+void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
                                                Loop *L) {
   Function *F = loopHeader->getParent();
   DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
@@ -800,8 +787,6 @@ bool LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
-  if (HasIndirectBrsInPreds(ExitBlocks))
-    return false;
 
   // Split all of the edges from inside the loop to their exit blocks.  Update
   // the appropriate Phi nodes as we do so.
@@ -916,8 +901,6 @@ bool LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
   if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
       LICHandle && !isa<Constant>(LICHandle))
     RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
-
-  return true;
 }
 
 /// RemoveFromWorklist - Remove all instances of I from the worklist vector

diff --git a/lib/Transforms/Utils/LoopUnroll.cpp b/lib/Transforms/Utils/LoopUnroll.cpp
index 512b6895011bfb0c380cd41289579a58b70db8c3..e15497a77ae3f5ed742e5172eecf161c36712d97 100644 (file)
--- a/lib/Transforms/Utils/LoopUnroll.cpp
+++ b/lib/Transforms/Utils/LoopUnroll.cpp
@@ -149,6 +149,12 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
     return false;
   }
 
+  // Loops with indirectbr cannot be cloned.
+  if (!L->isSafeToClone()) {
+    DEBUG(dbgs() << "  Can't unroll; Loop body cannot be cloned.\n");
+    return false;
+  }
+
   BasicBlock *Header = L->getHeader();
   BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
 

diff --git a/test/Transforms/LoopUnroll/2012-04-09-unroll-indirectbr.ll b/test/Transforms/LoopUnroll/2012-04-09-unroll-indirectbr.ll
new file mode 100644 (file)
index 0000000..8946a23
--- /dev/null
+++ b/test/Transforms/LoopUnroll/2012-04-09-unroll-indirectbr.ll
@@ -0,0 +1,40 @@
+; RUN: opt < %s -S -loop-unroll -simplifycfg | FileCheck %s
+; PR12513: Loop unrolling breaks with indirect branches.
+; If loop unrolling attempts to transform this loop, it replaces the
+; indirectbr successors. SimplifyCFG then considers them to be unreachable.
+declare void @subtract() nounwind uwtable
+
+; CHECK-NOT: unreachable
+define i32 @main(i32 %argc, i8** nocapture %argv) nounwind uwtable {
+entry:
+  %vals19 = alloca [5 x i32], align 16
+  %x20 = alloca i32, align 4
+  store i32 135, i32* %x20, align 4
+  br label %for.body
+
+for.body:                                         ; preds = ; %call2_termjoin, %call3_termjoin
+  %indvars.iv = phi i64 [ 0, %entry ], [ %joinphi15.in.in, %call2_termjoin ]
+  %a6 = call coldcc i8* @funca(i8* blockaddress(@main, %for.body_code), i8*
+blockaddress(@main, %for.body_codeprime)) nounwind
+  indirectbr i8* %a6, [label %for.body_code, label %for.body_codeprime]
+
+for.body_code:                                    ; preds = %for.body
+  call void @subtract()
+  br label %call2_termjoin
+
+call2_termjoin:                                   ; preds = %for.body_codeprime, %for.body_code
+  %joinphi15.in.in = add i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %joinphi15.in.in, 5
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %call2_termjoin
+  ret i32 0
+
+for.body_codeprime:                               ; preds = %for.body
+  call void @subtract_v2(i64 %indvars.iv)
+  br label %call2_termjoin
+}
+
+declare coldcc i8* @funca(i8*, i8*) readonly
+
+declare void @subtract_v2(i64) nounwind uwtable

diff --git a/test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll b/test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll
index c677bde116f35918be28c5b758e39ce73f0e1766..c92f0a2be3fc995c98f944d4e71b28946352d9a9 100644 (file)
--- a/test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll
+++ b/test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll
@@ -1,18 +1,13 @@
-; RUN: opt -loop-unswitch -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
-; RUN: opt -S -loop-unswitch -verify-loop-info -verify-dom-info %s | FileCheck %s
-
-; STATS: 1 loop-unswitch - Total number of instructions analyzed
+; RUN: opt < %s -S -loop-unswitch -verify-loop-info -verify-dom-info | FileCheck %s
+; PR12343: -loop-unswitch crash on indirect branch
 
 ; CHECK:       %0 = icmp eq i64 undef, 0
 ; CHECK-NEXT:  br i1 %0, label %"5", label %"4"
 
 ; CHECK:       "5":                                              ; preds = %entry
-; CHECK-NEXT:  br label %"5.split"
-
-; CHECK:       "5.split":                                        ; preds = %"5"
 ; CHECK-NEXT:  br label %"16"
 
-; CHECK:       "16":                                             ; preds = %"22", %"5.split"
+; CHECK:       "16":                                             ; preds = %"22", %"5"
 ; CHECK-NEXT:  indirectbr i8* undef, [label %"22", label %"33"]
 
 ; CHECK:       "22":                                             ; preds = %"16"