From 49cc96a66c18580b73c91893d52a07442bedbd63 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Tue, 28 May 2019 18:08:31 +0000 Subject: [PATCH] [ValueTracking][ConstantRange] Distinguish low/high always overflow 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). Differential Revision: https://reviews.llvm.org/D62463 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@361858 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ValueTracking.h | 11 +++- include/llvm/IR/ConstantRange.h | 11 +++- lib/Analysis/ValueTracking.cpp | 6 +- lib/IR/ConstantRange.cpp | 18 ++--- .../InstCombine/InstCombineCalls.cpp | 4 +- .../InstCombine/InstCombineCompares.cpp | 3 +- unittests/IR/ConstantRangeTest.cpp | 65 ++++++++++++------- 7 files changed, 80 insertions(+), 38 deletions(-) diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index bc6be583307..8e03b7773e8 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -412,7 +412,16 @@ class Value; 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, diff --git a/include/llvm/IR/ConstantRange.h b/include/llvm/IR/ConstantRange.h index f8d4e0a4a9a..0b176747f7c 100644 --- a/include/llvm/IR/ConstantRange.h +++ b/include/llvm/IR/ConstantRange.h @@ -416,7 +416,16 @@ public: /// 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; diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index d46ddc428b2..640063700e8 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -3992,8 +3992,10 @@ 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; } diff --git a/lib/IR/ConstantRange.cpp b/lib/IR/ConstantRange.cpp index 0d44c3815b3..30b6a27078c 100644 --- a/lib/IR/ConstantRange.cpp +++ b/lib/IR/ConstantRange.cpp @@ -1208,9 +1208,9 @@ ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow( 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 @@ ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow( // 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 @@ ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow( 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 @@ ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow( // 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 @@ ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow( (void) Min.umul_ov(OtherMin, Overflow); if (Overflow) - return OverflowResult::AlwaysOverflows; + return OverflowResult::AlwaysOverflowsHigh; (void) Max.umul_ov(OtherMax, Overflow); if (Overflow) diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp index e2813f9d9d4..a18043ef33f 100644 --- a/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -2064,7 +2064,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { 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 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { 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; diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index ab2da177d7b..b3eb75ea8a8 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -3993,7 +3993,8 @@ bool InstCombiner::OptimizeOverflowCheck( 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(); diff --git a/unittests/IR/ConstantRangeTest.cpp b/unittests/IR/ConstantRangeTest.cpp index 4709baad346..eeebe2e73ae 100644 --- a/unittests/IR/ConstantRangeTest.cpp +++ b/unittests/IR/ConstantRangeTest.cpp @@ -1487,8 +1487,10 @@ TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange) { #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 @@ TEST_F(ConstantRangeTest, UnsignedAddOverflow) { 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 @@ TEST_F(ConstantRangeTest, UnsignedSubOverflow) { 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 @@ TEST_F(ConstantRangeTest, SignedAddOverflow) { 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 @@ TEST_F(ConstantRangeTest, SignedAddOverflow) { 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 @@ TEST_F(ConstantRangeTest, SignedSubOverflow) { 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 @@ TEST_F(ConstantRangeTest, SignedSubOverflow) { 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 @@ static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) { 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 @@ static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) { if (CR1.isEmptySet() || CR2.isEmptySet()) break; - EXPECT_TRUE(RangeHasOverflow); + EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh); EXPECT_TRUE(RangeHasNoOverflow); break; } @@ -1700,9 +1716,10 @@ static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) { 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, UnsignedAddOverflowExhaustive) { 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, UnsignedSubOverflowExhaustive) { 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, UnsignedMulOverflowExhaustive) { 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, SignedAddOverflowExhaustive) { 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) { -- 2.40.0