[CVP] Remove some {s|u}add.with.overflow checks.
ClosedPublic

Authored by jgalenson on Oct 31 2017, 4:35 PM.

Details

Summary

This adds logic to CVP to remove some overflow checks. It uses LVI to remove operations with at least one constant. Specifically, this can remove many overflow intrinsics immediately following an overflow check in the source code, such as:

if (x < INT_MAX)

... x + 1 ...

Diff Detail

Repository
rL LLVM
jgalenson created this revision.Oct 31 2017, 4:35 PM
pirama added a subscriber: pirama.Nov 6 2017, 3:14 PM
sanjoy added inline comments.Nov 6 2017, 5:17 PM
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
350 ↗(On Diff #121768)

This case should be getting constant folded. If it isn't, that's an InstCombine bug. Once you remove this, you can just directly have the second switch.

355 ↗(On Diff #121768)

We should be canonicalizing commutative ops so that if there is a constant operand it is the RHS (if not, that's again an instcombine bugs).

376 ↗(On Diff #121768)

Can you avoid doing this stuff by hand by using the LazyValueInfo::getConstantRange and the ConstantRange::makeGuaranteedNoWrapRegion APIs?

fhahn added a subscriber: fhahn.Nov 7 2017, 1:40 AM
jgalenson updated this revision to Diff 121966.Nov 7 2017, 1:12 PM

Thanks for the comments. As you suggested, I removed the unnecessary checks.

The new API is indeed cleaner, but it only works for addition. Modifying it to support other operations might be useful, bit I figured that could be a separate commit if necessary.

sanjoy requested changes to this revision.Nov 7 2017, 6:40 PM
sanjoy added inline comments.
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
329 ↗(On Diff #121966)

I'd call this willNotOverflow instead, since that's what this is computing.

382 ↗(On Diff #121966)

I'd avoid adding this kind of logic here. Instead I think the right factoring is to start off by doing what ConstantRange lets us do today (i.e. sadd and uadd) and then improving ConstantRange to handle the subtraction (and other) cases you're interested in. Putting this logic in ConstantRange will make it more likely that the code is re-used (besides making it easier to test).

This revision now requires changes to proceed.Nov 7 2017, 6:40 PM
jgalenson updated this revision to Diff 122110.Nov 8 2017, 9:40 AM

I've done the rename, although I'll note that I slightly prefer the old name since it makes it obvious that the function only applies to overflow intrinsics, not any intrinsic.

As for changing ConstantRange, as I said before, I agree that should be done, but it seems to me like it should be done in a separate commit. Once we have that, we should add a processSub (like processAdd), and we should add multiplication and division in all the places, but keeping focused commits seems like a better strategy to me.

sanjoy added a comment.Nov 8 2017, 9:46 AM

I've done the rename, although I'll note that I slightly prefer the old name since it makes it obvious that the function only applies to overflow intrinsics, not any intrinsic.

If you think the previous name was better I'm ok with that.

As for changing ConstantRange, as I said before, I agree that should be done, but it seems to me like it should be done in a separate commit. Once we have that, we should add a processSub (like processAdd), and we should add multiplication and division in all the places, but keeping focused commits seems like a better strategy to me.

I'm not suggesting you change ConstantRange in this commit (that indeed is not a great idea). I'm suggesting that instead of adding a bunch of logic here only to move it to ConstantRange in a later commit, how about:

  • Commit0: Only process uadd and sadd in CVP with ConstantRange::makeGuaranteedNoWrapRegion.
  • Commit1: Teach makeGuaranteedNoWrapRegion about usub and ssub
  • Commit2: Use Commit1 to process ssub and usub in CVP
  • ...

If anything, the sequence above will make the commits even more focussed. I hope I made sense.

If you think the previous name was better I'm ok with that.

I don't have a strong preference, so I'll keep yours.

I'm not suggesting you change ConstantRange in this commit (that indeed is not a great idea). I'm suggesting that instead of adding a bunch of logic here only to move it to ConstantRange in a later commit, how about:

  • Commit0: Only process uadd and sadd in CVP with ConstantRange::makeGuaranteedNoWrapRegion.
  • Commit1: Teach makeGuaranteedNoWrapRegion about usub and ssub
  • Commit2: Use Commit1 to process ssub and usub in CVP
  • ...

    If anything, the sequence above will make the commits even more focussed. I hope I made sense.

Ah, sorry, I misunderstood you. Looks like we agree. :) I'll do that.

By the way, I would also like to get this code to handle non-constant arithmetic for cases such as:

if (x >= y)

.. x - y ...

But that's even harder, so I'll leave it for later.

jgalenson updated this revision to Diff 122112.Nov 8 2017, 10:18 AM
jgalenson retitled this revision from [CVP] Remove some {s|u}{add|sub}.with.overflow checks. to [CVP] Remove some {s|u}add.with.overflow checks..
sanjoy requested changes to this revision.Nov 8 2017, 10:15 PM
sanjoy added inline comments.
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
333 ↗(On Diff #122112)

I don't think you need this either -- you can just directly go to the switch below.

337 ↗(On Diff #122112)

How about calling this NoWrapOnAddition ?

351 ↗(On Diff #122112)

You don't need these anymore.

364 ↗(On Diff #122112)

process is too vague -- how about eraseOverflowIntrinsic?

test/Transforms/CorrelatedValuePropagation/overflows.ll
183 ↗(On Diff #122112)

Typical idiom is to use CHECK-LABEL for the function name, as:

; CHECK-LABEL: @unsigned_add_r1(
; CHECK-NOT: ...
This revision now requires changes to proceed.Nov 8 2017, 10:15 PM
jgalenson added inline comments.Nov 9 2017, 9:19 AM
lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
364 ↗(On Diff #122112)

I actually think process is better here because it mirrors all the other functions in this file (processCallSite, processSRem, etc).

jgalenson updated this revision to Diff 122257.Nov 9 2017, 9:29 AM

I suppose I could pull this lambda out into a static function....

jgalenson updated this revision to Diff 122340.Nov 9 2017, 2:59 PM

Added a statistic.

sanjoy accepted this revision.Nov 9 2017, 4:10 PM

LGTM

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
359 ↗(On Diff #122340)

Super-minor nit: s/Illegal/Unexpected/

This revision is now accepted and ready to land.Nov 9 2017, 4:10 PM

Thanks! Could you commit this for me?

I'll make that nit change in the follow-up commit that handles sub.

This revision was automatically updated to reflect the committed changes.