Fix ScalarEvolution's "exhaustive" trip count evaluation code to avoid

assuming that loops are in canonical form, as ScalarEvolution doesn't
depend on LoopSimplify itself. Also, with indirectbr not all loops can
be simplified. This fixes PR7416.


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

2 files changed, 36 insertions, 2 deletions

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 7e7fc75..251b57a 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -4238,8 +4238,11 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
   PHINode *PN = getConstantEvolvingPHI(Cond, L);
   if (PN == 0) return getCouldNotCompute();
 
-  // Since the loop is canonicalized, the PHI node must have two entries.  One
-  // entry must be a constant (coming in from outside of the loop), and the
+  // If the loop is canonicalized, the PHI will have exactly two entries.
+  // That's the only form we support here.
+  if (PN->getNumIncomingValues() != 2) return getCouldNotCompute();
+
+  // One entry must be a constant (coming in from outside of the loop), and the
   // second must be derived from the same PHI.
   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
   Constant *StartCST =
diff --git a/test/Analysis/ScalarEvolution/trip-count10.ll b/test/Analysis/ScalarEvolution/trip-count10.ll
index 0a992f9..2386cf4 100644
--- a/test/Analysis/ScalarEvolution/trip-count10.ll
+++ b/test/Analysis/ScalarEvolution/trip-count10.ll
@@ -74,3 +74,34 @@ loop:
 return:
   ret void
 }
+
+; Trip counts for non-polynomial iterations. It's theoretically possible
+; to compute a maximum count for these, but short of that, ScalarEvolution
+; should return unknown.
+
+; PR7416
+; CHECK: Determining loop execution counts for: @nonpolynomial
+; CHECK-NEXT: Loop %loophead: Unpredictable backedge-taken count
+; CHECK-NEXT: Loop %loophead: Unpredictable max backedge-taken count
+
+declare i1 @g() nounwind
+
+define void @nonpolynomial() {
+entry:
+  br label %loophead
+loophead:
+  %x = phi i32 [0, %entry], [%x.1, %bb1], [%x.2, %bb2]
+  %y = icmp slt i32 %x, 100
+  br i1 %y, label %loopbody, label %retbb
+loopbody:
+  %z = call i1 @g()
+  br i1 %z, label %bb1, label %bb2
+bb1:
+  %x.1 = add i32 %x, 2
+  br label %loophead
+bb2:
+  %x.2 = add i32 %x, 3
+  br label %loophead
+retbb:
+  ret void
+}