[SCEV] get a more accurate range for AddRecExpr with nsw flag

[shchenz]

Summary

This is follow up of https://reviews.llvm.org/D71690.

In this patch, handle nsw as well

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

5688–5689

With the new code, we can skip operand zero (start) here. We only need that the step operands have a known sign so the addrec moves in a known direction, but the sign of the start value doesn't matter.

[shchenz]

operand 0 does not required to be NonPos/NonNeg

llvm/lib/Analysis/ScalarEvolution.cpp

5688–5689

Good point.

[efriedma]

I'd like to see a few more testcases here, to cover the new functionality

[nikic]

Logic looks good to me. As @efriedma mentioned some extra tests would be good, especially for the different sign cases. The current test only covers negative start with negative step.

llvm/lib/Analysis/ScalarEvolution.cpp

5702

It's possible to use getNonEmpty() to avoid the explicit check for signed-min / signed-max:

ConservativeResult = ConservativeResult.intersectWith(
    ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
    APInt::getSignedMinValue(BitWidth)),
    RangeType);

[shchenz]

use getNonEmpty() interface & add more test cases

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

5704

This looks a bit ugly, it might make sense to insert a newline after getNonEmpty( instead and only do the 4-space indent, so there's still space for the + 1.

[shchenz]

llvm/lib/Analysis/ScalarEvolution.cpp

5704

Thanks, this is formatted by clang-format. I will reformat it manually.

llvm/lib/Analysis/ScalarEvolution.cpp

if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
     // If there's no unsigned wrap, the value will never be less than its
     // initial value.
     if (AddRec->hasNoUnsignedWrap())
       if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))
         if (!C->getValue()->isZero())
           ConservativeResult = ConservativeResult.intersectWith(
               ConstantRange(C->getAPInt(), APInt(BitWidth, 0)), RangeType);
 
-    // If there's no signed wrap, and all the operands have the same sign or
-    // zero, the value won't ever change sign.
+    // If there's no signed wrap, and all the operands except initial value have
+    // the same sign or zero, the value won't ever be:
+    // 1: smaller than initial value if operands are non negative,
+    // 2: bigger than initial value if operands are non positive.
+    // For both cases, value can not cross signed min/max boundary.
     if (AddRec->hasNoSignedWrap()) {
       bool AllNonNeg = true;
       bool AllNonPos = true;
-      for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
-        if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false;
-        if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false;
+      for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) {
+        if (!isKnownNonNegative(AddRec->getOperand(i)))
+          AllNonNeg = false;
+        if (!isKnownNonPositive(AddRec->getOperand(i)))
+          AllNonPos = false;
       }
       if (AllNonNeg)
         ConservativeResult = ConservativeResult.intersectWith(
-          ConstantRange(APInt(BitWidth, 0),
-                        APInt::getSignedMinValue(BitWidth)), RangeType);
+            ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
+                                       APInt::getSignedMinValue(BitWidth)),
+            RangeType);
       else if (AllNonPos)
         ConservativeResult = ConservativeResult.intersectWith(
-          ConstantRange(APInt::getSignedMinValue(BitWidth),
-                        APInt(BitWidth, 1)), RangeType);
+            ConstantRange::getNonEmpty(
+                APInt::getSignedMinValue(BitWidth),
+                getSignedRangeMax(AddRec->getStart()) + 1),
+            RangeType);
     }
 
     // TODO: non-affine addrec
     if (AddRec->isAffine()) {
       const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(AddRec->getLoop());
       if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
           getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
         auto RangeFromAffine = getRangeForAffineAR(

llvm/test/Analysis/ScalarEvolution/range_nw_flag.ll

loop:
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret void
 }
 
 ; CHECK-LABEL: @test-addrec-nsw-start-neg-strip-neg
-; CHECK: -->  {(-1 + (-10 smin %offset))<nsw>,+,-1}<nsw><%loop> U: [-2147483648,1) S: [-2147483648,1)
+; CHECK: -->  {(-1 + (-10 smin %offset))<nsw>,+,-1}<nsw><%loop> U: [-2147483648,-10) S: [-2147483648,-10)
 define void @test-addrec-nsw-start-neg-strip-neg(float* %input, i32 %offset, i32 %numIterations) {
 entry:
   %cmp = icmp slt i32 %offset, -10
   %max = select i1 %cmp, i32 %offset, i32 -10
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
   %nexti = add nsw i32 %i, -1
   %index32 = add nsw i32 %nexti, %max
   %ptr = getelementptr inbounds float, float* %input, i32 %index32
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret void
 }
 
 ; CHECK-LABEL: @test-addrec-nsw-start-pos-strip-neg
-; CHECK: -->  {(-1 + (10 smin %offset))<nsw>,+,-1}<nsw><%loop> U: full-set S: full-set
+; CHECK: -->  {(-1 + (10 smin %offset))<nsw>,+,-1}<nsw><%loop> U: [-2147483648,10) S: [-2147483648,10)
 define void @test-addrec-nsw-start-pos-strip-neg(float* %input, i32 %offset, i32 %numIterations) {
 entry:
   %cmp = icmp slt i32 %offset, 10
   %max = select i1 %cmp, i32 %offset, i32  10
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
   %nexti = add nsw i32 %i, -1
   %index32 = add nsw i32 %nexti, %max
   %ptr = getelementptr inbounds float, float* %input, i32 %index32
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret void
 }
 
 ; CHECK-LABEL: @test-addrec-nsw-start-pos-strip-pos
-; CHECK: -->  {(1 + (10 smax %offset))<nuw><nsw>,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648)
+; CHECK: -->  {(1 + (10 smax %offset))<nuw><nsw>,+,1}<nuw><nsw><%loop> U: [11,-2147483648) S: [11,-2147483648)
 define void @test-addrec-nsw-start-pos-strip-pos(float* %input, i32 %offset, i32 %numIterations) {
 entry:
   %cmp = icmp sgt i32 %offset, 10
   %min = select i1 %cmp, i32 %offset, i32  10
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
   %nexti = add nsw i32 %i, 1
   %index32 = add nsw i32 %nexti, %min
   %ptr = getelementptr inbounds float, float* %input, i32 %index32
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret void
 }
 
 ; CHECK-LABEL: @test-addrec-nsw-start-neg-strip-pos
-; CHECK: -->  {(1 + (-10 smax %offset))<nsw>,+,1}<nsw><%loop> U: full-set S: full-set
+; CHECK: -->  {(1 + (-10 smax %offset))<nsw>,+,1}<nsw><%loop> U: [-9,-2147483648) S: [-9,-2147483648)
 define void @test-addrec-nsw-start-neg-strip-pos(float* %input, i32 %offset, i32 %numIterations) {
 entry:
   %cmp = icmp sgt i32 %offset, -10
   %min = select i1 %cmp, i32 %offset, i32  -10
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
   %nexti = add nsw i32 %i, 1