Index: llvm/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/include/llvm/IR/ConstantRange.h +++ llvm/include/llvm/IR/ConstantRange.h @@ -277,7 +277,8 @@ /// elements of both sets, but may contain more. For example, [3, 9) union /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included /// in either set before. - ConstantRange unionWith(const ConstantRange &CR) const; + ConstantRange unionWith(const ConstantRange &CR, + PreferredRangeType Type = Smallest) const; /// Return a new range representing the possible values resulting /// from an application of the specified cast operator to this range. \p Index: llvm/lib/IR/ConstantRange.cpp =================================================================== --- llvm/lib/IR/ConstantRange.cpp +++ llvm/lib/IR/ConstantRange.cpp @@ -467,6 +467,27 @@ return intersectWith(CR.inverse()); } +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() && @@ -479,24 +500,6 @@ if (!isUpperWrapped() && CR.isUpperWrapped()) return CR.intersectWith(*this, Type); - auto GetPreferredRange = [&]() { - if (Type == PreferredRangeType::Unsigned) { - if (!isWrappedSet() && CR.isWrappedSet()) - return *this; - if (isWrappedSet() && !CR.isWrappedSet()) - return CR; - } else if (Type == PreferredRangeType::Signed) { - if (!isSignWrappedSet() && CR.isSignWrappedSet()) - return *this; - if (isSignWrappedSet() && !CR.isSignWrappedSet()) - return CR; - } - - if (isSizeStrictlySmallerThan(CR)) - return *this; - return CR; - }; - if (!isUpperWrapped() && !CR.isUpperWrapped()) { if (Lower.ult(CR.Lower)) { // L---U : this @@ -542,7 +545,7 @@ // ------U L--- : this // L----------U : CR - return GetPreferredRange(); + return getPreferredRange(*this, CR, Type); } if (CR.Lower.ult(Lower)) { // --U L---- : this @@ -564,7 +567,7 @@ // ------U L-- : this // --U L------ : CR if (CR.Lower.ult(Upper)) - return GetPreferredRange(); + return getPreferredRange(*this, CR, Type); // ----U L-- : this // --U L---- : CR @@ -588,26 +591,24 @@ // --U L------ : this // ------U L-- : CR - return GetPreferredRange(); + return getPreferredRange(*this, CR, Type); } -ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { +ConstantRange ConstantRange::unionWith(const ConstantRange &CR, + PreferredRangeType Type) const { assert(getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!"); if ( isFullSet() || CR.isEmptySet()) return *this; if (CR.isFullSet() || isEmptySet()) return CR; - if (!isUpperWrapped() && CR.isUpperWrapped()) return CR.unionWith(*this); + if (!isUpperWrapped() && CR.isUpperWrapped()) + return CR.unionWith(*this, Type); if (!isUpperWrapped() && !CR.isUpperWrapped()) { - if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { - // If the two ranges are disjoint, find the smaller gap and bridge it. - APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; - if (d1.ult(d2)) - return ConstantRange(Lower, CR.Upper); - return ConstantRange(CR.Lower, Upper); - } + if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) + return getPreferredRange( + ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type); APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper; @@ -631,22 +632,18 @@ // ----U L---- : this // L---U : CR - // - if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { - APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; - if (d1.ult(d2)) - return ConstantRange(Lower, CR.Upper); - return ConstantRange(CR.Lower, Upper); - } + if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) + return getPreferredRange( + ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type); // ----U L----- : this // L----U : CR - if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) + if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper)) return ConstantRange(CR.Lower, Upper); // ------U L---- : this // L-----U : CR - assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && + assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) && "ConstantRange::unionWith missed a case with one range wrapped"); return ConstantRange(Lower, CR.Upper); } Index: llvm/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/unittests/IR/ConstantRangeTest.cpp +++ llvm/unittests/IR/ConstantRangeTest.cpp @@ -363,7 +363,8 @@ EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0))); } -TEST_F(ConstantRangeTest, IntersectWithExhaustive) { +template +void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 InResultFn) { unsigned Bits = 4; EnumerateTwoConstantRanges(Bits, [=](const ConstantRange &CR1, const ConstantRange &CR2) { @@ -379,7 +380,7 @@ APInt Num(Bits, 0); for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num) { - if (!CR1.contains(Num) || !CR2.contains(Num)) { + if (!InResultFn(CR1, CR2, Num)) { if (HaveRange3) HaveInterrupt3 = true; else if (HaveRange2) @@ -409,12 +410,9 @@ assert(!HaveInterrupt3 && "Should have at most three ranges"); - ConstantRange SmallestCR = - CR1.intersectWith(CR2, ConstantRange::Smallest); - ConstantRange UnsignedCR = - CR1.intersectWith(CR2, ConstantRange::Unsigned); - ConstantRange SignedCR = - CR1.intersectWith(CR2, ConstantRange::Signed); + ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest); + ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned); + ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed); if (!HaveRange1) { EXPECT_TRUE(SmallestCR.isEmptySet()); @@ -492,6 +490,28 @@ }); } +TEST_F(ConstantRangeTest, IntersectWithExhaustive) { + testBinarySetOperationExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2, + ConstantRange::PreferredRangeType Type) { + return CR1.intersectWith(CR2, Type); + }, + [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) { + return CR1.contains(N) && CR2.contains(N); + }); +} + +TEST_F(ConstantRangeTest, UnionWithExhaustive) { + testBinarySetOperationExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2, + ConstantRange::PreferredRangeType Type) { + return CR1.unionWith(CR2, Type); + }, + [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) { + return CR1.contains(N) || CR2.contains(N); + }); +} + TEST_F(ConstantRangeTest, UnionWith) { EXPECT_EQ(Wrap.unionWith(One), ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));