diff --git a/llvm/include/llvm/IR/ConstantRange.h b/llvm/include/llvm/IR/ConstantRange.h --- a/llvm/include/llvm/IR/ConstantRange.h +++ b/llvm/include/llvm/IR/ConstantRange.h @@ -350,6 +350,14 @@ /// from a subtraction of a value in this range and a value in \p Other. ConstantRange sub(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting + /// from an subtraction 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 subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, + PreferredRangeType RangeType = Smallest) const; + /// Return a new range representing the possible values resulting /// from a multiplication of a value in this range and a value in \p Other, /// treating both this and \p Other as unsigned ranges. diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp --- a/llvm/lib/IR/ConstantRange.cpp +++ b/llvm/lib/IR/ConstantRange.cpp @@ -864,41 +864,17 @@ 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 an overflow happens for every value pair in these two constant ranges, + // we must return Empty set. In this case, we get that for free, because we + // get lucky that intersection of add() with uadd_sat()/sadd_sat() results + // in an empty set. if (NoWrapKind & OBO::NoSignedWrap) - Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType); + Result = Result.intersectWith(sadd_sat(Other), RangeType); + if (NoWrapKind & OBO::NoUnsignedWrap) - Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType); + Result = Result.intersectWith(uadd_sat(Other), RangeType); + return Result; } @@ -922,6 +898,36 @@ return X; } +ConstantRange ConstantRange::subWithNoWrap(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 = sub(Other); + + // If an overflow happens for every value pair in these two constant ranges, + // we must return Empty set. In signed case, we get that for free, because we + // get lucky that intersection of add() with ssub_sat() results in an + // empty set. But for unsigned we must perform the overflow check manually. + + if (NoWrapKind & OBO::NoSignedWrap) + Result = Result.intersectWith(ssub_sat(Other), RangeType); + + if (NoWrapKind & OBO::NoUnsignedWrap) { + if (getUnsignedMax().ult(Other.getUnsignedMin())) + return getEmpty(); + Result = Result.intersectWith(usub_sat(Other), RangeType); + } + + return Result; +} + ConstantRange ConstantRange::multiply(const ConstantRange &Other) const { // TODO: If either operand is a single element and the multiply is known to diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp --- a/llvm/unittests/IR/ConstantRangeTest.cpp +++ b/llvm/unittests/IR/ConstantRangeTest.cpp @@ -651,11 +651,13 @@ ConstantRange CR = RangeFn(CR1, CR2); APInt Min = APInt::getSignedMaxValue(Bits); APInt Max = APInt::getSignedMinValue(Bits); + bool AllOverflow = true; ForeachNumInConstantRange(CR1, [&](const APInt &N1) { ForeachNumInConstantRange(CR2, [&](const APInt &N2) { bool IsOverflow = false; APInt N = IntFn(IsOverflow, N1, N2); if (!IsOverflow) { + AllOverflow = false; if (N.slt(Min)) Min = N; if (N.sgt(Max)) @@ -664,6 +666,9 @@ } }); }); + + EXPECT_EQ(CR.isEmptySet(), AllOverflow); + if (!CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) { if (Min.sgt(Max)) { EXPECT_TRUE(CR.isEmptySet()); @@ -684,11 +689,13 @@ ConstantRange CR = RangeFn(CR1, CR2); APInt Min = APInt::getMaxValue(Bits); APInt Max = APInt::getMinValue(Bits); + bool AllOverflow = true; ForeachNumInConstantRange(CR1, [&](const APInt &N1) { ForeachNumInConstantRange(CR2, [&](const APInt &N2) { bool IsOverflow = false; APInt N = IntFn(IsOverflow, N1, N2); if (!IsOverflow) { + AllOverflow = false; if (N.ult(Min)) Min = N; if (N.ugt(Max)) @@ -698,6 +705,8 @@ }); }); + EXPECT_EQ(CR.isEmptySet(), AllOverflow); + if (!CR1.isWrappedSet() && !CR2.isWrappedSet()) { if (Min.ugt(Max)) { EXPECT_TRUE(CR.isEmptySet()); @@ -722,12 +731,14 @@ APInt UMax = APInt::getMinValue(Bits); APInt SMin = APInt::getSignedMaxValue(Bits); APInt SMax = APInt::getSignedMinValue(Bits); + bool AllOverflow = true; 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) { + AllOverflow = false; if (N.slt(SMin)) SMin = N; if (N.sgt(SMax)) @@ -741,6 +752,8 @@ }); }); + EXPECT_EQ(CR.isEmptySet(), AllOverflow); + if (!CR1.isWrappedSet() && !CR2.isWrappedSet() && !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) { if (UMin.ugt(UMax) || SMin.sgt(SMax)) { @@ -921,6 +934,34 @@ ConstantRange(APInt(16, 0x6))); } +TEST_F(ConstantRangeTest, SubWithNoWrap) { + typedef OverflowingBinaryOperator OBO; + TestAddWithNoSignedWrapExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.subWithNoWrap(CR2, OBO::NoSignedWrap); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.ssub_ov(N2, IsOverflow); + }); + TestAddWithNoUnsignedWrapExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.usub_ov(N2, IsOverflow); + }); + TestAddWithNoSignedUnsignedWrapExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.ssub_ov(N2, IsOverflow); + }, + [](bool &IsOverflow, const APInt &N1, const APInt &N2) { + return N1.usub_ov(N2, IsOverflow); + }); +} + TEST_F(ConstantRangeTest, Multiply) { EXPECT_EQ(Full.multiply(Full), Full); EXPECT_EQ(Full.multiply(Empty), Empty);