aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Support/ConstantRange.h16
-rw-r--r--lib/Analysis/LoopVR.cpp9
-rw-r--r--lib/Support/ConstantRange.cpp48
-rw-r--r--lib/Transforms/Scalar/PredicateSimplifier.cpp20
-rw-r--r--unittests/Support/ConstantRangeTest.cpp21
5 files changed, 29 insertions, 85 deletions
diff --git a/include/llvm/Support/ConstantRange.h b/include/llvm/Support/ConstantRange.h
index cbf3f87..3b72b04 100644
--- a/include/llvm/Support/ConstantRange.h
+++ b/include/llvm/Support/ConstantRange.h
@@ -153,21 +153,13 @@ public:
ConstantRange subtract(const APInt &CI) const;
/// intersectWith - Return the range that results from the intersection of
- /// this range with another range. The resultant range is pruned as much as
- /// possible, but there may be cases where elements are included that are in
- /// one of the sets but not the other. For example: [100, 8) intersect [3,
- /// 120) yields [3, 120)
- ///
- ConstantRange intersectWith(const ConstantRange &CR) const;
-
- /// maximalIntersectWith - Return the range that results from the intersection
- /// of this range with another range. The resultant range is guaranteed to
+ /// this range with another range. The resultant range is guaranteed to
/// include all elements contained in both input ranges, and to have the
/// smallest possible set size that does so. Because there may be two
- /// intersections with the same set size, A.maximalIntersectWith(B) might not
- /// be equal to B.maximalIntersectWith(A).
+ /// intersections with the same set size, A.intersectWith(B) might not
+ /// be equal to B.intersectWith(A).
///
- ConstantRange maximalIntersectWith(const ConstantRange &CR) const;
+ ConstantRange intersectWith(const ConstantRange &CR) const;
/// unionWith - Return the range that results from the union of this range
/// with another range. The resultant range is guaranteed to include the
diff --git a/lib/Analysis/LoopVR.cpp b/lib/Analysis/LoopVR.cpp
index 6854e95..e4dac8f 100644
--- a/lib/Analysis/LoopVR.cpp
+++ b/lib/Analysis/LoopVR.cpp
@@ -142,14 +142,13 @@ ConstantRange LoopVR::getRange(const SCEV *S, const SCEV *T, ScalarEvolution &SE
if (R.getUnsignedMin() == 0) {
// Just because it contains zero, doesn't mean it will also contain one.
- // Use maximalIntersectWith to get the right behaviour.
ConstantRange NotZero(APInt(L.getBitWidth(), 1),
APInt::getNullValue(L.getBitWidth()));
- R = R.maximalIntersectWith(NotZero);
+ R = R.intersectWith(NotZero);
}
- // But, the maximal intersection might still include zero. If it does, then
- // we know it also included one.
+ // But, the intersection might still include zero. If it does, then we know
+ // it also included one.
if (R.contains(APInt::getNullValue(L.getBitWidth())))
Upper = L.getUnsignedMax();
else
@@ -295,5 +294,5 @@ void LoopVR::narrow(Value *V, const ConstantRange &CR) {
if (I == Map.end())
Map[V] = new ConstantRange(CR);
else
- Map[V] = new ConstantRange(Map[V]->maximalIntersectWith(CR));
+ Map[V] = new ConstantRange(Map[V]->intersectWith(CR));
}
diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
index 4cb54bd..5f3d6f8 100644
--- a/lib/Support/ConstantRange.cpp
+++ b/lib/Support/ConstantRange.cpp
@@ -275,58 +275,20 @@ ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
}
/// intersectWith - Return the range that results from the intersection of this
-/// range with another range.
-///
+/// range with another range. The resultant range is guaranteed to include all
+/// elements contained in both input ranges, and to have the smallest possible
+/// set size that does so. Because there may be two intersections with the
+/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
assert(getBitWidth() == CR.getBitWidth() &&
"ConstantRange types don't agree!");
- // Handle common special cases
- if (isEmptySet() || CR.isFullSet())
- return *this;
- if (isFullSet() || CR.isEmptySet())
- return CR;
-
- if (!isWrappedSet()) {
- if (!CR.isWrappedSet()) {
- APInt L = APIntOps::umax(Lower, CR.Lower);
- APInt U = APIntOps::umin(Upper, CR.Upper);
-
- if (L.ult(U)) // If range isn't empty...
- return ConstantRange(L, U);
- else
- return ConstantRange(getBitWidth(), false);// Otherwise, empty set
- } else
- return intersect1Wrapped(CR, *this);
- } else { // We know "this" is wrapped...
- if (!CR.isWrappedSet())
- return intersect1Wrapped(*this, CR);
- else {
- // Both ranges are wrapped...
- APInt L = APIntOps::umax(Lower, CR.Lower);
- APInt U = APIntOps::umin(Upper, CR.Upper);
- return ConstantRange(L, U);
- }
- }
- return *this;
-}
-
-/// maximalIntersectWith - Return the range that results from the intersection
-/// of this range with another range. The resultant range is guaranteed to
-/// include all elements contained in both input ranges, and to have the
-/// smallest possible set size that does so. Because there may be two
-/// intersections with the same set size, A.maximalIntersectWith(B) might not
-/// be equal to B.maximalIntersect(A).
-ConstantRange
-ConstantRange::maximalIntersectWith(const ConstantRange &CR) const {
- assert(getBitWidth() == CR.getBitWidth() &&
- "ConstantRange types don't agree!");
// Handle common cases.
if ( isEmptySet() || CR.isFullSet()) return *this;
if (CR.isEmptySet() || isFullSet()) return CR;
if (!isWrappedSet() && CR.isWrappedSet())
- return CR.maximalIntersectWith(*this);
+ return CR.intersectWith(*this);
if (!isWrappedSet() && !CR.isWrappedSet()) {
if (Lower.ult(CR.Lower)) {
diff --git a/lib/Transforms/Scalar/PredicateSimplifier.cpp b/lib/Transforms/Scalar/PredicateSimplifier.cpp
index 51de4f7..9845f5f 100644
--- a/lib/Transforms/Scalar/PredicateSimplifier.cpp
+++ b/lib/Transforms/Scalar/PredicateSimplifier.cpp
@@ -968,7 +968,7 @@ namespace {
std::lower_bound(begin(), E, std::make_pair(Subtree, empty), swo);
if (I != end() && I->first == Subtree) {
- ConstantRange CR2 = I->second.maximalIntersectWith(CR);
+ ConstantRange CR2 = I->second.intersectWith(CR);
assert(!CR2.isEmptySet() && !CR2.isSingleElement() &&
"Invalid union of ranges.");
I->second = CR2;
@@ -1000,18 +1000,18 @@ namespace {
ConstantRange Range(CR.getBitWidth());
if (LV_s == SGT_BIT) {
- Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+ Range = Range.intersectWith(ConstantRange::makeICmpRegion(
hasEQ ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SGT, CR));
} else if (LV_s == SLT_BIT) {
- Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+ Range = Range.intersectWith(ConstantRange::makeICmpRegion(
hasEQ ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_SLT, CR));
}
if (LV_u == UGT_BIT) {
- Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+ Range = Range.intersectWith(ConstantRange::makeICmpRegion(
hasEQ ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_UGT, CR));
} else if (LV_u == ULT_BIT) {
- Range = Range.maximalIntersectWith(ConstantRange::makeICmpRegion(
+ Range = Range.intersectWith(ConstantRange::makeICmpRegion(
hasEQ ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_ULT, CR));
}
@@ -1083,7 +1083,7 @@ namespace {
switch (LV) {
default: assert(!"Impossible lattice value!");
case NE:
- return CR1.maximalIntersectWith(CR2).isEmptySet();
+ return CR1.intersectWith(CR2).isEmptySet();
case ULT:
return CR1.getUnsignedMax().ult(CR2.getUnsignedMin());
case ULE:
@@ -1149,7 +1149,7 @@ namespace {
unsigned i = VN.valueNumber(*I, Subtree);
ConstantRange CR_Kill = i ? range(i, Subtree) : range(*I);
if (CR_Kill.isFullSet()) continue;
- Merged = Merged.maximalIntersectWith(CR_Kill);
+ Merged = Merged.intersectWith(CR_Kill);
}
if (Merged.isFullSet() || Merged == CR_New) return;
@@ -1159,7 +1159,7 @@ namespace {
void applyRange(unsigned n, const ConstantRange &CR,
DomTreeDFS::Node *Subtree, VRPSolver *VRP) {
- ConstantRange Merged = CR.maximalIntersectWith(range(n, Subtree));
+ ConstantRange Merged = CR.intersectWith(range(n, Subtree));
if (Merged.isEmptySet()) {
markBlock(VRP);
return;
@@ -1249,13 +1249,13 @@ namespace {
ConstantRange CR2 = range(n2, Subtree);
if (!CR1.isSingleElement()) {
- ConstantRange NewCR1 = CR1.maximalIntersectWith(create(LV, CR2));
+ ConstantRange NewCR1 = CR1.intersectWith(create(LV, CR2));
if (NewCR1 != CR1)
applyRange(n1, NewCR1, Subtree, VRP);
}
if (!CR2.isSingleElement()) {
- ConstantRange NewCR2 = CR2.maximalIntersectWith(
+ ConstantRange NewCR2 = CR2.intersectWith(
create(reversePredicate(LV), CR1));
if (NewCR2 != CR2)
applyRange(n2, NewCR2, Subtree, VRP);
diff --git a/unittests/Support/ConstantRangeTest.cpp b/unittests/Support/ConstantRangeTest.cpp
index 3ebb929..b77ac6a 100644
--- a/unittests/Support/ConstantRangeTest.cpp
+++ b/unittests/Support/ConstantRangeTest.cpp
@@ -203,22 +203,13 @@ TEST_F(ConstantRangeTest, IntersectWith) {
EXPECT_TRUE(Some.intersectWith(Wrap).isEmptySet());
EXPECT_TRUE(One.intersectWith(Wrap).isEmptySet());
EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
-}
-TEST_F(ConstantRangeTest, MaximalIntersectWith) {
- EXPECT_TRUE(Empty.maximalIntersectWith(Full).isEmptySet());
- EXPECT_TRUE(Empty.maximalIntersectWith(Empty).isEmptySet());
- EXPECT_TRUE(Empty.maximalIntersectWith(One).isEmptySet());
- EXPECT_TRUE(Empty.maximalIntersectWith(Some).isEmptySet());
- EXPECT_TRUE(Empty.maximalIntersectWith(Wrap).isEmptySet());
- EXPECT_TRUE(Full.maximalIntersectWith(Full).isFullSet());
- EXPECT_TRUE(Some.maximalIntersectWith(Some) == Some);
- EXPECT_TRUE(Some.maximalIntersectWith(One) == One);
- EXPECT_TRUE(Full.maximalIntersectWith(One) == One);
- EXPECT_TRUE(Full.maximalIntersectWith(Some) == Some);
- EXPECT_TRUE(Some.maximalIntersectWith(Wrap).isEmptySet());
- EXPECT_TRUE(One.maximalIntersectWith(Wrap).isEmptySet());
- EXPECT_EQ(One.maximalIntersectWith(Wrap), Wrap.maximalIntersectWith(One));
+ // Klee generated testcase from PR4545.
+ // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
+ // 01..4.6789ABCDEF where the dots represent values not in the intersection.
+ ConstantRange LHS(APInt(16, 4), APInt(16, 2));
+ ConstantRange RHS(APInt(16, 6), APInt(16, 5));
+ EXPECT_EQ(LHS.intersectWith(RHS), LHS);
}
TEST_F(ConstantRangeTest, UnionWith) {
generated by cgit v1.1 at 2024-07-31 07:33:37 +0000