[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 ↗

(On Diff #152216)

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

336 ↗

(On Diff #152216)

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 ↗

(On Diff #152520)

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 ↗

(On Diff #152520)

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

1056 ↗

(On Diff #152520)

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 ↗

(On Diff #152520)

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/trunk/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).
+    const bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
+    const auto makeSingleValueRegion = [Unsigned,
+                                        BitWidth](APInt V) -> ConstantRange {
+      // Handle special case for 0, -1 and 1. See the last for reason why we
+      // specialize -1 and 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 = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
+        Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);
+      } else if (Unsigned) {
+        Lower = APIntOps::RoundingUDiv(MinValue, V, APInt::Rounding::UP);
+        Upper = APIntOps::RoundingUDiv(MaxValue, V, APInt::Rounding::DOWN);
+      } else {
+        Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
+        Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);
+      }
+      if (Unsigned) {
+        Lower = Lower.zextOrSelf(BitWidth);
+        Upper = Upper.zextOrSelf(BitWidth);
+      } else {
+        Lower = Lower.sextOrSelf(BitWidth);
+        Upper = Upper.sextOrSelf(BitWidth);
+      }
+      // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1).
+      // Upper + 1 is guanranteed not to overflow, because |divisor| > 1. 0, -1,
+      // and 1 are already handled as special cases.
+      return ConstantRange(Lower, Upper + 1);
+    };
+
+    if (Unsigned)
+      return makeSingleValueRegion(Other.getUnsignedMax());
+
+    return SubsetIntersect(makeSingleValueRegion(Other.getSignedMin()),
+                           makeSingleValueRegion(Other.getSignedMax()));
+  }
   }
 }
 
 bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
 
 bool ConstantRange::isEmptySet() const {

llvm/trunk/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, MakeGuaranteedNoWrapRegionMulUnsignedSingleValue) {
+  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)));
+    }
+  }
+}
+
+TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedSingleValue) {
+  typedef OverflowingBinaryOperator OBO;
+
+  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, /*isSigned=*/true),
+                      APInt(8, I + 1, /*isSigned=*/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, /*isSigned=*/true)
+          .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
+      EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
+    }
+  }
+}
+
+TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedAndSignedSingleValue) {
+  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 | 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, /*isSigned=*/true),
+                    APInt(8, Hi + 1, /*isSigned=*/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, /*isSigned=*/true)
+          .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
+      AnyOverflow |= Overflow;
+    }
+    EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
+  }
+}
+
 }  // anonymous namespace