Page MenuHomePhabricator

[ConstantRange / SCEV] generalize overflow checking for ConstantRanges
Needs RevisionPublic

Authored by regehr on May 26 2016, 2:22 AM.

Details

Summary

This patch eliminates makeGuaranteedNoWrapRegion(), which had a single use case: detecting, in SCEV, the potential for overflow when pairs of ConstantRanges are added. The replacement is mayOverflow(), a new ConstantRange method that is less code, easier to use (because it does the whole job of detecting overflow, not just part of it), and more general (also handles subtract and multiply).

I ran the two implementations of overflow checking (the new one and the one based on makeGuaranteedNoWrapRegion()) in parallel for a while and they always return the same answers while performing interesting tasks such as bootstrapping LLVM.

This patch is a prelude to LVI-based integer overflow check removal.

Diff Detail

Event Timeline

regehr updated this revision to Diff 58578.May 26 2016, 2:22 AM
regehr retitled this revision from to [ConstantRange / SCEV] generalize overflow checking for ConstantRanges.
regehr updated this object.
regehr added reviewers: sanjoy, reames.
sanjoy requested changes to this revision.May 29 2016, 4:17 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
include/llvm/IR/ConstantRange.h
99

Why not have this be a member function?

lib/IR/ConstantRange.cpp
181

One problem with doing this is that we'll incur three malloc s and free s when Width is 64. My guess that this is probably fine, but can you please do a sanity test that this does not observably regress compile time?

198

I don't think we should handle both overflow intrinsics and normal
integer operations here, since it isn't clear (for instance) that what
it means to have sadd_with_overflow with Signed to false. It
feels like we have more degrees of freedom than it makes sense to
have.

There are two alternate design points, both of which I like better
than what is here currently:

  • Given that they're not used yet, remove these for now; if we need them later then we can add helper function around mayOverflow that dispatches to, e.g. Instruction::Add and Signed = true for sadd_with_overflow.
  • Remove the Signed parameter entirely, and only accept the *_with_overflow values as opcodes, and deduce the signedness of the check from the opcode.
This revision now requires changes to proceed.May 29 2016, 4:17 PM
regehr added inline comments.May 30 2016, 11:51 PM
lib/IR/ConstantRange.cpp
181

Ugh... this change causes about a 1% overall slowdown, I didn't see that coming. So I'll revert the part of this patch that makes SCEV use mayOverflow().

Is it OK to keep mayOverflow() and use it from the new overflow removal code? People will only pay the extra cost when building sanitized code and in that case a slightly slower overflow check should not be a big deal.

sanjoy added a subscriber: pcc.Jun 2 2016, 3:48 PM
sanjoy added inline comments.
lib/IR/ConstantRange.cpp
181

Is it OK to keep mayOverflow() and use it from the new overflow removal code? People will only pay the extra cost when building sanitized code and in that case a slightly slower overflow check should not be a big deal.

I'd say that's fine for now, but do take a look at the "Use Rvalue refs in APInt" thread from @pcc to check if you can use move constructors to make the extensions less expensive.

This seems to be stuck. There were many changes to ConstantRange, so a rebase is needed.
I wonder if the slow-down is still there?

nikic added a comment.Aug 31 2019, 6:45 AM

ConstantRange has (efficient) overflow detection for most cases now, but signedMulMayOverflow() is still missing. We could add that and then replace makeGNWR uses.