[SCEV] See through op.with.overflow intrinsics
ClosedPublic

Authored by sanjoy on Apr 1 2016, 12:06 AM.

Details

Summary

This change teaches SCEV to see reduce `(extractvalue
0 (op.with.overflow X Y)) into op X Y` (with a no-wrap tag if
possible).

Diff Detail

Repository
rL LLVM
sanjoy retitled this revision from to [SCEV] See through op.with.overflow intrinsics.Apr 1 2016, 12:06 AM
sanjoy updated this object.
sanjoy added reviewers: atrick, regehr.
sanjoy added a subscriber: llvm-commits.
regehr added a comment.Apr 7 2016, 5:23 AM

Sanjoy do you mind exposing IsResultNoOverflow() in such a way that it can be used by other passes? I was going to implement this myself (it's what I was asking about on twitter last night) but of course would rather just use yours.

regehr added inline comments.Apr 7 2016, 6:11 AM
lib/Analysis/ScalarEvolution.cpp
3841 ↗(On Diff #52330)

I'm a little confused about this loop-- since we're looking for one branch, why do we want the loop here instead of just returning false if the CallInst has more than one user?

sanjoy added inline comments.Apr 7 2016, 9:35 AM
lib/Analysis/ScalarEvolution.cpp
3841 ↗(On Diff #52330)

We're also accumulating the result projections into AddVals (which in retrospect should be called something else, since they're not just additions -- I'll fix that).

suyog added a subscriber: suyog.Apr 8 2016, 12:08 AM
sanjoy updated this revision to Diff 53157.Apr 9 2016, 1:52 PM

Address review:

  • Export isOverflowIntrinsicNoWrap to ValueTracking
  • Generalize the logic a bit and add more tests to demonstrate

I couldn't find a better name than isOverflowIntrinsicNoWrap that
isn't also terribly verbose. Suggestions welcome!

atrick accepted this revision.Apr 9 2016, 8:39 PM

This looks great. It seems like it will work well for createAddRecFromPHI.

I think we're still missing intrinsic support in getNoWrapFlagsFromUB.

This revision is now accepted and ready to land.Apr 9 2016, 8:39 PM
regehr accepted this revision.Apr 10 2016, 1:15 AM

Looks great.

include/llvm/Analysis/ValueTracking.h
332 ↗(On Diff #53157)

would something isOverflowGuard() work better?

sanjoy added inline comments.Apr 10 2016, 3:51 PM
include/llvm/Analysis/ValueTracking.h
332 ↗(On Diff #53157)

I'd say that would be misleading since we're not checking if the arithmetic operation can overflow, but that the "arithmetic result" projection of the intrinsic can be treated as no-wrap. So, as an example, the routine can (and will, in most cases) return true for an overflow intrinsic for which the "arithmetic result" projection is unused.

This revision was automatically updated to reflect the committed changes.