From a7d9ec8751b1bb045f83934e9be202a191249db8 Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Sat, 23 Jul 2016 00:54:36 +0000
Subject: [PATCH] [SCEV] Make isImpliedCondOperandsViaRanges smarter

This change lets us prove things like

  "{X,+,10} s< 5000" implies "{X+7,+,10} does not sign overflow"

It does this by replacing replacing getConstantDifference by
computeConstantDifference (which is smarter) in
isImpliedCondOperandsViaRanges.

llvm-svn: 276505
---
 llvm/include/llvm/Analysis/ScalarEvolution.h       |  9 ---
 llvm/lib/Analysis/ScalarEvolution.cpp              | 12 +---
 .../ScalarEvolution/no-wrap-unknown-becount.ll     | 66 ++++++++++++++++++++++
 3 files changed, 67 insertions(+), 20 deletions(-)

diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
index 6e2e359..765b4a9 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1175,15 +1175,6 @@ namespace llvm {
     /// add recurrence on the loop \p L.
     bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
 
-    /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
-    /// constant, and None if it isn't.
-    ///
-    /// This is intended to be a cheaper version of getMinusSCEV.  We can be
-    /// frugal here since we just bail out of actually constructing and
-    /// canonicalizing an expression in the cases where the result isn't going
-    /// to be a constant.
-    Optional<APInt> getConstantDifference(const SCEV *LHS, const SCEV *RHS);
-
   public:
     ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,
                     DominatorTree &DT, LoopInfo &LI);
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 89c09a8..d881e81 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8571,16 +8571,6 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
   return false;
 }
 
-Optional<APInt> ScalarEvolution::getConstantDifference(const SCEV *LHS,
-                                                       const SCEV *RHS) {
-  if (const SCEVAddExpr *AddLHS = dyn_cast<SCEVAddExpr>(LHS))
-    if (AddLHS->getOperand(1) == RHS)
-      if (auto *Addend = dyn_cast<SCEVConstant>(AddLHS->getOperand(0)))
-        return Addend->getAPInt();
-
-  return None;
-}
-
 bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
                                                      const SCEV *LHS,
                                                      const SCEV *RHS,
@@ -8591,7 +8581,7 @@ bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
     // reduce the compile time impact of this optimization.
     return false;
 
-  Optional<APInt> Addend = getConstantDifference(LHS, FoundLHS);
+  Optional<APInt> Addend = computeConstantDifference(LHS, FoundLHS);
   if (!Addend)
     return false;
 
diff --git a/llvm/test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll b/llvm/test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll
index 1f972f3..bc01f22 100644
--- a/llvm/test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll
+++ b/llvm/test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll
@@ -63,6 +63,50 @@ leave:
   ret void
 }
 
+define void @s_3(i32 %start, i1* %cond) {
+; CHECK-LABEL: Classifying expressions for: @s_3
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.inc, %be ]
+  %cmp = icmp slt i32 %iv, 10000
+  br i1 %cmp, label %be, label %leave
+
+be:
+  %iv.inc = add i32 %iv, 3
+  %iv.inc.sext = sext i32 %iv.inc to i64
+; CHECK:  %iv.inc.sext = sext i32 %iv.inc to i64
+; CHECK-NEXT:  -->  {(sext i32 (3 + %start) to i64),+,3}<nsw><%loop>
+  %c = load volatile i1, i1* %cond
+  br i1 %c, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @s_4(i32 %start, i1* %cond) {
+; CHECK-LABEL: Classifying expressions for: @s_4
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.inc, %be ]
+  %cmp = icmp sgt i32 %iv, -1000
+  br i1 %cmp, label %be, label %leave
+
+be:
+  %iv.inc = add i32 %iv, -3
+  %iv.inc.sext = sext i32 %iv.inc to i64
+; CHECK:  %iv.inc.sext = sext i32 %iv.inc to i64
+; CHECK-NEXT:  -->  {(sext i32 (-3 + %start) to i64),+,-3}<nsw><%loop>
+  %c = load volatile i1, i1* %cond
+  br i1 %c, label %loop, label %leave
+
+leave:
+  ret void
+}
+
 define void @u_0(i32 %n, i1* %cond) {
 ; CHECK-LABEL: Classifying expressions for: @u_0
 entry:
@@ -122,3 +166,25 @@ loop:
 leave:
   ret void
 }
+
+define void @u_3(i32 %start, i1* %cond) {
+; CHECK-LABEL: Classifying expressions for: @u_3
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.inc, %be ]
+  %cmp = icmp ult i32 %iv, 10000
+  br i1 %cmp, label %be, label %leave
+
+be:
+  %iv.inc = add i32 %iv, 3
+  %iv.inc.zext = zext i32 %iv.inc to i64
+; CHECK:  %iv.inc.zext = zext i32 %iv.inc to i64
+; CHECK-NEXT:  -->  {(zext i32 (3 + %start) to i64),+,3}<nuw><%loop>
+  %c = load volatile i1, i1* %cond
+  br i1 %c, label %loop, label %leave
+
+leave:
+  ret void
+}
-- 
2.7.4