Index: llvm/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/include/llvm/IR/ConstantRange.h +++ llvm/include/llvm/IR/ConstantRange.h @@ -330,6 +330,12 @@ /// 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. + 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/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,18 @@ if (const SCEVAddExpr *Add = dyn_cast(S)) { ConstantRange X = getRangeRef(Add->getOperand(0), SignHint); - for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) - X = X.add(getRangeRef(Add->getOperand(i), SignHint)); + for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) { + if (Add->hasNoSignedWrap() && + SignHint == ScalarEvolution::HINT_RANGE_SIGNED) + X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), + OBO::NoSignedWrap); + else if (Add->hasNoUnsignedWrap() && + SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) + X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), + OBO::NoUnsignedWrap); + else + X = X.add(getRangeRef(Add->getOperand(i), SignHint)); + } 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,34 @@ 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) + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + if (isFullSet() && Other.isFullSet()) + return getFull(); + + using OBO = OverflowingBinaryOperator; + assert( + (NoWrapKind == OBO::NoSignedWrap || NoWrapKind == OBO::NoUnsignedWrap) && + "NoWrapKind invalid!"); + + auto ConstantRangeWithNW = [&](const ConstantRange &NonFullRange, + const ConstantRange &Other) { + if (NonFullRange.isFullSet()) + return getFull(); + auto NWRange = ConstantRange::makeGuaranteedNoWrapRegion( + BinaryOperator::Add, NonFullRange, NoWrapKind); + auto NWConstrainedRange = Other.intersectWith(NWRange); + + return NWConstrainedRange.add(NonFullRange); + }; + return Other.isFullSet() ? ConstantRangeWithNW(*this, Other) + : ConstantRangeWithNW(Other, *this); +} + 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,73 @@ 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, -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, -INT8_MIN + 5), APInt(8, 9))); + // TODO: this should return [-INT8_MIN+5, 9) + EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20)) + .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)), + OBO::NoSignedWrap), + ConstantRange(8, false)); + + 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, 10), APInt(8, 20)) + .addWithNoWrap(ConstantRange(APInt(8, 1), APInt(8, 5)), + OBO::NoUnsignedWrap), + ConstantRange(APInt(8, 11), APInt(8, 24))); + 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, 50), APInt(8, 200)) + .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)), + 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);