Merging r258184:

------------------------------------------------------------------------
r258184 | sanjoy | 2016-01-19 12:53:51 -0800 (Tue, 19 Jan 2016) | 20 lines

[SCEV] Fix PR26207

In some cases, the max backedge taken count can be more conservative
than the exact backedge taken count (for instance, because
ScalarEvolution::getRange is not control-flow sensitive whereas
computeExitLimitFromICmp can be).  In these cases,
computeExitLimitFromCond (specifically the bit that deals with `and` and
`or` instructions) can create an ExitLimit instance with a
`SCEVCouldNotCompute` max backedge count expression, but a computable
exact backedge count expression.  This violates an implicit SCEV
assumption: a computable exact BE count should imply a computable max BE
count.

This change

 - Makes the above implicit invariant explicit by adding an assert to
   ExitLimit's constructor

 - Changes `computeExitLimitFromCond` to be more robust around
   conservative max backedge counts
------------------------------------------------------------------------

git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_38@258869 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index c08335de3e7deb1b210eda435a37415d13559dc4..ef9305788849e7bd609aaa12edce7a89591283f1 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -412,7 +412,11 @@ namespace llvm {
 
       /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {}
 
-      ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {}
+      ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {
+        assert((isa<SCEVCouldNotCompute>(Exact) ||
+                !isa<SCEVCouldNotCompute>(Max)) &&
+               "Exact is not allowed to be less precise than Max");
+      }
 
       /// Test whether this ExitLimit contains any computed information, or
       /// whether it's all SCEVCouldNotCompute values.

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 34074efd1cebcce7fe41395dd8d3e98c4bed374f..ef1bb3a36c8d4205652560cfa9c04bf112c9e540 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -5368,6 +5368,14 @@ ScalarEvolution::computeExitLimitFromCond(const Loop *L,
           BECount = EL0.Exact;
       }
 
+      // There are cases (e.g. PR26207) where computeExitLimitFromCond is able
+      // to be more aggressive when computing BECount than when computing
+      // MaxBECount.  In these cases it is possible for EL0.Exact and EL1.Exact
+      // to match, but for EL0.Max and EL1.Max to not.
+      if (isa<SCEVCouldNotCompute>(MaxBECount) &&
+          !isa<SCEVCouldNotCompute>(BECount))
+        MaxBECount = BECount;
+
       return ExitLimit(BECount, MaxBECount);
     }
     if (BO->getOpcode() == Instruction::Or) {

diff --git a/test/Transforms/IndVarSimplify/pr26207.ll b/test/Transforms/IndVarSimplify/pr26207.ll
new file mode 100644 (file)
index 0000000..9d351e0
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/pr26207.ll
@@ -0,0 +1,20 @@
+; RUN: opt -S -indvars < %s | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @main(i16 %in) {
+; CHECK-LABEL: @main(
+  br label %bb2
+
+bb2:                                              ; preds = %bb1.i, %bb2, %0
+  %_tmp44.i = icmp slt i16 %in, 2
+  br i1 %_tmp44.i, label %bb1.i, label %bb2
+
+bb1.i:                                            ; preds = %bb1.i, %bb2
+  %_tmp25.i = phi i16 [ %in, %bb2 ], [ %_tmp6.i, %bb1.i ]
+  %_tmp6.i = add nsw i16 %_tmp25.i, 1
+  %_tmp10.i = icmp sge i16 %_tmp6.i, 2
+  %exitcond.i = icmp eq i16 %_tmp6.i, 2
+  %or.cond = and i1 %_tmp10.i, %exitcond.i
+  br i1 %or.cond, label %bb2, label %bb1.i
+}