[ConstantRange] Add unsigned and signed intersection type

[nikic]

Summary

The intersection of two ConstantRanges may consist of two disjoint ranges. As we can only return one range as the result, we need to return one of the two possible ranges that cover both. Currently the result is picked based on set size. However, this is not always optimal: If we're in an unsigned context, we'd prefer to get a large unsigned range over a small signed range -- the latter effectively becomes a full set in the unsigned domain.

This revision adds an IntersectionType, which can be either Smallest, Unsigned or Signed. Smallest is the current behavior and Unsigned and Signed are new variants that prefer not to wrap the unsigned/signed domain. The new type isn't used anywhere yet (but SCEV will be a good first user).

I've also added some comments to illustrate the various cases in intersectWith(), which should hopefully make it more obvious what is going on.

[lebedev.ri]

llvm/unittests/IR/ConstantRangeTest.cpp

400 ↗

(On Diff #192711)

This looks inconsistent?
"Should have at most *two* ranges" maybe?

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

400 ↗

(On Diff #192711)

While the intersection consists of at most two ranges in the sense of potentially wrapping ConstantRanges, if we're using a non-wrapping representation (as is the case in this testing code), then there may be three ranges. An example:

----]    [---]   [----   Two ConstantRanges
[---]    [---]   [---]   Three non-wrapping ranges

[nikic]

Also add signed intersection type. I think that adding both makes the implementation more obvious in this case, as the logic for the range preference is extracted more neatly.

[lebedev.ri]

Tests look good, but i wonder if @nlopes might want to show-off some Z3 magic..

[lebedev.ri]

Hmm, yes, GetPreferredRange() did make this more obvious.
I would still prefer to see some Z3 magic, but the tests look reassuring to me.

llvm/include/llvm/IR/ConstantRange.h

255–256 ↗

(On Diff #192793)

The or if both possibilities wrap or don't wrap, the smaller set. is applicable for both the Unsigned and Signed IntersectionTypes. Maybe move that phrase to the end, after explaining Unsigned?

[nikic]

I think I'd like to make two more changes here: Rename IntersectionType to OperationType or similar, as the Smallest/Unsigned/Signed classification will be useful in other places as well (e.g. it is also directly applicable to unions). Furthermore I'd like to change the enum class to an enum, as I don't think that ConstantRange::OperationType::Smallest adds anything over just ConstantRange::Smallest, beyond being unwieldy.

[lebedev.ri]

In D59959#1457356, @nikic wrote:

I think I'd like to make two more changes here: Rename IntersectionType to OperationType or similar, as the Smallest/Unsigned/Signed classification will be useful in other places as well (e.g. it is also directly applicable to unions).

So i agree that IntersectionType will be misleading for other ops. But operation is a bit too generic maybe?
We are saying "please intersect these two ranges, and out of all the intersections (common elements? overlapped elements?, ???), try to pick smallest/one with no wrap/...".
So i wonder if it would be better not to talk about *operation*, but about the result of operation?
How does e.g. DesiredRangeVariant sound?

Furthermore I'd like to change the enum class to an enum, as I don't think that ConstantRange::OperationType::Smallest adds anything over just ConstantRange::Smallest, beyond being unwieldy.

As long as it stays within ConstantRange prefix, i think that could be fine.

[nikic]

In D59959#1457360, @lebedev.ri wrote:

In D59959#1457356, @nikic wrote:

I think I'd like to make two more changes here: Rename IntersectionType to OperationType or similar, as the Smallest/Unsigned/Signed classification will be useful in other places as well (e.g. it is also directly applicable to unions).

So i agree that IntersectionType will be misleading for other ops. But operation is a bit too generic maybe?
We are saying "please intersect these two ranges, and out of all the intersections (common elements? overlapped elements?, ???), try to pick smallest/one with no wrap/...".
So i wonder if it would be better not to talk about *operation*, but about the result of operation?
How does e.g. DesiredRangeVariant sound?

Yes, I agree that it makes more sense to talk about the result here. PreferredRangeType would be another possibility, which matches the terminology in the implementation.

[lebedev.ri]

In D59959#1457362, @nikic wrote:

In D59959#1457360, @lebedev.ri wrote:

In D59959#1457356, @nikic wrote:

I think I'd like to make two more changes here: Rename IntersectionType to OperationType or similar, as the Smallest/Unsigned/Signed classification will be useful in other places as well (e.g. it is also directly applicable to unions).

So i agree that IntersectionType will be misleading for other ops. But operation is a bit too generic maybe?
We are saying "please intersect these two ranges, and out of all the intersections (common elements? overlapped elements?, ???), try to pick smallest/one with no wrap/...".
So i wonder if it would be better not to talk about *operation*, but about the result of operation?
How does e.g. DesiredRangeVariant sound?

Yes, I agree that it makes more sense to talk about the result here. PreferredRangeType would be another possibility, which matches the terminology in the implementation.

Yes, that also is a good alternative.

[nikic]

Rename IntersectionType to PreferredRangeType, switch to plain enum.

llvm/trunk/include/llvm/IR/ConstantRange.h

public:
 
   /// Subtract the specified constant from the endpoints of this constant range.
   ConstantRange subtract(const APInt &CI) const;
 
   /// Subtract the specified range from this range (aka relative complement of
   /// the sets).
   ConstantRange difference(const ConstantRange &CR) const;
 
-  /// 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 intersectWith(const ConstantRange &CR) const;
+  /// If represented precisely, the result of some range operations may consist
+  /// of multiple disjoint ranges. As only a single range may be returned, any
+  /// range covering these disjoint ranges constitutes a valid result, but some
+  /// may be more useful than others depending on context. The preferred range
+  /// type specifies whether a range that is non-wrapping in the unsigned or
+  /// signed domain, or has the smallest size, is preferred. If a signedness is
+  /// preferred but all ranges are non-wrapping or all wrapping, then the
+  /// smallest set size is preferred. If there are multiple smallest sets, any
+  /// one of them may be returned.
+  enum PreferredRangeType { Smallest, Unsigned, Signed };
+
+  /// Return the range that results from the intersection of this range with
+  /// another range. If the intersection is disjoint, such that two results
+  /// are possible, the preferred range is determined by the PreferredRangeType.
+  ConstantRange intersectWith(const ConstantRange &CR,
+                              PreferredRangeType Type = Smallest) const;
 
   /// 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.
   ConstantRange unionWith(const ConstantRange &CR) const;
 

llvm/trunk/lib/IR/ConstantRange.cpp

if (Lower == Upper)
     return *this;
   return ConstantRange(Lower - Val, Upper - Val);
 }
 
 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
   return intersectWith(CR.inverse());
 }
 
-ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
+static ConstantRange getPreferredRange(
+    const ConstantRange &CR1, const ConstantRange &CR2,
+    ConstantRange::PreferredRangeType Type) {
+  if (Type == ConstantRange::Unsigned) {
+    if (!CR1.isWrappedSet() && CR2.isWrappedSet())
+      return CR1;
+    if (CR1.isWrappedSet() && !CR2.isWrappedSet())
+      return CR2;
+  } else if (Type == ConstantRange::Signed) {
+    if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
+      return CR1;
+    if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
+      return CR2;
+  }
+
+  if (CR1.isSizeStrictlySmallerThan(CR2))
+    return CR1;
+  return CR2;
+}
+
+ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,
+                                           PreferredRangeType Type) const {
   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 (!isUpperWrapped() && CR.isUpperWrapped())
-    return CR.intersectWith(*this);
+    return CR.intersectWith(*this, Type);
 
   if (!isUpperWrapped() && !CR.isUpperWrapped()) {
     if (Lower.ult(CR.Lower)) {
+      // L---U       : this
+      //       L---U : CR
       if (Upper.ule(CR.Lower))
         return getEmpty();
 
+      // L---U       : this
+      //   L---U     : CR
       if (Upper.ult(CR.Upper))
         return ConstantRange(CR.Lower, Upper);
 
+      // L-------U   : this
+      //   L---U     : CR
       return CR;
     }
+    //   L---U     : this
+    // L-------U   : CR
     if (Upper.ult(CR.Upper))
       return *this;
 
+    //   L-----U   : this
+    // L-----U     : CR
     if (Lower.ult(CR.Upper))
       return ConstantRange(Lower, CR.Upper);
 
+    //       L---U : this
+    // L---U       : CR
     return getEmpty();
   }
 
   if (isUpperWrapped() && !CR.isUpperWrapped()) {
     if (CR.Lower.ult(Upper)) {
+      // ------U   L--- : this
+      //  L--U          : CR
       if (CR.Upper.ult(Upper))
         return CR;
 
+      // ------U   L--- : this
+      //  L------U      : CR
       if (CR.Upper.ule(Lower))
         return ConstantRange(CR.Lower, Upper);
 
-      if (isSizeStrictlySmallerThan(CR))
-        return *this;
-      return CR;
+      // ------U   L--- : this
+      //  L----------U  : CR
+      return getPreferredRange(*this, CR, Type);
     }
     if (CR.Lower.ult(Lower)) {
+      // --U      L---- : this
+      //     L--U       : CR
       if (CR.Upper.ule(Lower))
         return getEmpty();
 
+      // --U      L---- : this
+      //     L------U   : CR
       return ConstantRange(Lower, CR.Upper);
     }
+
+    // --U  L------ : this
+    //        L--U  : CR
     return CR;
   }
 
   if (CR.Upper.ult(Upper)) {
-    if (CR.Lower.ult(Upper)) {
-      if (isSizeStrictlySmallerThan(CR))
-        return *this;
-      return CR;
-    }
+    // ------U L-- : this
+    // --U L------ : CR
+    if (CR.Lower.ult(Upper))
+      return getPreferredRange(*this, CR, Type);
 
+    // ----U   L-- : this
+    // --U   L---- : CR
     if (CR.Lower.ult(Lower))
       return ConstantRange(Lower, CR.Upper);
 
+    // ----U L---- : this
+    // --U     L-- : CR
     return CR;
   }
   if (CR.Upper.ule(Lower)) {
+    // --U     L-- : this
+    // ----U L---- : CR
     if (CR.Lower.ult(Lower))
       return *this;
 
+    // --U   L---- : this
+    // ----U   L-- : CR
     return ConstantRange(CR.Lower, Upper);
   }
-  if (isSizeStrictlySmallerThan(CR))
-    return *this;
-  return CR;
+
+  // --U L------ : this
+  // ------U L-- : CR
+  return getPreferredRange(*this, CR, Type);
 }
 
 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
   assert(getBitWidth() == CR.getBitWidth() &&
          "ConstantRange types don't agree!");
 
   if (   isFullSet() || CR.isEmptySet()) return *this;
   if (CR.isFullSet() ||    isEmptySet()) return CR;

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

EnumerateTwoConstantRanges(Bits,
           } else {
             HaveRange1 = true;
             Lower1 = Upper1 = Num;
           }
         }
 
         assert(!HaveInterrupt3 && "Should have at most three ranges");
 
-        ConstantRange CR = CR1.intersectWith(CR2);
+        ConstantRange SmallestCR =
+            CR1.intersectWith(CR2, ConstantRange::Smallest);
+        ConstantRange UnsignedCR =
+            CR1.intersectWith(CR2, ConstantRange::Unsigned);
+        ConstantRange SignedCR =
+            CR1.intersectWith(CR2, ConstantRange::Signed);
 
         if (!HaveRange1) {
-          EXPECT_TRUE(CR.isEmptySet());
+          EXPECT_TRUE(SmallestCR.isEmptySet());
+          EXPECT_TRUE(UnsignedCR.isEmptySet());
+          EXPECT_TRUE(SignedCR.isEmptySet());
           return;
         }
 
         if (!HaveRange2) {
           if (Lower1 == Upper1 + 1) {
-            EXPECT_TRUE(CR.isFullSet());
+            EXPECT_TRUE(SmallestCR.isFullSet());
+            EXPECT_TRUE(UnsignedCR.isFullSet());
+            EXPECT_TRUE(SignedCR.isFullSet());
           } else {
             ConstantRange Expected(Lower1, Upper1 + 1);
-            EXPECT_EQ(Expected, CR);
+            EXPECT_EQ(Expected, SmallestCR);
+            EXPECT_EQ(Expected, UnsignedCR);
+            EXPECT_EQ(Expected, SignedCR);
           }
           return;
         }
 
         ConstantRange Variant1(Bits, /*full*/ true);
         ConstantRange Variant2(Bits, /*full*/ true);
         if (!HaveRange3) {
           // Compute the two possible ways to cover two disjoint ranges.
           if (Lower1 != Upper2 + 1)
             Variant1 = ConstantRange(Lower1, Upper2 + 1);
           if (Lower2 != Upper1 + 1)
             Variant2 = ConstantRange(Lower2, Upper1 + 1);
         } else {
           // If we have three ranges, the first and last one have to be adjacent
           // to the unsigned domain. It's better to think of this as having two
           // holes, and we can construct one range using each hole.
           assert(Lower1.isNullValue() && Upper3.isMaxValue());
           Variant1 = ConstantRange(Lower2, Upper1 + 1);
           Variant2 = ConstantRange(Lower3, Upper2 + 1);
         }
 
-        // The intersection should return the smaller of the two variants.
+        // Smallest: Smaller set, then any set.
         if (Variant1.isSizeStrictlySmallerThan(Variant2))
-          EXPECT_EQ(Variant1, CR);
+          EXPECT_EQ(Variant1, SmallestCR);
         else if (Variant2.isSizeStrictlySmallerThan(Variant1))
-          EXPECT_EQ(Variant2, CR);
+          EXPECT_EQ(Variant2, SmallestCR);
         else
-          EXPECT_TRUE(Variant1 == CR || Variant2 == CR);
+          EXPECT_TRUE(Variant1 == SmallestCR || Variant2 == SmallestCR);
+
+        // Unsigned: Non-wrapped set, then smaller set, then any set.
+        bool Variant1Full = Variant1.isFullSet() || Variant1.isWrappedSet();
+        bool Variant2Full = Variant2.isFullSet() || Variant2.isWrappedSet();
+        if (!Variant1Full && Variant2Full)
+          EXPECT_EQ(Variant1, UnsignedCR);
+        else if (Variant1Full && !Variant2Full)
+          EXPECT_EQ(Variant2, UnsignedCR);
+        else if (Variant1.isSizeStrictlySmallerThan(Variant2))
+          EXPECT_EQ(Variant1, UnsignedCR);
+        else if (Variant2.isSizeStrictlySmallerThan(Variant1))
+          EXPECT_EQ(Variant2, UnsignedCR);
+        else
+          EXPECT_TRUE(Variant1 == UnsignedCR || Variant2 == UnsignedCR);
+
+        // Signed: Signed non-wrapped set, then smaller set, then any set.
+        Variant1Full = Variant1.isFullSet() || Variant1.isSignWrappedSet();
+        Variant2Full = Variant2.isFullSet() || Variant2.isSignWrappedSet();
+        if (!Variant1Full && Variant2Full)
+          EXPECT_EQ(Variant1, SignedCR);
+        else if (Variant1Full && !Variant2Full)
+          EXPECT_EQ(Variant2, SignedCR);
+        else if (Variant1.isSizeStrictlySmallerThan(Variant2))
+          EXPECT_EQ(Variant1, SignedCR);
+        else if (Variant2.isSizeStrictlySmallerThan(Variant1))
+          EXPECT_EQ(Variant2, SignedCR);
+        else
+          EXPECT_TRUE(Variant1 == SignedCR || Variant2 == SignedCR);
       });
 }
 
 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);