From 068acc3caa113db0925766d327bf9cae6a9eb885 Mon Sep 17 00:00:00 2001
From: Eli Friedman <eli.friedman@gmail.com>
Date: Wed, 30 Jul 2008 00:04:08 +0000
Subject: [PATCH] Fix for PR2607: SCEV miscomputing the loop count for loops
 with an SGT exit condition.  Essentially, the correct way to flip an
 inequality in 2's complement is the not operator, not the negation operator.
 That said, the difference only affects cases involving INT_MIN.

Also, enhance the pre-test search logic to be a bit smarter about
inequalities flipped with a not operator, so it can eliminate the smax
from the iteration count for simple loops.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54184 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/ScalarEvolution.cpp              | 10 ++++---
 .../2008-07-29-SGTTripCount.ll                | 27 +++++++++++++++++++
 2 files changed, 34 insertions(+), 3 deletions(-)
 create mode 100644 test/Analysis/ScalarEvolution/2008-07-29-SGTTripCount.ll

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 737d9b3823e..14c1389b434 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1976,8 +1976,8 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
     break;
   }
   case ICmpInst::ICMP_SGT: {
-    SCEVHandle TC = HowManyLessThans(SE.getNegativeSCEV(LHS),
-                                     SE.getNegativeSCEV(RHS), L, true);
+    SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
+                                     SE.getNotSCEV(RHS), L, true);
     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
     break;
   }
@@ -2724,7 +2724,11 @@ bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned,
 
   if (!PreCondLHS->getType()->isInteger()) return false;
 
-  return LHS == getSCEV(PreCondLHS) && RHS == getSCEV(PreCondRHS);
+  SCEVHandle PreCondLHSSCEV = getSCEV(PreCondLHS);
+  SCEVHandle PreCondRHSSCEV = getSCEV(PreCondRHS);
+  return (LHS == PreCondLHSSCEV && RHS == PreCondRHSSCEV) ||
+         (LHS == SE.getNotSCEV(PreCondRHSSCEV) &&
+          RHS == SE.getNotSCEV(PreCondLHSSCEV));
 }
 
 /// HowManyLessThans - Return the number of times a backedge containing the
diff --git a/test/Analysis/ScalarEvolution/2008-07-29-SGTTripCount.ll b/test/Analysis/ScalarEvolution/2008-07-29-SGTTripCount.ll
new file mode 100644
index 00000000000..307439f7b86
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/2008-07-29-SGTTripCount.ll
@@ -0,0 +1,27 @@
+; RUN: llvm-as < %s | opt -analyze -scalar-evolution -disable-output \
+; RUN:   -scalar-evolution-max-iterations=0 | \
+; RUN: grep -F "( -1 + ( -1 *  %j)) iterations"
+; PR2607
+
+define i32 @_Z1aj(i32 %j) nounwind  {
+entry:
+	icmp sgt i32 0, %j		; <i1>:0 [#uses=1]
+	br i1 %0, label %bb.preheader, label %return
+
+bb.preheader:		; preds = %entry
+	br label %bb
+
+bb:		; preds = %bb, %bb.preheader
+	%i.01 = phi i32 [ %1, %bb ], [ 0, %bb.preheader ]		; <i32> [#uses=1]
+	add i32 %i.01, -1		; <i32>:1 [#uses=3]
+	icmp sgt i32 %1, %j		; <i1>:2 [#uses=1]
+	br i1 %2, label %bb, label %return.loopexit
+
+return.loopexit:		; preds = %bb
+	br label %return
+
+return:		; preds = %return.loopexit, %entry
+	%i.0.lcssa = phi i32 [ 0, %entry ], [ %1, %return.loopexit ]		; <i32> [#uses=1]
+	ret i32 %i.0.lcssa
+}
+
-- 
2.34.1