Page MenuHomePhabricator

[LAA] Try to prove non-wrapping of pointers if SCEV cannot
ClosedPublic

Authored by anemet on Jun 15 2015, 10:34 PM.

Details

Summary

Scalar evolution does not propagate the non-wrapping flags to values
that are derived from a non-wrapping induction variable because
the non-wrapping property could be flow-sensitive.

This change is a first attempt to establish the non-wrapping property in
some simple cases. The main idea is to look through the operations
defining the pointer. As long as we arrive to a non-wrapping AddRec via
a small chain of non-wrapping instruction, the pointer should not wrap
either.

I believe that this essentially is what Andy described in
http://article.gmane.org/gmane.comp.compilers.llvm.cvs/220731 as the way
forward.

Diff Detail

Repository
rL LLVM

Event Timeline

anemet updated this revision to Diff 27748.Jun 15 2015, 10:34 PM
anemet retitled this revision from to [LAA] Try to prove non-wrapping of pointers if SCEV cannot.
anemet updated this object.
anemet edited the test plan for this revision. (Show Details)
anemet added reviewers: aschwaighofer, nadav, atrick, sanjoy.
anemet added a subscriber: Unknown Object (MLST).
sanjoy requested changes to this revision.Jun 15 2015, 11:07 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Analysis/LoopAccessAnalysis.cpp
509 ↗(On Diff #27748)

I'm not clear on how LAA uses this property, but I think this function should mention what kind of no-wrap (signed or unsigned) behavior it is trying to prove. IOW, Ptr is supposed to be monotonically increasing/decreasing in the signed or unsigned sense?

540 ↗(On Diff #27748)

What if OBO is nuw (and not nsw) and OpAR is nsw (and not nuw)? Or vice-versa?

This revision now requires changes to proceed.Jun 15 2015, 11:07 PM
anemet added inline comments.Jun 16 2015, 3:30 PM
lib/Analysis/LoopAccessAnalysis.cpp
509 ↗(On Diff #27748)

It's unsigned. Pointers are unsigned in LLVM IR as mentioned in the GEP FAQ. I'll add a comment.

540 ↗(On Diff #27748)

Yeah, this certainly required more thinking on my behalf, thanks for pressing it.

So to document why this was wrong, let's take this counterexample:

Consider the AddRec {0,+,100} <nuw> in i8. The first three iterations of that yields: 0, 100, 200.

Putting this through a *signed* add of 3, the input is now interpreted as signed: 0, 100, -56.

No signed overflow on the result (3, 103, -53), yet the result is wrapped.

Similarly, we can't take <nuw>-only for index. Index is interpreted as signed. With the above (i8) {0,+,100} example we'd get a wrapping range even though it may be inbounds for the array.

Let me know if you or others disagree or have further comments. Otherwise I'll update the patch accordingly.

sanjoy added inline comments.Jun 17 2015, 4:08 PM
lib/Analysis/LoopAccessAnalysis.cpp
540 ↗(On Diff #27748)

I think you're right w.r.t. the (no-)wrapping logic. I have not worked on LAA so I cannot comment on how isNoWrapAddRec is used.

anemet updated this revision to Diff 27890.Jun 17 2015, 4:22 PM
anemet edited edge metadata.

Updated to only check NSW when analyzing the (signed) index.

Also added a FIXME for what I think is a pre-existing problem with the code.

atrick accepted this revision.Jun 25 2015, 9:57 PM
atrick edited edge metadata.

LGTM. Sorry for the delay.

It's not clear to me how comprehensive this analysis is, but at least it covers some important cases.

lib/Analysis/LoopAccessAnalysis.cpp
511 ↗(On Diff #27890)

I agree with you here. If NSW/NW are valid conditions, it's not obvious to me and the original author needs to explain it.

This revision was automatically updated to reflect the committed changes.

Thanks for confirming and the review, Andy!