Index: llvm/trunk/include/llvm/IR/ConstantRange.h
===================================================================
--- llvm/trunk/include/llvm/IR/ConstantRange.h
+++ llvm/trunk/include/llvm/IR/ConstantRange.h
@@ -255,13 +255,22 @@
/// the sets).
ConstantRange difference(const ConstantRange &CR) const;
- /// 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.intersectWith(B) might not
- /// be equal to B.intersectWith(A).
- ConstantRange intersectWith(const ConstantRange &CR) const;
+ /// If represented precisely, the result of some range operations may consist
+ /// of multiple disjoint ranges. As only a single range may be returned, any
+ /// range covering these disjoint ranges constitutes a valid result, but some
+ /// may be more useful than others depending on context. The preferred range
+ /// type specifies whether a range that is non-wrapping in the unsigned or
+ /// signed domain, or has the smallest size, is preferred. If a signedness is
+ /// preferred but all ranges are non-wrapping or all wrapping, then the
+ /// smallest set size is preferred. If there are multiple smallest sets, any
+ /// one of them may be returned.
+ enum PreferredRangeType { Smallest, Unsigned, Signed };
+
+ /// Return the range that results from the intersection of this range with
+ /// another range. If the intersection is disjoint, such that two results
+ /// are possible, the preferred range is determined by the PreferredRangeType.
+ ConstantRange intersectWith(const ConstantRange &CR,
+ PreferredRangeType Type = Smallest) const;
/// Return the range that results from the union of this range
/// with another range. The resultant range is guaranteed to include the
Index: llvm/trunk/lib/IR/ConstantRange.cpp
===================================================================
--- llvm/trunk/lib/IR/ConstantRange.cpp
+++ llvm/trunk/lib/IR/ConstantRange.cpp
@@ -467,7 +467,28 @@
return intersectWith(CR.inverse());
}
-ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
+static ConstantRange getPreferredRange(
+ const ConstantRange &CR1, const ConstantRange &CR2,
+ ConstantRange::PreferredRangeType Type) {
+ if (Type == ConstantRange::Unsigned) {
+ if (!CR1.isWrappedSet() && CR2.isWrappedSet())
+ return CR1;
+ if (CR1.isWrappedSet() && !CR2.isWrappedSet())
+ return CR2;
+ } else if (Type == ConstantRange::Signed) {
+ if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
+ return CR1;
+ if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
+ return CR2;
+ }
+
+ if (CR1.isSizeStrictlySmallerThan(CR2))
+ return CR1;
+ return CR2;
+}
+
+ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,
+ PreferredRangeType Type) const {
assert(getBitWidth() == CR.getBitWidth() &&
"ConstantRange types don't agree!");
@@ -476,69 +497,100 @@
if (CR.isEmptySet() || isFullSet()) return CR;
if (!isUpperWrapped() && CR.isUpperWrapped())
- return CR.intersectWith(*this);
+ return CR.intersectWith(*this, Type);
if (!isUpperWrapped() && !CR.isUpperWrapped()) {
if (Lower.ult(CR.Lower)) {
+ // L---U : this
+ // L---U : CR
if (Upper.ule(CR.Lower))
return getEmpty();
+ // L---U : this
+ // L---U : CR
if (Upper.ult(CR.Upper))
return ConstantRange(CR.Lower, Upper);
+ // L-------U : this
+ // L---U : CR
return CR;
}
+ // L---U : this
+ // L-------U : CR
if (Upper.ult(CR.Upper))
return *this;
+ // L-----U : this
+ // L-----U : CR
if (Lower.ult(CR.Upper))
return ConstantRange(Lower, CR.Upper);
+ // L---U : this
+ // L---U : CR
return getEmpty();
}
if (isUpperWrapped() && !CR.isUpperWrapped()) {
if (CR.Lower.ult(Upper)) {
+ // ------U L--- : this
+ // L--U : CR
if (CR.Upper.ult(Upper))
return CR;
+ // ------U L--- : this
+ // L------U : CR
if (CR.Upper.ule(Lower))
return ConstantRange(CR.Lower, Upper);
- if (isSizeStrictlySmallerThan(CR))
- return *this;
- return CR;
+ // ------U L--- : this
+ // L----------U : CR
+ return getPreferredRange(*this, CR, Type);
}
if (CR.Lower.ult(Lower)) {
+ // --U L---- : this
+ // L--U : CR
if (CR.Upper.ule(Lower))
return getEmpty();
+ // --U L---- : this
+ // L------U : CR
return ConstantRange(Lower, CR.Upper);
}
+
+ // --U L------ : this
+ // L--U : CR
return CR;
}
if (CR.Upper.ult(Upper)) {
- if (CR.Lower.ult(Upper)) {
- if (isSizeStrictlySmallerThan(CR))
- return *this;
- return CR;
- }
+ // ------U L-- : this
+ // --U L------ : CR
+ if (CR.Lower.ult(Upper))
+ return getPreferredRange(*this, CR, Type);
+ // ----U L-- : this
+ // --U L---- : CR
if (CR.Lower.ult(Lower))
return ConstantRange(Lower, CR.Upper);
+ // ----U L---- : this
+ // --U L-- : CR
return CR;
}
if (CR.Upper.ule(Lower)) {
+ // --U L-- : this
+ // ----U L---- : CR
if (CR.Lower.ult(Lower))
return *this;
+ // --U L---- : this
+ // ----U L-- : CR
return ConstantRange(CR.Lower, Upper);
}
- if (isSizeStrictlySmallerThan(CR))
- return *this;
- return CR;
+
+ // --U L------ : this
+ // ------U L-- : CR
+ return getPreferredRange(*this, CR, Type);
}
ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
Index: llvm/trunk/unittests/IR/ConstantRangeTest.cpp
===================================================================
--- llvm/trunk/unittests/IR/ConstantRangeTest.cpp
+++ llvm/trunk/unittests/IR/ConstantRangeTest.cpp
@@ -409,19 +409,30 @@
assert(!HaveInterrupt3 && "Should have at most three ranges");
- ConstantRange CR = CR1.intersectWith(CR2);
+ ConstantRange SmallestCR =
+ CR1.intersectWith(CR2, ConstantRange::Smallest);
+ ConstantRange UnsignedCR =
+ CR1.intersectWith(CR2, ConstantRange::Unsigned);
+ ConstantRange SignedCR =
+ CR1.intersectWith(CR2, ConstantRange::Signed);
if (!HaveRange1) {
- EXPECT_TRUE(CR.isEmptySet());
+ EXPECT_TRUE(SmallestCR.isEmptySet());
+ EXPECT_TRUE(UnsignedCR.isEmptySet());
+ EXPECT_TRUE(SignedCR.isEmptySet());
return;
}
if (!HaveRange2) {
if (Lower1 == Upper1 + 1) {
- EXPECT_TRUE(CR.isFullSet());
+ EXPECT_TRUE(SmallestCR.isFullSet());
+ EXPECT_TRUE(UnsignedCR.isFullSet());
+ EXPECT_TRUE(SignedCR.isFullSet());
} else {
ConstantRange Expected(Lower1, Upper1 + 1);
- EXPECT_EQ(Expected, CR);
+ EXPECT_EQ(Expected, SmallestCR);
+ EXPECT_EQ(Expected, UnsignedCR);
+ EXPECT_EQ(Expected, SignedCR);
}
return;
}
@@ -443,13 +454,41 @@
Variant2 = ConstantRange(Lower3, Upper2 + 1);
}
- // The intersection should return the smaller of the two variants.
+ // Smallest: Smaller set, then any set.
if (Variant1.isSizeStrictlySmallerThan(Variant2))
- EXPECT_EQ(Variant1, CR);
+ EXPECT_EQ(Variant1, SmallestCR);
else if (Variant2.isSizeStrictlySmallerThan(Variant1))
- EXPECT_EQ(Variant2, CR);
+ EXPECT_EQ(Variant2, SmallestCR);
else
- EXPECT_TRUE(Variant1 == CR || Variant2 == CR);
+ EXPECT_TRUE(Variant1 == SmallestCR || Variant2 == SmallestCR);
+
+ // Unsigned: Non-wrapped set, then smaller set, then any set.
+ bool Variant1Full = Variant1.isFullSet() || Variant1.isWrappedSet();
+ bool Variant2Full = Variant2.isFullSet() || Variant2.isWrappedSet();
+ if (!Variant1Full && Variant2Full)
+ EXPECT_EQ(Variant1, UnsignedCR);
+ else if (Variant1Full && !Variant2Full)
+ EXPECT_EQ(Variant2, UnsignedCR);
+ else if (Variant1.isSizeStrictlySmallerThan(Variant2))
+ EXPECT_EQ(Variant1, UnsignedCR);
+ else if (Variant2.isSizeStrictlySmallerThan(Variant1))
+ EXPECT_EQ(Variant2, UnsignedCR);
+ else
+ EXPECT_TRUE(Variant1 == UnsignedCR || Variant2 == UnsignedCR);
+
+ // Signed: Signed non-wrapped set, then smaller set, then any set.
+ Variant1Full = Variant1.isFullSet() || Variant1.isSignWrappedSet();
+ Variant2Full = Variant2.isFullSet() || Variant2.isSignWrappedSet();
+ if (!Variant1Full && Variant2Full)
+ EXPECT_EQ(Variant1, SignedCR);
+ else if (Variant1Full && !Variant2Full)
+ EXPECT_EQ(Variant2, SignedCR);
+ else if (Variant1.isSizeStrictlySmallerThan(Variant2))
+ EXPECT_EQ(Variant1, SignedCR);
+ else if (Variant2.isSizeStrictlySmallerThan(Variant1))
+ EXPECT_EQ(Variant2, SignedCR);
+ else
+ EXPECT_TRUE(Variant1 == SignedCR || Variant2 == SignedCR);
});
}