[ConstantRange] makeGuaranteedNoWrapRegion(): `shl` support

[lebedev.ri]

Summary

If all the shifts amount are already poison-producing,
then we can add more poison-producing flags ontop:
https://rise4fun.com/Alive/Ocwi

Otherwise, we should only consider the possible range of shift amts that don't result in poison.

For unsigned range not not overflow, we must not shift out any set bits,
and the actual limit for x can be computed by backtransforming
the maximal value we could ever get out of the shl - -1 through
lshr. If the x is any larger than that then it will overflow.

Likewise for signed range, but just in signed domain..

This is based on the general idea outlined by @nikic in https://reviews.llvm.org/D68672#1714990

[nikic]

llvm/lib/IR/ConstantRange.cpp

276

While an empty set here is conservatively correct, I believe that the more precise return value would be the range containing only zero [0, 1). The shift amount is < the bitwidth by assumption (otherwise the result is poison), and [0, 1) is the result for the worst-case assumption of shift amount = bitwidth - 1.

Even more precise would be to intersect the incoming range with [0, BitWidth), which may differ non-trivially from this approach for wrapped ranges. E.g. if you have a signed range [INT_MIN, 5), the UMax will be UINT_MAX, but the intersection [INT_MIN, 5) /\ [0, 32) is [0, 5) and the UMax will be 4, resulting in a much larger guaranteed nowrap region.

[lebedev.ri]

llvm/lib/IR/ConstantRange.cpp

276

The shift amount is < the bitwidth by assumption (otherwise the result is poison)

Ah, good point.

But by that logic, then for signed the range should be [-1, 1), correct?
0 << 7 == 0 - doesn't overflow in both signed and unsigned domains,
while -1 << 7 == -128 does not overflow in signed domain - still the same sign.

[lebedev.ri]

llvm/lib/IR/ConstantRange.cpp

276

Actually no, wait, if we are assuming that we will at worst get bitwidth-1 shift amount,
then we should produce [0, 2) for unsigned or [-1, 1) for signed.
Or i'm missing the point.

[nikic]

llvm/lib/IR/ConstantRange.cpp

276

I guess it should be [0, 2) unsigned and [-1, 1) signed then, as 1 << 7 does not overflow unsigned either.

Rather than special-casing this, we could just take ShAmtUMax = Other.getUnsignedMax().umin(BitWidth-1) and reuse the general code.

Or do

ConstantRange ShAmt = Other.intersect(ConstantRange(
    APInt(BitWidth, 0), APInt(BitWidth, BitWidth)));`
if (ShAmt.isEmptySet())
  return getEmpty(); // or getFull()?
APInt ShAmtUMax = ShAmt.getUnsignedMax();

for the fully precise variant.

[lebedev.ri]

Clamp max shift amount to bitwidth-1

llvm/lib/IR/ConstantRange.cpp

276

I guess it should be [0, 2) unsigned and [-1, 1) signed then, as 1 << 7 does not overflow unsigned either.
Rather than special-casing this, we could just take ShAmtUMax = Other.getUnsignedMax().umin(BitWidth-1) and reuse the general code.

Indeed, which is why i was having trouble grasping why it would be [0, 1) for shamt=bitwidth all of a sudden.

Didn't think about intersection yet.

[lebedev.ri]

Improve tests and go full on intersectWith().

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

1613

So, I wrote this test, but I can't say I understand why it does what it does... Enumerating over all ranges CR1 seems to be entirely unnecessary, it would be sufficient to just iterate over all N1 in the full range to get the same coverage, and save us a whole lot of unnecessary iterations.

That should allow us to run this test with a larger bit width, in which case you could just drop the MakeGuaranteedNoWrapRegionShl(Un)signedSingleValue tests entirely, as they are special cases of what is checked here (just with a larger bit width).

1938

Why is this test structurally different from the previous one?

[lebedev.ri]

Tune some tests

llvm/unittests/IR/ConstantRangeTest.cpp

1938

This was carbon copy from 4 tests above; TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange)
in this case; let's streamline..

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

1613

As it's unrelated to this revision, I've made this change in rL375369. Now testing 5 bits, which is good enough I think.

[lebedev.ri]

Rebased

[nikic]

LGTM

[lebedev.ri]

In D69217#1715974, @nikic wrote:

LGTM

Thank you for the review.
Will post CVP patch later, needs tests, but the effect is similar to the mul patch (D69203).

llvm/lib/IR/ConstantRange.cpp

ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
   }
 
   case Instruction::Mul:
     if (Unsigned)
       return makeExactMulNUWRegion(Other.getUnsignedMax());
 
     return makeExactMulNSWRegion(Other.getSignedMin())
         .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));
+
+  case Instruction::Shl: {
+    // For given range of shift amounts, if we ignore all illegal shift amounts
+    // (that always produce poison), what shift amount range is left?
+    ConstantRange ShAmt = Other.intersectWith(
+        ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1)));
+    if (ShAmt.isEmptySet()) {
+      // If the entire range of shift amounts is already poison-producing,
+      // then we can freely add more poison-producing flags ontop of that.
+      return getFull(BitWidth);
+    }
+    // There are some legal shift amounts, we can compute conservatively-correct
+    // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax
+    // to be at most bitwidth-1, which results in most conservative range.
+    APInt ShAmtUMax = ShAmt.getUnsignedMax();
+    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);
+  }
   }
 }
 
 ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
                                                    const APInt &Other,
                                                    unsigned NoWrapKind) {
   // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
   // "for all" and "for any" coincide in this case.

llvm/unittests/IR/ConstantRangeTest.cpp

EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
             ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Sub, One, OBO::NoSignedWrap),
             ConstantRange(APInt::getSignedMinValue(32) + 1,
                           APInt::getSignedMinValue(32)));
   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Sub, One, OBO::NoUnsignedWrap),
             ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
+
+  ConstantRange OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);
+  ConstantRange UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
+            ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
+            ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
+            ConstantRange(APInt(32, 0), APInt(32, 1) + 1));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
+            ConstantRange(APInt(32, -1), APInt(32, 0) + 1));
+
+  EXPECT_EQ(
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, ConstantRange::getFull(32), OBO::NoUnsignedWrap),
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
+  EXPECT_EQ(
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, ConstantRange::getFull(32), OBO::NoSignedWrap),
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
+
+  ConstantRange IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, IllegalShAmt, OBO::NoUnsignedWrap),
+            ConstantRange::getFull(32));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl, IllegalShAmt, OBO::NoSignedWrap),
+            ConstantRange::getFull(32));
+
+  EXPECT_EQ(
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
+          OBO::NoUnsignedWrap),
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
+          OBO::NoUnsignedWrap));
+  EXPECT_EQ(
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
+          OBO::NoSignedWrap),
+      ConstantRange::makeGuaranteedNoWrapRegion(
+          Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
+          OBO::NoSignedWrap));
+
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl,
+                ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
+                OBO::NoUnsignedWrap),
+            ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));
+  EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
+                Instruction::Shl,
+                ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
+                OBO::NoSignedWrap),
+            ConstantRange(APInt(32, -32768), APInt(32, 32767) + 1));
 }
 
 template<typename Fn>
 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
                                 unsigned NoWrapKind, Fn OverflowFn) {
   // When using 4 bits this test needs ~3s on a debug build.
   unsigned Bits = 3;
   EnumerateTwoConstantRanges(Bits,
       [&](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);
         ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
           bool NoOverflow = true;
           bool Overflow = true;
           ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
             if (OverflowFn(N1, N2))
               NoOverflow = false;
             else
               Overflow = false;
           });
TestNoWrapRegionExhaustive(
       });
   TestNoWrapRegionExhaustive(
       Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
       [](const APInt &N1, const APInt &N2) {
         bool Overflow;
         (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) {
   APInt RHS;
   CmpInst::Predicate Pred;
 
   EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
                   .getEquivalentICmp(Pred, RHS));
for (int64_t I = Lo; I <= Hi; I++) {
       (void)APInt(8, I, /*isSigned=*/true)
           .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
       AnyOverflow |= Overflow;
     }
     EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
   }
 }
 
+TEST(ConstantRange, MakeGuaranteedNoWrapRegionShlUnsignedSingleValue) {
+  typedef OverflowingBinaryOperator OBO;
+
+  static constexpr int Bitwidth = 8;
+
+  for (uint64_t I = std::numeric_limits<uint8_t>::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<uint8_t>::min();
+         V <= std::numeric_limits<uint8_t>::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<uint8_t>::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<int8_t>::min();
+         V <= std::numeric_limits<int8_t>::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<uint8_t>::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;
+
+  for (uint64_t Lo = std::numeric_limits<uint8_t>::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::NoSignedWrap),
+                ConstantRange::makeGuaranteedNoWrapRegion(
+                    Instruction::Shl,
+                    ConstantRange(APInt(Bitwidth, Hi), APInt(Bitwidth, Hi + 1)),
+                    OBO::NoSignedWrap));
+    }
+  }
+}
+
 #define EXPECT_MAY_OVERFLOW(op) \
   EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
 #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
   EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
 #define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
   EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
 #define EXPECT_NEVER_OVERFLOWS(op) \
   EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
 
 TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
   // Ill-defined - may overflow is a conservative result.
   EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
   EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));