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

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 7e7fc756d104ddbeb85db8161f63d85f1e7f6be5..251b57a0f984b3543a37c371572265f75d4694b8 100644 (file)
--- 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 0a992f952a802da886648d785444964b2ad0645e..2386cf4f597c86bff83201325137767f65da707e 100644 (file)
--- 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
+}