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 @@ -269,6 +269,17 @@ return makeExactMulNSWRegion(Other.getSignedMin()) .intersectWith(makeExactMulNSWRegion(Other.getSignedMax())); + + case Instruction::Shl: { + APInt ShAmtUMax = Other.getUnsignedMax(); + if (ShAmtUMax.uge(BitWidth)) + return getEmpty(BitWidth); // Shift by bitwidth or more always overflows. + if (Unsigned) + return getNonEmpty(APInt::getNullValue(BitWidth), + APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1); + return getNonEmpty(APInt::getSignedMinValue(BitWidth).ashr(ShAmtUMax), + APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1); + } } } 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 @@ -1610,6 +1610,20 @@ (void) N1.smul_ov(N2, Overflow); return Overflow; }); + TestNoWrapRegionExhaustive(Instruction::Shl, + OverflowingBinaryOperator::NoUnsignedWrap, + [](const APInt &N1, const APInt &N2) { + bool Overflow; + (void)N1.ushl_ov(N2, Overflow); + return Overflow; + }); + TestNoWrapRegionExhaustive(Instruction::Shl, + OverflowingBinaryOperator::NoSignedWrap, + [](const APInt &N1, const APInt &N2) { + bool Overflow; + (void)N1.sshl_ov(N2, Overflow); + return Overflow; + }); } TEST(ConstantRange, GetEquivalentICmp) { @@ -1773,6 +1787,79 @@ } } +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlUnsignedSingleValue) { + typedef OverflowingBinaryOperator OBO; + + for (uint64_t I = std::numeric_limits::min(); + I <= std::numeric_limits::max(); I++) { + auto Range = ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, ConstantRange(APInt(8, I), APInt(8, I + 1)), + OBO::NoUnsignedWrap); + + for (uint64_t V = std::numeric_limits::min(); + V <= std::numeric_limits::max(); V++) { + bool Overflow; + (void)APInt(8, V).ushl_ov(APInt(8, I), Overflow); + EXPECT_EQ(!Overflow, Range.contains(APInt(8, V))); + } + } +} + +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlSignedSingleValue) { + typedef OverflowingBinaryOperator OBO; + + for (uint64_t I = std::numeric_limits::min(); + I <= std::numeric_limits::max(); I++) { + auto Range = ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, ConstantRange(APInt(8, I), APInt(8, I + 1)), + OBO::NoSignedWrap); + + for (int64_t V = std::numeric_limits::min(); + V <= std::numeric_limits::max(); V++) { + bool Overflow; + (void)APInt(8, V, /*isSigned=*/true).sshl_ov(APInt(8, I), Overflow); + EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true))); + } + } +} + +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlUnsignedRange) { + typedef OverflowingBinaryOperator OBO; + + for (uint64_t Lo = std::numeric_limits::min(); + Lo <= std::numeric_limits::max(); Lo++) { + for (uint64_t Hi = Lo; Hi <= std::numeric_limits::max(); Hi++) { + EXPECT_EQ( + ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, ConstantRange(APInt(8, Lo), APInt(8, Hi + 1)), + OBO::NoUnsignedWrap), + ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, ConstantRange(APInt(8, Hi), APInt(8, Hi + 1)), + OBO::NoUnsignedWrap)); + } + } +} + +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlSignedRange) { + typedef OverflowingBinaryOperator OBO; + + int Lo = -12, Hi = 16; + auto Range = ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, ConstantRange(APInt(8, Lo), APInt(8, Hi + 1)), + OBO::NoSignedWrap); + + for (int64_t V = std::numeric_limits::min(); + V <= std::numeric_limits::max(); V++) { + bool AnyOverflow = false; + for (int64_t I = Lo; I <= Hi; I++) { + bool Overflow; + (void)APInt(8, V, /*isSigned=*/true).sshl_ov(APInt(8, I), Overflow); + AnyOverflow |= Overflow; + } + EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true))); + } +} + #define EXPECT_MAY_OVERFLOW(op) \ EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op)) #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \