[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

5581–5588

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

5583

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

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

5581–5588

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

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

5581–5588

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

5582

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

5586

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

5582

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

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

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

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

llvm/include/llvm/IR/Operator.h

 };
 
 /// Utility class for integer operators which may exhibit overflow - Add, Sub,
 /// Mul, and Shl. It does not include SDiv, despite that operator having the
 /// potential for overflow.
 class OverflowingBinaryOperator : public Operator {
 public:
   enum {
+    AnyWrap        = 0,
     NoUnsignedWrap = (1 << 0),
     NoSignedWrap   = (1 << 1)
   };
 
 private:
   friend class Instruction;
   friend class ConstantExpr;
 

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getRangeRef(const SCEV *S,
   if (I != Cache.end())
     return I->second;
 
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
     return setRange(C, SignHint, ConstantRange(C->getAPInt()));
 
   unsigned BitWidth = getTypeSizeInBits(S->getType());
   ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true);
+  using OBO = OverflowingBinaryOperator;
 
   // 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())
+      WrapType |= OBO::NoSignedWrap;
+    if (Add->hasNoUnsignedWrap())
+      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, RangeType);
     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));

llvm/test/Analysis/ScalarEvolution/range_nw_flag.ll

 ; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
 
 ; copied from flags-from-poison.ll
 ; CHECK-LABEL: @test-add-nuw
-; CHECK: -->  {(1 + %offset)<nuw>,+,1}<nuw><%loop> U: full-set S: full-set
+; CHECK: -->  {(1 + %offset)<nuw>,+,1}<nuw><%loop> U: [1,0) S: [1,0)
 define void @test-add-nuw(float* %input, i32 %offset, i32 %numIterations) {
 entry:
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
   %nexti = add nuw i32 %i, 1
   %index32 = add nuw i32 %nexti, %offset
   %ptr = getelementptr inbounds float, float* %input, i32 %index32

llvm/test/Transforms/IRCE/ranges_of_different_types.ll

 ; CHECK-LABEL: test_02(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add nuw nsw i32 %len, -2147483647
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[LEN_MINUS_SMAX]], -13
 ; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[LEN_MINUS_SMAX]], i32 -13
 ; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 %len, [[SMAX1]]
 ; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
-; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 101
-; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SMAX2]], 0
-; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SMAX2]], i32 0
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         loop.preloop:
 ; CHECK-NEXT:      %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 0, %loop.preloop.preheader ]
 ; CHECK-NEXT:      %idx.next.preloop = add i32 %idx.preloop, 1
 ; CHECK-NEXT:      %idx.offset.preloop = sub i32 %idx.preloop, 13
 ; CHECK-NEXT:      %abc.preloop = icmp ult i32 %idx.offset.preloop, %len
 ; CHECK-NEXT:      br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
 ; CHECK:         in.bounds.preloop:

 ; CHECK-LABEL: test_06(
 ; CHECK:         entry:
 ; CHECK-NEXT:      %len = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:      [[LEN_MINUS_SMAX:%[^ ]+]] = add nuw nsw i32 %len, -2147483647
 ; CHECK-NEXT:      [[CMP1:%[^ ]+]] = icmp sgt i32 [[LEN_MINUS_SMAX]], -13
 ; CHECK-NEXT:      [[SMAX1:%[^ ]+]] = select i1 [[CMP1]], i32 [[LEN_MINUS_SMAX]], i32 -13
 ; CHECK-NEXT:      [[SUB1:%[^ ]+]] = sub i32 %len, [[SMAX1]]
 ; CHECK-NEXT:      [[CMP2:%[^ ]+]] = icmp slt i32 [[SUB1]], 101
-; CHECK-NEXT:      [[SMAX2:%[^ ]+]] = select i1 [[CMP2]], i32 [[SUB1]], i32 101
-; CHECK-NEXT:      [[CMP3:%[^ ]+]] = icmp sgt i32 [[SMAX2]], 0
-; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP3]], i32 [[SMAX2]], i32 0
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP2]], i32 [[SUB1]], i32 101
 ; CHECK-NEXT:      br i1 true, label %loop.preloop.preheader
 ; CHECK:         in.bounds.preloop:
 ; CHECK-NEXT:      %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
 ; CHECK-NEXT:      store i32 0, i32* %addr.preloop
 ; CHECK-NEXT:      %next.preloop = icmp slt i32 %idx.next.preloop, 101
 ; CHECK-NEXT:      [[PRELOOP_COND:%[^ ]+]] = icmp slt i32 %idx.next.preloop, 13
 ; CHECK-NEXT:      br i1 [[PRELOOP_COND]], label %loop.preloop, label %preloop.exit.selector
 ; CHECK:         postloop: