[ConstantRange] Add support of mul in makeGuaranteedNoWrapRegion.

[timshen]

Summary

This is trying to add support for r334428.

[timshen]

Add comments for div round up/down.

[timshen]

Remove extra braces.

[timshen]

Formatting.

[sanjoy]

llvm/lib/IR/ConstantRange.cpp

270

Sorry for being difficult, but these should live on APInt and be individually unit-tested.

336

Can you please given an informal description of how this works? For example, naively I'd think for unsigned overflow just checking [0,Other.getUnsignedMax()) would be sufficient.

[timshen]

Factored out APInt code, and simplified unsigned code.

[sanjoy]

LGTM modulo comments on the test coverage inline.

I didn't check the math too carefully since the test coverage looks good.

llvm/unittests/IR/ConstantRangeTest.cpp

1024

All of these tests would have passed without your change right (since earlier we'd return an empty range for multiplication)?

If yes, maybe add a couple of tests that check that we return non-trivial results (i.e. not empty sets) for some inputs?

1051

Maybe add an /*isSigned=*/true here?

1056

Minor nit, but it looks like these three loops can be different test cases with more descriptive names.

[timshen]

Updated comments and style.

[timshen]

llvm/unittests/IR/ConstantRangeTest.cpp

1024

All of these tests would have passed without your change right (since earlier we'd return an empty range for multiplication)?

No they don't pass. These tests test the inverse cases too, e.g. "iff" instead of "if". Looking at EXPECT_EQ(!Overflow, Range.contains(...));, if Overflow is false and Range is empty, the test will fail.

[timshen]

Add missing typedef.

llvm/lib/IR/ConstantRange.cpp

if (NoWrapKind & OBO::NoSignedWrap) {
                           APInt::getSignedMinValue(BitWidth)));
       if (SignedMin.isNegative())
         Result = SubsetIntersect(
             Result,
             ConstantRange(APInt::getSignedMinValue(BitWidth),
                           APInt::getSignedMinValue(BitWidth) + SignedMin));
     }
     return Result;
+  case Instruction::Mul: {
+    if (NoWrapKind == (OBO::NoSignedWrap | OBO::NoUnsignedWrap)) {
+      return SubsetIntersect(
+          makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoSignedWrap),
+          makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoUnsignedWrap));
+    }
+
+    // Equivalent to calling makeGuaranteedNoWrapRegion() on [V, V+1).
+    bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
+    const auto makeSingleValueRegion = [Unsigned,
+                                        BitWidth](APInt V) -> ConstantRange {
+      const auto DivRoundDown = [Unsigned](APInt A, APInt B) -> APInt {
+        if (Unsigned)
+          return A.udiv(B);
+        APInt Quo, Rem;
+        APInt::sdivrem(A, B, Quo, Rem);
+        if (Rem == 0)
+          return Quo;
+        // sdiv rounds the result towards zero. We want to check whether the
+        // non-integer part of the mathematical value is negative or not.
+        // If the non-integer part is negative, we need to round down from Quo;
+        // otherwise, if it's positive or 0, we return Quo, as it's already
+        // rounded down.
+        if (Rem.isNegative() != B.isNegative())
+          return Quo - 1;
+        return Quo;
+      };
+      const auto DivRoundUp = [Unsigned](APInt A, APInt B) -> APInt {
+        if (Unsigned) {
+          APInt Quo, Rem;
+          APInt::udivrem(A, B, Quo, Rem);
+          if (Rem == 0)
+            return Quo;
+          return Quo + 1;
+        }
+        APInt Quo, Rem;
+        APInt::sdivrem(A, B, Quo, Rem);
+        if (Rem == 0)
+          return Quo;
+        // Similar to DivRoundDown above, but do the opposite.
+        if (Rem.isNegative() != B.isNegative())
+          return Quo;
+        return Quo + 1;
+      };
+
+      if (V == 0 || V.isOneValue())
+        return ConstantRange(BitWidth, true);
+
+      APInt MinValue, MaxValue;
+      if (Unsigned) {
+        MinValue = APInt::getMinValue(BitWidth);
+        MaxValue = APInt::getMaxValue(BitWidth);
+      } else {
+        MinValue = APInt::getSignedMinValue(BitWidth);
+        MaxValue = APInt::getSignedMaxValue(BitWidth);
+      }
+      // e.g. Returning [-127, 127], represented as [-127, -128).
+      if (!Unsigned && V.isAllOnesValue())
+        return ConstantRange(-MaxValue, MinValue);
+
+      APInt Lower, Upper;
+      if (!Unsigned && V.isNegative()) {
+        Lower = DivRoundUp(MaxValue, V);
+        Upper = DivRoundDown(MinValue, V);
+      } else {
+        Lower = DivRoundUp(MinValue, V);
+        Upper = DivRoundDown(MaxValue, V);
+      }
+      if (Unsigned) {
+        Lower = Lower.zextOrSelf(BitWidth);
+        Upper = Upper.zextOrSelf(BitWidth);
+      } else {
+        Lower = Lower.sextOrSelf(BitWidth);
+        Upper = Upper.sextOrSelf(BitWidth);
+      }
+      return ConstantRange(Lower, Upper + 1);
+    };
+    return SubsetIntersect(
+        makeSingleValueRegion(Unsigned ? Other.getUnsignedMin()
+                                       : Other.getSignedMin()),
+        makeSingleValueRegion(Unsigned ? Other.getUnsignedMax()
+                                       : Other.getSignedMax()));
+  }
   }
 }
 
 bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
 
 bool ConstantRange::isEmptySet() const {

llvm/unittests/IR/ConstantRangeTest.cpp

TEST(ConstantRange, GetEquivalentICmp) {
   EXPECT_EQ(RHS, APInt(32, -1));
 
   EXPECT_TRUE(
       ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
   EXPECT_EQ(Pred, CmpInst::ICMP_NE);
   EXPECT_EQ(RHS, APInt(32, -1));
 }
 
+TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSingleValue) {
+  typedef OverflowingBinaryOperator OBO;
+
+  for (uint64_t i = std::numeric_limits<uint8_t>::min();
+       i <= std::numeric_limits<uint8_t>::max(); i++) {
+    auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
+        Instruction::Mul, ConstantRange(APInt(8, i), APInt(8, 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(8, i).umul_ov(APInt(8, v), Overflow);
+      EXPECT_EQ(!Overflow, Range.contains(APInt(8, v)));
+    }
+  }
+
+  for (int64_t i = std::numeric_limits<int8_t>::min();
+       i <= std::numeric_limits<int8_t>::max(); i++) {
+    auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
+        Instruction::Mul,
+        ConstantRange(APInt(8, i, true), APInt(8, i + 1, true)),
+        OBO::NoSignedWrap);
+
+    for (int64_t v = std::numeric_limits<int8_t>::min();
+         v <= std::numeric_limits<int8_t>::max(); v++) {
+      bool Overflow;
+      (void)APInt(8, i, true).smul_ov(APInt(8, v, true), Overflow);
+      EXPECT_EQ(!Overflow, Range.contains(APInt(8, v, true)));
+    }
+  }
+
+  for (uint64_t i = std::numeric_limits<uint8_t>::min();
+       i <= std::numeric_limits<uint8_t>::max(); i++) {
+    auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
+        Instruction::Mul, ConstantRange(APInt(8, i), APInt(8, i + 1)),
+        OBO::NoUnsignedWrap | OBO::NoSignedWrap);
+
+    for (uint64_t v = std::numeric_limits<uint8_t>::min();
+         v <= std::numeric_limits<uint8_t>::max(); v++) {
+      bool UOverflow;
+      (void)APInt(8, i).umul_ov(APInt(8, v), UOverflow);
+      bool SOverflow;
+      (void)APInt(8, i).smul_ov(APInt(8, v), SOverflow);
+      EXPECT_EQ(!(UOverflow || SOverflow), Range.contains(APInt(8, v)));
+    }
+  }
+}
+
+TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) {
+  typedef OverflowingBinaryOperator OBO;
+
+  for (uint64_t lo = std::numeric_limits<uint8_t>::min();
+       lo <= std::numeric_limits<uint8_t>::max(); lo++) {
+    for (uint64_t hi = lo; hi <= std::numeric_limits<uint8_t>::max(); hi++) {
+      EXPECT_EQ(
+          ConstantRange::makeGuaranteedNoWrapRegion(
+              Instruction::Mul, ConstantRange(APInt(8, lo), APInt(8, hi + 1)),
+              OBO::NoUnsignedWrap),
+          ConstantRange::makeGuaranteedNoWrapRegion(
+              Instruction::Mul, ConstantRange(APInt(8, hi), APInt(8, hi + 1)),
+              OBO::NoUnsignedWrap));
+    }
+  }
+}
+
+TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange) {
+  typedef OverflowingBinaryOperator OBO;
+
+  int lo = -12, hi = 16;
+  auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
+      Instruction::Mul,
+      ConstantRange(APInt(8, lo, true), APInt(8, hi + 1, true)),
+      OBO::NoSignedWrap);
+
+  for (int64_t v = std::numeric_limits<int8_t>::min();
+       v <= std::numeric_limits<int8_t>::max(); v++) {
+    bool AnyOverflow = false;
+    for (int64_t i = lo; i <= hi; i++) {
+      bool Overflow;
+      (void)APInt(8, i, true).smul_ov(APInt(8, v, true), Overflow);
+      AnyOverflow |= Overflow;
+    }
+    EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, v, true)));
+  }
+}
+
 }  // anonymous namespace