This is an archive of the discontinued LLVM Phabricator instance.

[ConstantRange] makeGuaranteedNoWrapRegion(): `shl` support
ClosedPublic

Authored by lebedev.ri on Oct 19 2019, 1:19 PM.

Details

Summary

If all the shifts amount are already poison-producing,
then we can add more poison-producing flags ontop:
https://rise4fun.com/Alive/Ocwi

Otherwise, we should only consider the possible range of shift amts that don't result in poison.

For unsigned range not not overflow, we must not shift out any set bits,
and the actual limit for x can be computed by backtransforming
the maximal value we could ever get out of the shl - -1 through
lshr. If the x is any larger than that then it will overflow.

Likewise for signed range, but just in signed domain..

This is based on the general idea outlined by @nikic in https://reviews.llvm.org/D68672#1714990

Diff Detail

Event Timeline

lebedev.ri created this revision.Oct 19 2019, 1:19 PM
nikic added inline comments.Oct 19 2019, 1:54 PM
llvm/lib/IR/ConstantRange.cpp
276

While an empty set here is conservatively correct, I believe that the more precise return value would be the range containing only zero [0, 1). The shift amount is < the bitwidth by assumption (otherwise the result is poison), and [0, 1) is the result for the worst-case assumption of shift amount = bitwidth - 1.

Even more precise would be to intersect the incoming range with [0, BitWidth), which may differ non-trivially from this approach for wrapped ranges. E.g. if you have a signed range [INT_MIN, 5), the UMax will be UINT_MAX, but the intersection [INT_MIN, 5) /\ [0, 32) is [0, 5) and the UMax will be 4, resulting in a much larger guaranteed nowrap region.

lebedev.ri marked an inline comment as done.Oct 19 2019, 2:37 PM
lebedev.ri added inline comments.
llvm/lib/IR/ConstantRange.cpp
276

The shift amount is < the bitwidth by assumption (otherwise the result is poison)

Ah, good point.

But by that logic, then for signed the range should be [-1, 1), correct?
0 << 7 == 0 - doesn't overflow in both signed and unsigned domains,
while -1 << 7 == -128 does not overflow in signed domain - still the same sign.

lebedev.ri marked an inline comment as done.Oct 19 2019, 3:15 PM
lebedev.ri added inline comments.
llvm/lib/IR/ConstantRange.cpp
276

Actually no, wait, if we are assuming that we will at worst get bitwidth-1 shift amount,
then we should produce [0, 2) for unsigned or [-1, 1) for signed.
Or i'm missing the point.

nikic added inline comments.Oct 19 2019, 3:26 PM
llvm/lib/IR/ConstantRange.cpp
276

I guess it should be [0, 2) unsigned and [-1, 1) signed then, as 1 << 7 does not overflow unsigned either.

Rather than special-casing this, we could just take ShAmtUMax = Other.getUnsignedMax().umin(BitWidth-1) and reuse the general code.

Or do

ConstantRange ShAmt = Other.intersect(ConstantRange(
    APInt(BitWidth, 0), APInt(BitWidth, BitWidth)));`
if (ShAmt.isEmptySet())
  return getEmpty(); // or getFull()?
APInt ShAmtUMax = ShAmt.getUnsignedMax();

for the fully precise variant.

lebedev.ri marked 2 inline comments as done.

Clamp max shift amount to bitwidth-1

llvm/lib/IR/ConstantRange.cpp
276

I guess it should be [0, 2) unsigned and [-1, 1) signed then, as 1 << 7 does not overflow unsigned either.
Rather than special-casing this, we could just take ShAmtUMax = Other.getUnsignedMax().umin(BitWidth-1) and reuse the general code.

Indeed, which is why i was having trouble grasping why it would be [0, 1) for shamt=bitwidth all of a sudden.

Didn't think about intersection yet.

lebedev.ri marked an inline comment as done.
lebedev.ri edited the summary of this revision. (Show Details)

Improve tests and go full on intersectWith().

nikic added inline comments.Oct 20 2019, 9:28 AM
llvm/unittests/IR/ConstantRangeTest.cpp
1601–1602

So, I wrote this test, but I can't say I understand why it does what it does... Enumerating over all ranges CR1 seems to be entirely unnecessary, it would be sufficient to just iterate over all N1 in the full range to get the same coverage, and save us a whole lot of unnecessary iterations.

That should allow us to run this test with a larger bit width, in which case you could just drop the MakeGuaranteedNoWrapRegionShl(Un)signedSingleValue tests entirely, as they are special cases of what is checked here (just with a larger bit width).

1858

Why is this test structurally different from the previous one?

lebedev.ri marked 2 inline comments as done.

Tune some tests

llvm/unittests/IR/ConstantRangeTest.cpp
1858

This was carbon copy from 4 tests above; TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange)
in this case; let's streamline..

nikic added inline comments.Oct 20 2019, 12:03 PM
llvm/unittests/IR/ConstantRangeTest.cpp
1601–1602

As it's unrelated to this revision, I've made this change in rL375369. Now testing 5 bits, which is good enough I think.

lebedev.ri marked 2 inline comments as done.

Rebased

nikic accepted this revision.Oct 20 2019, 12:12 PM

LGTM

This revision is now accepted and ready to land.Oct 20 2019, 12:12 PM

LGTM

Thank you for the review.
Will post CVP patch later, needs tests, but the effect is similar to the mul patch (D69203).

This revision was automatically updated to reflect the committed changes.