Page MenuHomePhabricator

Replace the implementation of ConstantRange::binaryAnd.
Needs ReviewPublic

Authored by nicholas on Jun 5 2016, 8:29 PM.

Details

Summary

The idea is to find two representatives out of the two ranges which will (by construction) form the UMin of the post-binaryAnd range when and'd, and do it again for the UMax.

For wrapped ranges, we break the range in two non-wrapping ConstantRanges, a low part and a high part, and use the algorithm above to pick representatives between the LHS ranges and RHS ranges.

I'm quite confident that the resulting range includes all possible results, and that the result is the smallest to do so except maybe for wrapping ranges.

I'd greatly appreciate any help simplifying this algorithm, both in implementation and in explanation (the details in the comments). As it stands I think this is too messy to commit and I'm hopeful that the review discussion will lead to significant improvements.

Diff Detail

Event Timeline

nicholas updated this revision to Diff 59687.Jun 5 2016, 8:29 PM
nicholas retitled this revision from to Replace the implementation of ConstantRange::binaryAnd..
nicholas updated this object.
sanjoy edited edge metadata.Jun 5 2016, 10:53 PM

Hi Nick,

I haven't read the code yet (will do that soon), but I wonder if you've tried the following approach: map a ConstantRange to KnownOne and KnownZero, use these to compute the binary and, and map the resultant KnownOne and KnownZero back to a ConstantRange. That will probably not be easier in terms of code, but will make the code organization more obvious, and most of the interesting logic can be re-used for binaryOr.

Sanjoy Das wrote:

sanjoy added a comment.

Hi Nick,

I haven't read the code yet (will do that soon), but I wonder if you've tried the following approach: map a ConstantRange to KnownOne and KnownZero, use these to compute the binary and, and map the resultant KnownOne and KnownZero back to a ConstantRange. That will probably not be easier in terms of code, but will make the code organization more obvious, and most of the interesting logic can be re-used for binaryOr.

That is the very first thing I tried. :-D

I still have the code (and tests!) for working fromKnownBits and
toKnownBits methods if you want them. I was surprised at how small and
efficient they were.

Extracting one test which would fail with that implementation:

EXPECT_EQ(ConstantRange(APInt(8, 21), APInt(8, 25))
              .binaryAnd(ConstantRange(APInt(8, 22), APInt(8, 26))),
          ConstantRange(APInt(8, 16), APInt(8, 25)));
NOTE: Closed ranges below, not half-open!

This is testing i8 [21, 24] & [22, 25]

21 0x15 0b10101 LHS only
22 0x16 0b10110 LHS and RHS
23 0x17 0b10111 LHS and RHS
24 0x18 0b11000 LHS and RHS
25 0x19 0b11001 RHS only

LHS range has known bits 0b1xxxx and RHS has known bits 0b1xxxx. The
binary-and of those is 0b1xxxx, which produces the range i8 [16, 31],
but there is no pair of values which, when and'd, produce 26, 27, 28,
29, 30 or 31. You can get 16 by taking 21 from LHS and 24 from RHS, and
24 by taking 24 from both ranges. i8 [21, 24] is the correct answer.

That example worked out too cleanly; the lower was equal to 'choosing 0
for unknown bits' and the upper-1 was the umin of the unsigned-max's of
each range. To dispel a few patterns up front, i8 [4, 5] & [8, 9] is an
example where the new upper-1 is 1 not 5, while i8 [5, 6] & [5, 6] has a
new lower of 4, but i8 [5, 6] & [5] has a new lower of 5.

And since I have it on my brain, here's a little more about wrapped
ranges. I made an error thinking that I could 'unroll' wrapped ranges,
turning i8 [255, 0] into i9 [255, 256], binary-and those, and then
truncate the resulting range. Not so! It's correct, but it does not
produce the smallest range. Correctly:

  i8 [255, 0] & i8 [255, 0]
= i8 {255&255, 255&0, 0&255, 0&0}  (curly braces for sets)
= i8 {255, 0, 0, 0}
= i8 {255, 0}
= i8 [255, 0].

With the unrolling:

i8 [255, 0] & i8 [255, 0]

--> i9 [255, 256] & i9 [255, 256]

= i9 {255&255, 255&256, 256&255, 256&256}
= i9 {255, 0, 0, 256}  (here be dragons!)
= i9 [0, 256]  (this range includes 1 and 2 and 3, ...)

--> i8 full-set

My current approach gets this particular case right, and I'm pretty sure
it always produces ranges that cover all resulting values, but I'm not
sure it always produces the smallest range.

Nick

Nick Lewycky wrote:

nicholas added a subscriber: nicholas.
nicholas added a comment.

Sanjoy Das wrote:

sanjoy added a comment.

Hi Nick,

I haven't read the code yet (will do that soon), but I wonder if you've tried the following approach: map a ConstantRange to KnownOne and KnownZero, use these to compute the binary and, and map the resultant KnownOne and KnownZero back to a ConstantRange. That will probably not be easier in terms of code, but will make the code organization more obvious, and most of the interesting logic can be re-used for binaryOr.

That is the very first thing I tried. :-D

I still have the code (and tests!) for working fromKnownBits and
toKnownBits methods if you want them. I was surprised at how small and
efficient they were.

Extracting one test which would fail with that implementation:

EXPECT_EQ(ConstantRange(APInt(8, 21), APInt(8, 25))
              .binaryAnd(ConstantRange(APInt(8, 22), APInt(8, 26))),
          ConstantRange(APInt(8, 16), APInt(8, 25)));

NOTE: Closed ranges below, not half-open!

This is testing i8 [21, 24]& [22, 25]

21 0x15 0b10101 LHS only
22 0x16 0b10110 LHS and RHS
23 0x17 0b10111 LHS and RHS
24 0x18 0b11000 LHS and RHS
25 0x19 0b11001 RHS only

LHS range has known bits 0b1xxxx and RHS has known bits 0b1xxxx. The
binary-and of those is 0b1xxxx, which produces the range i8 [16, 31],
but there is no pair of values which, when and'd, produce 26, 27, 28,
29, 30 or 31. You can get 16 by taking 21 from LHS and 24 from RHS, and
24 by taking 24 from both ranges. i8 [21, 24] is the correct answer.

I need to strike an example from this paragraph:

That example worked out too cleanly; the lower was equal to 'choosing 0
for unknown bits' and the upper-1 was the umin of the unsigned-max's of
each range. To dispel a few patterns up front, i8 [4, 5]& [8, 9] is an
example where the new upper-1 is 1 not 5, while i8 [5, 6]& [5, 6] has a
new lower of 4, but i8 [5, 6]& [5] has a new lower of 5.

"but i8 [5, 6] & [5] has a new lower of 5" is wrong. i8 [5, 6] & [5, 5]
has a lower of 5&6 = 4.

I'll trade it in for a new example: i8 [152, 155] & [176, 191] has a
umin of 144.

The result-lower does have to be less than or equal to the min(lhs
lower, rhs lower), because anding can't produce a value larger than the
smaller of its inputs. Similarly the result upper-1 is always less than
or equal to the min of the upper-1's of the ranges.

Nick

And since I have it on my brain, here's a little more about wrapped
ranges. I made an error thinking that I could 'unroll' wrapped ranges,
turning i8 [255, 0] into i9 [255, 256], binary-and those, and then
truncate the resulting range. Not so! It's correct, but it does not
produce the smallest range. Correctly:

  i8 [255, 0]&  i8 [255, 0]
= i8 {255&255, 255&0, 0&255, 0&0}  (curly braces for sets)
= i8 {255, 0, 0, 0}
= i8 {255, 0}
= i8 [255, 0].

With the unrolling:

i8 [255, 0]&  i8 [255, 0]

--> i9 [255, 256]& i9 [255, 256]

= i9 {255&255, 255&256, 256&255, 256&256}
= i9 {255, 0, 0, 256}  (here be dragons!)
= i9 [0, 256]  (this range includes 1 and 2 and 3, ...)

--> i8 full-set

My current approach gets this particular case right, and I'm pretty sure
it always produces ranges that cover all resulting values, but I'm not
sure it always produces the smallest range.

Nick

http://reviews.llvm.org/D21010

regehr edited edge metadata.Jun 6 2016, 1:37 AM

Great to see some work going on here!

There is a known algorithm for solving these problems that is, I believe, both correct and precise. It's in Hacker's Delight (sorry, don't have my copy handy so can't give a page number). You can also find code here (and nearby):

https://github.com/sav-tools/wrapped-intervals/blob/master/lib/RangeAnalysis/BaseRange.cpp#L227

I think we should make sure to understand the relationship between this algorithm and Nick's code before committing to anything. I haven't fully grokked Nick's code yet but it looks like the proposed code may be more or less equivalent.

Thank you. I looked around but all I found were ways to compute the
binary-and of all integers in an interval, not between two intervals.

I'll study this and come back with an update ...

John Regehr wrote:

regehr added a comment.

Also see section 3.5 of this paper (by the authors of the code above):

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0ahUKEwjc4LqtgJPNAhXENhoKHRuLDX8QFggdMAA&url=https%3A%2F%2Fti.arc.nasa.gov%2Fpublications%2F20091%2Fdownload%2F&usg=AFQjCNEQ7Z1NLOlnzVYsL8PmV-z5w7mzyA&sig2=CDe8MBmoIeeGGyc0sd318w

http://reviews.llvm.org/D21010

regehr added a comment.Jun 8 2016, 1:28 PM

I've looked at the code and I agree that the implementation is sound and is precise for non-wrapped inputs.

A bad case for this algorithm is [-1,0) & [-1,1) where it returns the full set, but the precise result would be [-1, 1).

sanjoy resigned from this revision.Jun 24 2017, 12:38 PM

Inactive, as far as I can tell.