From 2ceba77dfa50c3b936963d4760c69e958e41febd Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Mon, 9 Feb 2015 18:34:55 +0000
Subject: [PATCH] Bugfix: SCEV incorrectly marks certain add recurrences as nsw

When creating a scev for sext({X,+,Y}), scev checks if the expression
is equivalent to {sext X,+,zext Y}.  If it can prove that, it also
tags the original {X,+,Y} as <nsw>, which is not correct.

In the test case I run `-scalar-evolution` twice because the bug
manifests only once SCEV has run through and seen the `sext`
expressions (and then does a in-place mutation on {X,+,Y}).

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



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@228586 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/ScalarEvolution.cpp              | 12 +++++++--
 .../Analysis/ScalarEvolution/incorrect-nsw.ll | 26 +++++++++++++++++++
 2 files changed, 36 insertions(+), 2 deletions(-)
 create mode 100644 test/Analysis/ScalarEvolution/incorrect-nsw.ll

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 649c6e0d575..9aefe8c33f7 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1550,8 +1550,16 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
                        getMulExpr(WideMaxBECount,
                                   getZeroExtendExpr(Step, WideTy)));
           if (SAdd == OperandExtendedAdd) {
-            // Cache knowledge of AR NSW, which is propagated to this AddRec.
-            const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
+            // If AR wraps around then
+            //
+            //    abs(Step) * MaxBECount > unsigned-max(AR->getType())
+            // => SAdd != OperandExtendedAdd
+            //
+            // Thus (AR is not NW => SAdd != OperandExtendedAdd) <=>
+            // (SAdd == OperandExtendedAdd => AR is NW)
+
+            const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
+
             // Return the expression with the addrec on the outside.
             return getAddRecExpr(getSignExtendAddRecStart(AR, Ty, this),
                                  getZeroExtendExpr(Step, Ty),
diff --git a/test/Analysis/ScalarEvolution/incorrect-nsw.ll b/test/Analysis/ScalarEvolution/incorrect-nsw.ll
new file mode 100644
index 00000000000..dd981c404cc
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/incorrect-nsw.ll
@@ -0,0 +1,26 @@
+; RUN: opt -analyze -scalar-evolution -scalar-evolution < %s | FileCheck %s
+
+define void @bad.nsw() {
+; CHECK-LABEL: Classifying expressions for: @bad.nsw
+; CHECK-LABEL: Classifying expressions for: @bad.nsw
+ entry: 
+  br label %loop
+
+ loop:
+  %i = phi i8 [ -1, %entry ], [ %i.inc, %loop ]
+; CHECK:  %i = phi i8 [ -1, %entry ], [ %i.inc, %loop ]
+; CHECK-NEXT: -->  {-1,+,-128}<nw><%loop>
+; CHECK-NOT: -->  {-1,+,-128}<nsw><%loop>
+
+  %counter = phi i8 [ 0, %entry ], [ %counter.inc, %loop ]
+
+  %i.inc = add i8 %i, -128
+  %i.sext = sext i8 %i to i16
+
+  %counter.inc = add i8 %counter, 1
+  %continue = icmp eq i8 %counter, 1
+  br i1 %continue, label %exit, label %loop
+
+ exit:
+  ret void  
+}
-- 
2.34.1