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/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -5546,6 +5546,7 @@ if (const SCEVConstant *C = dyn_cast(S)) return setRange(C, SignHint, ConstantRange(C->getAPInt())); + using OBO = OverflowingBinaryOperator; unsigned BitWidth = getTypeSizeInBits(S->getType()); ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true); @@ -5566,8 +5567,16 @@ if (const SCEVAddExpr *Add = dyn_cast(S)) { ConstantRange X = getRangeRef(Add->getOperand(0), SignHint); + unsigned WrapType = OBO::AnyWrap; + if (Add->hasNoSignedWrap() && + SignHint == ScalarEvolution::HINT_RANGE_SIGNED) + WrapType = OBO::NoSignedWrap; + else if (Add->hasNoUnsignedWrap() && + SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) + WrapType = OBO::NoUnsignedWrap; for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) - X = X.add(getRangeRef(Add->getOperand(i), SignHint)); + X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), + WrapType); return setRange(Add, SignHint, ConservativeResult.intersectWith(X, RangeType)); } Index: llvm/lib/IR/ConstantRange.cpp =================================================================== --- llvm/lib/IR/ConstantRange.cpp +++ llvm/lib/IR/ConstantRange.cpp @@ -815,6 +815,99 @@ 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); + + OverflowResult OR = unsignedAddMayOverflow(Other); + + if (OR == OverflowResult::AlwaysOverflowsHigh || + OR == OverflowResult::AlwaysOverflowsLow) + return getEmpty(); + else if (OR == OverflowResult::NeverOverflows) { + // For unsigned value, new lower and new upper may be both equal to + // 0, this is full range, but can not be represented by + // [0, 0) which is empty range. + if (getUnsignedMin() + Other.getUnsignedMin() == + getUnsignedMax() + Other.getUnsignedMax() + 1) + return getFull(); + return ConstantRange(getUnsignedMin() + Other.getUnsignedMin(), + getUnsignedMax() + Other.getUnsignedMax() + 1); + } else { // OverflowResult::MayOverflow + // For unsigned value, new lower and new upper may be both equal to + // 0, this is full range, but can not be represented by + // [0, 0) which is empty range. + if ((getUnsignedMin() + Other.getUnsignedMin()) == 0) + return getFull(); + return ConstantRange(getUnsignedMin() + Other.getUnsignedMin(), + APInt::getMinValue(getBitWidth())); + } + } else { + // FIXME: handle Non-continuous range add with no wrap flags. + if (isSignWrappedSet() || Other.isSignWrappedSet()) + return add(Other); + + OverflowResult OR = signedAddMayOverflow(Other); + + if (OR == OverflowResult::AlwaysOverflowsHigh || + OR == OverflowResult::AlwaysOverflowsLow) + return getEmpty(); + else if (OR == OverflowResult::NeverOverflows) { + // For sign value, new lower and new upper may be both equal to + // SignedMin, this is full range, but can not be represented by + // [SignedMin, SignedMin) which is not a valid range. + if ((getSignedMin() + Other.getSignedMin()) == + (getSignedMax() + Other.getSignedMax() + 1)) + return getFull(); + return ConstantRange(getSignedMin() + Other.getSignedMin(), + getSignedMax() + Other.getSignedMax() + 1); + } else { // OverflowResult::MayOverflow + APInt Min = getSignedMin(), Max = getSignedMax(); + APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax(); + + APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); + APInt SignedMax = APInt::getSignedMaxValue(getBitWidth()); + bool MayOverflowsHigh = false; + bool MayOverflowsLow = false; + + if (Max.isNonNegative() && OtherMax.isNonNegative() && + Max.sgt(SignedMax - OtherMax)) + MayOverflowsHigh = true; + if (Min.isNegative() && OtherMin.isNegative() && + Min.slt(SignedMin - OtherMin)) + MayOverflowsLow = true; + + APInt NewLower = MayOverflowsLow ? SignedMin : Min + OtherMin; + APInt NewUpper = MayOverflowsHigh ? SignedMax + 1 : Max + OtherMax + 1; + + // For signed value, new lower and new upper may be both equal to + // SignedMin, this is full range, but can not be represented by + // [SignedMin, SignedMin) which is not a valid range. + if (NewLower == NewUpper) + return getFull(); + return ConstantRange(std::move(NewLower), std::move(NewUpper)); + } + } +} + 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/test/Analysis/ScalarEvolution/max-trip-count.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/max-trip-count.ll +++ llvm/test/Analysis/ScalarEvolution/max-trip-count.ll @@ -342,7 +342,7 @@ define void @changing_end_bound3(i32 %start, i32* %n_addr, i32* %addr) { ; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound3 ; CHECK: Loop %loop: Unpredictable backedge-taken count. -; CHECK: Loop %loop: max backedge-taken count is 1073741823 +; CHECK: Loop %loop: max backedge-taken count is 1073741822 entry: br label %loop Index: llvm/test/Analysis/ScalarEvolution/trip-count12.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/trip-count12.ll +++ llvm/test/Analysis/ScalarEvolution/trip-count12.ll @@ -2,7 +2,7 @@ ; CHECK: Determining loop execution counts for: @test ; CHECK: Loop %for.body: backedge-taken count is ((-2 + %len) /u 2) -; CHECK: Loop %for.body: max backedge-taken count is 1073741823 +; CHECK: Loop %for.body: max backedge-taken count is 1073741822 define zeroext i16 @test(i16* nocapture %p, i32 %len) nounwind readonly { entry: Index: llvm/test/Analysis/ScalarEvolution/trip-count9.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/trip-count9.ll +++ llvm/test/Analysis/ScalarEvolution/trip-count9.ll @@ -180,7 +180,7 @@ ; CHECK: Determining loop execution counts for: @nsw_startx ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n)) -; CHECK: Loop %loop: max backedge-taken count is -1 +; CHECK: Loop %loop: max backedge-taken count is -2 define void @nsw_startx(i4 %n, i4 %x) { entry: %s = icmp sgt i4 %n, 0 @@ -196,7 +196,7 @@ ; CHECK: Determining loop execution counts for: @nsw_startx_step2 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2) -; CHECK: Loop %loop: max backedge-taken count is 7 +; CHECK: Loop %loop: max backedge-taken count is 6 define void @nsw_startx_step2(i4 %n, i4 %x) { entry: %s = icmp sgt i4 %n, 0 @@ -227,6 +227,7 @@ ret void } +; CHECK-LABEL: even_step2 ; CHECK: Determining loop execution counts for: @even_step2 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2) ; CHECK: Loop %loop: max backedge-taken count is 2 @@ -382,7 +383,7 @@ ; CHECK: Determining loop execution counts for: @even_nsw_startx ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n))) -; CHECK: Loop %loop: max backedge-taken count is -2 +; CHECK: Loop %loop: max backedge-taken count is -3 define void @even_nsw_startx(i4 %n, i4 %x) { entry: %m = shl i4 %n, 1 @@ -399,7 +400,7 @@ ; CHECK: Determining loop execution counts for: @even_nsw_startx_step2 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2) -; CHECK: Loop %loop: max backedge-taken count is 7 +; CHECK: Loop %loop: max backedge-taken count is 6 define void @even_nsw_startx_step2(i4 %n, i4 %x) { entry: %m = shl i4 %n, 1 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);