Index: llvm/trunk/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/trunk/include/llvm/IR/ConstantRange.h +++ llvm/trunk/include/llvm/IR/ConstantRange.h @@ -330,6 +330,14 @@ /// from an addition of a value in this range and a value in \p Other. ConstantRange add(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting + /// from an addition with wrap type \p NoWrapKind of a value in this + /// range and a value in \p Other. + /// If the result range is disjoint, the preferred range is determined by the + /// \p PreferredRangeType. + ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, + PreferredRangeType RangeType = Smallest) const; + /// Return a new range representing the possible values resulting from a /// known NSW addition of a value in this range and \p Other constant. ConstantRange addWithNoSignedWrap(const APInt &Other) const; Index: llvm/trunk/lib/IR/ConstantRange.cpp =================================================================== --- llvm/trunk/lib/IR/ConstantRange.cpp +++ llvm/trunk/lib/IR/ConstantRange.cpp @@ -815,6 +815,57 @@ return X; } +ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other, + unsigned NoWrapKind, + PreferredRangeType RangeType) const { + // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow). + // (X is from this, and Y is from Other) + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + if (isFullSet() && Other.isFullSet()) + return getFull(); + + using OBO = OverflowingBinaryOperator; + ConstantRange Result = add(Other); + + auto addWithNoUnsignedWrap = [this](const ConstantRange &Other) { + APInt LMin = getUnsignedMin(), LMax = getUnsignedMax(); + APInt RMin = Other.getUnsignedMin(), RMax = Other.getUnsignedMax(); + bool Overflow; + APInt NewMin = LMin.uadd_ov(RMin, Overflow); + if (Overflow) + return getEmpty(); + APInt NewMax = LMax.uadd_sat(RMax); + return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1); + }; + + auto addWithNoSignedWrap = [this](const ConstantRange &Other) { + APInt LMin = getSignedMin(), LMax = getSignedMax(); + APInt RMin = Other.getSignedMin(), RMax = Other.getSignedMax(); + if (LMin.isNonNegative()) { + bool Overflow; + APInt Temp = LMin.sadd_ov(RMin, Overflow); + if (Overflow) + return getEmpty(); + } + if (LMax.isNegative()) { + bool Overflow; + APInt Temp = LMax.sadd_ov(RMax, Overflow); + if (Overflow) + return getEmpty(); + } + APInt NewMin = LMin.sadd_sat(RMin); + APInt NewMax = LMax.sadd_sat(RMax); + return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1); + }; + + if (NoWrapKind & OBO::NoSignedWrap) + Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType); + if (NoWrapKind & OBO::NoUnsignedWrap) + Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType); + return Result; +} + ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const { // Calculate the subset of this range such that "X + Other" is // guaranteed not to wrap (overflow) for all X in this subset. Index: llvm/trunk/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/ConstantRangeTest.cpp +++ llvm/trunk/unittests/IR/ConstantRangeTest.cpp @@ -669,6 +669,262 @@ ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10))); } +template +static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) { + unsigned Bits = 4; + EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1, + const ConstantRange &CR2) { + ConstantRange CR = RangeFn(CR1, CR2); + APInt Min = APInt::getSignedMaxValue(Bits); + APInt Max = APInt::getSignedMinValue(Bits); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + bool IsOverflow = false; + APInt N = IntFn(IsOverflow, N1, N2); + if (!IsOverflow) { + if (N.slt(Min)) + Min = N; + if (N.sgt(Max)) + Max = N; + EXPECT_TRUE(CR.contains(N)); + } + }); + }); + if (!CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) { + if (Min.sgt(Max)) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1); + EXPECT_EQ(Exact, CR); + } + }); +} + +template +static void TestAddWithNoUnsignedWrapExhaustive(Fn1 RangeFn, Fn2 IntFn) { + unsigned Bits = 4; + EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1, + const ConstantRange &CR2) { + ConstantRange CR = RangeFn(CR1, CR2); + APInt Min = APInt::getMaxValue(Bits); + APInt Max = APInt::getMinValue(Bits); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + bool IsOverflow = false; + APInt N = IntFn(IsOverflow, N1, N2); + if (!IsOverflow) { + if (N.ult(Min)) + Min = N; + if (N.ugt(Max)) + Max = N; + EXPECT_TRUE(CR.contains(N)); + } + }); + }); + + if (!CR1.isWrappedSet() && !CR2.isWrappedSet()) { + if (Min.ugt(Max)) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1); + EXPECT_EQ(Exact, CR); + } + }); +} + +template +static void TestAddWithNoSignedUnsignedWrapExhaustive(Fn1 RangeFn, + Fn2 IntFnSigned, + Fn3 IntFnUnsigned) { + unsigned Bits = 4; + EnumerateTwoConstantRanges( + Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) { + ConstantRange CR = RangeFn(CR1, CR2); + APInt UMin = APInt::getMaxValue(Bits); + APInt UMax = APInt::getMinValue(Bits); + APInt SMin = APInt::getSignedMaxValue(Bits); + APInt SMax = APInt::getSignedMinValue(Bits); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + bool IsOverflow = false, IsSignedOverflow = false; + APInt N = IntFnSigned(IsSignedOverflow, N1, N2); + (void) IntFnUnsigned(IsOverflow, N1, N2); + if (!IsSignedOverflow && !IsOverflow) { + if (N.slt(SMin)) + SMin = N; + if (N.sgt(SMax)) + SMax = N; + if (N.ult(UMin)) + UMin = N; + if (N.ugt(UMax)) + UMax = N; + EXPECT_TRUE(CR.contains(N)); + } + }); + }); + + if (!CR1.isWrappedSet() && !CR2.isWrappedSet() && + !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) { + if (UMin.ugt(UMax) || SMin.sgt(SMax)) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + ConstantRange Exact = + ConstantRange::getNonEmpty(SMin, SMax + 1) + .intersectWith(ConstantRange::getNonEmpty(UMin, UMax + 1)); + EXPECT_EQ(Exact, CR); + } + }); +} + +TEST_F(ConstantRangeTest, AddWithNoWrap) { + typedef OverflowingBinaryOperator OBO; + EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoSignedWrap), Empty); + EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoSignedWrap), Empty); + EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoSignedWrap), Full); + EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoSignedWrap), Full); + EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoSignedWrap), Full); + EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)), + OBO::NoSignedWrap), + ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN))); + EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2)) + .addWithNoWrap(Full, OBO::NoSignedWrap), + ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN))); + EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, -1), APInt(16, 0)), + OBO::NoSignedWrap), + ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX))); + EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120)) + .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)), + OBO::NoSignedWrap), + ConstantRange(8, false)); + EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, -100)) + .addWithNoWrap(ConstantRange(APInt(8, -110), APInt(8, -100)), + OBO::NoSignedWrap), + ConstantRange(8, false)); + EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101)) + .addWithNoWrap(ConstantRange(APInt(8, -128), APInt(8, 28)), + OBO::NoSignedWrap), + ConstantRange(8, true)); + EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101)) + .addWithNoWrap(ConstantRange(APInt(8, -120), APInt(8, 29)), + OBO::NoSignedWrap), + ConstantRange(APInt(8, -120), APInt(8, -128))); + EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)) + .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)), + OBO::NoSignedWrap), + ConstantRange(APInt(8, -40), APInt(8, 69))); + EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20)) + .addWithNoWrap(ConstantRange(APInt(8, -50), APInt(8, 50)), + OBO::NoSignedWrap), + ConstantRange(APInt(8, -40), APInt(8, 69))); + EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10)) + .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)), + OBO::NoSignedWrap), + ConstantRange(APInt(8, 125), APInt(8, 9))); + EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20)) + .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)), + OBO::NoSignedWrap), + ConstantRange(APInt(8, 125), APInt(8, 9))); + + TestAddWithNoSignedWrapExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.addWithNoWrap(CR2, OBO::NoSignedWrap); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.sadd_ov(N2, IsOverflow); + }); + + EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoUnsignedWrap), Empty); + EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty); + EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full); + EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoUnsignedWrap), Full); + EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full); + EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(16, 1), APInt(16, 0))); + EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2)) + .addWithNoWrap(Full, OBO::NoUnsignedWrap), + ConstantRange(APInt(16, 1), APInt(16, 0))); + EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220)) + .addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)), + OBO::NoUnsignedWrap), + ConstantRange(8, false)); + EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101)) + .addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)), + OBO::NoUnsignedWrap), + ConstantRange(8, true)); + EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101)) + .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 10), APInt(8, 129))); + EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10)) + .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 50), APInt(8, 0))); + EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20)) + .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 60), APInt(8, -37))); + EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30)) + .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 25), APInt(8, -11))); + EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20)) + .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 25), APInt(8, -11))); + + TestAddWithNoUnsignedWrapExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.uadd_ov(N2, IsOverflow); + }); + + EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100)) + .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)), + OBO::NoSignedWrap), + ConstantRange(APInt(8, 70), APInt(8, -128))); + EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100)) + .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 70), APInt(8, 169))); + EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100)) + .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)), + OBO::NoUnsignedWrap | OBO::NoSignedWrap), + ConstantRange(APInt(8, 70), APInt(8, -128))); + + EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50)) + .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)), + OBO::NoSignedWrap), + ConstantRange(APInt(8, -80), APInt(8, -21))); + EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50)) + .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 176), APInt(8, 235))); + EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50)) + .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)), + OBO::NoUnsignedWrap | OBO::NoSignedWrap), + ConstantRange(APInt(8, 176), APInt(8, 235))); + + TestAddWithNoSignedUnsignedWrapExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.sadd_ov(N2, IsOverflow); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.uadd_ov(N2, IsOverflow); + }); +} + TEST_F(ConstantRangeTest, Sub) { EXPECT_EQ(Full.sub(APInt(16, 4)), Full); EXPECT_EQ(Full.sub(Full), Full);