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: { + // By definition shift by bitwidth (or more) is poison, so we can assume + // worst-case scenario of shifting by bitwidth-1. + uint64_t ShAmtUMax = Other.getUnsignedMax().getLimitedValue(BitWidth - 1); + 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 @@ -1532,6 +1532,25 @@ EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( Instruction::Sub, One, OBO::NoUnsignedWrap), ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32))); + + ConstantRange OneLessThanBitWidth(APInt(32, 31), APInt(32, 32)); + ConstantRange BitWidth(APInt(32, 32), APInt(32, 33)); + EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, BitWidth, OBO::NoUnsignedWrap), + ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap)); + EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, BitWidth, OBO::NoSignedWrap), + ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap)); + EXPECT_EQ( + ConstantRange::makeGuaranteedNoWrapRegion(Instruction::Shl, BitWidth, + OBO::NoUnsignedWrap), + ConstantRange(APInt::getNullValue(32), APInt::getNullValue(32) + 2)); + EXPECT_EQ( + ConstantRange::makeGuaranteedNoWrapRegion(Instruction::Shl, BitWidth, + OBO::NoSignedWrap), + ConstantRange(APInt::getAllOnesValue(32), APInt::getNullValue(32) + 1)); } template @@ -1543,6 +1562,8 @@ [&](const ConstantRange &CR1, const ConstantRange &CR2) { if (CR2.isEmptySet()) return; + if (Instruction::isShift(BinOp) && CR2.getUnsignedMax().uge(Bits)) + return; ConstantRange NoWrap = ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR2, NoWrapKind); @@ -1610,6 +1631,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 +1808,92 @@ } } +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlUnsignedSingleValue) { + typedef OverflowingBinaryOperator OBO; + + static constexpr int Bitwidth = 8; + + for (uint64_t I = std::numeric_limits::min(); I < Bitwidth; I++) { + auto Range = ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, + ConstantRange(APInt(Bitwidth, I), APInt(Bitwidth, I + 1)), + OBO::NoUnsignedWrap); + + for (uint64_t V = std::numeric_limits::min(); + V <= std::numeric_limits::max(); V++) { + bool Overflow; + (void)APInt(Bitwidth, V).ushl_ov(APInt(Bitwidth, I), Overflow); + EXPECT_EQ(!Overflow, Range.contains(APInt(Bitwidth, V))); + } + } +} + +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlSignedSingleValue) { + typedef OverflowingBinaryOperator OBO; + + static constexpr int Bitwidth = 8; + + for (uint64_t I = std::numeric_limits::min(); I < Bitwidth; I++) { + auto Range = ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, + ConstantRange(APInt(Bitwidth, I), APInt(Bitwidth, I + 1)), + OBO::NoSignedWrap); + + for (int64_t V = std::numeric_limits::min(); + V <= std::numeric_limits::max(); V++) { + bool Overflow; + (void)APInt(Bitwidth, V, /*isSigned=*/true) + .sshl_ov(APInt(Bitwidth, I), Overflow); + EXPECT_EQ(!Overflow, + Range.contains(APInt(Bitwidth, V, /*isSigned=*/true))); + } + } +} + +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlUnsignedRange) { + typedef OverflowingBinaryOperator OBO; + + static constexpr int Bitwidth = 8; + + for (uint64_t Lo = std::numeric_limits::min(); Lo < Bitwidth; Lo++) { + for (uint64_t Hi = Lo; Hi < Bitwidth; Hi++) { + EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, + ConstantRange(APInt(Bitwidth, Lo), APInt(Bitwidth, Hi + 1)), + OBO::NoUnsignedWrap), + ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, + ConstantRange(APInt(Bitwidth, Hi), APInt(Bitwidth, Hi + 1)), + OBO::NoUnsignedWrap)); + } + } +} + +TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlSignedRange) { + typedef OverflowingBinaryOperator OBO; + + static constexpr int Bitwidth = 8; + + int Lo = 2, Hi = 5; + auto Range = ConstantRange::makeGuaranteedNoWrapRegion( + Instruction::Shl, + ConstantRange(APInt(Bitwidth, Lo), APInt(Bitwidth, 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(Bitwidth, V, /*isSigned=*/true) + .sshl_ov(APInt(Bitwidth, I), Overflow); + AnyOverflow |= Overflow; + } + EXPECT_EQ(!AnyOverflow, + Range.contains(APInt(Bitwidth, V, /*isSigned=*/true))); + } +} + #define EXPECT_MAY_OVERFLOW(op) \ EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op)) #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \