Replace the implementation of ConstantRange::binaryAnd.

[nicholas]

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.

[sanjoy]

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.

[nicholas]

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

[nicholas]

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]

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.

[regehr]

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

[nicholas]

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]

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]

Inactive, as far as I can tell.

lib/IR/ConstantRange.cpp

ConstantRange::udiv(const ConstantRange &RHS) const {
 
   return ConstantRange(Lower, Upper);
 }
 
 ConstantRange
 ConstantRange::binaryAnd(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+  if (isFullSet() && Other.isFullSet())
+    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+  if (isFullSet() || Other.isFullSet()) {
+    APInt NewUMax = isFullSet() ? Other.getUnsignedMax() : getUnsignedMax();
+    if (NewUMax.isMaxValue())
+      return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+    return ConstantRange(APInt::getNullValue(getBitWidth()), NewUMax + 1);
+  }
 
-  // TODO: replace this with something less conservative
+  // Note that 'wrapped' means Upper u< Lower, which is true for all ranges
+  // that contain -1 even if they don't include 0. For our purposes we only
+  // worry about those which include both.
+
+  if ((Other.isWrappedSet() && !Other.Upper.isMinValue()) && !isWrappedSet())
+    return Other.binaryAnd(*this);
+
+  if (isWrappedSet() && !Upper.isMinValue()) {
+    // Break wrapped ranges into two ranges, a low part and a high part. Compute
+    // binaryAnd between all the combinations, then union those together.
+    ConstantRange Low(APInt::getMinValue(getBitWidth()), Upper);
+    ConstantRange High(Lower, APInt::getMinValue(getBitWidth()));
+    if (Other.isWrappedSet() && !Other.Upper.isMinValue()) {
+      ConstantRange OtherLow(APInt::getMinValue(getBitWidth()), Other.Upper);
+      ConstantRange OtherHigh(Other.Lower, APInt::getMinValue(getBitWidth()));
+      return Low.binaryAnd(OtherLow)
+          .unionWith(Low.binaryAnd(OtherHigh))
+          .unionWith(High.binaryAnd(OtherLow))
+          .unionWith(High.binaryAnd(OtherHigh));
+    }
+    return Low.binaryAnd(Other).unionWith(High.binaryAnd(Other));
+  }
+
+  // Compute the min. To do this, we pick one representative from each range,
+  // such that they will have the lowest possible value when and'd together,
+  // by construction. In particular:
+  //   * each representative is between unsigned-min and unsigned-max inclusive
+  //     (we do not support wrapped ranges below, those are handled above)
+  //   * we try to avoid choosing a 1 bit in both representatives for the same
+  //     bit position. When we must, we try to make it happen in the least
+  //     significant bit possible.
+  //   * it is safe to choose a 1 bit in one representative if the other one has
+  //     a zero in the same bit position. We try to make this happen in the most
+  //     significant bit possible, since doing so removes restrictions on the
+  //     choice of remaining bits.
+  //
+  // Here's an example run of the algorithm. Consider i3 [1, 2) & i3 [5, 0).
+  // Starting with the left-most bit, LHS rep becomes 0xx, RHS rep becomes 1xx
+  // in order to stay in range. Next bit, LHS rep becomes 00x, RHS rep has the
+  // choice between 11x and 10x; because the LHS has a '0' bit here, we choose
+  // to put in a '1' now. Next is 001 and 110, aka i3 1 and i3 6 which when
+  // and'd together produce 0.
+
+  // Compute the min. Pick a sample value out of each range that when and'd
+  // produces the lowest possible value. We assume that any value between min
+  // and max is valid (ie., no wrapped ranges unless Upper == 0).
+  APInt UMax = getUnsignedMax(), UMin = getUnsignedMin();
+  APInt OtherUMax = Other.getUnsignedMax(), OtherUMin = Other.getUnsignedMin();
+
+  APInt MinSample = APInt::getMinValue(getBitWidth());
+  APInt OtherMinSample = APInt::getMinValue(getBitWidth());
+  for (int i = getBitWidth() - 1; i >= 0; --i) {
+    // Given the bits chosen in MinSample so far, are we free to pick a 0 or 1?
+    // Check by loading in '01...1' and '10...0' in to MinSample.
+    bool KnownZero = false, KnownOne = false;
+    bool OtherKnownZero = false, OtherKnownOne = false;
+    {
+      APInt ZeroThenOnes = APInt::getLowBitsSet(getBitWidth(), i);
+      APInt OneThenZeros = ZeroThenOnes + 1;
+      if ((MinSample | ZeroThenOnes).ult(UMin))
+        KnownOne = true;
+      if ((MinSample | OneThenZeros).ugt(UMax))
+        KnownZero = true;
+      if ((OtherMinSample | ZeroThenOnes).ult(OtherUMin))
+        OtherKnownOne = true;
+      if ((OtherMinSample | OneThenZeros).ugt(OtherUMax))
+        OtherKnownZero = true;
+    }
+
+    assert(!(KnownZero && KnownOne));
+    assert(!(OtherKnownZero && OtherKnownOne));
+
+    if ((KnownZero || KnownOne) && (OtherKnownZero || OtherKnownOne)) {
+      if (KnownOne) {
+        MinSample.setBit(i);
+      }
+      if (OtherKnownOne) {
+        OtherMinSample.setBit(i);
+      }
+      continue;
+    }
+
+    if (KnownZero) {
+      // MinSample picks a '0' now, OtherMinSample picks a '1' followed by all
+      // '0's.
+      MinSample = UMin;
+      OtherMinSample.setBit(i);
+      break;
+    }
+    if (KnownOne) {
+      MinSample.setBit(i);
+      continue;
+    }
+
+    if (OtherKnownZero) {
+      OtherMinSample = OtherUMin;
+      MinSample.setBit(i);
+      break;
+    }
+    if (OtherKnownOne) {
+      OtherMinSample.setBit(i);
+      continue;
+    }
+
+    // We have a free hand? I choose a 1 followed by all 0s for Sample, and a
+    // 0 followed by all 1s for OtherSample.
+    MinSample.setBit(i);
+    OtherMinSample |= APInt::getLowBitsSet(getBitWidth(), i);
+    break;
+  }
+
+  assert(UMin.ule(MinSample) && MinSample.ule(UMax));
+  assert(OtherUMin.ule(OtherMinSample) && OtherMinSample.ule(OtherUMax));
+  APInt NewUMin = MinSample & OtherMinSample;
+
+  // Compute the max. Similarly to computing the min, we want to choose a sample
+  // that has 1s in the same bit position for both samples. When a bit can be
+  // chosen to be either 0 or 1 and the other side is guaranteed to have a 0,
+  // we can safely choose 0 now which guarantees that choosing 1s for the rest
+  // of the bits will not go outside the range.
+  APInt MaxSample = APInt::getMinValue(getBitWidth());
+  APInt OtherMaxSample = APInt::getMinValue(getBitWidth());
+  for (int i = getBitWidth() - 1; i >= 0; --i) {
+    // Given the bits chosen in MaxSample so far, are we free to pick a 0 or 1?
+    // Check by loading in '01...1' and '10...0' in to MaxSample.
+    bool KnownZero = false, KnownOne = false;
+    bool OtherKnownZero = false, OtherKnownOne = false;
+    {
+      APInt ZeroThenOnes = APInt::getLowBitsSet(getBitWidth(), i);
+      APInt OneThenZeros = ZeroThenOnes + 1;
+      if ((MaxSample | ZeroThenOnes).ult(UMin))
+        KnownOne = true;
+      if ((MaxSample | OneThenZeros).ugt(UMax))
+        KnownZero = true;
+      if ((OtherMaxSample | ZeroThenOnes).ult(OtherUMin))
+        OtherKnownOne = true;
+      if ((OtherMaxSample | OneThenZeros).ugt(OtherUMax))
+        OtherKnownZero = true;
+    }
+
+    assert(!(KnownZero && KnownOne));
+    assert(!(OtherKnownZero && OtherKnownOne));
+
+    if ((KnownZero || KnownOne) && (OtherKnownZero || OtherKnownOne)) {
+      if (KnownOne) {
+        MaxSample.setBit(i);
+      }
+      if (OtherKnownOne) {
+        OtherMaxSample.setBit(i);
+      }
+      continue;
+    }
+
+    if (KnownOne) {
+      MaxSample.setBit(i);
+      OtherMaxSample.setBit(i);
+      continue;
+    }
+
+    if (OtherKnownOne) {
+      MaxSample.setBit(i);
+      OtherMaxSample.setBit(i);
+      continue;
+    }
+
+    if (KnownZero) {
+      // MaxSample picks a '0' now, OtherMaxSample picks a '0' followed by all
+      // '1's.
+      MaxSample = UMax;
+      OtherMaxSample |= APInt::getLowBitsSet(getBitWidth(), i);
+      break;
+    }
+
+    if (OtherKnownZero) {
+      OtherMaxSample = OtherUMax;
+      MaxSample |= APInt::getLowBitsSet(getBitWidth(), i);
+      break;
+    }
+
+    // We have a free hand? Choose 1s for both.
+    MaxSample.setBit(i);
+    OtherMaxSample.setBit(i);
+  }
+
+  assert(UMin.ule(MaxSample) && MaxSample.ule(UMax));
+  assert(OtherUMin.ule(OtherMaxSample) && OtherMaxSample.ule(OtherUMax));
+  APInt NewUMax = MaxSample & OtherMaxSample;
 
-  APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
-  if (umin.isAllOnesValue())
+  if (NewUMin.isMinValue() && NewUMax.isAllOnesValue())
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
-  return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
+
+  return ConstantRange(NewUMin, NewUMax + 1);
 }
 
 ConstantRange
 ConstantRange::binaryOr(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 
   // TODO: replace this with something less conservative

unittests/IR/ConstantRangeTest.cpp

EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
                              APInt::getSignedMinValue(32) + APInt(32, 100))
                    .getEquivalentICmp(Pred, RHS));
 
   EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
                              APInt::getMinValue(32) + APInt(32, 100))
                    .getEquivalentICmp(Pred, RHS));
 }
 
+TEST_F(ConstantRangeTest, BinaryAnd) {
+  EXPECT_EQ(Full.binaryAnd(Full), Full);
+  EXPECT_EQ(Full.binaryAnd(Empty), Empty);
+  EXPECT_EQ(Full.binaryAnd(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
+  EXPECT_EQ(Full.binaryAnd(Some),
+            ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
+  EXPECT_EQ(Full.binaryAnd(Wrap), Full);
+  EXPECT_EQ(Empty.binaryAnd(Empty), Empty);
+  EXPECT_EQ(Empty.binaryAnd(One), Empty);
+  EXPECT_EQ(Empty.binaryAnd(Some), Empty);
+  EXPECT_EQ(Empty.binaryAnd(Wrap), Empty);
+  EXPECT_EQ(One.binaryAnd(One), One);
+  EXPECT_EQ(One.binaryAnd(Some), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
+  EXPECT_EQ(One.binaryAnd(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
+  EXPECT_EQ(Some.binaryAnd(Some),
+            ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
+  EXPECT_EQ(Some.binaryAnd(Wrap),
+            ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
+  EXPECT_EQ(Wrap.binaryAnd(Wrap), Full);
+
+  EXPECT_EQ(ConstantRange(APInt(8, 0x30), APInt(8, 0x3a))
+                .binaryAnd(ConstantRange(APInt(8, 0x20), APInt(8, 0x3f))),
+            ConstantRange(APInt(8, 0x20), APInt(8, 0x3a)));
+  EXPECT_EQ(ConstantRange(APInt(8, 21), APInt(8, 25))
+                .binaryAnd(ConstantRange(APInt(8, 22), APInt(8, 26))),
+            ConstantRange(APInt(8, 16), APInt(8, 25)));
+  EXPECT_EQ(ConstantRange(APInt(8, 4), APInt(8, 6))
+                .binaryAnd(ConstantRange(APInt(8, 8), APInt(8, 10))),
+            ConstantRange(APInt(8, 0), APInt(8, 2)));
+  EXPECT_EQ(ConstantRange(APInt(8, 255), APInt(8, 1))
+                .binaryAnd(ConstantRange(APInt(8, 255), APInt(8, 1))),
+            ConstantRange(APInt(8, 255), APInt(8, 1)));
+}
+
 }  // anonymous namespace