From 0afc9b33fef2d41d8be638320ed5c65dc1d09d9a Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Wed, 18 Feb 2015 00:43:19 +0000
Subject: [PATCH] Bugfix: SCEV incorrectly marks certain expressions as nsw

I could not come up with a test case for this one; but I don't think
`getPreStartForSignExtend` can assume `AR` is `nsw` -- there is one
place in scalar evolution that calls `getSignExtendAddRecStart(AR,
...)` without proving that `AR` is `nsw`

(line 1564)

   OperandExtendedAdd =
     getAddExpr(WideStart,
                getMulExpr(WideMaxBECount,
                           getZeroExtendExpr(Step, WideTy)));
   if (SAdd == OperandExtendedAdd) {
     // 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),
                          L, AR->getNoWrapFlags());
   }

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



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@229594 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/ScalarEvolution.cpp | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 6edd8621ab3..2ff254394a3 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1327,12 +1327,12 @@ static const SCEV *getOverflowLimitForStep(const SCEV *Step,
   return nullptr;
 }
 
-// The recurrence AR has been shown to have no signed wrap. Typically, if we can
-// prove NSW for AR, then we can just as easily prove NSW for its preincrement
-// or postincrement sibling. This allows normalizing a sign extended AddRec as
-// such: {sext(Step + Start),+,Step} => {(Step + sext(Start),+,Step} As a
-// result, the expression "Step + sext(PreIncAR)" is congruent with
-// "sext(PostIncAR)"
+// The recurrence AR has been shown to have no signed wrap or something close to
+// it.  Typically, if we can prove NSW for AR, then we can just as easily prove
+// NSW for its preincrement or postincrement sibling. This allows normalizing a
+// sign extended AddRec as such: {sext(Step + Start),+,Step} => {(Step +
+// sext(Start),+,Step} As a result, the expression "Step + sext(PreIncAR)" is
+// congruent with "sext(PostIncAR)"
 static const SCEV *getPreStartForSignExtend(const SCEVAddRecExpr *AR,
                                             Type *Ty,
                                             ScalarEvolution *SE) {
@@ -1392,7 +1392,7 @@ static const SCEV *getPreStartForSignExtend(const SCEVAddRecExpr *AR,
                    SE->getSignExtendExpr(Step, WideTy));
   if (SE->getSignExtendExpr(Start, WideTy) == OperandExtendedStart) {
     // Cache knowledge of PreAR NSW.
-    if (PreAR)
+    if (PreAR && AR->getNoWrapFlags(SCEV::FlagNSW))
       const_cast<SCEVAddRecExpr *>(PreAR)->setNoWrapFlags(SCEV::FlagNSW);
     // FIXME: this optimization needs a unit test
     DEBUG(dbgs() << "SCEV: untested prestart overflow check\n");
-- 
2.40.0