[ConstantRange] Add srem() support

[nikic]

Summary

Add support for srem() to ConstantRange so we can use it in LVI. For srem the sign of the result matches the sign of the LHS. For the RHS only the absolute value is important. Apart from that the logic is like urem.

Just like for urem this is only an approximate implementation. The tests check a few specific cases and run an exhaustive test for conservative correctness (but not exactness).

[lebedev.ri]

llvm/unittests/IR/ConstantRangeTest.cpp

127

Hm, i wonder if we can also check that the result
is exact when the ranges contain a single element?
Not sure if that would hold for the current implementations though.

I also wonder if some kind of a "precision" metric should be calculated,
e.g. ConstantRange returned range with 75 elements, and exhaustive test
returned range with 67 elements then let's say it's 67/75.
And then just average that metric over all the checked ranges.

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

127

Hm, i wonder if we can also check that the result
is exact when the ranges contain a single element?
Not sure if that would hold for the current implementations though.

Unfortunately the current implementation (also the urem implementation) is not exact for single element ranges, even if both ranges only have a single element. For example 15 % 10 will return [0, 9] instead of 5.

The basic problem is that if the LHS is larger than the RHS, we have to perform a modular reduction so that [12, 18] % 10 maps onto [2, 8]. However, if both ends of the range do not divide to the same value, then we get back the full modulus range, such as [18, 22] % 10 being [0, 9], because 18 / 10 == 1 while 24 / 10 == 2.

For a single-element modulus this would be easy enough to handle, but once we get a proper range, I'm not sure how to do this, or if it's even possible to do it efficiently.

Special handling for the single-element case would definitely be possible, I'm just not sure if it's a good idea (I don't think I've seen any of the other constant range code do that).

I also wonder if some kind of a "precision" metric should be calculated,
e.g. ConstantRange returned range with 75 elements, and exhaustive test
returned range with 67 elements then let's say it's 67/75.
And then just average that metric over all the checked ranges.

What would be the goal of the metric? To make sure that the "precision" never becomes lower if the implementation is changed?

[lebedev.ri]

llvm/unittests/IR/ConstantRangeTest.cpp

127

Special handling for the single-element case would definitely be possible, I'm just not sure if it's a good idea (I don't think I've seen any of the other constant range code do that).

Yep, i was *not* suggesting special-casing single-element ranges.

What would be the goal of the metric? To make sure that the "precision" never becomes lower if the implementation is changed?

That, or to gauge which operation needs more work.
Just a thought, i'm not sure how useful it would be.

[lebedev.ri]

Ok, LG as conservative implementation.

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

127

I gave the precision metric (with your suggested definition) a try and checked it against a couple of bit widths. This gave me 90% (3 bits), 95% (4 bits) and 97% (5 bits) precision.

Not sure what exactly that tells us though ^^ This is probably something that needs to be evaluated over the actual probability density of the input, otherwise we end up biasing heavily in favor of ranges with little practical relevance (at least one operand will the wrapping in 75% of the cases).

llvm/include/llvm/IR/ConstantRange.h

public:
   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 signed remainder operation of a value in this range and a
+  /// value in \p Other.
+  ConstantRange srem(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/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
   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::SRem:
+    return srem(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);
ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
   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::srem(const ConstantRange &RHS) const {
+  if (isEmptySet() || RHS.isEmptySet())
+    return getEmpty();
+
+  ConstantRange AbsRHS = RHS.abs();
+  APInt MinAbsRHS = AbsRHS.getUnsignedMin();
+  APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
+
+  // Modulus by zero is UB.
+  if (MaxAbsRHS.isNullValue())
+    return getEmpty();
+
+  if (MinAbsRHS.isNullValue())
+    ++MinAbsRHS;
+
+  APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
+
+  if (MinLHS.isNonNegative()) {
+    // L % R for L < R is L.
+    if (MaxLHS.ult(MinAbsRHS))
+      return *this;
+
+    // L % R is <= L and < R.
+    APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
+    return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
+  }
+
+  // Same basic logic as above, but the result is negative.
+  if (MaxLHS.isNegative()) {
+    if (MinLHS.ugt(-MinAbsRHS))
+      return *this;
+
+    APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
+    return getNonEmpty(std::move(Lower), APInt(getBitWidth(), 1));
+  }
+
+  // LHS range crosses zero.
+  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
+  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
+  return getNonEmpty(std::move(Lower), 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/unittests/IR/ConstantRangeTest.cpp

if (CorrectnessOnly) {
       EXPECT_TRUE(CR.contains(Exact));
     } else {
       EXPECT_EQ(Exact, CR);
     }
   });
 }
 
 template<typename Fn1, typename Fn2>
-static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) {
+static void TestSignedBinOpExhaustive(
+    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::getSignedMaxValue(Bits);
     APInt Max = APInt::getSignedMinValue(Bits);
     ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
       ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        if (SkipZeroRHS && N2 == 0)
+          return;
+
         APInt N = IntFn(N1, N2);
         if (N.slt(Min))
           Min = N;
         if (N.sgt(Max))
           Max = N;
       });
     });
 
-    EXPECT_EQ(ConstantRange::getNonEmpty(Min, Max + 1), CR);
+    ConstantRange CR = RangeFn(CR1, CR2);
+    if (Min.sgt(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);
+    }
   });
 }
 
 ConstantRange ConstantRangeTest::Full(16, true);
 ConstantRange ConstantRangeTest::Empty(16, false);
 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
TestUnsignedBinOpExhaustive(
         return CR1.urem(CR2);
       },
       [](const APInt &N1, const APInt &N2) {
         return N1.urem(N2);
       },
       /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
 }
 
+TEST_F(ConstantRangeTest, SRem) {
+  EXPECT_EQ(Full.srem(Empty), Empty);
+  EXPECT_EQ(Empty.srem(Full), Empty);
+  // srem by zero is UB.
+  EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
+  // srem by full range doesn't contain SignedMinValue.
+  EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
+                                           APInt::getSignedMinValue(16)));
+
+  ConstantRange PosMod(APInt(16, 10), APInt(16, 21));  // [10, 20]
+  ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
+  ConstantRange IntMinMod(APInt::getSignedMinValue(16));
+
+  ConstantRange Expected(16, true);
+
+  // srem is bounded by abs(RHS) minus one.
+  ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
+  Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
+  EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
+  EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
+  ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
+  Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
+  EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
+  EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
+  ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
+  Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
+  EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
+  EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
+
+  // srem is bounded by LHS.
+  ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
+  EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
+  EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
+  EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
+  ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
+  EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
+  EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
+  EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
+  ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
+  EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
+  EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
+  EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
+
+  // srem is LHS if it is smaller than RHS.
+  ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
+  EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
+  EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
+  EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
+  ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
+  EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
+  EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
+  EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
+  ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
+  EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
+  EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
+  EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
+
+  // Example of a suboptimal result:
+  // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
+  EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
+                .srem(ConstantRange(APInt(16, 10))),
+            ConstantRange(APInt(16, 0), APInt(16, 10)));
+
+  TestSignedBinOpExhaustive(
+      [](const ConstantRange &CR1, const ConstantRange &CR2) {
+        return CR1.srem(CR2);
+      },
+      [](const APInt &N1, const APInt &N2) {
+        return N1.srem(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);