[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

5675

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

5675

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

5690

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

5688

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

5688

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

llvm/lib/Analysis/ScalarEvolution.cpp

if (AddRec->hasNoUnsignedWrap())
           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 (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;
       }
       if (AllNonNeg)
         ConservativeResult = ConservativeResult.intersectWith(
-          ConstantRange(APInt(BitWidth, 0),
+          ConstantRange(getSignedRangeMin(AddRec->getStart()),
                         APInt::getSignedMinValue(BitWidth)), RangeType);
       else if (AllNonPos)
         ConservativeResult = ConservativeResult.intersectWith(
           ConstantRange(APInt::getSignedMinValue(BitWidth),
-                        APInt(BitWidth, 1)), RangeType);
+                        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(
             AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount,
             BitWidth);
         if (!RangeFromAffine.isFullSet())
           ConservativeResult =

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
-; 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(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