Page MenuHomePhabricator

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

Authored by shchenz on Jul 17 2019, 7:31 AM.

Details

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.

This patch is to improve this issue. This patch is based on patch https://reviews.llvm.org/D64868

Diff Detail

Event Timeline

shchenz created this revision.Jul 17 2019, 7:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 17 2019, 7:31 AM
reames requested changes to this revision.Jul 17 2019, 9:16 AM
reames added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
5570–5581

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

5572

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

This revision now requires changes to proceed.Jul 17 2019, 9:16 AM
nikic added inline comments.Jul 17 2019, 9:57 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5570–5581

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

reames added inline comments.Jul 17 2019, 10:06 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5570–5581

That looks entirely reasonable. Land that, and rebase?

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

shchenz updated this revision to Diff 211507.Jul 24 2019, 8:04 AM

address @reames comments

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

reames requested changes to this revision.Aug 6 2019, 1:26 PM
reames added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
5571

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

Why not allow both?

834

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

This revision now requires changes to proceed.Aug 6 2019, 1:26 PM
shchenz updated this revision to Diff 214575.Aug 11 2019, 10:40 PM
shchenz marked an inline comment as done.

address @reames comments

shchenz marked 2 inline comments as done.Aug 12 2019, 12:23 AM
shchenz added inline comments.
llvm/lib/IR/ConstantRange.cpp
829

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.

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

reames accepted this revision.Mon, Aug 19, 1:58 PM

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp
5575

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

This revision is now accepted and ready to land.Mon, Aug 19, 1:58 PM
nikic requested changes to this revision.Mon, Aug 19, 3:10 PM

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).

This revision now requires changes to proceed.Mon, Aug 19, 3:10 PM
shchenz planned changes to this revision.Tue, Aug 20, 6:22 PM

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 updated this revision to Diff 218590.Tue, Sep 3, 10:15 PM

new implementation not based on makeGuaranteedNoWrapRegion

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

nikic added a comment.Sat, Sep 7, 4:23 AM

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

llvm/lib/IR/ConstantRange.cpp
853

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

862

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 updated this revision to Diff 219287.Sun, Sep 8, 8:09 PM

address @nikic comments

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.