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

[jmolloy]

Summary

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.

[hfinkel]

LGTM.

[sanjoy]

ConstantRange
+ConstantRange::smultiply(const ConstantRange &Other) const {
+ TODO: If either operand is a single element and the multiply is known to
+ be non-wrapping, round the result min and max value to the appropriate
+ multiple of that element. If wrapping is possible, at least adjust the
+ range according to the greatest power-of-two factor of the single element.
+
+ if (isEmptySet() || Other.isEmptySet())
+ return ConstantRange(getBitWidth(), /*isFullSet=*/false);
+
+ 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);
+
+ ConstantRange Result_zext = ConstantRange(this_min * Other_min,
+ this_max * Other_max + 1);
+ return Result_zext.truncate(getBitWidth());

I'm not sure if this is correct: if we multiply [-1, 2) with itself,
won't this return [1, 2)? Shouldn't [-1,2) * [-1,2) be [-1,2)?

• Sanjoy

[sanjoy]

Small nit inline. I think this looks okay, but I don't know this part of LLVM to LGTM this.

lib/IR/ConstantRange.cpp

609

This example is a bit off, the min should be min(-1*-2, -1*2, 3*-2, 3*2) = -6. The code is correct, as far as I can tell.

[jmolloy]

Hi Nick,

Gentle ping.

Cheers,

James

[nlewycky]

I got a bounce message ...

include/llvm/IR/ConstantRange.h

public:
   ConstantRange add(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from a subtraction of a value in this range and a value in \p Other.
   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.
   ConstantRange multiply(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from a signed maximum of a value in this range and a value in \p Other.
   ConstantRange smax(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from an unsigned maximum of a value in this range and a value in \p Other.

lib/IR/ConstantRange.cpp

ConstantRange::multiply(const ConstantRange &Other) const {
   // TODO: If either operand is a single element and the multiply is known to
   // be non-wrapping, round the result min and max value to the appropriate
   // multiple of that element. If wrapping is possible, at least adjust the
   // range according to the greatest power-of-two factor of the single element.
 
   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);
   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
 
   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*3, 4*-2, 4*3) = -8.
+  // 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
 ConstantRange::smax(const ConstantRange &Other) const {
   // X smax Y is: range(smax(X_smin, Y_smin),
   //                    smax(X_smax, Y_smax))
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);

unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, Multiply) {
   EXPECT_EQ(Full.multiply(Zero), Zero);
   EXPECT_EQ(Some.multiply(Zero), Zero);
   EXPECT_EQ(Wrap.multiply(Zero), Zero);
 
   // http://llvm.org/PR4545
   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) {
   EXPECT_EQ(Full.umax(Full), Full);
   EXPECT_EQ(Full.umax(Empty), Empty);
   EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
   EXPECT_EQ(Full.umax(Wrap), Full);
   EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));