[IR] Fix bug in `ConstantRange::intersectWith`

[sanjoy]

Summary

NOTE: this is still failing tests, so it isn't yet ready to go in and is a WIP. The failing tests will have to be audited manually before checking this in.

NOTE: all of the fixes in ConstantRangeTest.cpp were bugs to begin with, AFAICT.

This "fixes" a bug in intersectWith by rewriting it. The idea is that
we can extend the bitwidth of a constant range by a bit and use that to
simplify the logic around checking for wrapped ranges.

Roughly, if this is our number line with a wrapped range

|---)----[-------|

we map the wrapped range to

|--------[-------|---)------------|  .. (A)

and if this is the number line with an not-wrapped range

|---[----)-------|

we map it to

|---[----)-------|----------------|  .. (B)

or

|----------------|---[----)-------|  .. (C)

When intersecting a wrapped range with an unwrapped one (the "hard"
case), we intersect (A) with (B) and (A) with (C); and pick the larger
of the two.

We can do the same thing for unions.

[sanjoy]

Note: the only reason I introduced UnwrappedLimit instead of using APInt is that I wanted to avoid an allocation if we were working with a word-wide range. If you think that that's an acceptable overhead, I can switch this to use APInt instead.

[nlewycky]

lib/IR/ConstantRange.cpp

318–319

clang-format?

338–339

Please comment what this produces. A reader may wonder why HighBitPref is ignored on the wrapped set case; why doesn't it control whether the 'gap' is in the high or low half?

unittests/IR/ConstantRangeTest.cpp

285

Remove this newline?

[sanjoy]

This change is unnecessary and buggy. I was working under the assumption that everything in X.intersectWith(Y) has to belong to both X and Y; whereas X.intersectWith(Y) is allowed to return a superset of the actual mathematical intersection of X and Y. This change is buggy today because it will sometimes return a proper subset of the mathematical intersection of X and Y.

lib/IR/ConstantRange.cpp

 }
 
 /// \brief Subtract the specified range from this range (aka relative complement
 /// of the sets).
 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
   return intersectWith(CR.inverse());
 }
 
+
+/// Represents an unsigned "LowBits.getBitWidth() + 1" bit integer, with
+/// `HighBit` as the MSB.
+struct UnwrappedLimit {
+  const APInt &LowBits;
+  bool HighBit = false;
+
+  explicit UnwrappedLimit(const APInt &LowBits, bool HighBit = false) :
+    LowBits(LowBits), HighBit(HighBit) {}
+
+  bool ult(const UnwrappedLimit &Other) {
+    if (HighBit && !Other.HighBit) return false;
+    if (!HighBit && Other.HighBit) return true;
+    return LowBits.ult(Other.LowBits);
+  }
+
+  UnwrappedLimit umin(const UnwrappedLimit &Other) {
+    if (ult(Other)) return *this;
+    return Other;
+  }
+
+  UnwrappedLimit umax(const UnwrappedLimit &Other) {
+    if (ult(Other)) return Other;
+    return *this;
+  }
+};
+
+static std::pair<UnwrappedLimit, UnwrappedLimit>
+GetUnwrappedLimits(const ConstantRange &CR, bool HighBitPref) {
+  if (!CR.isWrappedSet())
+    return std::make_pair(UnwrappedLimit(CR.getLower(), HighBitPref),
+                          UnwrappedLimit(CR.getUpper(), HighBitPref));
+
+  return std::make_pair(UnwrappedLimit(CR.getLower()),
+                        UnwrappedLimit(CR.getUpper(), true));
+}
+
 /// intersectWith - Return the range that results from the intersection of this
 /// range with another range.  The resultant range is guaranteed to include all
 /// elements contained in both input ranges, and to have the smallest possible
 /// set size that does so.  Because there may be two intersections with the
 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
-  assert(getBitWidth() == CR.getBitWidth() && 
+  assert(getBitWidth() == CR.getBitWidth() &&
          "ConstantRange types don't agree!");
 
   // Handle common cases.
   if (   isEmptySet() || CR.isFullSet()) return *this;
   if (CR.isEmptySet() ||    isFullSet()) return CR;
 
-  if (!isWrappedSet() && CR.isWrappedSet())
-    return CR.intersectWith(*this);
-
-  if (!isWrappedSet() && !CR.isWrappedSet()) {
-    if (Lower.ult(CR.Lower)) {
-      if (Upper.ule(CR.Lower))
-        return ConstantRange(getBitWidth(), false);
+  auto IntersectViaUnwrapping =
+    [this](const ConstantRange &CR0, bool HighBitPref0,
+           const ConstantRange &CR1, bool HighBitPref1) {
+    auto SelfUnwrapped = GetUnwrappedLimits(CR0, HighBitPref0);
+    auto OtherUnwrapped = GetUnwrappedLimits(CR1, HighBitPref1);
+
+    auto NewLower = SelfUnwrapped.first.umax(OtherUnwrapped.first);
+    auto NewUpper = SelfUnwrapped.second.umin(OtherUnwrapped.second);
+
+    if (NewLower.ult(NewUpper))
+      return ConstantRange(NewLower.LowBits, NewUpper.LowBits);
+    return ConstantRange(getBitWidth(), false /* empty */);
+  };
 
-      if (Upper.ult(CR.Upper))
-        return ConstantRange(CR.Lower, Upper);
+  if (isWrappedSet() == CR.isWrappedSet())
+    return IntersectViaUnwrapping(*this, false, CR, false);
 
-      return CR;
-    }
-    if (Upper.ult(CR.Upper))
-      return *this;
-
-    if (Lower.ult(CR.Upper))
-      return ConstantRange(Lower, CR.Upper);
-
-    return ConstantRange(getBitWidth(), false);
-  }
-
-  if (isWrappedSet() && !CR.isWrappedSet()) {
-    if (CR.Lower.ult(Upper)) {
-      if (CR.Upper.ult(Upper))
-        return CR;
-
-      if (CR.Upper.ule(Lower))
-        return ConstantRange(CR.Lower, Upper);
-
-      if (getSetSize().ult(CR.getSetSize()))
-        return *this;
-      return CR;
-    }
-    if (CR.Lower.ult(Lower)) {
-      if (CR.Upper.ule(Lower))
-        return ConstantRange(getBitWidth(), false);
-
-      return ConstantRange(Lower, CR.Upper);
-    }
-    return CR;
-  }
-
-  if (CR.Upper.ult(Upper)) {
-    if (CR.Lower.ult(Upper)) {
-      if (getSetSize().ult(CR.getSetSize()))
-        return *this;
-      return CR;
-    }
+  if (!isWrappedSet() && CR.isWrappedSet())
+    return CR.intersectWith(*this);
 
-    if (CR.Lower.ult(Lower))
-      return ConstantRange(Lower, CR.Upper);
+  ConstantRange I0 = IntersectViaUnwrapping(*this, false, CR, true);
+  ConstantRange I1 = IntersectViaUnwrapping(*this, false, CR, false);
 
-    return CR;
-  }
-  if (CR.Upper.ule(Lower)) {
-    if (CR.Lower.ult(Lower))
-      return *this;
-
-    return ConstantRange(CR.Lower, Upper);
-  }
-  if (getSetSize().ult(CR.getSetSize()))
-    return *this;
-  return CR;
+  return I0.getSetSize().ugt(I1.getSetSize()) ? I0 : I1;
 }
 
 
 /// unionWith - Return the range that results from the union of this range with
 /// another range.  The resultant range is guaranteed to include the elements of
 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is
 /// [3, 15), which includes 9, 10, and 11, which were not included in either
 /// set before.

unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, IntersectWith) {
   EXPECT_EQ(One.intersectWith(Wrap), Empty);
   EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
 
   // Klee generated testcase from PR4545.
   // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
   // 01..4.6789ABCDEF where the dots represent values not in the intersection.
   ConstantRange LHS(APInt(16, 4), APInt(16, 2));
   ConstantRange RHS(APInt(16, 6), APInt(16, 5));
-  EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
+  EXPECT_TRUE(LHS.intersectWith(RHS) ==
+              ConstantRange(APInt(16, 6), APInt(16, 2)));
 
   // previous bug: intersection of [min, 3) and [2, max) should be 2
   LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3));
   RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));
   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));
 
-  // [2, 0) /\ [4, 3) = [2, 0)
+  // [2, 0) /\ [4, 3) = [4, 0)
   LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
   RHS = ConstantRange(APInt(32, 4), APInt(32, 3));
-  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));
+  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
 
   // [2, 0) /\ [4, 2) = [4, 0)
   LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
   RHS = ConstantRange(APInt(32, 4), APInt(32, 2));
   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
 
   // [4, 2) /\ [5, 1) = [5, 1)
   LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
   RHS = ConstantRange(APInt(32, 5), APInt(32, 1));
   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));
 
-  // [2, 0) /\ [7, 4) = [7, 4)
+  // [2, 0) /\ [7, 4) = [7, 0)
   LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
   RHS = ConstantRange(APInt(32, 7), APInt(32, 4));
-  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));
+  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 0)));
 
   // [4, 2) /\ [1, 0) = [1, 0)
   LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
   RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
-  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
- 
+  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
   // [15, 0) /\ [7, 6) = [15, 0)
   LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
   RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
+
+  LHS = ConstantRange(APInt(4, 0), APInt(4, -1));
+  RHS = ConstantRange(APInt(4, -8), APInt(4, 7));
+
+  EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(4, -8), APInt(4, -1)));
 }
 
 TEST_F(ConstantRangeTest, UnionWith) {
   EXPECT_EQ(Wrap.unionWith(One),
             ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
   EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));
   EXPECT_EQ(Empty.unionWith(Empty), Empty);
   EXPECT_EQ(Full.unionWith(Full), Full);