[ConstantRange] Teach multiply to be cleverer about signed ranges.

Multiplication is not dependent on signedness, so just treating
all input ranges as unsigned is not incorrect. However it will cause
overly pessimistic ranges (such as full-set) when used with signed
negative values.

Teach multiply to try to interpret its inputs as both signed and
unsigned, and then to take the most specific (smallest population)
as its result.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231483 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/IR/ConstantRange.h b/include/llvm/IR/ConstantRange.h
index 5e8cd34c4d696f2c566576706cfa328a03a6aa49..ebb1bf0b04b42d53993c0ce84b120b55f944e79f 100644 (file)
--- a/include/llvm/IR/ConstantRange.h
+++ b/include/llvm/IR/ConstantRange.h
@@ -208,8 +208,8 @@ public:
   ConstantRange sub(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
-  /// from a multiplication of a value in this range and a value in \p Other.
-  /// TODO: This isn't fully implemented yet.
+  /// from a multiplication of a value in this range and a value in \p Other,
+  /// treating both this and \p Other as unsigned ranges.
   ConstantRange multiply(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting

diff --git a/lib/IR/ConstantRange.cpp b/lib/IR/ConstantRange.cpp
index f8e9ba4f42cf9be36efe41d68ad30e3589b4ee38..eec18b95fb8997272bc9c2c9ff1d6bbd2da510d4 100644 (file)
--- a/lib/IR/ConstantRange.cpp
+++ b/lib/IR/ConstantRange.cpp
@@ -587,6 +587,13 @@ ConstantRange::multiply(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 
+  // Multiplication is signedness-independent. However different ranges can be
+  // obtained depending on how the input ranges are treated. These different
+  // ranges are all conservatively correct, but one might be better than the
+  // other. We calculate two ranges; one treating the inputs as unsigned
+  // and the other signed, then return the smallest of these ranges.
+
+  // Unsigned range first.
   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
@@ -594,7 +601,26 @@ ConstantRange::multiply(const ConstantRange &Other) const {
 
   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
                                             this_max * Other_max + 1);
-  return Result_zext.truncate(getBitWidth());
+  ConstantRange UR = Result_zext.truncate(getBitWidth());
+
+  // Now the signed range. 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.
+
+  this_min = getSignedMin().sext(getBitWidth() * 2);
+  this_max = getSignedMax().sext(getBitWidth() * 2);
+  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
+  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); };
+  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
+  ConstantRange SR = Result_sext.truncate(getBitWidth());
+
+  return UR.getSetSize().ult(SR.getSetSize()) ? UR : SR;
 }
 
 ConstantRange

diff --git a/unittests/IR/ConstantRangeTest.cpp b/unittests/IR/ConstantRangeTest.cpp
index fa03302ad2bb3c6f7435f05eec2664e712f9ec26..fe95b0db9c5c0c1ac3af5c051072202e014a84cd 100644 (file)
--- a/unittests/IR/ConstantRangeTest.cpp
+++ b/unittests/IR/ConstantRangeTest.cpp
@@ -400,6 +400,13 @@ TEST_F(ConstantRangeTest, Multiply) {
   EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
                 ConstantRange(APInt(4, 6), APInt(4, 2))),
             ConstantRange(4, /*isFullSet=*/true));
+
+  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
+              ConstantRange(APInt(8, 252), APInt(8, 4))),
+            ConstantRange(APInt(8, 250), APInt(8, 9)));
+  EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
+              ConstantRange(APInt(8, 2), APInt(8, 4))),
+            ConstantRange(APInt(8, 250), APInt(8, 253)));
 }
 
 TEST_F(ConstantRangeTest, UMax) {