Index: llvm/trunk/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/trunk/include/llvm/IR/ConstantRange.h +++ llvm/trunk/include/llvm/IR/ConstantRange.h @@ -116,16 +116,10 @@ static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other); - /// Return the largest range containing all X such that "X BinOpC Y" is + /// Return the exact range containing all X such that "X BinOpC Y" is /// guaranteed not to wrap (overflow) for all Y in Other. /// - /// If only one of NoUnsignedWrap or NoSignedWrap is specified, the returned - /// range is exact: It contains *all* possible values of X for which - /// "X BinOpC Y" does not wrap. However, if both NUW and NSW are specified, it - /// may return only a subset of non-wrapping values. In this case the - /// returned region cannot be used to constrain X's range. E.g. in the - /// fourth example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2), - /// but (-2) is not in the set returned. + /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap. /// /// Examples: /// typedef OverflowingBinaryOperator OBO; @@ -133,13 +127,9 @@ /// 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) /// MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128) /// MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0) - /// MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap | OBO::NoSignedWrap) - /// == [1,INT_MAX) static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind); Index: llvm/trunk/lib/IR/ConstantRange.cpp =================================================================== --- llvm/trunk/lib/IR/ConstantRange.cpp +++ llvm/trunk/lib/IR/ConstantRange.cpp @@ -214,8 +214,7 @@ assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!"); assert((NoWrapKind == OBO::NoSignedWrap || - NoWrapKind == OBO::NoUnsignedWrap || - NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && + NoWrapKind == OBO::NoUnsignedWrap) && "NoWrapKind invalid!"); unsigned BitWidth = Other.getBitWidth(); @@ -231,11 +230,12 @@ if (C->isNullValue()) // Full set: nothing signed / unsigned wraps when added to 0. return getFull(BitWidth); - if (NoWrapKind & OBO::NoUnsignedWrap) - Result = - SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth), - -Other.getUnsignedMax())); - if (NoWrapKind & OBO::NoSignedWrap) { + + if (NoWrapKind == OBO::NoUnsignedWrap) + return ConstantRange(APInt::getNullValue(BitWidth), + -Other.getUnsignedMax()); + + if (NoWrapKind == OBO::NoSignedWrap) { const APInt &SignedMin = Other.getSignedMin(); const APInt &SignedMax = Other.getSignedMax(); if (SignedMax.isStrictlyPositive()) @@ -256,11 +256,12 @@ if (C->isNullValue()) // Full set: nothing signed / unsigned wraps when subtracting 0. return getFull(BitWidth); - if (NoWrapKind & OBO::NoUnsignedWrap) - Result = - SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(), - APInt::getMinValue(BitWidth))); - if (NoWrapKind & OBO::NoSignedWrap) { + + if (NoWrapKind == OBO::NoUnsignedWrap) + return ConstantRange(Other.getUnsignedMax(), + APInt::getMinValue(BitWidth)); + + if (NoWrapKind == OBO::NoSignedWrap) { const APInt &SignedMin = Other.getSignedMin(); const APInt &SignedMax = Other.getSignedMax(); if (SignedMax.isStrictlyPositive()) @@ -275,13 +276,8 @@ APInt::getSignedMinValue(BitWidth) + SignedMin)); } return Result; - case Instruction::Mul: { - if (NoWrapKind == (OBO::NoSignedWrap | OBO::NoUnsignedWrap)) { - return SubsetIntersect( - makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoSignedWrap), - makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoUnsignedWrap)); - } + case Instruction::Mul: { // Equivalent to calling makeGuaranteedNoWrapRegion() on [V, V+1). const bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap; const auto makeSingleValueRegion = [Unsigned, Index: llvm/trunk/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/ConstantRangeTest.cpp +++ llvm/trunk/unittests/IR/ConstantRangeTest.cpp @@ -922,12 +922,6 @@ EXPECT_FALSE(NSWRegion.isEmptySet()); - auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap); - - EXPECT_FALSE(NoWrapRegion.isEmptySet()); - EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion)); - for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; ++I) { bool Overflow = false; @@ -941,17 +935,6 @@ (void)I.sadd_ov(C, Overflow); EXPECT_FALSE(Overflow); } - - for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E; - ++I) { - bool Overflow = false; - - (void)I.sadd_ov(C, Overflow); - EXPECT_FALSE(Overflow); - - (void)I.uadd_ov(C, Overflow); - EXPECT_FALSE(Overflow); - } } for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) { @@ -967,12 +950,6 @@ EXPECT_FALSE(NSWRegion.isEmptySet()); - auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Sub, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap); - - EXPECT_FALSE(NoWrapRegion.isEmptySet()); - EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion)); - for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; ++I) { bool Overflow = false; @@ -986,17 +963,6 @@ (void)I.ssub_ov(C, Overflow); EXPECT_FALSE(Overflow); } - - for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E; - ++I) { - bool Overflow = false; - - (void)I.ssub_ov(C, Overflow); - EXPECT_FALSE(Overflow); - - (void)I.usub_ov(C, Overflow); - EXPECT_FALSE(Overflow); - } } auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( @@ -1023,32 +989,14 @@ EXPECT_TRUE(NUWForAllValues.isSingleElement() && NUWForAllValues.getSingleElement()->isMaxValue()); - auto NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, ConstantRange(32, /* isFullSet = */ true), - OBO::NoUnsignedWrap | OBO::NoSignedWrap); - EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() && - NUWAndNSWForAllValues.getSingleElement()->isMinValue()); - - NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Sub, ConstantRange(32, /* isFullSet = */ true), - OBO::NoUnsignedWrap | OBO::NoSignedWrap); - EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() && - NUWAndNSWForAllValues.getSingleElement()->isMaxValue()); - EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, APInt(32, 0), - OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet()); - EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); - EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Sub, APInt(32, 0), - OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet()); ConstantRange OneToFive(APInt(32, 1), APInt(32, 6)); EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( @@ -1058,10 +1006,6 @@ 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)); EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, OneToFive, OBO::NoSignedWrap), ConstantRange(APInt::getSignedMinValue(32) + 5, @@ -1069,10 +1013,6 @@ EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, OneToFive, OBO::NoUnsignedWrap), ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32))); - EXPECT_EQ( - ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Sub, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt::getMinValue(32) + 5, APInt::getSignedMinValue(32))); ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1)); EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( @@ -1083,10 +1023,6 @@ 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))); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap), ConstantRange(APInt::getSignedMinValue(32), APInt::getSignedMaxValue(32) - 4)); @@ -1094,11 +1030,6 @@ Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), ConstantRange(APInt::getMaxValue(32) - 1, APInt::getMinValue(32))); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Sub, MinusFiveToMinusTwo, - OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt::getMaxValue(32) - 1, - APInt::getMinValue(32))); ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2)); EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( @@ -1109,10 +1040,6 @@ 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))); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap), ConstantRange(APInt::getSignedMinValue(32) + 1, APInt::getSignedMinValue(32) - 1)); @@ -1120,11 +1047,6 @@ Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap), ConstantRange(APInt::getMaxValue(32), APInt::getMinValue(32))); - EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Sub, MinusOneToOne, - OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt::getMaxValue(32), - APInt::getMinValue(32))); ConstantRange One(APInt(32, 1), APInt(32, 2)); EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( @@ -1134,10 +1056,6 @@ EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Add, One, OBO::NoUnsignedWrap), ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32))); - EXPECT_EQ( - ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Add, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt(32, 0), APInt::getSignedMaxValue(32))); EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, One, OBO::NoSignedWrap), ConstantRange(APInt::getSignedMinValue(32) + 1, @@ -1145,10 +1063,6 @@ EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, One, OBO::NoUnsignedWrap), ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32))); - EXPECT_EQ( - ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Sub, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap), - ConstantRange(APInt::getMinValue(32) + 1, APInt::getSignedMinValue(32))); } template @@ -1342,26 +1256,6 @@ } } -TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedAndSignedSingleValue) { - typedef OverflowingBinaryOperator OBO; - - for (uint64_t I = std::numeric_limits::min(); - I <= std::numeric_limits::max(); I++) { - auto Range = ConstantRange::makeGuaranteedNoWrapRegion( - Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)), - OBO::NoUnsignedWrap | OBO::NoSignedWrap); - - for (uint64_t V = std::numeric_limits::min(); - V <= std::numeric_limits::max(); V++) { - bool UOverflow; - (void)APInt(8, I).umul_ov(APInt(8, V), UOverflow); - bool SOverflow; - (void)APInt(8, I).smul_ov(APInt(8, V), SOverflow); - EXPECT_EQ(!(UOverflow || SOverflow), Range.contains(APInt(8, V))); - } - } -} - TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) { typedef OverflowingBinaryOperator OBO;