summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/ValueTracking.h11
-rw-r--r--llvm/include/llvm/IR/ConstantRange.h11
-rw-r--r--llvm/lib/Analysis/ValueTracking.cpp6
-rw-r--r--llvm/lib/IR/ConstantRange.cpp18
-rw-r--r--llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp4
-rw-r--r--llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp3
-rw-r--r--llvm/unittests/IR/ConstantRangeTest.cpp65
7 files changed, 80 insertions, 38 deletions
diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h
index bc6be583307..8e03b7773e8 100644
--- a/llvm/include/llvm/Analysis/ValueTracking.h
+++ b/llvm/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/llvm/include/llvm/IR/ConstantRange.h b/llvm/include/llvm/IR/ConstantRange.h
index f8d4e0a4a9a..0b176747f7c 100644
--- a/llvm/include/llvm/IR/ConstantRange.h
+++ b/llvm/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/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index d46ddc428b2..640063700e8 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/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/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index 0d44c3815b3..30b6a27078c 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/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/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
index e2813f9d9d4..a18043ef33f 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ b/llvm/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/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index ab2da177d7b..b3eb75ea8a8 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/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/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp
index 4709baad346..eeebe2e73ae 100644
--- a/llvm/unittests/IR/ConstantRangeTest.cpp
+++ b/llvm/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) {
OpenPOWER on IntegriCloud