From cb4736636632da83fbd746a6ce42a06d04af8448 Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Thu, 22 Jan 2015 00:48:47 +0000
Subject: [PATCH] Make ScalarEvolution less aggressive with respect to no-wrap
 flags.

ScalarEvolution currently lowers a subtraction recurrence to an add
recurrence with the same no-wrap flags as the subtraction.  This is
incorrect because `sub nsw X, Y` is not the same as `add nsw X, -Y`
and `sub nuw X, Y` is not the same as `add nuw X, -Y`.  This patch
fixes the issue, and adds two test cases demonstrating the bug.

Differential Revision: http://reviews.llvm.org/D7081

llvm-svn: 226755
---
 llvm/lib/Analysis/ScalarEvolution.cpp         | 15 ++++---
 .../ScalarEvolution/nw-sub-is-not-nw-add.ll   | 41 +++++++++++++++++++
 2 files changed, 48 insertions(+), 8 deletions(-)
 create mode 100644 llvm/test/Analysis/ScalarEvolution/nw-sub-is-not-nw-add.ll

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 6a58ce153b58..510523ec60a1 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -3154,8 +3154,9 @@ const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
   if (LHS == RHS)
     return getConstant(LHS->getType(), 0);
 
-  // X - Y --> X + -Y
-  return getAddExpr(LHS, getNegativeSCEV(RHS), Flags);
+  // X - Y --> X + -Y.
+  // X -(nsw || nuw) Y --> X + -Y.
+  return getAddExpr(LHS, getNegativeSCEV(RHS));
 }
 
 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
@@ -3461,12 +3462,10 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
                   if (isKnownPositive(getMinusSCEV(getSCEV(GEP), Ptr)))
                     Flags = setFlags(Flags, SCEV::FlagNUW);
                 }
-              } else if (const SubOperator *OBO =
-                           dyn_cast<SubOperator>(BEValueV)) {
-                if (OBO->hasNoUnsignedWrap())
-                  Flags = setFlags(Flags, SCEV::FlagNUW);
-                if (OBO->hasNoSignedWrap())
-                  Flags = setFlags(Flags, SCEV::FlagNSW);
+
+                // We cannot transfer nuw and nsw flags from subtraction
+                // operations -- sub nuw X, Y is not the same as add nuw X, -Y
+                // for instance.
               }
 
               const SCEV *StartVal = getSCEV(StartValueV);
diff --git a/llvm/test/Analysis/ScalarEvolution/nw-sub-is-not-nw-add.ll b/llvm/test/Analysis/ScalarEvolution/nw-sub-is-not-nw-add.ll
new file mode 100644
index 000000000000..41b07d5cd537
--- /dev/null
+++ b/llvm/test/Analysis/ScalarEvolution/nw-sub-is-not-nw-add.ll
@@ -0,0 +1,41 @@
+; RUN: opt -S -indvars < %s | FileCheck %s
+
+; Check that SCEV does not assume sub nuw X Y == add nuw X, -Y
+define void @f(i32* %loc) {
+; CHECK-LABEL: @f
+ entry:
+  br label %loop
+
+ loop:
+  %idx = phi i32 [ 6, %entry ], [ %idx.dec, %loop ]
+  store i32 %idx, i32* %loc
+  %idx.dec = sub nuw i32 %idx, 1
+  %cond = icmp uge i32 %idx.dec, 5
+  br i1 %cond, label %loop, label %exit
+; CHECK-NOT: br i1 true, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+declare void @use_i1(i1)
+
+; Check that SCEV does not assume sub nsw X Y == add nsw X, -Y
+define void @g(i32 %lim) {
+; CHECK-LABEL: @g
+ entry:
+  br label %loop
+
+ loop:
+  %idx = phi i32 [ -1, %entry ], [ %idx.dec, %loop ]
+  %t = icmp sgt i32 %idx, 0
+; CHECK-NOT:   call void @use_i1(i1 false)
+; CHECK: call void @use_i1(i1 %t)
+  call void @use_i1(i1 %t)
+  %idx.dec = sub nsw i32 %idx, -2147483648
+  %cond = icmp eq i32 %idx.dec, %lim
+  br i1 %cond, label %loop, label %exit
+
+ exit:
+  ret void
+}
-- 
2.34.1