[CR][WIP] Add `subWithNoWrap()` method

[lebedev.ri]

Summary

Much like D67339, adds ConstantRange handling for
when we know no-wrap behavior of the sub.

This is WIP, just barely working enough to post.

As noted in https://reviews.llvm.org/D67339#inline-629306,
there is something wrong with the exhaustive tests,
Those overflow checks in addWithNoWrap() aren't needed,
as per test coverage.

Even if i add a check `if every permutation
of ForeachNumInConstantRange()*ForeachNumInConstantRange()` says
there's overflow, then ConstantRange::*WithNoWrap() should
have returned Empty set, those overflow checks
are still not needed for add. One check is needed for sub though.

So, what is the missing check?

[nikic]

@lebedev.ri I suspect this is due to the intersection with the raw add() range. Maybe it happens that the intersection between add() and [MAX, MAX] is always empty in the case where the overflow check triggers? Can you try removing that intersection and see what happens?

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

[lebedev.ri]

In D69918#1736111, @nikic wrote:

@lebedev.ri I suspect this is due to the intersection with the raw add() range. Maybe it happens that the intersection between add() and [MAX, MAX] is always empty in the case where the overflow check triggers? Can you try removing that intersection and see what happens?

Ah, that appears to be the case:

diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index 21a93b723b7..6e0c388aaa9 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -882,8 +882,16 @@ ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
 
   if (NoWrapKind & OBO::NoSignedWrap)
     Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType);
-  if (NoWrapKind & OBO::NoUnsignedWrap)
+  if (NoWrapKind & OBO::NoUnsignedWrap) {
     Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType);
+
+    APInt LMin = getUnsignedMin(), LMax = getUnsignedMax();
+    APInt RMin = Other.getUnsignedMin(), RMax = Other.getUnsignedMax();
+    bool Overflow;
+    APInt NewMin = LMin.uadd_ov(RMin, Overflow);
+    if(Overflow)
+      assert(Result.isEmptySet());
+  }
   return Result;
 }

Didn't check signed case.

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

Now that i've added EXPECT_EQ(CR.isEmptySet(), AllOverflow); test,
that seems like a safe assumption to me? Seems like a net win to me.

[nikic]

In D69918#1736118, @lebedev.ri wrote:

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

Now that i've added EXPECT_EQ(CR.isEmptySet(), AllOverflow); test,
that seems like a safe assumption to me? Seems like a net win to me.

I guess it's okay, please add a comment to the implementation that we're relying on this lucky accident though. You might also want to piggy-back on the existing CR.uadd_sat and CR.sadd_sat implementations, now that the code is essentially the same.

[lebedev.ri]

In D69918#1736126, @nikic wrote:

In D69918#1736118, @lebedev.ri wrote:

If that's the case, I'm not sure whether or not we should rely on that, it seems rather subtle.

Now that i've added EXPECT_EQ(CR.isEmptySet(), AllOverflow); test,
that seems like a safe assumption to me? Seems like a net win to me.

I guess it's okay, please add a comment to the implementation that we're relying on this lucky accident though.

You might also want to piggy-back on the existing CR.uadd_sat and CR.sadd_sat implementations, now that the code is essentially the same.

D'oh! So *that's* why all that code looked weird to me. Now this is much better i think :)

[nikic]

LGTM. addWithNoWrap() has some more tests for specific inputs, but I don't think we really need them here.

llvm/lib/IR/ConstantRange.cpp

869

interception -> intersection

I'd may write "that intersection of add() with uadd_sat()/sadd_sat() results in an empty set", as it's not necessary the MAX bound.

[nikic]

llvm/lib/IR/ConstantRange.cpp

925

As we're not using the NewMax result here (doesn't this warn?) you might want to write this as if (getUnsignedMax().ult(Other.getUnsignedMin())), as the overflow condition for usub is trivial...

[lebedev.ri]

In D69918#1736201, @nikic wrote:

LGTM. addWithNoWrap() has some more tests for specific inputs, but I don't think we really need them here.

Well, okay then.
Thank you for the review!

[lebedev.ri]

(will follow up with LVI later; not sure about SCEV)

llvm/include/llvm/IR/ConstantRange.h

public:
   ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
                               PreferredRangeType RangeType = Smallest) const;
 
   /// Return a new range representing the possible values resulting
   /// from a subtraction of a value in this range and a value in \p Other.
   ConstantRange sub(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
+  /// from an subtraction with wrap type \p NoWrapKind of a value in this
+  /// range and a value in \p Other.
+  /// If the result range is disjoint, the preferred range is determined by the
+  /// \p PreferredRangeType.
+  ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
+                              PreferredRangeType RangeType = Smallest) const;
+
+  /// Return a new range representing the possible values resulting
   /// from a multiplication of a value in this range and a value in \p Other,
   /// treating both this and \p Other as unsigned ranges.
   ConstantRange multiply(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from a signed maximum of a value in this range and a value in \p Other.
   ConstantRange smax(const ConstantRange &Other) const;
 

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
   if (isFullSet() && Other.isFullSet())
     return getFull();
 
   using OBO = OverflowingBinaryOperator;
   ConstantRange Result = add(Other);
 
-  auto addWithNoUnsignedWrap = [this](const ConstantRange &Other) {
-    APInt LMin = getUnsignedMin(), LMax = getUnsignedMax();
-    APInt RMin = Other.getUnsignedMin(), RMax = Other.getUnsignedMax();
-    bool Overflow;
-    APInt NewMin = LMin.uadd_ov(RMin, Overflow);
-    if (Overflow)
-      return getEmpty();
-    APInt NewMax = LMax.uadd_sat(RMax);
-    return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1);
-  };
-
-  auto addWithNoSignedWrap = [this](const ConstantRange &Other) {
-    APInt LMin = getSignedMin(), LMax = getSignedMax();
-    APInt RMin = Other.getSignedMin(), RMax = Other.getSignedMax();
-    if (LMin.isNonNegative()) {
-      bool Overflow;
-      APInt Temp = LMin.sadd_ov(RMin, Overflow);
-      if (Overflow)
-        return getEmpty();
-    }
-    if (LMax.isNegative()) {
-      bool Overflow;
-      APInt Temp = LMax.sadd_ov(RMax, Overflow);
-      if (Overflow)
-        return getEmpty();
-    }
-    APInt NewMin = LMin.sadd_sat(RMin);
-    APInt NewMax = LMax.sadd_sat(RMax);
-    return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1);
-  };
+  // If an overflow happens for every value pair in these two constant ranges,
+  // we must return Empty set. In this case, we get that for free, because we
+  // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
+  // in an empty set.
 
   if (NoWrapKind & OBO::NoSignedWrap)
-    Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType);
+    Result = Result.intersectWith(sadd_sat(Other), RangeType);
+
   if (NoWrapKind & OBO::NoUnsignedWrap)
-    Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType);
+    Result = Result.intersectWith(uadd_sat(Other), RangeType);
+
   return Result;
 }
 
 ConstantRange
 ConstantRange::sub(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
   if (isFullSet() || Other.isFullSet())
     return getFull();
 
   APInt NewLower = getLower() - Other.getUpper() + 1;
   APInt NewUpper = getUpper() - Other.getLower();
   if (NewLower == NewUpper)
     return getFull();
 
   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
   if (X.isSizeStrictlySmallerThan(*this) ||
       X.isSizeStrictlySmallerThan(Other))
     // We've wrapped, therefore, full set.
     return getFull();
   return X;
 }
 
+ConstantRange ConstantRange::subWithNoWrap(const ConstantRange &Other,
+                                           unsigned NoWrapKind,
+                                           PreferredRangeType RangeType) const {
+  // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
+  // (X is from this, and Y is from Other)
+  if (isEmptySet() || Other.isEmptySet())
+    return getEmpty();
+  if (isFullSet() && Other.isFullSet())
+    return getFull();
+
+  using OBO = OverflowingBinaryOperator;
+  ConstantRange Result = sub(Other);
+
+  // If an overflow happens for every value pair in these two constant ranges,
+  // we must return Empty set. In signed case, we get that for free, because we
+  // get lucky that intersection of add() with ssub_sat() results in an
+  // empty set. But for unsigned we must perform the overflow check manually.
+
+  if (NoWrapKind & OBO::NoSignedWrap)
+    Result = Result.intersectWith(ssub_sat(Other), RangeType);
+
+  if (NoWrapKind & OBO::NoUnsignedWrap) {
+    if (getUnsignedMax().ult(Other.getUnsignedMin()))
+      return getEmpty();
+    Result = Result.intersectWith(usub_sat(Other), RangeType);
+  }
+
+  return Result;
+}
+
 ConstantRange
 ConstantRange::multiply(const ConstantRange &Other) const {
   // TODO: If either operand is a single element and the multiply is known to
   // be non-wrapping, round the result min and max value to the appropriate
   // multiple of that element. If wrapping is possible, at least adjust the
   // range according to the greatest power-of-two factor of the single element.
 
   if (isEmptySet() || Other.isEmptySet())

llvm/unittests/IR/ConstantRangeTest.cpp

 template <typename Fn1, typename Fn2>
 static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
     ConstantRange CR = RangeFn(CR1, CR2);
     APInt Min = APInt::getSignedMaxValue(Bits);
     APInt Max = APInt::getSignedMinValue(Bits);
+    bool AllOverflow = true;
     ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
       ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
         bool IsOverflow = false;
         APInt N = IntFn(IsOverflow, N1, N2);
         if (!IsOverflow) {
+          AllOverflow = false;
           if (N.slt(Min))
             Min = N;
           if (N.sgt(Max))
             Max = N;
           EXPECT_TRUE(CR.contains(N));
         }
       });
     });
+
+    EXPECT_EQ(CR.isEmptySet(), AllOverflow);
+
     if (!CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) {
       if (Min.sgt(Max)) {
         EXPECT_TRUE(CR.isEmptySet());
         return;
       }
 
       ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
       EXPECT_EQ(Exact, CR);
     }
   });
 }
 
 template <typename Fn1, typename Fn2>
 static void TestAddWithNoUnsignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
     ConstantRange CR = RangeFn(CR1, CR2);
     APInt Min = APInt::getMaxValue(Bits);
     APInt Max = APInt::getMinValue(Bits);
+    bool AllOverflow = true;
     ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
       ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
         bool IsOverflow = false;
         APInt N = IntFn(IsOverflow, N1, N2);
         if (!IsOverflow) {
+          AllOverflow = false;
           if (N.ult(Min))
             Min = N;
           if (N.ugt(Max))
             Max = N;
           EXPECT_TRUE(CR.contains(N));
         }
       });
     });
 
+    EXPECT_EQ(CR.isEmptySet(), AllOverflow);
+
     if (!CR1.isWrappedSet() && !CR2.isWrappedSet()) {
       if (Min.ugt(Max)) {
         EXPECT_TRUE(CR.isEmptySet());
         return;
       }
 
       ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
       EXPECT_EQ(Exact, CR);
     }
   });
 }
 
 template <typename Fn1, typename Fn2, typename Fn3>
 static void TestAddWithNoSignedUnsignedWrapExhaustive(Fn1 RangeFn,
                                                       Fn2 IntFnSigned,
                                                       Fn3 IntFnUnsigned) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(
       Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) {
         ConstantRange CR = RangeFn(CR1, CR2);
         APInt UMin = APInt::getMaxValue(Bits);
         APInt UMax = APInt::getMinValue(Bits);
         APInt SMin = APInt::getSignedMaxValue(Bits);
         APInt SMax = APInt::getSignedMinValue(Bits);
+        bool AllOverflow = true;
         ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
           ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
             bool IsOverflow = false, IsSignedOverflow = false;
             APInt N = IntFnSigned(IsSignedOverflow, N1, N2);
             (void) IntFnUnsigned(IsOverflow, N1, N2);
             if (!IsSignedOverflow && !IsOverflow) {
+              AllOverflow = false;
               if (N.slt(SMin))
                 SMin = N;
               if (N.sgt(SMax))
                 SMax = N;
               if (N.ult(UMin))
                 UMin = N;
               if (N.ugt(UMax))
                 UMax = N;
               EXPECT_TRUE(CR.contains(N));
             }
           });
         });
 
+        EXPECT_EQ(CR.isEmptySet(), AllOverflow);
+
         if (!CR1.isWrappedSet() && !CR2.isWrappedSet() &&
             !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) {
           if (UMin.ugt(UMax) || SMin.sgt(SMax)) {
             EXPECT_TRUE(CR.isEmptySet());
             return;
           }
 
           ConstantRange Exact =
TEST_F(ConstantRangeTest, Sub) {
   EXPECT_EQ(Some.sub(Some),
             ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
   EXPECT_EQ(Wrap.sub(APInt(16, 4)),
             ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
   EXPECT_EQ(One.sub(APInt(16, 4)),
             ConstantRange(APInt(16, 0x6)));
 }
 
+TEST_F(ConstantRangeTest, SubWithNoWrap) {
+  typedef OverflowingBinaryOperator OBO;
+  TestAddWithNoSignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.subWithNoWrap(CR2, OBO::NoSignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.ssub_ov(N2, IsOverflow);
+      });
+  TestAddWithNoUnsignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.usub_ov(N2, IsOverflow);
+      });
+  TestAddWithNoSignedUnsignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.ssub_ov(N2, IsOverflow);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.usub_ov(N2, IsOverflow);
+      });
+}
+
 TEST_F(ConstantRangeTest, Multiply) {
   EXPECT_EQ(Full.multiply(Full), Full);
   EXPECT_EQ(Full.multiply(Empty), Empty);
   EXPECT_EQ(Full.multiply(One), Full);
   EXPECT_EQ(Full.multiply(Some), Full);
   EXPECT_EQ(Full.multiply(Wrap), Full);
   EXPECT_EQ(Empty.multiply(Empty), Empty);
   EXPECT_EQ(Empty.multiply(One), Empty);