[ConstantRange] Add overflow check helpers

[nikic]

Summary

Add functions to ConstantRange that determine whether the unsigned/signed addition/subtraction of two ConstantRanges may/always/never overflows. This will allow checking overflow conditions based on known constant ranges in addition to known bits (with D59071 in mind).

I'm implementing these methods on ConstantRange to allow them to be unit tested independently of any ValueTracking machinery.

The OverflowResult enum is redeclared on ConstantRange, because I wanted to avoid a dependency in either direction between ValueTracking.h and ConstantRange.h.

[lebedev.ri]

This looks extremely error prone.
This needs to be verified (keywords: alive, SMT) somehow ideally.

[nikic]

In D59193#1424028, @lebedev.ri wrote:

This looks extremely error prone.
This needs to be verified (keywords: alive, SMT) somehow ideally.

Maybe I can just include some exhaustive tests? I'm thinking on 4-bit numbers we have 16^2 possible ranges with less than 16^4 values contained in them in total. That's few enough to try all of them.

[lebedev.ri]

In D59193#1424032, @nikic wrote:

In D59193#1424028, @lebedev.ri wrote:

This looks extremely error prone.
This needs to be verified (keywords: alive, SMT) somehow ideally.

Maybe I can just include some exhaustive tests? I'm thinking on 4-bit numbers we have 16^2 possible ranges with less than 16^4 values contained in them in total. That's few enough to try all of them.

Sure, for one-time thing brute-force verification could work (how do you plan to produce the 'truth' you will be verifying against?)

Also, see @nlopes's ConstantRange section of https://llvm.org/devmtg/2013-11/slides/Lopes-SMT.pdf.
This is rather not suited for day-to-day use, but i'm not sure there are friendlier wrappers for such a rare use-case..

[nikic]

@lebedev.ri I've implemented the following code for exhaustive checking on 4-bit numbers: https://gist.github.com/nikic/3d37a4742a8685c5dd101524f928fe58 The source of truth are APInt uadd_ov and friends.

Is this something I should include in the patch (possibly reduced to 3-bit testing) or is this okay as a one-off test?

[lebedev.ri]

In D59193#1424072, @nikic wrote:

@lebedev.ri I've implemented the following code for exhaustive checking on 4-bit numbers: https://gist.github.com/nikic/3d37a4742a8685c5dd101524f928fe58 The source of truth are APInt uadd_ov and friends.

Nice, not manual hardcoding, but cross-checking.

Is this something I should include in the patch (possibly reduced to 3-bit testing) or is this okay as a one-off test?

What's the runtime of the current 4-bit case?

[nikic]

In D59193#1424073, @lebedev.ri wrote:

What's the runtime of the current 4-bit case?

The run-times for the 4-bit checks I get on a debug build:

[ RUN      ] ConstantRangeTest.UnsignedAddOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedAddOverflowExhautive (609 ms)
[ RUN      ] ConstantRangeTest.UnsignedSubOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedSubOverflowExhautive (589 ms)
[ RUN      ] ConstantRangeTest.SignedAddOverflowExhautive
[       OK ] ConstantRangeTest.SignedAddOverflowExhautive (726 ms)
[ RUN      ] ConstantRangeTest.SignedSubOverflowExhautive
[       OK ] ConstantRangeTest.SignedSubOverflowExhautive (735 ms)

For 3-bit checks:

[ RUN      ] ConstantRangeTest.UnsignedAddOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedAddOverflowExhautive (11 ms)
[ RUN      ] ConstantRangeTest.UnsignedSubOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedSubOverflowExhautive (10 ms)
[ RUN      ] ConstantRangeTest.SignedAddOverflowExhautive
[       OK ] ConstantRangeTest.SignedAddOverflowExhautive (13 ms)
[ RUN      ] ConstantRangeTest.SignedSubOverflowExhautive
[       OK ] ConstantRangeTest.SignedSubOverflowExhautive (14 ms)

[lebedev.ri]

In D59193#1424074, @nikic wrote:

In D59193#1424073, @lebedev.ri wrote:

What's the runtime of the current 4-bit case?

The run-times for the 4-bit checks I get on a debug build:

[ RUN      ] ConstantRangeTest.UnsignedAddOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedAddOverflowExhautive (609 ms)
[ RUN      ] ConstantRangeTest.UnsignedSubOverflowExhautive
[       OK ] ConstantRangeTest.UnsignedSubOverflowExhautive (589 ms)
[ RUN      ] ConstantRangeTest.SignedAddOverflowExhautive
[       OK ] ConstantRangeTest.SignedAddOverflowExhautive (726 ms)
[ RUN      ] ConstantRangeTest.SignedSubOverflowExhautive
[       OK ] ConstantRangeTest.SignedSubOverflowExhautive (735 ms)

I was expecting something like 10 sec total, that looks like nothing to me.
Please add those tests into appropriate place :)
It's not SMT, but better than nothing i suppose.

[nikic]

Add exhaustive tests for overflow checks.

[lebedev.ri]

Looks good, some nits.

llvm/unittests/IR/ConstantRangeTest.cpp

1315–1316 ↗

(On Diff #190048)

On the first look this is confusing.
Maybe add Set/Range prefix, so it is clearer that it is over the whole set, not just some one point.

1317–1329 ↗

(On Diff #190048)

Hm, so this is iterating so that N1 is every point in CR1 and N2 is every point in CR2.
Took me a moment to get that.
Can this perhaps be rewritten with for-loop somehow, more explicitly?

for(APInt N1 = CR1.getLower(), APInt N1Max = CR1.getUpper(); N1 != N1Max; N1++) {
  for(APInt N2 = CR2.getLower(), APInt N2Max = CR2.getUpper(); N2 != N2Max; N2++) {
    assert(CR1.contains(N1));
    assert(CR2.contains(N2));

    if (OverflowFn(N1, N2))
      HasOverflow = true;
    else
       HasNoOverflow = true;
  }
}

[nikic]

Rename to RangeHasOverflow/RangeHasNoOverflow, add comment.

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

1317–1329 ↗

(On Diff #190048)

A simple for loop will not work for the case of a full range (as N1 != N1Max will fail immediately). That's why I'm using the current code based on the range size. I've added a comment to that effect.

[lebedev.ri]

Okay, thanks, looks sane to me.
You may want to wait for @spatel / @craig.topper comments though.

[nikic]

@spatel Anything to add here?

[spatel]

LGTM

llvm/include/llvm/IR/ConstantRange.h

331 ↗

(On Diff #190139)

other -> Other ?

(hoping we can standardize to camelCase variables, but we're not there yet?)

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

public:
 
   /// Return a new range representing the possible values resulting from a
   /// arithmetic right shift of a value in this range and a value in \p Other.
   ConstantRange ashr(const ConstantRange &Other) const;
 
   /// Return a new range that is the logical not of the current set.
   ConstantRange inverse() const;
 
+  /// Represents whether an operation on the given constant range is known to
+  /// always or never overflow.
+  enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows };
+
+  /// Return whether unsigned add of the two ranges always/never overflows.
+  OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const;
+
+  /// Return whether signed add of the two ranges always/never overflows.
+  OverflowResult signedAddMayOverflow(const ConstantRange &Other) const;
+
+  /// Return whether unsigned sub of the two ranges always/never overflows.
+  OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const;
+
+  /// Return whether signed sub of the two ranges always/never overflows.
+  OverflowResult signedSubMayOverflow(const ConstantRange &Other) const;
+
   /// Print out the bounds to a stream.
   void print(raw_ostream &OS) const;
 
   /// Allow printing from a debugger easily.
   void dump() const;
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const ConstantRange &CR) {

llvm/trunk/lib/IR/ConstantRange.cpp

 ConstantRange ConstantRange::inverse() const {
   if (isFullSet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
   if (isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
   return ConstantRange(Upper, Lower);
 }
 
+ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
+  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
+
+  // a u+ b overflows iff a u> ~b.
+  if (Min.ugt(~OtherMin))
+    return OverflowResult::AlwaysOverflows;
+  if (Max.ugt(~OtherMax))
+    return OverflowResult::MayOverflow;
+  return OverflowResult::NeverOverflows;
+}
+
+ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getSignedMin(), Max = getSignedMax();
+  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
+
+  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
+  APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
+
+  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
+  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
+  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
+      Min.sgt(SignedMax - OtherMin))
+    return OverflowResult::AlwaysOverflows;
+  if (Max.isNegative() && OtherMax.isNegative() &&
+      Max.slt(SignedMin - OtherMax))
+    return OverflowResult::AlwaysOverflows;
+
+  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
+      Max.sgt(SignedMax - OtherMax))
+    return OverflowResult::MayOverflow;
+  if (Min.isNegative() && OtherMin.isNegative() &&
+      Min.slt(SignedMin - OtherMin))
+    return OverflowResult::MayOverflow;
+
+  return OverflowResult::NeverOverflows;
+}
+
+ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
+  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
+
+  // a u- b overflows iff a u< b.
+  if (Max.ult(OtherMin))
+    return OverflowResult::AlwaysOverflows;
+  if (Min.ult(OtherMax))
+    return OverflowResult::MayOverflow;
+  return OverflowResult::NeverOverflows;
+}
+
+ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(
+    const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return OverflowResult::MayOverflow;
+
+  APInt Min = getSignedMin(), Max = getSignedMax();
+  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
+
+  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
+  APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
+
+  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
+  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
+  if (Min.isNonNegative() && OtherMax.isNegative() &&
+      Min.sgt(SignedMax + OtherMax))
+    return OverflowResult::AlwaysOverflows;
+  if (Max.isNegative() && OtherMin.isNonNegative() &&
+      Max.slt(SignedMin + OtherMin))
+    return OverflowResult::AlwaysOverflows;
+
+  if (Max.isNonNegative() && OtherMin.isNegative() &&
+      Max.sgt(SignedMax + OtherMin))
+    return OverflowResult::MayOverflow;
+  if (Min.isNegative() && OtherMax.isNonNegative() &&
+      Min.slt(SignedMin + OtherMax))
+    return OverflowResult::MayOverflow;
+
+  return OverflowResult::NeverOverflows;
+}
+
 void ConstantRange::print(raw_ostream &OS) const {
   if (isFullSet())
     OS << "full-set";
   else if (isEmptySet())
     OS << "empty-set";
   else
     OS << "[" << Lower << "," << Upper << ")";
 }

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

for (int64_t I = Lo; I <= Hi; I++) {
       (void)APInt(8, I, /*isSigned=*/true)
           .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
       AnyOverflow |= Overflow;
     }
     EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
   }
 }
 
+#define EXPECT_MAY_OVERFLOW(op) \
+  EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
+#define EXPECT_ALWAYS_OVERFLOWS(op) \
+  EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflows, (op))
+#define EXPECT_NEVER_OVERFLOWS(op) \
+  EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
+
+TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
+  // Ill-defined - may overflow is a conservative result.
+  EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
+  EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
+
+  // Never overflow despite one full/wrap set.
+  ConstantRange Zero(APInt::getNullValue(16));
+  EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
+  EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
+  EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
+  EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
+
+  // But usually full/wrap always may overflow.
+  EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
+  EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
+
+  ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
+  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
+  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
+  EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
+  EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
+  EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
+  EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
+
+  ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
+  ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
+  EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
+  EXPECT_ALWAYS_OVERFLOWS(A.unsignedAddMayOverflow(C2));
+  EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
+  EXPECT_ALWAYS_OVERFLOWS(C2.unsignedAddMayOverflow(A));
+}
+
+TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
+  // Ill-defined - may overflow is a conservative result.
+  EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
+  EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
+
+  // Never overflow despite one full/wrap set.
+  ConstantRange Zero(APInt::getNullValue(16));
+  ConstantRange Max(APInt::getAllOnesValue(16));
+  EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
+  EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
+  EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
+  EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
+
+  // But usually full/wrap always may overflow.
+  EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
+  EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
+
+  ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
+  ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
+  EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
+  EXPECT_ALWAYS_OVERFLOWS(A.unsignedSubMayOverflow(B));
+
+  ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
+  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
+  EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
+  EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
+
+  ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
+  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
+  EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
+  EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
+}
+
+TEST_F(ConstantRangeTest, SignedAddOverflow) {
+  // Ill-defined - may overflow is a conservative result.
+  EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
+  EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
+
+  // Never overflow despite one full/wrap set.
+  ConstantRange Zero(APInt::getNullValue(16));
+  EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
+  EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
+  EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
+  EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
+
+  // But usually full/wrap always may overflow.
+  EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
+  EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
+
+  ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
+  ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
+  ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
+  EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
+  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
+  ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
+  ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
+  EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
+  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
+  ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
+  ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
+  EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
+  EXPECT_ALWAYS_OVERFLOWS(A.signedAddMayOverflow(B6));
+
+  ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
+  ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
+  ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
+  EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
+  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
+  ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
+  ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
+  EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
+  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
+  ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
+  ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
+  EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
+  EXPECT_ALWAYS_OVERFLOWS(C.signedAddMayOverflow(D6));
+
+  ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
+  EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
+  ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
+  EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
+}
+
+TEST_F(ConstantRangeTest, SignedSubOverflow) {
+  // Ill-defined - may overflow is a conservative result.
+  EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
+  EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
+
+  // Never overflow despite one full/wrap set.
+  ConstantRange Zero(APInt::getNullValue(16));
+  EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
+  EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
+
+  // But usually full/wrap always may overflow.
+  EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
+  EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
+  EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
+
+  ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
+  ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
+  ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
+  EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
+  EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
+  ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
+  ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
+  EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
+  EXPECT_ALWAYS_OVERFLOWS(A.signedSubMayOverflow(B4));
+
+  ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
+  ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
+  ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
+  EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
+  EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
+  ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
+  ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
+  EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
+  EXPECT_ALWAYS_OVERFLOWS(C.signedSubMayOverflow(D4));
+
+  ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
+  EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
+  ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
+  EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
+}
+
+template<typename Fn1, typename Fn2>
+static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
+  // Constant range overflow checks are tested exhaustively on 4-bit numbers.
+  unsigned Bits = 4;
+  unsigned Max = 1 << Bits;
+  for (unsigned Lo1 = 0; Lo1 < Max; Lo1++) {
+    for (unsigned Hi1 = 0; Hi1 < Max; Hi1++) {
+      // Enforce ConstantRange invariant.
+      if (Lo1 == Hi1 && Lo1 != 0 && Lo1 != Max - 1)
+        continue;
+
+      ConstantRange CR1(APInt(Bits, Lo1), APInt(Bits, Hi1));
+      unsigned Size1 = CR1.getSetSize().getLimitedValue();
+
+      for (unsigned Lo2 = 0; Lo2 < Max; Lo2++) {
+        for (unsigned Hi2 = 0; Hi2 < Max; Hi2++) {
+          // Enforce ConstantRange invariant.
+          if (Lo2 == Hi2 && Lo2 != 0 && Lo2 != Max - 1)
+            continue;
+
+          ConstantRange CR2(APInt(Bits, Lo2), APInt(Bits, Hi2));
+          unsigned Size2 = CR2.getSetSize().getLimitedValue();
+
+          // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
+          // operations have overflow / have no overflow. These loops are based
+          // on Size1/Size2 to properly handle empty/full ranges.
+          bool RangeHasOverflow = false;
+          bool RangeHasNoOverflow = false;
+          APInt N1(Bits, Lo1);
+          for (unsigned I1 = 0; I1 < Size1; I1++, N1++) {
+            APInt N2(Bits, Lo2);
+            for (unsigned I2 = 0; I2 < Size2; I2++, N2++) {
+              assert(CR1.contains(N1));
+              assert(CR2.contains(N2));
+
+              if (OverflowFn(N1, N2))
+                RangeHasOverflow = true;
+              else
+                RangeHasNoOverflow = true;
+            }
+          }
+
+          ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
+          switch (OR) {
+            case ConstantRange::OverflowResult::AlwaysOverflows:
+              EXPECT_TRUE(RangeHasOverflow);
+              EXPECT_FALSE(RangeHasNoOverflow);
+              break;
+            case ConstantRange::OverflowResult::NeverOverflows:
+              EXPECT_FALSE(RangeHasOverflow);
+              EXPECT_TRUE(RangeHasNoOverflow);
+              break;
+            case ConstantRange::OverflowResult::MayOverflow:
+              // We return MayOverflow for empty sets as a conservative result,
+              // but of course neither the RangeHasOverflow nor the
+              // RangeHasNoOverflow flags will be set.
+              if (CR1.isEmptySet() || CR2.isEmptySet())
+                break;
+
+              EXPECT_TRUE(RangeHasOverflow);
+              EXPECT_TRUE(RangeHasNoOverflow);
+              break;
+            default:
+              llvm_unreachable("Invalid enum return value");
+          }
+        }
+      }
+    }
+  }
+}
+
+TEST_F(ConstantRangeTest, UnsignedAddOverflowExhautive) {
+  TestOverflowExhaustive(
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        N1.uadd_ov(N2, Overflow);
+        return Overflow;
+      },
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.unsignedAddMayOverflow(CR2);
+      });
+}
+
+TEST_F(ConstantRangeTest, UnsignedSubOverflowExhautive) {
+  TestOverflowExhaustive(
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        N1.usub_ov(N2, Overflow);
+        return Overflow;
+      },
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.unsignedSubMayOverflow(CR2);
+      });
+}
+
+TEST_F(ConstantRangeTest, SignedAddOverflowExhautive) {
+  TestOverflowExhaustive(
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        N1.sadd_ov(N2, Overflow);
+        return Overflow;
+      },
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.signedAddMayOverflow(CR2);
+      });
+}
+
+TEST_F(ConstantRangeTest, SignedSubOverflowExhautive) {
+  TestOverflowExhaustive(
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        N1.ssub_ov(N2, Overflow);
+        return Overflow;
+      },
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.signedSubMayOverflow(CR2);
+      });
+}
+
 }  // anonymous namespace