[KnownBits] Add implementation for `KnownBits::sdiv`

[goldstein.w.n]

Summary

Can figure out some of the upper bits (similiar to udiv) if we know
the sign of the inputs.

As well, if we have the exact flag we can sometimes determine some
low-bits.

[RKSimon]

llvm/lib/Support/KnownBits.cpp

538

assertion message

591

assert !Known.hasConflict()

[nikic]

FWIW, if we know the sign bits of sdiv, we should really always be converting it to udiv. We actually already do this in CVP, and should also implement the same in InstCombine. It currently only handles the non-negative case, but the others can be implemented by adding the necessary negations.

[goldstein.w.n]

In D150093#4326402, @nikic wrote:

FWIW, if we know the sign bits of sdiv, we should really always be converting it to udiv. We actually already do this in CVP, and should also implement the same in InstCombine. It currently only handles the non-negative case, but the others can be implemented by adding the necessary negations.

I saw that. It increases instruction count though. It's also hard to undo in the backend and results in worse codegen. I was planning to make a patch to actually stop doing it for non-constant operands because of that.

[goldstein.w.n]

Rebase

[goldstein.w.n]

N/A

[RKSimon]

LGTM - cheers

llvm/lib/Support/KnownBits.cpp

559

Xxact -> Exact

[goldstein.w.n]

Fix misspell

[goldstein.w.n]

Rebase

[foad]

Sorry I'm late.

llvm/lib/Support/KnownBits.cpp

533

Typo "Equivalent"

541

Typo "Denom"

551

Why strictly positive here? I don't think you need to worry about divide-by-zero (poison) cases.

552

Typoe "Result is negative ..."

559

Typo "Result is negative ..."

569

At this point the sign of Res should match ResultSign, so you don't need a std::optional, you could just have a "bool ResultSignKnown".

572

Don't need this, or the makeNegative call below.

[goldstein.w.n]

In D150093#4352283, @foad wrote:

Sorry I'm late.

Shoot, this has already been pushed.

Would you like me to create a follow up patch? (likewise for the udiv patch).

[foad]

In D150093#4353040, @goldstein.w.n wrote:

In D150093#4352283, @foad wrote:

Sorry I'm late.

Shoot, this has already been pushed.

Would you like me to create a follow up patch? (likewise for the udiv patch).

Sure, unless you think the changes are trivial enough not to need (pre-commit) review.

[foad]

In D150093#4353040, @goldstein.w.n wrote:

In D150093#4352283, @foad wrote:

Sorry I'm late.

Shoot, this has already been pushed.

Would you like me to create a follow up patch? (likewise for the udiv patch).

Just FYI, on matters of process:
https://llvm.org/docs/CodeReview.html#must-code-be-reviewed-prior-to-being-committed
https://llvm.org/docs/CodeReview.html#can-code-be-reviewed-after-it-is-committed

[goldstein.w.n]

In D150093#4353043, @foad wrote:

In D150093#4353040, @goldstein.w.n wrote:

In D150093#4352283, @foad wrote:

Sorry I'm late.

Shoot, this has already been pushed.

Would you like me to create a follow up patch? (likewise for the udiv patch).

Just FYI, on matters of process:
https://llvm.org/docs/CodeReview.html#must-code-be-reviewed-prior-to-being-committed
https://llvm.org/docs/CodeReview.html#can-code-be-reviewed-after-it-is-committed

Created D150921, D150922, and D150923 think addressed all your concerns except the ones explicitly commented there.

llvm/include/llvm/Support/KnownBits.h

static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS,
                        bool NoUndefSelfMultiply = false);
 
   /// Compute known bits from sign-extended multiply-hi.
   static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
 
   /// Compute known bits from zero-extended multiply-hi.
   static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
 
+  /// Compute known bits for sdiv(LHS, RHS).
+  static KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS,
+                        bool Exact = false);
+
   /// Compute known bits for udiv(LHS, RHS).
   static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
 
   /// Compute known bits for urem(LHS, RHS).
   static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
 
   /// Compute known bits for srem(LHS, RHS).
   static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);

llvm/lib/Support/KnownBits.cpp

KnownBits KnownBits::mulhu(const KnownBits &LHS, const KnownBits &RHS) {
   unsigned BitWidth = LHS.getBitWidth();
   assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
          !RHS.hasConflict() && "Operand mismatch");
   KnownBits WideLHS = LHS.zext(2 * BitWidth);
   KnownBits WideRHS = RHS.zext(2 * BitWidth);
   return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
 }
 
+KnownBits KnownBits::sdiv(const KnownBits &LHS, const KnownBits &RHS,
+                          bool Exact) {
+  // Equivilent of `udiv`. We must have caught this before it was folded.
+  if (LHS.isNonNegative() && RHS.isNonNegative())
+    return udiv(LHS, RHS);
+
+  unsigned BitWidth = LHS.getBitWidth();
+  assert(!LHS.hasConflict() && !RHS.hasConflict() && "Bad inputs");
+  KnownBits Known(BitWidth);
+
+  APInt Num, Denum;
+  // Positive -> true
+  // Negative -> false
+  // Unknown -> nullopt
+  std::optional<bool> ResultSign;
+  if (LHS.isNegative() && RHS.isNegative()) {
+    Denum = RHS.getSignedMaxValue();
+    Num = LHS.getSignedMinValue();
+    ResultSign = true;
+    // Result non-negative.
+  } else if (LHS.isNegative() && RHS.isStrictlyPositive()) {
+    // Result is non-negative if Exact OR -LHS u>= RHS.
+    if (Exact || (-LHS.getSignedMaxValue()).uge(RHS.getSignedMaxValue())) {
+      Denum = RHS.getSignedMinValue();
+      Num = LHS.getSignedMinValue();
+      ResultSign = false;
+    }
+  } else if (LHS.isStrictlyPositive() && RHS.isNegative()) {
+    // Result is non-negative if Exact OR LHS u>= -RHS.
+    if (Exact || LHS.getSignedMinValue().uge(-RHS.getSignedMinValue())) {
+      Denum = RHS.getSignedMaxValue();
+      Num = LHS.getSignedMaxValue();
+      ResultSign = false;
+    }
+  }
+
+  if (ResultSign) {
+    APInt Res = Num.sdiv(Denum);
+    if (*ResultSign) {
+      unsigned LeadZ = Res.countLeadingZeros();
+      Known.Zero.setHighBits(LeadZ);
+      Known.makeNonNegative();
+    } else {
+      unsigned LeadO = Res.countLeadingOnes();
+      Known.One.setHighBits(LeadO);
+      Known.makeNegative();
+    }
+  }
+
+  if (Exact) {
+    // Odd / Odd -> Odd
+    if (LHS.One[0] && RHS.One[0]) {
+      Known.Zero.clearBit(0);
+      Known.One.setBit(0);
+    }
+    // Even / Odd -> Even
+    else if (LHS.Zero[0] && RHS.One[0]) {
+      Known.One.clearBit(0);
+      Known.Zero.setBit(0);
+    }
+    // Odd / Even -> impossible
+    // Even / Even -> unknown
+  }
+
+  assert(!Known.hasConflict() && "Bad Output");
+  return Known;
+}
+
 KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS) {
   unsigned BitWidth = LHS.getBitWidth();
   assert(!LHS.hasConflict() && !RHS.hasConflict());
   KnownBits Known(BitWidth);
 
   // For the purposes of computing leading zeros we can conservatively
   // treat a udiv as a logical right shift by the power of 2 known to
   // be less than the denominator.

llvm/unittests/Support/KnownBitsTest.cpp

ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
       KnownBits KnownUMax(KnownAnd);
       KnownBits KnownUMin(KnownAnd);
       KnownBits KnownSMax(KnownAnd);
       KnownBits KnownSMin(KnownAnd);
       KnownBits KnownMul(KnownAnd);
       KnownBits KnownMulHS(KnownAnd);
       KnownBits KnownMulHU(KnownAnd);
       KnownBits KnownUDiv(KnownAnd);
+      KnownBits KnownSDiv(KnownAnd);
+      KnownBits KnownSDivExact(KnownAnd);
       KnownBits KnownURem(KnownAnd);
       KnownBits KnownSRem(KnownAnd);
       KnownBits KnownShl(KnownAnd);
       KnownBits KnownLShr(KnownAnd);
       KnownBits KnownAShr(KnownAnd);
 
       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
             Res = N1.udiv(N2);
             KnownUDiv.One &= Res;
             KnownUDiv.Zero &= ~Res;
 
             Res = N1.urem(N2);
             KnownURem.One &= Res;
             KnownURem.Zero &= ~Res;
 
+            // INT_MIN / -1 is UB.
+            if (!N1.isMinSignedValue() || !N2.isAllOnes()) {
               Res = N1.srem(N2);
               KnownSRem.One &= Res;
               KnownSRem.Zero &= ~Res;
+
+              Res = N1.sdiv(N2);
+              KnownSDiv.One &= Res;
+              KnownSDiv.Zero &= ~Res;
+
+              if (N1.srem(N2).isZero()) {
+                KnownSDivExact.One &= Res;
+                KnownSDivExact.Zero &= ~Res;
+              }
+            }
           }
 
           if (N2.ult(1ULL << N1.getBitWidth())) {
             Res = N1.shl(N2);
             KnownShl.One &= Res;
             KnownShl.Zero &= ~Res;
 
             Res = N1.lshr(N2);
ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
       KnownBits ComputedMulHU = KnownBits::mulhu(Known1, Known2);
       EXPECT_TRUE(ComputedMulHU.Zero.isSubsetOf(KnownMulHU.Zero));
       EXPECT_TRUE(ComputedMulHU.One.isSubsetOf(KnownMulHU.One));
 
       KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2);
       EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero));
       EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One));
 
+      KnownBits ComputedSDiv = KnownBits::sdiv(Known1, Known2, false);
+      EXPECT_TRUE(ComputedSDiv.Zero.isSubsetOf(KnownSDiv.Zero));
+      EXPECT_TRUE(ComputedSDiv.One.isSubsetOf(KnownSDiv.One));
+
+      KnownBits ComputedSDivExact = KnownBits::sdiv(Known1, Known2, true);
+      EXPECT_TRUE(ComputedSDivExact.Zero.isSubsetOf(KnownSDivExact.Zero));
+      EXPECT_TRUE(ComputedSDivExact.One.isSubsetOf(KnownSDivExact.One));
+
       KnownBits ComputedURem = KnownBits::urem(Known1, Known2);
       EXPECT_TRUE(ComputedURem.Zero.isSubsetOf(KnownURem.Zero));
       EXPECT_TRUE(ComputedURem.One.isSubsetOf(KnownURem.One));
 
       KnownBits ComputedSRem = KnownBits::srem(Known1, Known2);
       EXPECT_TRUE(ComputedSRem.Zero.isSubsetOf(KnownSRem.Zero));
       EXPECT_TRUE(ComputedSRem.One.isSubsetOf(KnownSRem.One));