Index: llvm/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/include/llvm/IR/ConstantRange.h +++ llvm/include/llvm/IR/ConstantRange.h @@ -330,6 +330,13 @@ /// 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 \p NoWrapKind is AnyWrap, this is a normal range add. + ConstantRange addWithNoWrap(const ConstantRange &Other, + unsigned NoWrapKind) 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/include/llvm/IR/Operator.h =================================================================== --- llvm/include/llvm/IR/Operator.h +++ llvm/include/llvm/IR/Operator.h @@ -66,6 +66,7 @@ class OverflowingBinaryOperator : public Operator { public: enum { + AnyWrap = 0, NoUnsignedWrap = (1 << 0), NoSignedWrap = (1 << 1) }; Index: llvm/lib/IR/ConstantRange.cpp =================================================================== --- llvm/lib/IR/ConstantRange.cpp +++ llvm/lib/IR/ConstantRange.cpp @@ -815,6 +815,60 @@ return X; } +ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other, + unsigned NoWrapKind) const { + // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow). + // (X is from this, and Y is from Other) + using OBO = OverflowingBinaryOperator; + if (NoWrapKind == OBO::AnyWrap) + return add(Other); + + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + if (isFullSet() && Other.isFullSet()) + return getFull(); + + assert( + (NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap) && + "NoWrapKind invalid!"); + + if (NoWrapKind == OBO::NoUnsignedWrap) { + // FIXME: handle Non-continuous range add with no wrap flags. + if (isWrappedSet() || Other.isWrappedSet()) + return add(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 ConstantRange::getEmpty(LMin.getBitWidth()); + APInt NewMax = LMax.uadd_sat(RMax); + return ConstantRange::getNonEmpty(std::move(NewMin), std::move(NewMax) + 1); + } else { + // FIXME: handle Non-continuous range add with no wrap flags. + if (isSignWrappedSet() || Other.isSignWrappedSet()) + return add(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 ConstantRange::getEmpty(LMin.getBitWidth()); + } + if (LMax.isNegative()) { + bool Overflow; + APInt Temp = LMax.sadd_ov(RMax, Overflow); + if (Overflow) + return ConstantRange::getEmpty(LMax.getBitWidth()); + } + APInt NewMin = LMin.sadd_sat(RMin); + APInt NewMax = LMax.sadd_sat(RMax); + return ConstantRange::getNonEmpty(std::move(NewMin), std::move(NewMax) + 1); + } +} + 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/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/unittests/IR/ConstantRangeTest.cpp +++ llvm/unittests/IR/ConstantRangeTest.cpp @@ -669,6 +669,96 @@ ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10))); } +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))); + + 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(8, true)); + 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))); +} + TEST_F(ConstantRangeTest, Sub) { EXPECT_EQ(Full.sub(APInt(16, 4)), Full); EXPECT_EQ(Full.sub(Full), Full);