[ConstantRange] Add `ushl_sat()`/`sshl_sat()` methods.

[lebedev.ri]

Summary

To be used in ConstantRange::shlWithNoOverflow(),
may in future be useful for when saturating shift/mul ops are added.

Unlike ConstantRange::shl(), these are precise.

[nikic]

Unlike ConstantRange::shl(), these are precise.

At least when modelling the APInt semantics. If we treat too large shifts as poison, then we could produce empty sets in more cases. But this seems like a reasonable starting point...

llvm/lib/IR/ConstantRange.cpp

1359

Wondering if a formulation along the lines of

APInt Min = getSignedMin(), Max = getSignedMax();
APInt ShiftMin = getUnsignedMin(), ShiftMax = getUnsignedMax();
APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShiftMin : ShiftMax);
APInt NewU = Max.sshl_sat(Max.isNonNegative() ? ShiftMax : ShiftMin) + 1;

might be cleaner?

[lebedev.ri]

Cleanup sshl_sat() with ternaries as suggested.

In D69960#1737565, @nikic wrote:

Unlike ConstantRange::shl(), these are precise.

At least when modelling the APInt semantics. If we treat too large shifts as poison, then we could produce empty sets in more cases.

Yeah, i think this might be a good thing to do, but later, more globally.

But this seems like a reasonable starting point...

[lebedev.ri]

This comment was removed by lebedev.ri.

llvm/lib/IR/ConstantRange.cpp

1359

A bit, yes.

[nikic]

LGTM

llvm/lib/IR/ConstantRange.cpp

1352

Mild preference for using Min.isNonNegative() and Max.isNegative() here, because it makes the relationship to the shifted value clear. Also fine as-is though.

llvm/include/llvm/IR/ConstantRange.h

public:
   ConstantRange sadd_sat(const ConstantRange &Other) const;
 
   /// Perform an unsigned saturating subtraction of two constant ranges.
   ConstantRange usub_sat(const ConstantRange &Other) const;
 
   /// Perform a signed saturating subtraction of two constant ranges.
   ConstantRange ssub_sat(const ConstantRange &Other) const;
 
+  /// Perform an unsigned saturating left shift of this constant range by a
+  /// value in \p Other.
+  ConstantRange ushl_sat(const ConstantRange &Other) const;
+
+  /// Perform a signed saturating left shift of this constant range by a
+  /// value in \p Other.
+  ConstantRange sshl_sat(const ConstantRange &Other) const;
+
   /// Return a new range that is the logical not of the current set.
   ConstantRange inverse() const;
 
   /// Calculate absolute value range. If the original range contains signed
   /// min, then the resulting range will also contain signed min.
   ConstantRange abs() const;
 
   /// Represents whether an operation on the given constant range is known to

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
 
   APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
   APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
   return getNonEmpty(std::move(NewL), std::move(NewU));
 }
 
+ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return getEmpty();
+
+  APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin());
+  APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1;
+  return getNonEmpty(std::move(NewL), std::move(NewU));
+}
+
+ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return getEmpty();
+
+  APInt NewL, NewU;
+  if (isAllNonNegative()) {
+    NewL = getSignedMin().sshl_sat(Other.getUnsignedMin());
+    NewU = getSignedMax().sshl_sat(Other.getUnsignedMax()) + 1;
+  } else if (isAllNegative()) {
+    NewL = getSignedMin().sshl_sat(Other.getUnsignedMax());
+    NewU = getSignedMax().sshl_sat(Other.getUnsignedMin()) + 1;
+  } else {
+    NewL = getSignedMin().sshl_sat(Other.getUnsignedMax());
+    NewU = getSignedMax().sshl_sat(Other.getUnsignedMax()) + 1;
+  }
+  return getNonEmpty(std::move(NewL), std::move(NewU));
+}
+
 ConstantRange ConstantRange::inverse() const {
   if (isFullSet())
     return getEmpty();
   if (isEmptySet())
     return getFull();
   return ConstantRange(Upper, Lower);
 }
 

llvm/unittests/IR/ConstantRangeTest.cpp

TestUnsignedBinOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.usub_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.usub_sat(N2);
       });
 }
 
+TEST_F(ConstantRangeTest, UShlSat) {
+  TestUnsignedBinOpExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.ushl_sat(CR2);
+      },
+      [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); });
+}
+
 TEST_F(ConstantRangeTest, SAddSat) {
   TestSignedBinOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.sadd_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.sadd_sat(N2);
       });
 }
 
 TEST_F(ConstantRangeTest, SSubSat) {
   TestSignedBinOpExhaustive(
       [](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.ssub_sat(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.ssub_sat(N2);
       });
 }
 
+TEST_F(ConstantRangeTest, SShlSat) {
+  TestSignedBinOpExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.sshl_sat(CR2);
+      },
+      [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); });
+}
+
 TEST_F(ConstantRangeTest, Abs) {
   unsigned Bits = 4;
   EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
     // We're working with unsigned integers here, because it makes the signed
     // min case non-wrapping.
     APInt Min = APInt::getMaxValue(Bits);
     APInt Max = APInt::getMinValue(Bits);
     ForeachNumInConstantRange(CR, [&](const APInt &N) {