Merging r258184:
authorSanjoy Das <sanjoy@playingwithpointers.com>
Tue, 26 Jan 2016 22:29:46 +0000 (22:29 +0000)
committerSanjoy Das <sanjoy@playingwithpointers.com>
Tue, 26 Jan 2016 22:29:46 +0000 (22:29 +0000)
------------------------------------------------------------------------
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

include/llvm/Analysis/ScalarEvolution.h
lib/Analysis/ScalarEvolution.cpp
test/Transforms/IndVarSimplify/pr26207.ll [new file with mode: 0644]

index c08335d..ef93057 100644 (file)
@@ -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.
index 34074ef..ef1bb3a 100644 (file)
@@ -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
@@ -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
+}