[ConstantRange] Add umul_sat()/smul_sat() methods

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

These are precise as far as i can tell.

I initially though i will need `APInt::[us]mul_sat()` for these,
but it turned out much simpler to do what `ConstantRange::multiply()`
does - perform multiplication in twice the bitwidth, and then truncate.
Though here we want saturating signed truncation.

Reviewers: nikic, reames, spatel

Reviewed By: nikic

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D69994

1 files changed, 35 insertions, 0 deletions

diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index e9bdf419352..71dd2d99bd7 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -1333,6 +1333,41 @@ ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {
   return getNonEmpty(std::move(NewL), std::move(NewU));
 }
 
+ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return getEmpty();
+
+  APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin());
+  APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1;
+  return getNonEmpty(std::move(NewL), std::move(NewU));
+}
+
+ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const {
+  if (isEmptySet() || Other.isEmptySet())
+    return getEmpty();
+
+  // Because we could be dealing with negative numbers here, the lower bound is
+  // the smallest of the cartesian product of the lower and upper ranges;
+  // for example:
+  //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
+  // Similarly for the upper bound, swapping min for max.
+
+  APInt this_min = getSignedMin().sext(getBitWidth() * 2);
+  APInt this_max = getSignedMax().sext(getBitWidth() * 2);
+  APInt Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
+  APInt Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
+
+  auto L = {this_min * Other_min, this_min * Other_max, this_max * Other_min,
+            this_max * Other_max};
+  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
+
+  // Note that we wanted to perform signed saturating multiplication,
+  // so since we performed plain multiplication in twice the bitwidth,
+  // we need to perform signed saturating truncation.
+  return getNonEmpty(std::min(L, Compare).truncSSat(getBitWidth()),
+                     std::max(L, Compare).truncSSat(getBitWidth()) + 1);
+}
+
 ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();