Make ScalarEvolution less aggressive with respect to no-wrap flags.

[sanjoy]

Summary

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 a test case demonstrating the bug.

[majnemer]

LGTM

lib/Analysis/ScalarEvolution.cpp

3149–3160

Flags doesn't seem very useful now, perhaps it should be removed?

[atrick]

LGTM with one suggestion for comment.
Thanks for the test cases.

lib/Analysis/ScalarEvolution.cpp

3464–3469

Add a short comment that subtract does not preserve nsw/nuw Flags.

[sanjoy]

Replies inline.

lib/Analysis/ScalarEvolution.cpp

3149–3160

Yup, I'll do that in a follow-up refactoring change.

3464–3469

Will do.

lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
   Type *Ty = V->getType();
   Ty = getEffectiveSCEVType(Ty);
   const SCEV *AllOnes =
                    getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)));
   return getMinusSCEV(AllOnes, V);
 }
 
 /// getMinusSCEV - Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.
 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
                                           SCEV::NoWrapFlags Flags) {
   assert(!maskFlags(Flags, SCEV::FlagNUW) && "subtraction does not have NUW");
 
   // Fast path: X - X --> 0.
   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
 /// input value to the specified type.  If the type must be extended, it is zero
 /// extended.
 const SCEV *
 ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty) {
   Type *SrcTy = V->getType();
   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
if (L->getHeader() == PN->getParent()) {
                 // indices form a positive value.
                 if (GEP->isInBounds()) {
                   Flags = setFlags(Flags, SCEV::FlagNW);
 
                   const SCEV *Ptr = getSCEV(GEP->getPointerOperand());
                   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);
               }
 
               const SCEV *StartVal = getSCEV(StartValueV);
               const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
 
               // Since the no-wrap flags are on the increment, they apply to the
               // post-incremented value as well.
               if (isLoopInvariant(Accum, L))

test/Analysis/ScalarEvolution/nw-sub-is-not-nw-add.ll

+; 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
+}