Page MenuHomePhabricator

[ConstantRange] Add `mulWithNoWrap()` method
AbandonedPublic

Authored by lebedev.ri on Nov 9 2019, 5:47 AM.

Details

Summary

I'm not fully happy about this.

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

However mulWithNoWrap does pass conservatively correctness test.
Though it is less constrained than the brute-force approach.
I don't think it needs a different testing approach though?

Here we don't get EXPECT_EQ(CR.isEmptySet(), AllOverflow);
postcondition for free in any of the cases, so it needs to be
manually enforced. I wonder, shouldn't we be using
unsigned*?MayOverflow() == OverflowResult::AlwaysOverflowsHigh*
for that, everywhere? Should be more readable than manual inlined checks..

Diff Detail

Event Timeline

lebedev.ri created this revision.Nov 9 2019, 5:47 AM
nikic added inline comments.Nov 21 2019, 3:19 AM
llvm/lib/IR/ConstantRange.cpp
1027

Why do these fetch the unsigned min/max for the signed multiplication case?

1046

Why do we need to specially handle the nuw+nsw combination here?

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

Fix OBO::NoSignedWrap modelling - what we are trying to check there is
whether multiplication of smallest values of two ranges do/don't multiply.
So we need to actually see what values are the smallest in this range.
And by smallest we mean closest to 0.

llvm/lib/IR/ConstantRange.cpp
1027

Right, this makes little sense.
I just ad-hoc-ked it because that is what worked, and it was likely wrong from precision standpoint.
I think this is more obvious now? (Did i horrendously over-engineer this and overlooking existing infra?)

1046

Even after fixing OBO::NoSignedWrap check this remains.
Here in OBO::NoUnsignedWrap we did check that
getUnsignedMin() * Other.getUnsignedMin()
does not exhibit *unsigned* overflow,
but we did not do any such check in OBO::NoSignedWrap.

There, even if UnsignedMin happens to be one of the values closest to 0,
since we check that all values overflow, unless said range only contains
a single UnsignedMin, we wouldn't discard such range as always-overflowing.

So i think this is correct.
At least until precision tests say otherwise.

lebedev.ri marked an inline comment as done.Nov 22 2019, 1:12 AM

Let me know if my explanation makes sense.

llvm/lib/IR/ConstantRange.cpp
1046

Example:
Bits 4 CR1 [2,0) CR2 [4,0) CR [-8,0)

This doesn't always overflow in unsigned domain - i4 2 * i4 4 == i4 -8 (signed overflow)
This doesn't always overflow in signed domain - both ranges contain -1 value - i4 -1 * i4 -1 == i4 1 (unsigned overflow)

But there is no such value pair that exhibits both no signed overflow and no unsigned overflow at the same time.

Alive proof: https://rise4fun.com/Alive/1aK

nikic added a comment.Nov 22 2019, 5:03 AM

@lebedev.ri Haven't looked too closely at the implementation yet, but my general feeling is that trying this hard to be precise about the empty set case is a bad tradeoff in terms of utility vs compilation time. Note in particular that a) we don't actually make use of empty sets in CVP (I believe they map to overdefined rather than undefined) and b) all the remaining calculations are only precise for non-wrapping sets (and the tests only check that).

I think it would make more sense to move the AllOverflow check in the to !isWrappedSet branches in the tests, which should make it possible to use a more naive, but for practical purposes probably equally good, implementation.

Streamline getClosestToZero(), reshuffle mulWithNoWrap() to do cheap checks first.

@lebedev.ri Haven't looked too closely at the implementation yet, but
my general feeling is that trying this hard to be precise about the
empty set case is a bad tradeoff in terms of utility vs compilation time.

Note in particular that a) we don't actually make use of empty sets in CVP
(I believe they map to overdefined rather than undefined)
and b) all the remaining calculations are only precise for non-wrapping sets
(and the tests only check that).

Aha, indeed. https://godbolt.org/z/N3KggA Interesting.

To not lose all that "mul is guaranteed to wrap" logic,
should i move it into signedMulMayOverflow() instead of just completely dropping?

I think it would make more sense to move the AllOverflow check in the
to !isWrappedSet branches in the tests, which should make it possible
to use a more naive, but for practical purposes probably equally good, implementation.

Bump. Posted https://lists.llvm.org/pipermail/llvm-dev/2019-December/137327.html

@lebedev.ri Haven't looked too closely at the implementation yet, but my general feeling is that trying this hard to be precise about the empty set case is a bad tradeoff in terms of utility vs compilation time. Note in particular that a) we don't actually make use of empty sets in CVP (I believe they map to overdefined rather than undefined) and b) all the remaining calculations are only precise for non-wrapping sets (and the tests only check that).

I think it would make more sense to move the AllOverflow check in the to !isWrappedSet branches in the tests, which should make it possible to use a more naive, but for practical purposes probably equally good, implementation.

Can anyone else familiar with LVI (and other ConstantRange users) chime in
and comment whether we indeed should not be doing such modelling?

lebedev.ri updated this revision to Diff 232107.Dec 4 2019, 6:13 AM
lebedev.ri added a reviewer: sanjoy.

Split ConstantRange::getClosestToZero() into it's own review.
Added ConstantRange::shlWithNoWrap() support in a follow-up patch.

lebedev.ri updated this revision to Diff 232119.Dec 4 2019, 6:46 AM

Rebased, NFC.

nikic added a comment.Dec 5 2019, 9:36 AM

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

For my own sanity: This doesn't mean that the multiply() implementation is incorrect, just that this testing function is a bit overly aggressive in CorrectnessOnly mode. It expects the result to be a superset of the minimal unsigned bounding range. We might want to change the function to actually only check correctness via EXPECT_TRUE(CR.contains(N)).

Looking a bit into what causes the failures for mulWithNoWrap when testing not only correctness for the unsigned case. I think there are two main causes:

  • Something like [0, 1] * [-8, -5] produces [-8, 0], while the testing code expects [0, -5]. This actual result is consistent with the "smallest range" preferred range mode, so this is just a testing deficiency.
  • Something like [0, 2] * [-8, -5] produces full-set, while the testing code expects [0, -5]. The reason here is that the result can be in the ranges [0, 0], [-8, -5] or [2 * -8, 2 * -5], where the last range is unsigned (and signed) wrapping, so the result could actually be the same as for the previous case. However, we don't recognize that the 2 * [-8, -5] case is fully excluded.

So I guess it would be pretty hard to make this work non-approximately...

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

For my own sanity: This doesn't mean that the multiply() implementation is incorrect, just that this testing function is a bit overly aggressive in CorrectnessOnly mode. It expects the result to be a superset of the minimal unsigned bounding range.

Sure, of course, otherwise the EXPECT_TRUE(CR.contains(N)); would complain.

We might want to change the function to actually only check correctness via EXPECT_TRUE(CR.contains(N)).

Note that we already do that check, otherwise we wouldn't know that the result is at least conservatively correct.

Looking a bit into what causes the failures for mulWithNoWrap when testing not only correctness for the unsigned case. I think there are two main causes:

  • Something like [0, 1] * [-8, -5] produces [-8, 0], while the testing code expects [0, -5]. This actual result is consistent with the "smallest range" preferred range mode, so this is just a testing deficiency.
  • Something like [0, 2] * [-8, -5] produces full-set, while the testing code expects [0, -5]. The reason here is that the result can be in the ranges [0, 0], [-8, -5] or [2 * -8, 2 * -5], where the last range is unsigned (and signed) wrapping, so the result could actually be the same as for the previous case. However, we don't recognize that the 2 * [-8, -5] case is fully excluded.

    So I guess it would be pretty hard to make this work non-approximately...

Baseline ConstantRange::mul() does not have an exhaustive test,
and if i add one (TestUnsignedBinOpExhaustive()+/*CorrectnessOnly=*/true),
it doesn't pass.

For my own sanity: This doesn't mean that the multiply() implementation is incorrect,
just that this testing function is a bit overly aggressive in CorrectnessOnly mode.
It expects the result to be a superset of the minimal unsigned bounding range.

Sure, of course, otherwise the EXPECT_TRUE(CR.contains(N)); would complain.

We might want to change the function to actually only check correctness via EXPECT_TRUE(CR.contains(N)).

Note that we already do that check, otherwise we wouldn't know that the result is at least conservatively correct.

...

So I guess it would be pretty hard to make this work non-approximately...

As i have previously said, what's *really* missing is QoI testing:
just measure how constrained is the ConstantRange-returned result,
as compared to the ideal result, with <1 being not conservatively correct,
=1 ideal, and >1 non-optimal. That can totally replace
the existing EXPECT_EQ(Exact, CR); check,
and be that much more informative.

@reames @nikic But in the end, any suggestions on how to get *these* patches moving?
The replies to the maillist post are non-conclusive.
Anyone else have an opinion?

But in the end, any suggestions on how to get *these* patches moving?

My opinion here hasn't really changed ... I still think that if we want to handle wrapping ranges more accurately, we need to do so in a more principled fashion that does not special case empty sets only. Specifically I would expect this to entail:

  • Changing the getClosestToZero() helper to instead return two ranges, the positive and the negative one.
  • Changing the signed part of the multiply() code to use those split ranges, instead of simple smin/smax.
  • Possibly better, make the implementation of mulWithNoWrap() proper perform operations in the double bitwidth and then intersect with the legal part of the range. That way the empty set result should come about naturally as well.

It may well make sense to do this, but if we want to land something here more quickly, I would recommend:

  • Remove the EXPECT_EQ(CR.isEmptySet(), AllOverflow) assertions and the code necessary to satisfy them. We already check that empty sets are correctly computed for non-wrapping sets in a separate assertion.
  • Add some hand-written test coverage for mulWithNoWrap(). As the exhaustive tests are correctness-only, we should also check that we actually compute some reasonable ranges for a couple of inputs.
lebedev.ri abandoned this revision.Sat, Jan 25, 5:34 AM