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); }); }