Page MenuHomePhabricator

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

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.Tue, Aug 6, 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.Tue, Aug 6, 1:26 PM
shchenz updated this revision to Diff 214575.Sun, Aug 11, 10:40 PM
shchenz marked an inline comment as done.

address @reames comments

shchenz marked 2 inline comments as done.Mon, Aug 12, 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.