[ConstantRange] Add sdiv() support

[nikic]

Summary

Add the last missing binary op to ConstantRange: sdiv. This was a real struggle, both in terms of implementation and testing.

The implementation is conceptually simple: We separate the LHS and RHS into positive and negative components and then also compute the positive and negative components of the result, taking into account that e.g. only pos/pos and neg/neg will give a positive result.

However, there's one complication: SignedMin / -1 is UB for sdiv, and we can't just ignore it, because the APInt result of SignedMin would break the sign segregation. Instead we drop SignedMin or -1 from the corresponding ranges, taking into account some edge cases with wrapped ranges.

Because of the sign segregation, the implementation ends up being nearly fully precise even for wrapped ranges (the remaining imprecision is due to ranges that are both signed and unsigned wrapping and are divided by a trivial divisor like 1). This means that the testing cannot just check the signed envelope as we usually do. Instead we collect all possible results in a bitvector and construct a better sign wrapped range (than the full envelope).

[nikic]

Add the last missing binary op to ConstantRange: sdiv.

Turned out to be not quite true: We're also missing xor. But I don't think that one is really worthwhile to deal with in terms of ranges...

[nikic]

ping :)

[nikic]

ping :)

[jdoerfert]

llvm/lib/IR/ConstantRange.cpp

1018 ↗

(On Diff #197015)

I'm confused, isn't -3 / -3 = 1 ?

1030 ↗

(On Diff #197015)

Is it worth the hassle? Ignoring the special case and taking the APInt behavior seems like a much easier solution. Do we have evidence we don't want that? (I did not try to understand this special case yet!)

[nikic]

llvm/lib/IR/ConstantRange.cpp

1018 ↗

(On Diff #197015)

Right, this should read neg / neg = pos.

1030 ↗

(On Diff #197015)

Not handling this case would muddy the waters with regards to signs -- a negative number divided by a negative number should have a guaranteed positive result, and I would consider it important that we realize this.

The second motivation (and the reason why I'm going out of the way here to also treat wrapped ranges correctly), is that it allows us to exhaustively test the sdiv implementation for both conservative correctness and optimality, and thus give us full confidence in the implementation. Otherwise we would have to settle for conservative correctness only.

[jdoerfert]

llvm/lib/IR/ConstantRange.cpp

1030 ↗

(On Diff #197015)

Agreed.

I think I understand the code below but it is hard to follow the logic and map it back to the comment above. Could you explain what is going on so it is easier to read, e.g.,

// Filter the singleton set [-1,0) as it does not make a defined contribution to the result.
if (!NegR.Lower.isAllOnesValue()) {

[nikic]

Update comments so they are closer to the relevant branches in the implementation.

[jdoerfert]

Thanks for improving the comments. LGTM now.

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 a signed division of a value in this range and a value in
+  /// \p Other. Division by zero and division of SignedMin by -1 are considered
+  /// undefined behavior, in line with IR, and do not contribute towards the
+  /// result.
+  ConstantRange sdiv(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;

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::SDiv:
+    return sdiv(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);
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::sdiv(const ConstantRange &RHS) const {
+  // We split up the LHS and RHS into positive and negative components
+  // and then also compute the positive and negative components of the result
+  // separately by combining division results with the appropriate signs.
+  APInt Zero = APInt::getNullValue(getBitWidth());
+  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
+  ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin);
+  ConstantRange NegFilter(SignedMin, Zero);
+  ConstantRange PosL = intersectWith(PosFilter);
+  ConstantRange NegL = intersectWith(NegFilter);
+  ConstantRange PosR = RHS.intersectWith(PosFilter);
+  ConstantRange NegR = RHS.intersectWith(NegFilter);
+
+  ConstantRange PosRes = getEmpty();
+  if (!PosL.isEmptySet() && !PosR.isEmptySet())
+    // pos / pos = pos.
+    PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
+                           (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
+
+  if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
+    // neg / neg = pos.
+    //
+    // We need to deal with one tricky case here: SignedMin / -1 is UB on the
+    // IR level, so we'll want to exclude this case when calculating bounds.
+    // (For APInts the operation is well-defined and yields SignedMin.) We
+    // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
+    APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
+    if (NegL.Lower.isMinSignedValue() && NegR.Upper.isNullValue()) {
+      // Remove -1 from the LHS. Skip if it's the only element, as this would
+      // leave us with an empty set.
+      if (!NegR.Lower.isAllOnesValue()) {
+        APInt AdjNegRUpper;
+        if (RHS.Lower.isAllOnesValue())
+          // Negative part of [-1, X] without -1 is [SignedMin, X].
+          AdjNegRUpper = RHS.Upper;
+        else
+          // [X, -1] without -1 is [X, -2].
+          AdjNegRUpper = NegR.Upper - 1;
+
+        PosRes = PosRes.unionWith(
+            ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
+      }
+
+      // Remove SignedMin from the RHS. Skip if it's the only element, as this
+      // would leave us with an empty set.
+      if (NegL.Upper != SignedMin + 1) {
+        APInt AdjNegLLower;
+        if (Upper == SignedMin + 1)
+          // Negative part of [X, SignedMin] without SignedMin is [X, -1].
+          AdjNegLLower = Lower;
+        else
+          // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
+          AdjNegLLower = NegL.Lower + 1;
+
+        PosRes = PosRes.unionWith(
+            ConstantRange(std::move(Lo),
+                          AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
+      }
+    } else {
+      PosRes = PosRes.unionWith(
+          ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
+    }
+  }
+
+  ConstantRange NegRes = getEmpty();
+  if (!PosL.isEmptySet() && !NegR.isEmptySet())
+    // pos / neg = neg.
+    NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
+                           PosL.Lower.sdiv(NegR.Lower) + 1);
+
+  if (!NegL.isEmptySet() && !PosR.isEmptySet())
+    // neg / pos = neg.
+    NegRes = NegRes.unionWith(
+        ConstantRange(NegL.Lower.sdiv(PosR.Lower),
+                      (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
+
+  // Prefer a non-wrapping signed range here.
+  ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);
+
+  // Preserve the zero that we dropped when splitting the LHS by sign.
+  if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
+    Res = Res.unionWith(ConstantRange(Zero));
+  return Res;
+}
+
 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;
 

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/KnownBits.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
TEST_F(ConstantRangeTest, UDiv) {
   EXPECT_EQ(Zero.udiv(Full), Zero);
 
   EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
             ConstantRange(APInt(16, 0), APInt(16, 99)));
   EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
             ConstantRange(APInt(16, 0), APInt(16, 99)));
 }
 
+TEST_F(ConstantRangeTest, SDiv) {
+  unsigned Bits = 4;
+  EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
+                                       const ConstantRange &CR2) {
+    // Collect possible results in a bit vector. We store the signed value plus
+    // a bias to make it unsigned.
+    int Bias = 1 << (Bits - 1);
+    BitVector Results(1 << Bits);
+    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        // Division by zero is UB.
+        if (N2 == 0)
+          return;
+
+        // SignedMin / -1 is UB.
+        if (N1.isMinSignedValue() && N2.isAllOnesValue())
+          return;
+
+        APInt N = N1.sdiv(N2);
+        Results.set(N.getSExtValue() + Bias);
+      });
+    });
+
+    ConstantRange CR = CR1.sdiv(CR2);
+    if (Results.none()) {
+      EXPECT_TRUE(CR.isEmptySet());
+      return;
+    }
+
+    // If there is a non-full signed envelope, that should be the result.
+    APInt SMin(Bits, Results.find_first() - Bias);
+    APInt SMax(Bits, Results.find_last() - Bias);
+    ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
+    if (!Envelope.isFullSet()) {
+      EXPECT_EQ(Envelope, CR);
+      return;
+    }
+
+    // If the signed envelope is a full set, try to find a smaller sign wrapped
+    // set that is separated in negative and positive components (or one which
+    // can also additionally contain zero).
+    int LastNeg = Results.find_last_in(0, Bias) - Bias;
+    int LastPos = Results.find_next(Bias) - Bias;
+    if (Results[Bias]) {
+      if (LastNeg == -1)
+        ++LastNeg;
+      else if (LastPos == 1)
+        --LastPos;
+    }
+
+    APInt WMax(Bits, LastNeg);
+    APInt WMin(Bits, LastPos);
+    ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
+    EXPECT_EQ(Wrapped, CR);
+  });
+}
+
 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.