Index: llvm/trunk/include/llvm/Analysis/ValueTracking.h =================================================================== --- llvm/trunk/include/llvm/Analysis/ValueTracking.h +++ llvm/trunk/include/llvm/Analysis/ValueTracking.h @@ -412,7 +412,16 @@ 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, Index: llvm/trunk/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/trunk/include/llvm/IR/ConstantRange.h +++ llvm/trunk/include/llvm/IR/ConstantRange.h @@ -416,7 +416,16 @@ /// 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; Index: llvm/trunk/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/trunk/lib/Analysis/ValueTracking.cpp +++ llvm/trunk/lib/Analysis/ValueTracking.cpp @@ -3992,8 +3992,10 @@ 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; } Index: llvm/trunk/lib/IR/ConstantRange.cpp =================================================================== --- llvm/trunk/lib/IR/ConstantRange.cpp +++ llvm/trunk/lib/IR/ConstantRange.cpp @@ -1208,9 +1208,9 @@ APInt Min = getUnsignedMin(), Max = getUnsignedMax(); APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); - // a u+ b overflows iff a u> ~b. + // a u+ b overflows high iff a u> ~b. if (Min.ugt(~OtherMin)) - return OverflowResult::AlwaysOverflows; + return OverflowResult::AlwaysOverflowsHigh; if (Max.ugt(~OtherMax)) return OverflowResult::MayOverflow; return OverflowResult::NeverOverflows; @@ -1231,10 +1231,10 @@ // 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)) @@ -1254,9 +1254,9 @@ APInt Min = getUnsignedMin(), Max = getUnsignedMax(); APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); - // a u- b overflows iff a u< b. + // a u- b overflows low iff a u< b. if (Max.ult(OtherMin)) - return OverflowResult::AlwaysOverflows; + return OverflowResult::AlwaysOverflowsLow; if (Min.ult(OtherMax)) return OverflowResult::MayOverflow; return OverflowResult::NeverOverflows; @@ -1277,10 +1277,10 @@ // 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)) @@ -1303,7 +1303,7 @@ (void) Min.umul_ov(OtherMin, Overflow); if (Overflow) - return OverflowResult::AlwaysOverflows; + return OverflowResult::AlwaysOverflowsHigh; (void) Max.umul_ov(OtherMax, Overflow); if (Overflow) Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -2064,7 +2064,7 @@ 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; @@ -2072,7 +2072,7 @@ 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; Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -3993,7 +3993,8 @@ 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(); Index: llvm/trunk/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/ConstantRangeTest.cpp +++ llvm/trunk/unittests/IR/ConstantRangeTest.cpp @@ -1487,8 +1487,10 @@ #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)) @@ -1521,9 +1523,9 @@ 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) { @@ -1548,7 +1550,7 @@ 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)); @@ -1591,7 +1593,7 @@ 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)); @@ -1605,7 +1607,7 @@ 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)); @@ -1637,7 +1639,7 @@ 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)); @@ -1647,7 +1649,7 @@ 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)); @@ -1663,25 +1665,39 @@ 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: @@ -1691,7 +1707,7 @@ if (CR1.isEmptySet() || CR2.isEmptySet()) break; - EXPECT_TRUE(RangeHasOverflow); + EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh); EXPECT_TRUE(RangeHasNoOverflow); break; } @@ -1700,9 +1716,10 @@ 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) { @@ -1712,9 +1729,10 @@ 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) { @@ -1724,9 +1742,10 @@ 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) { @@ -1736,9 +1755,10 @@ 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) { @@ -1748,9 +1768,10 @@ 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) {