[SCEV] get more accurate range for AddExpr with NW flag

[shchenz]

Summary

for AddExpr (1 + %a)<nsw>, if %a (LoopInvariant, such as function parameter) range is fullset, 1 range is [1, 2), for now, constant range add operation will return fullset is any of its operand is fullset.

For above AddExpr, (1 + %a)<nsw> has No-Signed-Wrap flag, so SINT_MIN is not in (1 + %a)<nsw> range. But now we get a conservative range, fullset.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

5578–5579

Stylistically, it would be much cleaner to add a function to ConstantRange with the signature
CR add(CR, NoWrapKind)

5580

Your code is incorrect as implemented. There's no requirement that a SCEVAddExpr have only two operands.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

5578–5579

I was planning to add this ConstantRange functionality based on D61653.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

5578–5579

That looks entirely reasonable. Land that, and rebase?

[shchenz]

@reames Thanks for your comments. I will update this patch after @nikic lands his improvement in https://reviews.llvm.org/D61653

[shchenz]

address @reames comments

[shchenz]

I will commit another NFC patch to merge addWithNoSignedWrap and new added addWithNoWrap.

[shchenz]

ping...

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

5579

I'd very strongly prefer if you structured this as so:
NoWrapKind = compute(Add);
for each operand:

sum += sum.addWithWrapping(Op, NoWrapKind)

This requires that NoWrapKind above be any of: none, signed, unsigned, and both.

llvm/lib/IR/ConstantRange.cpp

829 ↗

(On Diff #211507)

Why not allow both?

834 ↗

(On Diff #211507)

I believe this is impossible from the dominating check, please convert to an assert.

[shchenz]

address @reames comments

[shchenz]

llvm/lib/IR/ConstantRange.cpp

829 ↗

(On Diff #211507)

I think we can not support both wrap type in one range type(unsigned/signed range). We have signed and unsigned range for one SCEV and we set nsw only based on signed range and nuw only based on unsigned range. For example, if one ADD SCEV's signed range is [-10, 20), and its unsigned range is [10, 20), in StrengthenNoWrapFlags, we will set this SCEV with nsw and nuw. But when we wants to get its range after nsw and nuw are set, MGNR unsigned wrap for [-10, 20) is [0, 1), after intersect with [10, 20), we get empty set for this SCEV for both signed range and unsigned range. This is not right. we should handle nsw for signed range and nuw for unsigned range.

[shchenz]

Hi @reames Could you help to have another look at this? Thanks

[reames]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

5583

Move this if/else chain outside the loop. It's loop invariant, and confusing (but correct) as written.

[nikic]

makeGuaranteedNoWrapRegion() cannot be used to constrain input ranges. E.g. consider that the RHS is [UINT_MAX-1, UINT_MAX]. Then the GWNR is just [0, 0], even though 1 would be a legal value for LHS (assuming the RHS is UINT_MAX-1).

[shchenz]

Agree with your comment. @nikic Now we may get a smaller range than its real one with this patch, it may leads to wrong opt. Get a bigger range like trunk is conservative, but right. I will seek for another change for this issue.

[shchenz]

new implementation not based on makeGuaranteedNoWrapRegion

[shchenz]

Hi @nikic @reames , could you help to have another look at the patch? Thanks in advance.

[nikic]

Can you please split off the ConstantRange addition into a separate revision?

llvm/lib/IR/ConstantRange.cpp

853 ↗

(On Diff #218590)

You can use getNonEmpty(A, B) here to avoid the explicit check for full range. Similar below.

862 ↗

(On Diff #218590)

I think that this whole code can be somewhat simplified. I have an unfinished implementation of add nuw lying around that looks like this:

APInt LMin = L.getUnsignedMin(), LMax = L.getUnsignedMax();
APInt RMin = R.getUnsignedMin(), RMax = R.getUnsignedMax();
bool Overflow;
APInt NewMin = LMin.uadd_ov(RMin, Overflow);
if (Overflow)
  return ConstantRange::getEmpty(L.getBitWidth());
APInt NewMax = LMax.uadd_sat(RMax);
return ConstantRange::getNonEmpty(NewMin, std::move(NewMax) + 1);

[shchenz]

address @nikic comments

[shchenz]

In D64869#1662068, @nikic wrote:

Can you please split off the ConstantRange addition into a separate revision?

@nikic done. addWithNoWrap is added in patch https://reviews.llvm.org/D67339 Thanks for your good comments.

[nikic]

The addWithNoWrap addition has landed, but I guess this is now blocked because D64868 has been reverted?

[shchenz]

Yes, I plan to take a look at https://reviews.llvm.org/D64868 firstly.

[shchenz]

Seems we can not simply add nsw|nuw for start + stride as I did in https://reviews.llvm.org/D64868. Since SCEV are shared with expressions in different blocks, we must ensure all expressions mapped to same SCEV can be added with nsw|nuw.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

5579

I'd suggest to also pass the RangeType here, though I'm not sure whether it makes any practical difference.

[nikic]

llvm/test/Transforms/IRCE/ranges_of_different_types.ll

87 ↗

(On Diff #234678)

Can you get a range dump for this code? I'm not entirely clear on why we get an improvement here (assuming the metadata on the load is taken into account, I don't see where addWithNoWrap would produce a better result).

[shchenz]

address @nikic comments

llvm/test/Transforms/IRCE/ranges_of_different_types.ll

87 ↗

(On Diff #234678)

Before the change, SCEV for exit.mainloop.at is (0 smax (101 smin ((-1 * (-13 smax (-2147483647 + %len)<nuw><nsw>))<nsw> + %len)<nuw><nsw>)), now we take nuw for add into account, so we get conclusion that (101 smin ((-1 * (-13 smax (-2147483647 + %len)<nuw><nsw>))<nsw> + %len)<nuw><nsw>) will not be smaller than 0. So after the change, SCEV for exit.mainloop.at is changed to (101 smin ((-1 * (-13 smax (-2147483647 + %len)<nuw><nsw>))<nsw> + %len)<nuw><nsw>)

[nikic]

LGTM

llvm/test/Transforms/IRCE/ranges_of_different_types.ll

87 ↗

(On Diff #234678)

Thanks. So the difference comes from the sub, which is really a add nuw nsw on '-1 * %smax1`.

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getRangeRef(const SCEV *S,
 
   // See if we've computed this range already.
   DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S);
   if (I != Cache.end())
     return I->second;
 
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
     return setRange(C, SignHint, ConstantRange(C->getAPInt()));
+  using OBO = OverflowingBinaryOperator;
 
   unsigned BitWidth = getTypeSizeInBits(S->getType());
   ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true);
 
   // If the value has known zeros, the maximum value will have those known zeros
   // as well.
   uint32_t TZ = GetMinTrailingZeros(S);
   if (TZ != 0) {
     if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED)
       ConservativeResult =
           ConstantRange(APInt::getMinValue(BitWidth),
                         APInt::getMaxValue(BitWidth).lshr(TZ).shl(TZ) + 1);
     else
       ConservativeResult = ConstantRange(
           APInt::getSignedMinValue(BitWidth),
           APInt::getSignedMaxValue(BitWidth).ashr(TZ).shl(TZ) + 1);
   }
 
   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
     ConstantRange X = getRangeRef(Add->getOperand(0), SignHint);
+    unsigned WrapType = OBO::AnyWrap;
+    if (Add->hasNoSignedWrap() &&
+        SignHint == ScalarEvolution::HINT_RANGE_SIGNED)
+      WrapType = OBO::NoSignedWrap;
+    else if (Add->hasNoUnsignedWrap() &&
+             SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED)
+      WrapType = OBO::NoUnsignedWrap;
     for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
-      X = X.add(getRangeRef(Add->getOperand(i), SignHint));
+      X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint),
+                          WrapType);
     return setRange(Add, SignHint,
                     ConservativeResult.intersectWith(X, RangeType));
   }
 
   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
     ConstantRange X = getRangeRef(Mul->getOperand(0), SignHint);
     for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
       X = X.multiply(getRangeRef(Mul->getOperand(i), SignHint));
     return setRange(Mul, SignHint,
                     ConservativeResult.intersectWith(X, RangeType));
   }
 

llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

 loop.exit:
   ret void
 }
 
 ; changing end bound and greater than one stride
 define void @changing_end_bound3(i32 %start, i32* %n_addr, i32* %addr) {
 ; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound3
 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
-; CHECK: Loop %loop: max backedge-taken count is 1073741823
+; CHECK: Loop %loop: max backedge-taken count is 1073741822
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
   %val = load atomic i32, i32* %addr unordered, align 4
   fence acquire

llvm/test/Analysis/ScalarEvolution/trip-count12.ll

 ; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
 
 ; CHECK: Determining loop execution counts for: @test
 ; CHECK: Loop %for.body: backedge-taken count is ((-2 + %len)<nsw> /u 2)
-; CHECK: Loop %for.body: max backedge-taken count is 1073741823
+; CHECK: Loop %for.body: max backedge-taken count is 1073741822
 
 define zeroext i16 @test(i16* nocapture %p, i32 %len) nounwind readonly {
 entry:
   %cmp2 = icmp sgt i32 %len, 1
   br i1 %cmp2, label %for.body.preheader, label %for.end
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body

llvm/test/Analysis/ScalarEvolution/trip-count9.ll

loop:
   %t = icmp slt i4 %i.next, %n
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @nsw_startx
 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x)<nsw> smax %n))
-; CHECK: Loop %loop: max backedge-taken count is -1
+; CHECK: Loop %loop: max backedge-taken count is -2
 define void @nsw_startx(i4 %n, i4 %x) {
 entry:
   %s = icmp sgt i4 %n, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 1
   %t = icmp slt i4 %i.next, %n
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @nsw_startx_step2
 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x)<nsw> smax %n)) /u 2)
-; CHECK: Loop %loop: max backedge-taken count is 7
+; CHECK: Loop %loop: max backedge-taken count is 6
 define void @nsw_startx_step2(i4 %n, i4 %x) {
 entry:
   %s = icmp sgt i4 %n, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 2
   %t = icmp slt i4 %i.next, %n
loop:
   %t = icmp slt i4 %i.next, %m
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @even_nsw_startx
 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x)<nsw> smax (2 * %n)))
-; CHECK: Loop %loop: max backedge-taken count is -2
+; CHECK: Loop %loop: max backedge-taken count is -3
 define void @even_nsw_startx(i4 %n, i4 %x) {
 entry:
   %m = shl i4 %n, 1
   %s = icmp sgt i4 %m, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 1
   %t = icmp slt i4 %i.next, %m
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @even_nsw_startx_step2
 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x)<nsw> smax (2 * %n))) /u 2)
-; CHECK: Loop %loop: max backedge-taken count is 7
+; CHECK: Loop %loop: max backedge-taken count is 6
 define void @even_nsw_startx_step2(i4 %n, i4 %x) {
 entry:
   %m = shl i4 %n, 1
   %s = icmp sgt i4 %m, 0
   br i1 %s, label %loop, label %exit
 loop:
   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
   %i.next = add nsw i4 %i, 2
   %t = icmp slt i4 %i.next, %m
   br i1 %t, label %loop, label %exit
 exit:
   ret void
 }