[ValueTracking][ConstantRange] Distinguish low/high always overflow

[nikic]

Summary

In order to fold an always overflowing signed saturating add/sub, we need to know in which direction the always overflow occurs. This patch splits up AlwaysOverflows into AlwaysOverflowsLow and AlwaysOverflowsHigh to pass through this information (but it is not used yet).

[lebedev.ri]

llvm/include/llvm/Analysis/ValueTracking.h

416

These now need a comment for each.
While with the enum on the LHS of the diff it is obvious,
here i'm not sure what low/high means.
The direction of the overflow?

[nikic]

Add comments for enum cases.

[nikic]

llvm/include/llvm/Analysis/ValueTracking.h

416

Yeah, this is the direction of overflow. For AlwaysOverflowLow the real result would be lower than signed/unsigned min, for AlwaysOverflowHigh it would be higher than signed/unsigned max.

[lebedev.ri]

Looks reasonable.

llvm/include/llvm/Analysis/ValueTracking.h

416

Thanks. Hmm, still a bit confusing, maybe adding a simple examples could help. Or not.

llvm/lib/IR/ConstantRange.cpp

1211

overflows low

[nikic]

llvm/lib/IR/ConstantRange.cpp

1211

What do you mean by this comment? The unsigned add is an overflow high case.

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   bool isAssumeLikeIntrinsic(const Instruction *I);
 
   /// Return true if it is valid to use the assumptions provided by an
   /// assume intrinsic, I, at the point in the control-flow identified by the
   /// context instruction, CxtI.
   bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI,
                                const DominatorTree *DT = nullptr);
 
-  enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows };
+  enum class OverflowResult {
+    /// Always overflows in the direction of signed/unsigned min value.
+    AlwaysOverflowsLow,
+    /// Always overflows in the direction of signed/unsigned max value.
+    AlwaysOverflowsHigh,
+    /// May or may not overflow.
+    MayOverflow,
+    /// Never overflows.
+    NeverOverflows,
+  };
 
   OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
                                                const Value *RHS,
                                                const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
                                                const DominatorTree *DT,
                                                bool UseInstrInfo = true);

llvm/include/llvm/IR/ConstantRange.h

public:
   ConstantRange inverse() const;
 
   /// Calculate absolute value range. If the original range contains signed
   /// min, then the resulting range will also contain signed min.
   ConstantRange abs() const;
 
   /// Represents whether an operation on the given constant range is known to
   /// always or never overflow.
-  enum class OverflowResult { AlwaysOverflows, MayOverflow, NeverOverflows };
+  enum class OverflowResult {
+    /// Always overflows in the direction of signed/unsigned min value.
+    AlwaysOverflowsLow,
+    /// Always overflows in the direction of signed/unsigned max value.
+    AlwaysOverflowsHigh,
+    /// May or may not overflow.
+    MayOverflow,
+    /// Never overflows.
+    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.

llvm/lib/Analysis/ValueTracking.cpp

bool llvm::mayBeMemoryDependent(const Instruction &I) {
   return I.mayReadOrWriteMemory() || !isSafeToSpeculativelyExecute(&I);
 }
 
 /// Convert ConstantRange OverflowResult into ValueTracking OverflowResult.
 static OverflowResult mapOverflowResult(ConstantRange::OverflowResult OR) {
   switch (OR) {
     case ConstantRange::OverflowResult::MayOverflow:
       return OverflowResult::MayOverflow;
-    case ConstantRange::OverflowResult::AlwaysOverflows:
-      return OverflowResult::AlwaysOverflows;
+    case ConstantRange::OverflowResult::AlwaysOverflowsLow:
+      return OverflowResult::AlwaysOverflowsLow;
+    case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
+      return OverflowResult::AlwaysOverflowsHigh;
     case ConstantRange::OverflowResult::NeverOverflows:
       return OverflowResult::NeverOverflows;
   }
   llvm_unreachable("Unknown OverflowResult");
 }
 
 /// Combine constant ranges from computeConstantRange() and computeKnownBits().
 static ConstantRange computeConstantRangeIncludingKnownBits(

llvm/lib/IR/ConstantRange.cpp

 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;
+    return OverflowResult::AlwaysOverflowsHigh;
   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;
+    return OverflowResult::AlwaysOverflowsHigh;
   if (Max.isNegative() && OtherMax.isNegative() &&
       Max.slt(SignedMin - OtherMax))
-    return OverflowResult::AlwaysOverflows;
+    return OverflowResult::AlwaysOverflowsLow;
 
   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;
+    return OverflowResult::AlwaysOverflowsLow;
   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;
+    return OverflowResult::AlwaysOverflowsHigh;
   if (Max.isNegative() && OtherMin.isNonNegative() &&
       Max.slt(SignedMin + OtherMin))
-    return OverflowResult::AlwaysOverflows;
+    return OverflowResult::AlwaysOverflowsLow;
 
   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;
 }
 
 ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow(
     const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return OverflowResult::MayOverflow;
 
   APInt Min = getUnsignedMin(), Max = getUnsignedMax();
   APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
   bool Overflow;
 
   (void) Min.umul_ov(OtherMin, Overflow);
   if (Overflow)
-    return OverflowResult::AlwaysOverflows;
+    return OverflowResult::AlwaysOverflowsHigh;
 
   (void) Max.umul_ov(OtherMax, Overflow);
   if (Overflow)
     return OverflowResult::MayOverflow;
 
   return OverflowResult::NeverOverflows;
 }
 

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::ssub_sat: {
     OverflowResult OR;
     switch (IID) {
     default:
       llvm_unreachable("Unexpected intrinsic!");
     case Intrinsic::uadd_sat:
       OR = computeOverflowForUnsignedAdd(Arg0, Arg1, II);
       if (OR == OverflowResult::NeverOverflows)
         return BinaryOperator::CreateNUWAdd(Arg0, Arg1);
-      if (OR == OverflowResult::AlwaysOverflows)
+      if (OR == OverflowResult::AlwaysOverflowsHigh)
         return replaceInstUsesWith(*II,
                                    ConstantInt::getAllOnesValue(II->getType()));
       break;
     case Intrinsic::usub_sat:
       OR = computeOverflowForUnsignedSub(Arg0, Arg1, II);
       if (OR == OverflowResult::NeverOverflows)
         return BinaryOperator::CreateNUWSub(Arg0, Arg1);
-      if (OR == OverflowResult::AlwaysOverflows)
+      if (OR == OverflowResult::AlwaysOverflowsLow)
         return replaceInstUsesWith(*II,
                                    ConstantInt::getNullValue(II->getType()));
       break;
     case Intrinsic::sadd_sat:
       if (willNotOverflowSignedAdd(Arg0, Arg1, *II))
         return BinaryOperator::CreateNSWAdd(Arg0, Arg1);
       break;
     case Intrinsic::ssub_sat:

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (isNeutralValue(BinaryOp, RHS)) {
     Result = LHS;
     Overflow = Builder.getFalse();
     return true;
   }
 
   switch (computeOverflow(BinaryOp, IsSigned, LHS, RHS, &OrigI)) {
     case OverflowResult::MayOverflow:
       return false;
-    case OverflowResult::AlwaysOverflows:
+    case OverflowResult::AlwaysOverflowsLow:
+    case OverflowResult::AlwaysOverflowsHigh:
       Result = Builder.CreateBinOp(BinaryOp, LHS, RHS);
       Result->takeName(&OrigI);
       Overflow = Builder.getTrue();
       return true;
     case OverflowResult::NeverOverflows:
       Result = Builder.CreateBinOp(BinaryOp, LHS, RHS);
       Result->takeName(&OrigI);
       Overflow = Builder.getFalse();

llvm/unittests/IR/ConstantRangeTest.cpp

for (int64_t I = Lo; I <= Hi; I++) {
       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_ALWAYS_OVERFLOWS_LOW(op) \
+  EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
+#define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
+  EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (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));
 
TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
   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_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
   EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
-  EXPECT_ALWAYS_OVERFLOWS(C2.unsignedAddMayOverflow(A));
+  EXPECT_ALWAYS_OVERFLOWS_HIGH(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));
+  EXPECT_ALWAYS_OVERFLOWS_LOW(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));
TEST_F(ConstantRangeTest, SignedAddOverflow) {
   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));
+  EXPECT_ALWAYS_OVERFLOWS_HIGH(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));
+  EXPECT_ALWAYS_OVERFLOWS_LOW(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) {
TEST_F(ConstantRangeTest, SignedSubOverflow) {
   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));
+  EXPECT_ALWAYS_OVERFLOWS_HIGH(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));
+  EXPECT_ALWAYS_OVERFLOWS_LOW(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;
   EnumerateTwoConstantRanges(Bits, [=](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
     // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
     // operations have overflow / have no overflow.
-    bool RangeHasOverflow = false;
+    bool RangeHasOverflowLow = false;
+    bool RangeHasOverflowHigh = false;
     bool RangeHasNoOverflow = false;
     ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
       ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
-        if (OverflowFn(N1, N2))
-          RangeHasOverflow = true;
-        else
+        bool IsOverflowHigh;
+        if (!OverflowFn(IsOverflowHigh, N1, N2)) {
           RangeHasNoOverflow = true;
+          return;
+        }
+
+        if (IsOverflowHigh)
+          RangeHasOverflowHigh = true;
+        else
+          RangeHasOverflowLow = true;
       });
     });
 
     ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
     switch (OR) {
-    case ConstantRange::OverflowResult::AlwaysOverflows:
-      EXPECT_TRUE(RangeHasOverflow);
+    case ConstantRange::OverflowResult::AlwaysOverflowsLow:
+      EXPECT_TRUE(RangeHasOverflowLow);
+      EXPECT_FALSE(RangeHasOverflowHigh);
+      EXPECT_FALSE(RangeHasNoOverflow);
+      break;
+    case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
+      EXPECT_TRUE(RangeHasOverflowHigh);
+      EXPECT_FALSE(RangeHasOverflowLow);
       EXPECT_FALSE(RangeHasNoOverflow);
       break;
     case ConstantRange::OverflowResult::NeverOverflows:
-      EXPECT_FALSE(RangeHasOverflow);
+      EXPECT_FALSE(RangeHasOverflowLow);
+      EXPECT_FALSE(RangeHasOverflowHigh);
       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(RangeHasOverflowLow || RangeHasOverflowHigh);
       EXPECT_TRUE(RangeHasNoOverflow);
       break;
     }
   });
 }
 
 TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
   TestOverflowExhaustive(
-      [](const APInt &N1, const APInt &N2) {
+      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
         bool Overflow;
         (void) N1.uadd_ov(N2, Overflow);
+        IsOverflowHigh = true;
         return Overflow;
       },
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.unsignedAddMayOverflow(CR2);
       });
 }
 
 TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
   TestOverflowExhaustive(
-      [](const APInt &N1, const APInt &N2) {
+      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
         bool Overflow;
         (void) N1.usub_ov(N2, Overflow);
+        IsOverflowHigh = false;
         return Overflow;
       },
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.unsignedSubMayOverflow(CR2);
       });
 }
 
 TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
   TestOverflowExhaustive(
-      [](const APInt &N1, const APInt &N2) {
+      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
         bool Overflow;
         (void) N1.umul_ov(N2, Overflow);
+        IsOverflowHigh = true;
         return Overflow;
       },
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.unsignedMulMayOverflow(CR2);
       });
 }
 
 TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
   TestOverflowExhaustive(
-      [](const APInt &N1, const APInt &N2) {
+      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
         bool Overflow;
         (void) N1.sadd_ov(N2, Overflow);
+        IsOverflowHigh = N1.isNonNegative();
         return Overflow;
       },
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.signedAddMayOverflow(CR2);
       });
 }
 
 TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
   TestOverflowExhaustive(
-      [](const APInt &N1, const APInt &N2) {
+      [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
         bool Overflow;
         (void) N1.ssub_ov(N2, Overflow);
+        IsOverflowHigh = N1.isNonNegative();
         return Overflow;
       },
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.signedSubMayOverflow(CR2);
       });
 }
 
 TEST_F(ConstantRangeTest, FromKnownBits) {