[ConstantRange] Fix isWrappedSet()

[nikic]

Summary

isWrappedSet() currently incorrectly returns true for ranges like i8 [42, 255], also known as i8 [42, 0). While a reasonable person might argue that the current behavior is correct if you interpret "wrapping" relative to the exclusive upper bound, the behavior is inconsistent with isSignWrappedSet() in two ways:

• While i8 [42, 0) is considered unsigned wrapping, i8 [42, -128) is not considered signed wrapping.
• The full set is not considered unsigned wrapping, but considered signed wrapping.

This patch changes isWrappedSet() and isSignWrappedSet() to behave consistently: They will both not consider 0/SignedMin upper bound as wrapping, and both not consider full sets as wrapping.

Additionally isUpperWrapped() and isUpperSignWrapped() methods are added which *do* consider 0/SignedMin as wrapping. Both interpretations of wrapping are useful depending on context, so both are provided.

[nikic]

llvm/lib/IR/ConstantRange.cpp

463

I should note that the use of isUpperWrapped() in this function is incorrect, I'm just using it to preserve the existing behavior. This function should be using isWrappedSet() and work on an inclusive upper bound. Right now it handles ranges with Upper=0 suboptimally. I will submit a followup for that.

[lebedev.ri]

This is a bit too low-level and intrusive than i feel comfortable reviewing..

It is best to split this up:

1. Rename isWrappedSet() into isUpperWrapped() (including all of it's uses). That would be an obvious, uncontroversial NFC commit.
2. Rename isSignWrappedSet() to something else like isSignWrappedSetLegacy(). NFC commit.
3. Introduce these 3 new functions. Also pretty much NFC.
4. The remaining of the patch

[lebedev.ri]

In D59749#1443675, @lebedev.ri wrote:

This is a bit too low-level and intrusive than i feel comfortable reviewing..

It is best to split this up:

1. Rename isWrappedSet() into isUpperWrapped() (including all of it's uses). That would be an obvious, uncontroversial NFC commit.
2. Rename isSignWrappedSet() to something else like isSignWrappedSetLegacy(). NFC commit.
3. Introduce these 3 new functions. Also pretty much NFC.
4. The remaining of the patch

.. or, if isSignWrappedSet() change is NFC, then that can be [yet another] NFC commit after Introduce these new functions diff.

[nikic]

After applying the other changes in rL357039, rL357107 and rL357112 there isn't really much left here. Could change one or two uses of isUpperWrapped() back to isWrappedSet() because it is the same in the used context...

[lebedev.ri]

In D59749#1445032, @nikic wrote:

After applying the other changes in rL357039, rL357107 and rL357112

Thanks!
Those three small diffs are oh so much better than this huge monolithic patch.

there isn't really much left here. Could change one or two uses of isUpperWrapped() back to isWrappedSet() because it is the same in the used context...

That sounds like a good cleanup to me, if you feel like it.

[lebedev.ri]

In D59749#1445202, @lebedev.ri wrote:

there isn't really much left here. Could change one or two uses of isUpperWrapped() back to isWrappedSet() because it is the same in the used context...

That sounds like a good cleanup to me, if you feel like it.

This differential basically fully landed.
Should be either abandoned, or rebased to contain the cleanup part.

[nikic]

Abandoning this one, don't think there's anything worthwhile left here.

llvm/include/llvm/IR/ConstantRange.h

public:
 
   /// Return true if this set contains all of the elements possible
   /// for this data-type.
   bool isFullSet() const;
 
   /// Return true if this set contains no members.
   bool isEmptySet() const;
 
-  /// Return true if this set wraps around the top of the range.
-  /// For example: [100, 8).
+  /// Return true if this set wraps around the unsigned domain. Special cases:
+  ///  * Empty set: Not wrapped.
+  ///  * Full set: Not wrapped.
+  ///  * [X, 0) == [X, Max]: Not wrapped.
   bool isWrappedSet() const;
 
-  /// Return true if this set wraps around the INT_MIN of
-  /// its bitwidth. For example: i8 [120, 140).
+  /// Return true if this set wraps around the signed domain. Special cases:
+  ///  * Empty set: Not wrapped.
+  ///  * Full set: Not wrapped.
+  ///  * [X, SignedMin) == [X, SignedMax]: Not wrapped.
   bool isSignWrappedSet() const;
 
+  /// Return true if the exclusive upper bound wraps around the unsigned
+  /// domain. Special cases:
+  ///  * Empty set: Not wrapped.
+  ///  * Full set: Not wrapped.
+  ///  * [X, 0): Wrapped.
+  bool isUpperWrapped() const;
+
+  /// Return true if the (exclusive) upper bound wraps around the signed
+  /// domain. Special cases:
+  ///  * Empty set: Not wrapped.
+  ///  * Full set: Not wrapped.
+  ///  * [X, SignedMin): Wrapped.
+  bool isUpperSignWrapped() const;
+
   /// Return true if the specified value is in the set.
   bool contains(const APInt &Val) const;
 
   /// Return true if the other range is a subset of this one.
   bool contains(const ConstantRange &CR) const;
 
   /// If this set contains a single element, return it, otherwise return null.
   const APInt *getSingleElement() const {

llvm/lib/IR/ConstantRange.cpp

bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
 
 bool ConstantRange::isEmptySet() const {
   return Lower == Upper && Lower.isMinValue();
 }
 
 bool ConstantRange::isWrappedSet() const {
-  return Lower.ugt(Upper);
+  return Lower.ugt(Upper) && !Upper.isNullValue();
 }
 
 bool ConstantRange::isSignWrappedSet() const {
-  return contains(APInt::getSignedMaxValue(getBitWidth())) &&
-         contains(APInt::getSignedMinValue(getBitWidth()));
+  return Lower.sgt(Upper) && !Upper.isMinSignedValue();
+}
+
+bool ConstantRange::isUpperWrapped() const {
+  return Lower.ugt(Upper);
+}
+
+bool ConstantRange::isUpperSignWrapped() const {
+  return Lower.sgt(Upper);
 }
 
 APInt ConstantRange::getSetSize() const {
   if (isFullSet())
     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
 
   // This is also correct for wrapped sets.
   return (Upper - Lower).zext(getBitWidth()+1);
ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
   // to represent the size.
   if (isFullSet())
     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
 
   return (Upper - Lower).ugt(MaxSize);
 }
 
 APInt ConstantRange::getUnsignedMax() const {
-  if (isFullSet() || isWrappedSet())
+  if (isFullSet() || isUpperWrapped())
     return APInt::getMaxValue(getBitWidth());
   return getUpper() - 1;
 }
 
 APInt ConstantRange::getUnsignedMin() const {
-  if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
+  if (isFullSet() || isWrappedSet())
     return APInt::getMinValue(getBitWidth());
   return getLower();
 }
 
 APInt ConstantRange::getSignedMax() const {
-  if (isFullSet() || Lower.sgt(Upper))
+  if (isFullSet() || isUpperSignWrapped())
     return APInt::getSignedMaxValue(getBitWidth());
   return getUpper() - 1;
 }
 
 APInt ConstantRange::getSignedMin() const {
-  if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
+  if (isFullSet() || isSignWrappedSet())
     return APInt::getSignedMinValue(getBitWidth());
   return getLower();
 }
 
 bool ConstantRange::contains(const APInt &V) const {
   if (Lower == Upper)
     return isFullSet();
 
-  if (!isWrappedSet())
+  if (!isUpperWrapped())
     return Lower.ule(V) && V.ult(Upper);
   return Lower.ule(V) || V.ult(Upper);
 }
 
 bool ConstantRange::contains(const ConstantRange &Other) const {
   if (isFullSet() || Other.isEmptySet()) return true;
   if (isEmptySet() || Other.isFullSet()) return false;
 
-  if (!isWrappedSet()) {
-    if (Other.isWrappedSet())
+  if (!isUpperWrapped()) {
+    if (Other.isUpperWrapped())
       return false;
 
     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
   }
 
-  if (!Other.isWrappedSet())
+  if (!Other.isUpperWrapped())
     return Other.getUpper().ule(Upper) ||
            Lower.ule(Other.getLower());
 
   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
 }
 
 ConstantRange ConstantRange::subtract(const APInt &Val) const {
   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");

 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) 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 (!isWrappedSet() && CR.isWrappedSet())
+  if (!isUpperWrapped() && CR.isUpperWrapped())
     return CR.intersectWith(*this);
 
-  if (!isWrappedSet() && !CR.isWrappedSet()) {
+  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
     if (Lower.ult(CR.Lower)) {
       if (Upper.ule(CR.Lower))
         return ConstantRange(getBitWidth(), false);
 
       if (Upper.ult(CR.Upper))
         return ConstantRange(CR.Lower, Upper);
 
       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 (isUpperWrapped() && !CR.isUpperWrapped()) {
     if (CR.Lower.ult(Upper)) {
       if (CR.Upper.ult(Upper))
         return CR;
 
       if (CR.Upper.ule(Lower))
         return ConstantRange(CR.Lower, Upper);
 
       if (isSizeStrictlySmallerThan(CR))

 
 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;
 
-  if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
+  if (!isUpperWrapped() && CR.isUpperWrapped()) return CR.unionWith(*this);
 
-  if (!isWrappedSet() && !CR.isWrappedSet()) {
+  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
       // If the two ranges are disjoint, find the smaller gap and bridge it.
       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
       if (d1.ult(d2))
         return ConstantRange(Lower, CR.Upper);
       return ConstantRange(CR.Lower, Upper);
     }
 
     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
 
     if (L.isNullValue() && U.isNullValue())
       return ConstantRange(getBitWidth());
 
     return ConstantRange(std::move(L), std::move(U));
   }
 
-  if (!CR.isWrappedSet()) {
+  if (!CR.isUpperWrapped()) {
     // ------U   L-----  and  ------U   L----- : this
     //   L--U                            L--U  : CR
     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
       return *this;
 
     // ------U   L----- : this
     //    L---------U   : CR
     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
   };
 }
 
 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 
   unsigned SrcTySize = getBitWidth();
   assert(SrcTySize < DstTySize && "Not a value extension");
-  if (isFullSet() || isWrappedSet()) {
+  if (isFullSet() || isUpperWrapped()) {
     // Change into [0, 1 << src bit width)
     APInt LowerExt(DstTySize, 0);
     if (!Upper) // special case: [X, 0) -- not really wrapping around
       LowerExt = Lower.zext(DstTySize);
     return ConstantRange(std::move(LowerExt),
                          APInt::getOneBitSet(DstTySize, SrcTySize));
   }
 
   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
 }
 
 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 
   unsigned SrcTySize = getBitWidth();
   assert(SrcTySize < DstTySize && "Not a value extension");
 
   // special case: [X, INT_MIN) -- not really wrapping around
   if (Upper.isMinSignedValue())
     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
 
-  if (isFullSet() || isSignWrappedSet()) {
+  if (isFullSet() || isUpperSignWrapped()) {
     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
   }
 
   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
 }
 
 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
   assert(getBitWidth() > DstTySize && "Not a value truncation");
   if (isEmptySet())
     return ConstantRange(DstTySize, /*isFullSet=*/false);
   if (isFullSet())
     return ConstantRange(DstTySize, /*isFullSet=*/true);
 
   APInt LowerDiv(Lower), UpperDiv(Upper);
   ConstantRange Union(DstTySize, /*isFullSet=*/false);
 
   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
   // then we do the union with [MaxValue, Upper)
-  if (isWrappedSet()) {
+  if (isUpperWrapped()) {
     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
     // truncated range.
     if (Upper.getActiveBits() > DstTySize ||
         Upper.countTrailingOnes() == DstTySize)
       return ConstantRange(DstTySize, /*isFullSet=*/true);
 
     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
     UpperDiv.setAllBits();
ConstantRange::multiply(const ConstantRange &Other) const {
   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
                                             this_max * Other_max + 1);
   ConstantRange UR = Result_zext.truncate(getBitWidth());
 
   // If the unsigned range doesn't wrap, and isn't negative then it's a range
   // from one positive number to another which is as good as we can generate.
   // In this case, skip the extra work of generating signed ranges which aren't
   // going to be better than this range.
-  if (!UR.isWrappedSet() &&
+  if (!UR.isUpperWrapped() &&
       (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
     return UR;
 
   // Now the signed range. Because we could be dealing with negative numbers
   // here, the lower bound is the smallest of the cartesian product of the
   // lower and upper ranges; for example:
   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
   // Similarly for the upper bound, swapping min for max.

llvm/unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
   EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
 
   // Found by Klee
   EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
             APInt(4, 7));
 }
 
 TEST_F(ConstantRangeTest, SignWrapped) {
-  EXPECT_TRUE(Full.isSignWrappedSet());
+  EXPECT_FALSE(Full.isSignWrappedSet());
   EXPECT_FALSE(Empty.isSignWrappedSet());
   EXPECT_FALSE(One.isSignWrappedSet());
   EXPECT_FALSE(Some.isSignWrappedSet());
   EXPECT_TRUE(Wrap.isSignWrappedSet());
 
   EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
   EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
   EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
   EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
   EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
   EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
   EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
 }
 
+TEST_F(ConstantRangeTest, UpperWrapped) {
+  // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
+  EXPECT_FALSE(Full.isUpperWrapped());
+  EXPECT_FALSE(Empty.isUpperWrapped());
+  EXPECT_FALSE(One.isUpperWrapped());
+  EXPECT_FALSE(Some.isUpperWrapped());
+  EXPECT_TRUE(Wrap.isUpperWrapped());
+  EXPECT_FALSE(Full.isUpperSignWrapped());
+  EXPECT_FALSE(Empty.isUpperSignWrapped());
+  EXPECT_FALSE(One.isUpperSignWrapped());
+  EXPECT_FALSE(Some.isUpperSignWrapped());
+  EXPECT_TRUE(Wrap.isUpperSignWrapped());
+
+  // The behavior differs if Upper is the Min/SignedMin value.
+  ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8));
+  EXPECT_FALSE(CR1.isWrappedSet());
+  EXPECT_TRUE(CR1.isUpperWrapped());
+
+  ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8));
+  EXPECT_FALSE(CR2.isSignWrappedSet());
+  EXPECT_TRUE(CR2.isUpperSignWrapped());
+}
+
 TEST_F(ConstantRangeTest, Trunc) {
   ConstantRange TFull = Full.truncate(10);
   ConstantRange TEmpty = Empty.truncate(10);
   ConstantRange TOne = One.truncate(10);
   ConstantRange TSome = Some.truncate(10);
   ConstantRange TWrap = Wrap.truncate(10);
   EXPECT_TRUE(TFull.isFullSet());
   EXPECT_TRUE(TEmpty.isEmptySet());