[ConstantRange] Add urem support

[nikic]

Summary

Add urem support to ConstantRange, so we can handle in in LVI. This is an approximate implementation that tries to capture the most useful conditions: If the LHS is always strictly smaller than the RHS, then the urem is a no-op and the result is the same as the LHS range. Otherwise the lower bound is zero and the upper bound is min(LHSMax, RHSMax - 1).

[nikic]

Make implementation slightly more obvious.

[lebedev.ri]

While i understand that you can't do a traditional exhaustive test that this produces *identical* results,
can't you at least test that the ConstantRange::urem() is still always conservatively correct?

[lebedev.ri]

LG other than exhaustive test suggestion.

Even in the cases where we can't test that exhaustive test produces identical results,
we should be able to at least test that ConstantRange is conservatively correct,
in the sense that ConstantRange returns a superset of the exhaustive test, no?

[nikic]

In D60952#1475582, @lebedev.ri wrote:

Even in the cases where we can't test that exhaustive test produces identical results,
we should be able to at least test that ConstantRange is conservatively correct,
in the sense that ConstantRange returns a superset of the exhaustive test, no?

Yup. I've extended TestUnsignedBinOpExhaustive to support checking correctness only and used it here.

[lebedev.ri]

In D60952#1475914, @nikic wrote:

In D60952#1475582, @lebedev.ri wrote:

Even in the cases where we can't test that exhaustive test produces identical results,
we should be able to at least test that ConstantRange is conservatively correct,
in the sense that ConstantRange returns a superset of the exhaustive test, no?

Yup. I've extended TestUnsignedBinOpExhaustive to support checking correctness only and used it here.

Great, thank you!

llvm/trunk/include/llvm/IR/ConstantRange.h

public:
   ConstantRange umin(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from an unsigned division of a value in this range and a value in
   /// \p Other.
   ConstantRange udiv(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
+  /// from an unsigned remainder operation of a value in this range and a
+  /// value in \p Other.
+  ConstantRange urem(const ConstantRange &Other) const;
+
+  /// Return a new range representing the possible values resulting
   /// from a binary-and of a value in this range by a value in \p Other.
   ConstantRange binaryAnd(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from a binary-or of a value in this range by a value in \p Other.
   ConstantRange binaryOr(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting

llvm/trunk/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
   case Instruction::Add:
     return add(Other);
   case Instruction::Sub:
     return sub(Other);
   case Instruction::Mul:
     return multiply(Other);
   case Instruction::UDiv:
     return udiv(Other);
+  case Instruction::URem:
+    return urem(Other);
   case Instruction::Shl:
     return shl(Other);
   case Instruction::LShr:
     return lshr(Other);
   case Instruction::AShr:
     return ashr(Other);
   case Instruction::And:
     return binaryAnd(Other);
if (RHS_umin.isNullValue()) {
     else
       RHS_umin = 1;
   }
 
   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
   return getNonEmpty(std::move(Lower), std::move(Upper));
 }
 
+ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
+  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
+    return getEmpty();
+
+  // L % R for L < R is L.
+  if (getUnsignedMax().ult(RHS.getUnsignedMin()))
+    return *this;
+
+  // L % R is <= L and < R.
+  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
+  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
+}
+
 ConstantRange
 ConstantRange::binaryAnd(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
 
   // TODO: replace this with something less conservative
 
   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
   if (!CR.isEmptySet()) {
     APInt N = CR.getLower();
     do TestFn(N);
     while (++N != CR.getUpper());
   }
 }
 
 template<typename Fn1, typename Fn2>
-static void TestUnsignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) {
+static void TestUnsignedBinOpExhaustive(
+    Fn1 RangeFn, Fn2 IntFn,
+    bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
-    ConstantRange CR = RangeFn(CR1, CR2);
-    if (CR1.isEmptySet() || CR2.isEmptySet()) {
-      EXPECT_TRUE(CR.isEmptySet());
-      return;
-    }
-
     APInt Min = APInt::getMaxValue(Bits);
     APInt Max = APInt::getMinValue(Bits);
     ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
       ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        if (SkipZeroRHS && N2 == 0)
+          return;
+
         APInt N = IntFn(N1, N2);
         if (N.ult(Min))
           Min = N;
         if (N.ugt(Max))
           Max = N;
       });
     });
 
-    EXPECT_EQ(ConstantRange::getNonEmpty(Min, Max + 1), CR);
+    ConstantRange CR = RangeFn(CR1, CR2);
+    if (Min.ugt(Max)) {
+      EXPECT_TRUE(CR.isEmptySet());
+      return;
+    }
+
+    ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
+    if (CorrectnessOnly) {
+      EXPECT_TRUE(CR.contains(Exact));
+    } else {
+      EXPECT_EQ(Exact, CR);
+    }
   });
 }
 
 template<typename Fn1, typename Fn2>
 static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) {
   unsigned Bits = 4;
   EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
                                        const ConstantRange &CR2) {
TEST_F(ConstantRangeTest, UDiv) {
   EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
   EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
   EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
   EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
   EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
   EXPECT_EQ(Wrap.udiv(Wrap), Full);
 }
 
+TEST_F(ConstantRangeTest, URem) {
+  EXPECT_EQ(Full.urem(Empty), Empty);
+  EXPECT_EQ(Empty.urem(Full), Empty);
+  // urem by zero is poison.
+  EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
+  // urem by full range doesn't contain MaxValue.
+  EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
+  // urem is upper bounded by maximum RHS minus one.
+  EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
+            ConstantRange(APInt(16, 0), APInt(16, 122)));
+  // urem is upper bounded by maximum LHS.
+  EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
+            ConstantRange(APInt(16, 0), APInt(16, 123)));
+  // If the LHS is always lower than the RHS, the result is the LHS.
+  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
+                .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
+            ConstantRange(APInt(16, 10), APInt(16, 20)));
+  // It has to be strictly lower, otherwise the top value may wrap to zero.
+  EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
+                .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
+            ConstantRange(APInt(16, 0), APInt(16, 20)));
+  // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
+  EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
+                .urem(ConstantRange(APInt(16, 10))),
+            ConstantRange(APInt(16, 0), APInt(16, 10)));
+
+  TestUnsignedBinOpExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.urem(CR2);
+      },
+      [](const APInt &N1, const APInt &N2) {
+        return N1.urem(N2);
+      },
+      /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
+}
+
 TEST_F(ConstantRangeTest, Shl) {
   ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
   ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
   EXPECT_EQ(Full.shl(Full), Full);
   EXPECT_EQ(Full.shl(Empty), Empty);
   EXPECT_EQ(Full.shl(One), Full);    // TODO: [0, (-1 << 0xa) + 1)
   EXPECT_EQ(Full.shl(Some), Full);   // TODO: [0, (-1 << 0xa) + 1)
   EXPECT_EQ(Full.shl(Wrap), Full);