Index: include/llvm/IR/ConstantRange.h =================================================================== --- include/llvm/IR/ConstantRange.h +++ include/llvm/IR/ConstantRange.h @@ -92,27 +92,12 @@ static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other); - /// Return the largest range containing all X such that "X BinOpC Y" is - /// guaranteed not to wrap (overflow) for all Y in Other. - /// - /// NB! The returned set does *not* contain **all** possible values of X for - /// which "X BinOpC Y" does not wrap -- some viable values of X may be - /// missing, so you cannot use this to contrain X's range. E.g. in the last - /// example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2), but (-2) - /// is not in the set returned. - /// - /// Examples: - /// typedef OverflowingBinaryOperator OBO; - /// #define MGNR makeGuaranteedNoWrapRegion - /// MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127) - /// MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1) - /// MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set - /// MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap) - /// == [0,INT_MAX) - /// MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4) - static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, - const ConstantRange &Other, - unsigned NoWrapKind); + /// Conservatively return true if any pair of values chosen from ranges L and + /// R can overflow a signed or unsigned addition, subtraction, or + /// multiplication. Conversely, return false if we can prove that no overflow + /// happens. + static bool mayOverflow(const ConstantRange &L, const ConstantRange &R, + unsigned Opcode, bool Signed); /// Set up \p Pred and \p RHS such that /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this. Return true if Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -1976,7 +1976,6 @@ const SmallVectorImpl &Ops, SCEV::NoWrapFlags Flags) { using namespace std::placeholders; - typedef OverflowingBinaryOperator OBO; bool CanAnalyze = Type == scAddExpr || Type == scAddRecExpr || Type == scMulExpr; @@ -2006,15 +2005,13 @@ const APInt &C = cast(Ops[0])->getAPInt(); if (!(SignOrUnsignWrap & SCEV::FlagNSW)) { - auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, C, OBO::NoSignedWrap); - if (NSWRegion.contains(SE->getSignedRange(Ops[1]))) + if (!ConstantRange::mayOverflow(C, SE->getSignedRange(Ops[1]), + Instruction::Add, true)) Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); } if (!(SignOrUnsignWrap & SCEV::FlagNUW)) { - auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, C, OBO::NoUnsignedWrap); - if (NUWRegion.contains(SE->getUnsignedRange(Ops[1]))) + if (!ConstantRange::mayOverflow(C, SE->getUnsignedRange(Ops[1]), + Instruction::Add, false)) Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); } } @@ -3801,16 +3798,14 @@ if (!AR->isAffine()) return SCEV::FlagAnyWrap; - typedef OverflowingBinaryOperator OBO; SCEV::NoWrapFlags Result = SCEV::FlagAnyWrap; if (!AR->hasNoSignedWrap()) { ConstantRange AddRecRange = getSignedRange(AR); ConstantRange IncRange = getSignedRange(AR->getStepRecurrence(*this)); - auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, IncRange, OBO::NoSignedWrap); - if (NSWRegion.contains(AddRecRange)) + if (!ConstantRange::mayOverflow(AddRecRange, IncRange, Instruction::Add, + true)) Result = ScalarEvolution::setFlags(Result, SCEV::FlagNSW); } @@ -3818,9 +3813,8 @@ ConstantRange AddRecRange = getUnsignedRange(AR); ConstantRange IncRange = getUnsignedRange(AR->getStepRecurrence(*this)); - auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, IncRange, OBO::NoUnsignedWrap); - if (NUWRegion.contains(AddRecRange)) + if (!ConstantRange::mayOverflow(AddRecRange, IncRange, Instruction::Add, + false)) Result = ScalarEvolution::setFlags(Result, SCEV::FlagNUW); } Index: lib/IR/ConstantRange.cpp =================================================================== --- lib/IR/ConstantRange.cpp +++ lib/IR/ConstantRange.cpp @@ -23,6 +23,7 @@ #include "llvm/IR/Instruction.h" #include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Intrinsics.h" #include "llvm/IR/Operator.h" #include "llvm/IR/ConstantRange.h" #include "llvm/Support/Debug.h" @@ -165,63 +166,54 @@ return Success; } -ConstantRange -ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, - const ConstantRange &Other, - unsigned NoWrapKind) { - typedef OverflowingBinaryOperator OBO; - - // Computes the intersection of CR0 and CR1. It is different from - // intersectWith in that the ConstantRange returned will only contain elements - // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or - // not, of both X and Y). - auto SubsetIntersect = - [](const ConstantRange &CR0, const ConstantRange &CR1) { - return CR0.inverse().unionWith(CR1.inverse()).inverse(); - }; - - assert(BinOp >= Instruction::BinaryOpsBegin && - BinOp < Instruction::BinaryOpsEnd && "Binary operators only!"); - - assert((NoWrapKind == OBO::NoSignedWrap || - NoWrapKind == OBO::NoUnsignedWrap || - NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && - "NoWrapKind invalid!"); - - unsigned BitWidth = Other.getBitWidth(); - if (BinOp != Instruction::Add) - // Conservative answer: empty set - return ConstantRange(BitWidth, false); - - if (auto *C = Other.getSingleElement()) - if (C->isMinValue()) - // Full set: nothing signed / unsigned wraps when added to 0. - return ConstantRange(BitWidth); - - ConstantRange Result(BitWidth); - - if (NoWrapKind & OBO::NoUnsignedWrap) - Result = - SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth), - -Other.getUnsignedMax())); - - if (NoWrapKind & OBO::NoSignedWrap) { - APInt SignedMin = Other.getSignedMin(); - APInt SignedMax = Other.getSignedMax(); - - if (SignedMax.isStrictlyPositive()) - Result = SubsetIntersect( - Result, - ConstantRange(APInt::getSignedMinValue(BitWidth), - APInt::getSignedMinValue(BitWidth) - SignedMax)); - - if (SignedMin.isNegative()) - Result = SubsetIntersect( - Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin, - APInt::getSignedMinValue(BitWidth))); +// Return false if we can prove that overflow does not occur. The strategy is to +// do a wider version of the interval arithmetic and then check if the result +// has an empty intersection with this ConstantRange (or its unsigned +// equivalent): +// +// orig INT_MIN orig INT_MAX +// | | +// v v +// --------------------U L-------------------- +// +bool ConstantRange::mayOverflow(const ConstantRange &L, const ConstantRange &R, + unsigned Opcode, bool Signed) { + const unsigned Width = L.getBitWidth(); + APInt Max, Min; + ConstantRange LExt(1), RExt(1); + if (Signed) { + Max = APInt::getSignedMaxValue(Width).sext(2 * Width); + Min = APInt::getSignedMinValue(Width).sext(2 * Width); + LExt = L.signExtend(2 * Width); + RExt = R.signExtend(2 * Width); + } else { + Max = APInt::getMaxValue(Width).zext(2 * Width); + Min = APInt::getMinValue(Width).zext(2 * Width); + LExt = L.zeroExtend(2 * Width); + RExt = R.zeroExtend(2 * Width); } - - return Result; + ConstantRange Result(1); + switch (Opcode) { + case Instruction::Add: + case Intrinsic::sadd_with_overflow: + case Intrinsic::uadd_with_overflow: + Result = LExt.add(RExt); + break; + case Instruction::Sub: + case Intrinsic::ssub_with_overflow: + case Intrinsic::usub_with_overflow: + Result = LExt.sub(RExt); + break; + case Instruction::Mul: + case Intrinsic::smul_with_overflow: + case Intrinsic::umul_with_overflow: + Result = LExt.multiply(RExt); + break; + default: + llvm_unreachable("unsupported operation"); + } + const ConstantRange OverflowRange(Max + 1, Min); + return !Result.intersectWith(OverflowRange).isEmptySet(); } /// isFullSet - Return true if this set contains all of the elements possible Index: unittests/IR/ConstantRangeTest.cpp =================================================================== --- unittests/IR/ConstantRangeTest.cpp +++ unittests/IR/ConstantRangeTest.cpp @@ -608,112 +608,133 @@ ConstantRange(APInt(8, 4), APInt(8, -128))); } -TEST(ConstantRange, MakeGuaranteedNoWrapRegion) { - const int IntMin4Bits = 8; - const int IntMax4Bits = 7; - typedef OverflowingBinaryOperator OBO; +TEST(ConstantRange, MayOverflow) { - for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) { - APInt C(4, Const, true /* = isSigned */); + // Test some singleton ConstantRanges where we can easily compare + // mayOverflow() against an independent implementation of overflow detection. + for (int Const1 = -8; Const1 < 8; ++Const1) { + APInt C1(4, Const1, /*isSigned=*/true); + for (int Const2 = -8; Const2 < 8; ++Const2) { + APInt C2(4, Const2, /*isSigned=*/true); + bool Overflow; - auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, C, OBO::NoUnsignedWrap); + C1.uadd_ov(C2, Overflow); + EXPECT_TRUE(ConstantRange::mayOverflow(C1, C2, Instruction::Add, false) + == Overflow); - EXPECT_FALSE(NUWRegion.isEmptySet()); + C1.sadd_ov(C2, Overflow); + EXPECT_TRUE(ConstantRange::mayOverflow(C1, C2, Instruction::Add, true) + == Overflow); - auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, C, OBO::NoSignedWrap); + C1.usub_ov(C2, Overflow); + EXPECT_TRUE(ConstantRange::mayOverflow(C1, C2, Instruction::Sub, false) + == Overflow); - EXPECT_FALSE(NSWRegion.isEmptySet()); + C1.ssub_ov(C2, Overflow); + EXPECT_TRUE(ConstantRange::mayOverflow(C1, C2, Instruction::Sub, true) + == Overflow); - auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap); + C1.umul_ov(C2, Overflow); + EXPECT_TRUE(ConstantRange::mayOverflow(C1, C2, Instruction::Mul, false) + == Overflow); - EXPECT_FALSE(NoWrapRegion.isEmptySet()); - EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion)); + C1.smul_ov(C2, Overflow); + EXPECT_TRUE(ConstantRange::mayOverflow(C1, C2, Instruction::Mul, true) + == Overflow); - for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; - ++I) { - bool Overflow = false; - I.uadd_ov(C, Overflow); - EXPECT_FALSE(Overflow); } + } - for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E; - ++I) { - bool Overflow = false; - I.sadd_ov(C, Overflow); - EXPECT_FALSE(Overflow); - } + // And now a few nontrivial ConstantRanges. + for (unsigned Width : {8, 16, 32, 64, 128, 256}) { - for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E; - ++I) { - bool Overflow = false; + APInt SMin = APInt::getSignedMinValue(Width); + APInt SMax = APInt::getSignedMaxValue(Width); + APInt UMin = APInt::getMinValue(Width); + APInt UMax = APInt::getMaxValue(Width); + APInt Zero = APInt::getMinValue(Width); + APInt One = APInt(Width, 1); + APInt Two = APInt(Width, 2); + APInt NegOne = APInt(Width, -1, /*isSigned=*/true); + APInt NegTwo = APInt(Width, -2, /*isSigned=*/true); + APInt SHalfMin = SMin.sdiv(Two); + APInt SHalfMax = SMax.sdiv(Two); + APInt Three = APInt(Width, 3); - I.sadd_ov(C, Overflow); - EXPECT_FALSE(Overflow); + ConstantRange Middle(SHalfMin, SHalfMax + 1); + ConstantRange UptoTwo(Zero, Two + 1); + ConstantRange UptoThree(Zero, Three + 1); + ConstantRange AllButSMax(SMin, SMax); + ConstantRange AllButSMin(SMin + 1, SMax + 1); + ConstantRange AllButUMax(Zero, UMax); + ConstantRange AllButUMin(Zero + 1, UMax + 1); + ConstantRange CRZero(Zero, Zero + 1); + ConstantRange CROne(One, One + 1); + ConstantRange CRTwo(One, Two + 1); + ConstantRange CRNegOne(NegOne, NegOne + 1); + ConstantRange CRNegTwo(NegTwo, NegTwo + 1); - I.uadd_ov(C, Overflow); - EXPECT_FALSE(Overflow); - } - } + // signed overflow + EXPECT_FALSE(ConstantRange::mayOverflow(Middle, Middle, Instruction::Add, + true)); + EXPECT_FALSE(ConstantRange::mayOverflow(Middle, Middle, Instruction::Sub, + true)); + EXPECT_FALSE(ConstantRange::mayOverflow(Middle, UptoTwo, Instruction::Mul, + true)); + EXPECT_TRUE(ConstantRange::mayOverflow(Middle, UptoThree, Instruction::Mul, + true)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButSMax, CROne, + Instruction::Add, true)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButSMax, CRTwo, + Instruction::Add, true)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButSMax, CROne, + Instruction::Sub, true)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButSMax, CRZero, + Instruction::Mul, true)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButSMax, CROne, + Instruction::Mul, true)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButSMax, CRTwo, + Instruction::Mul, true)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButSMin, CRNegOne, + Instruction::Add, true)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButSMin, CROne, + Instruction::Sub, true)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButSMin, CRNegTwo, + Instruction::Add, true)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButSMin, CRNegOne, + Instruction::Sub, true)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButSMin, CRZero, + Instruction::Mul, true)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButSMin, CROne, + Instruction::Mul, true)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButSMin, CRTwo, + Instruction::Mul, true)); - auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, ConstantRange(32, /* isFullSet = */ true), - OBO::NoSignedWrap); - EXPECT_TRUE(NSWForAllValues.isSingleElement() && - NSWForAllValues.getSingleElement()->isMinValue()); - auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, ConstantRange(32, /* isFullSet = */ true), - OBO::NoUnsignedWrap); - EXPECT_TRUE(NUWForAllValues.isSingleElement() && - NSWForAllValues.getSingleElement()->isMinValue()); + // unsigned overflow + EXPECT_FALSE(ConstantRange::mayOverflow(AllButUMax, CROne, + Instruction::Add, false)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButUMax, CRTwo, + Instruction::Add, false)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButUMax, CROne, + Instruction::Sub, false)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButUMax, CRZero, + Instruction::Mul, false)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButUMax, CROne, + Instruction::Mul, false)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButUMax, CRTwo, + Instruction::Mul, false)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButUMin, CROne, + Instruction::Sub, false)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButUMin, CRZero, + Instruction::Mul, false)); + EXPECT_FALSE(ConstantRange::mayOverflow(AllButUMin, CROne, + Instruction::Mul, false)); + EXPECT_TRUE(ConstantRange::mayOverflow(AllButUMin, CRTwo, + Instruction::Mul, false)); - auto NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, ConstantRange(32, /* isFullSet = */ true), - OBO::NoUnsignedWrap | OBO::NoSignedWrap); - EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() && - NSWForAllValues.getSingleElement()->isMinValue()); + } - ConstantRange OneToFive(APInt(32, 1), APInt(32, 6)); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, OneToFive, OBO::NoSignedWrap), - ConstantRange(APInt::getSignedMinValue(32), - APInt::getSignedMaxValue(32) - 4)); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, OneToFive, OBO::NoUnsignedWrap), - ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5)); - EXPECT_EQ( - ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt::getMinValue(32), APInt::getSignedMaxValue(32) - 4)); - - ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1)); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap), - ConstantRange(APInt::getSignedMinValue(32) + 5, - APInt::getSignedMinValue(32))); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), - ConstantRange(APInt(32, 0), APInt(32, 2))); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, MinusFiveToMinusTwo, - OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt(32, 0), APInt(32, 2))); - - ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2)); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, MinusOneToOne, OBO::NoSignedWrap), - ConstantRange(APInt::getSignedMinValue(32) + 1, - APInt::getSignedMinValue(32) - 1)); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap), - ConstantRange(APInt(32, 0), APInt(32, 1))); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, MinusOneToOne, - OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt(32, 0), APInt(32, 1))); } TEST(ConstantRange, GetEquivalentICmp) {