[ConstantRange] add helper function addWithNoWrap

[shchenz]

Summary

Currently there is only an add function for constant range without considering wrap flag. It may produce a conservative range.
For example, currently, full_set +nsw [1,3) will get full_set. But right range should be [SINT_MIN + 1, SINT_MIN)
Add a helper function to consider wrap flag, so we can get a more accurate range.

This is splitted from https://reviews.llvm.org/D64869.

[lebedev.ri]

It would be really good to add exaustive tests for this, see TestUnsignedBinOpExhaustive / TestSignedBinOpExhaustive / TestNoWrapRegionExhaustive / TestOverflowExhaustive.

[nikic]

The implementation looks correct to me. As @lebedev.ri mentioned we usually add exhaustive tests for ConstantRange methods nowadays. I'm not totally sure what should be tested here... I guess we should test a) conservative correctness (no wrong results produced) and b) tight bounds if the input sets are non-wrapping/non-sign-wrapping.

llvm/include/llvm/IR/ConstantRange.h

338 ↗

(On Diff #219286)

My preference would be to add this as an optional argument to add() instead. In the future, we'll likely want to accept NoWrapKind on more methods, and also thread it through binaryOp().

llvm/lib/IR/ConstantRange.cpp

833 ↗

(On Diff #219286)

I think we should also accept OBO::NoSignedWrap|OBO::NoUnsignedWrap here. This would allow directly passing through nowrap flags in LVI.

Possibly this can be implemented by computing both the nuw and the nsw result and intersecting both?

844 ↗

(On Diff #219286)

As this is a method on ConstantRange you can just write return getEmpty(); here.

[lebedev.ri]

In D67339#1663764, @nikic wrote:

The implementation looks correct to me. As @lebedev.ri mentioned we usually add exhaustive tests for ConstantRange methods nowadays.

I'm not totally sure what should be tested here... I guess we should test a) conservative correctness (no wrong results produced) and b) tight bounds if the input sets are non-wrapping/non-sign-wrapping.

That is what i was suggesting, yes; thought quick glance through code suggests that only a. can be enforced for the diff as present.

[lebedev.ri]

(marking as reviewed)

[shchenz]

address @nikic @lebedev.ri comments

[shchenz]

Sorry for the delay. Ready for further review.

llvm/include/llvm/IR/ConstantRange.h

338 ↗

(On Diff #219286)

Can I do it later in another seperated patch? I want to make this patch as small as possible. Combining with current add may introduce potential issue?

llvm/lib/IR/ConstantRange.cpp

833 ↗

(On Diff #219286)

I think there is no necessary for us to support OBO::NoSignedWrap|OBO::NoUnsignedWrap . We have different signed and unsigned ranges for one SCEV and we can only query one type range(Unsigned range or Signed range) for one time. Also we set nsw only based on signed range and nuw only based on unsigned range. Intersecting signed and unsigned range may get wrong result for SCEV's range if we use this intersecting range for signed/unsigned range. For example, if one ADDSCEV's signed range is [-10, 5), and its unsigned range is [10, 20), in StrengthenNoWrapFlags, we will set this SCEV with nsw and nuw. So we get Intersecting range is empty-set, if we use this range as signed range or unsigned range, we get empty-set, this should be wrong?

[nikic]

llvm/include/llvm/IR/ConstantRange.h

338 ↗

(On Diff #219286)

Sure, we can do that separately.

llvm/lib/IR/ConstantRange.cpp

833 ↗

(On Diff #219286)

I think there is no necessary for us to support OBO::NoSignedWrap|OBO::NoUnsignedWrap . We have different signed and unsigned ranges for one SCEV and we can only query one type range(Unsigned range or Signed range) for one time. Also we set nsw only based on signed range and nuw only based on unsigned range.

The addWithNoWrap() functionality is also useful outside of SCEV. LVI, which is used by CVP, does not distinguish between signed and unsigned ranges. It would simply pass through the nowrap flags on the (IR-level) add operation. It would be odd if analysis quality would decrease if an add had both nuw/nsw, rather than only one of them.

Intersecting signed and unsigned range may get wrong result for SCEV's range if we use this intersecting range for signed/unsigned range. For example, if one ADDSCEV's signed range is [-10, 5), and its unsigned range is [10, 20), in StrengthenNoWrapFlags, we will set this SCEV with nsw and nuw. So we get Intersecting range is empty-set, if we use this range as signed range or unsigned range, we get empty-set, this should be wrong?

Getting an empty set is correct in this case. The unsigned and signed SCEV ranges are *both* (conseratively) correct and the real range will be a subset of their intersection.

In D64869, you're using the addNoWrap() functionality by only setting nuw if both the add is nuw and the preferred range type is unsigned (and same for signed). I think this makes sense as a conservative choice that avoids regressions, but generally these are really orthogonal: The nowrap flags and the preferred signedness are independent concepts and may be mixed.

I think the ideal design here would actually be to expose both as separate arguments, nowrap using OBO flags and signedness using ConstantRange::PreferredRangeType:

ConstantRange addWithNoWrap(
    const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType);

In this case the implementation could, at a high level, look something like this:

// Normal wrapping addition as baseline.
ConstantRange Res = add(Other);
if (NoWrapKind & NUW) {
    // Intersect in NUW addition based on getUnsignedMin/Max().
    Res = Res.intersect(addNUW(Other), RangeType);
}
if (NoWrapKind == NSW) {
    // Intersect in NSW addition based on getSignedMin/Max().
    Res = Res.intersect(addNSW(Other), RangeType);
}
return Res;

I think this is both flexible in terms of how it may be used, and intuitive in how it works/behaves.

To take a specific example, consider an add nuw nsw i4 [0, 3], [5, 7]:

add: [5, 10]
addNUW: [5, 10]
addNSW: [5, 7]
intersection: [5, 7] (independent of sign preference in this case)

If this was a SCEV with an unsigned preference, then taking just the nuw flag would have given us a worse result than considering both. Even for the unsigned range, the nsw flag still provides useful information.

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

701 ↗

(On Diff #220286)

The logic here seems unnecessary complicated to me. Couldn't we do something like this?

bool IsOverflow = false;
APInt N = IntFn(IsOverflow, N1, N2);
if (!IsOverflow) {
    if (N.sle(Min))
        Min = N;
    if (N.sge(Max))
        Max = N;
}

here, and use just sadd_ov() (without sadd_sat) in IntFn? The empty set case can be checked as if (Min.sgt(Max)) EXPECT_TRUE(CR.isEmptySet()); I believe.

[shchenz]

address @nikic comments

[shchenz]

Hi @nikic, thanks for your comments. Could you help to have another look?

llvm/unittests/IR/ConstantRangeTest.cpp

701 ↗

(On Diff #220286)

Good idea.

[nikic]

Two more notes, otherwise this looks good to me :) @lebedev.ri Anything to add?

llvm/lib/IR/ConstantRange.cpp

834 ↗

(On Diff #221693)

You can remove the check for isWrappedSet / isSignWrappedSet now. We're going to intersect with the add() result anyway, so this is just going to intersect with itself. Even if one of the ranges is wrapped, we might still get a better result here if the other isn't. E.g. something like [10, MAX] + Wrapped will still get you [10, MAX] as the result here, which is likely better than what the wrapped calculation will provide.

llvm/unittests/IR/ConstantRangeTest.cpp

712 ↗

(On Diff #221693)

Rather than skipping these entirely, you can still check that the result is correct, even if not minimal. Something like this:

ConstantRange CR = RangeFn(CR1, CR2);
//... Loop
if (!IsOverflow) {
  // ... Collect Min/Max
  EXPECT_TRUE(CR.contains(N));
}

if (!CR1.isWrappedSet() && !CR2.isWrappedSet()) {
    // ... Do the exact check here
}

[shchenz]

llvm/lib/IR/ConstantRange.cpp

834 ↗

(On Diff #221693)

I am a little confuse about removing the check for isWrappedSet / isSignWrappedSet.
Assuming we have two unsigned ranges [10, 20), [200, 100), if we remove the check for wrap, we get [10, 20) as result.

But if we do the math, [10, 20) +nuw [200, 100) results in two disjoint ranges [10, 119) \/ [210, 0).
My previous is a little like getPreferredRange, we choose one range from above disjoint ranges based on preferred type.

If we use [10, 20), will it be too aggresive, since we use a smaller range?
If we use add result for wrap range, we get [210, 119) as result which is father range of "[10, 119) \/ [210, 0)", it is conservative but right?

[nikic]

llvm/lib/IR/ConstantRange.cpp

834 ↗

(On Diff #221693)

Assuming we have two unsigned ranges [10, 20), [200, 100), if we remove the check for wrap, we get [10, 20) as result.

In this case, you should get [10, 0) as the result. The wrapped range will be treated as a full range by getUnsignedMin() and getUnsignedMax(), so this is the same as doing [10, 20) + full.

Additionally, as you say, you will get [210, 119) from the normal add. These are then intersected and you will get back either [10, 0) (if there is an unsigned preference) or [210, 119) (if there is a smallest range preference). For SCEV, getting [10, 0) back will be more useful than getting the wrapped range back.

[shchenz]

address @nikic comments

[shchenz]

In this case, you should get [10, 0) as the result. The wrapped range will be treated as a full range by getUnsignedMin() and getUnsignedMax(), so this is the same as doing [10, 20) + full.

Ah, right, it should get [10, 0). my bad...

[nikic]

LGTM

llvm/unittests/IR/ConstantRangeTest.cpp

767 ↗

(On Diff #222375)

This should also check for EXPECT_TRUE(CR.contains(N)), if both overflow flags are false. Because N must be the same for both operations, it might make sense to not have two separate branches, that is:

bool IsSignedOverflow, IsUnsignedOverflow;
APInt N = IntFnSigned(IsSignedOverflow, N1, N2);
(void) IntFnUnsigned(IsSignedOverflow, N1, N2);
if (!IsSignedOverflow && !IsUnsignedOverflow) {
  // Compute SMin, SMax, UMin, UMax
  EXPECT_TRUE(CR.contains(N));
}

[shchenz]

Thanks very much for your helpful review @nikic

[lebedev.ri]

llvm/trunk/lib/IR/ConstantRange.cpp

834–856

@nikic @shchenz
So i'm trying to look into sub variant, and i'm missing a subtlety here.

In addWithNoSignedWrap() why those overflow checks are needed?
All tests pass without them.

In addWithNoUnsignedWrap() why is that overflow check needed?
All tests pass without it (with it replaced with uadd_sat)

[nikic]

llvm/trunk/lib/IR/ConstantRange.cpp

834–856

[i8 200, i8 200] add nuw [i8 200, i8 200] should result in empty-set rather than [i8 255, i8 255], this is what the overflow check is for.

Not sure why there is not test failure, I'd expect one of the EXPECT_TRUE(CR.isEmptySet()) checks to fail.

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

public:
   /// of this range and a right hand side of \p Other.
   ConstantRange binaryOp(Instruction::BinaryOps BinOp,
                          const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from an addition of a value in this range and a value in \p Other.
   ConstantRange add(const ConstantRange &Other) const;
 
+  /// Return a new range representing the possible values resulting
+  /// from an addition 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 addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind,
+                              PreferredRangeType RangeType = Smallest) const;
+
   /// Return a new range representing the possible values resulting from a
   /// known NSW addition of a value in this range and \p Other constant.
   ConstantRange addWithNoSignedWrap(const APInt &Other) 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;
 

llvm/trunk/lib/IR/ConstantRange.cpp

ConstantRange::add(const ConstantRange &Other) const {
   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::addWithNoWrap(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 = 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 (NoWrapKind & OBO::NoSignedWrap)
+    Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType);
+  if (NoWrapKind & OBO::NoUnsignedWrap)
+    Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType);
+  return Result;
+}
+
 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
   // Calculate the subset of this range such that "X + Other" is
   // guaranteed not to wrap (overflow) for all X in this subset.
   auto NSWRange = ConstantRange::makeExactNoWrapRegion(
       BinaryOperator::Add, Other, OverflowingBinaryOperator::NoSignedWrap);
   auto NSWConstrainedRange = intersectWith(NSWRange);
 
   return NSWConstrainedRange.add(ConstantRange(Other));

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, AddWithNoSignedWrap) {
   EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)),
             ConstantRange(APInt(8, INT8_MIN), APInt(8, 40)));
   EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -5)),
             ConstantRange(APInt(8, 115), APInt(8, -125)));
   EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -10)),
             ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10)));
 }
 
+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);
+    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        bool IsOverflow = false;
+        APInt N = IntFn(IsOverflow, N1, N2);
+        if (!IsOverflow) {
+          if (N.slt(Min))
+            Min = N;
+          if (N.sgt(Max))
+            Max = N;
+          EXPECT_TRUE(CR.contains(N));
+        }
+      });
+    });
+    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);
+    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        bool IsOverflow = false;
+        APInt N = IntFn(IsOverflow, N1, N2);
+        if (!IsOverflow) {
+          if (N.ult(Min))
+            Min = N;
+          if (N.ugt(Max))
+            Max = N;
+          EXPECT_TRUE(CR.contains(N));
+        }
+      });
+    });
+
+    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);
+        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) {
+              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));
+            }
+          });
+        });
+
+        if (!CR1.isWrappedSet() && !CR2.isWrappedSet() &&
+            !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) {
+          if (UMin.ugt(UMax) || SMin.sgt(SMax)) {
+            EXPECT_TRUE(CR.isEmptySet());
+            return;
+          }
+
+          ConstantRange Exact =
+              ConstantRange::getNonEmpty(SMin, SMax + 1)
+                  .intersectWith(ConstantRange::getNonEmpty(UMin, UMax + 1));
+          EXPECT_EQ(Exact, CR);
+        }
+      });
+}
+
+TEST_F(ConstantRangeTest, AddWithNoWrap) {
+  typedef OverflowingBinaryOperator OBO;
+  EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoSignedWrap), Empty);
+  EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoSignedWrap), Empty);
+  EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
+  EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoSignedWrap), Full);
+  EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
+  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
+  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
+                .addWithNoWrap(Full, OBO::NoSignedWrap),
+            ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
+  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, -1), APInt(16, 0)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
+  EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120))
+                .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)),
+                               OBO::NoSignedWrap),
+            ConstantRange(8, false));
+  EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, -100))
+                .addWithNoWrap(ConstantRange(APInt(8, -110), APInt(8, -100)),
+                               OBO::NoSignedWrap),
+            ConstantRange(8, false));
+  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
+                .addWithNoWrap(ConstantRange(APInt(8, -128), APInt(8, 28)),
+                               OBO::NoSignedWrap),
+            ConstantRange(8, true));
+  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
+                .addWithNoWrap(ConstantRange(APInt(8, -120), APInt(8, 29)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(8, -120), APInt(8, -128)));
+  EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50))
+                .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(8, -40), APInt(8, 69)));
+  EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
+                .addWithNoWrap(ConstantRange(APInt(8, -50), APInt(8, 50)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(8, -40), APInt(8, 69)));
+  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10))
+                .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(8, 125), APInt(8, 9)));
+  EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
+                .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(8, 125), APInt(8, 9)));
+
+  TestAddWithNoSignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.addWithNoWrap(CR2, OBO::NoSignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.sadd_ov(N2, IsOverflow);
+      });
+
+  EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);
+  EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);
+  EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
+  EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoUnsignedWrap), Full);
+  EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
+  EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(16, 1), APInt(16, 0)));
+  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
+                .addWithNoWrap(Full, OBO::NoUnsignedWrap),
+            ConstantRange(APInt(16, 1), APInt(16, 0)));
+  EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220))
+                .addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(8, false));
+  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
+                .addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(8, true));
+  EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
+                .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(8, 10), APInt(8, 129)));
+  EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10))
+                .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(8, 50), APInt(8, 0)));
+  EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
+                .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(8, 60), APInt(8, -37)));
+  EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30))
+                .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(8, 25), APInt(8, -11)));
+  EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
+                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(8, 25), APInt(8, -11)));
+
+  TestAddWithNoUnsignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.uadd_ov(N2, IsOverflow);
+      });
+
+  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
+                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(8, 70), APInt(8, -128)));
+  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
+                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(8, 70), APInt(8, 169)));
+  EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
+                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
+                               OBO::NoUnsignedWrap | OBO::NoSignedWrap),
+            ConstantRange(APInt(8, 70), APInt(8, -128)));
+
+  EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
+                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
+                               OBO::NoSignedWrap),
+            ConstantRange(APInt(8, -80), APInt(8, -21)));
+  EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
+                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
+                               OBO::NoUnsignedWrap),
+            ConstantRange(APInt(8, 176), APInt(8, 235)));
+  EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
+                .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
+                               OBO::NoUnsignedWrap | OBO::NoSignedWrap),
+            ConstantRange(APInt(8, 176), APInt(8, 235)));
+
+  TestAddWithNoSignedUnsignedWrapExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.sadd_ov(N2, IsOverflow);
+      },
+      [](bool &IsOverflow, const APInt &N1, const APInt &N2) {
+        return N1.uadd_ov(N2, IsOverflow);
+      });
+}
+
 TEST_F(ConstantRangeTest, Sub) {
   EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
   EXPECT_EQ(Full.sub(Full), Full);
   EXPECT_EQ(Full.sub(Empty), Empty);
   EXPECT_EQ(Full.sub(One), Full);
   EXPECT_EQ(Full.sub(Some), Full);
   EXPECT_EQ(Full.sub(Wrap), Full);
   EXPECT_EQ(Empty.sub(Empty), Empty);