[KnownBits] Cleanup some misspelling / logic in {u,s}div

[goldstein.w.n]

Summary

Chronically misspelled 'denominator' as 'denuminator' and a few other
cases.

On the logic side, no longer require RHS to be strictly positive in
sdiv. This in turn means we need to handle a possible zero denom
in the APInt division.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

578

@foad, re:

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".

Since Denom now can be zero (result of not using strictlypositive), we can't just grab the sign from the result so keeping as optional bool

578–579

@foad, re:

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

Needed for the same reason as above.

[foad]

llvm/lib/Support/KnownBits.cpp

578

I think you can copy what you do in udiv - if the min value of denom is 0, treat it as 1 (since if the value was really 0, the result would be poison).

[goldstein.w.n]

Remove unneeded sign logic

[goldstein.w.n]

Rebase

[nikic]

llvm/lib/Support/KnownBits.cpp

632–633

I expect either this check should be dropped, or we don't need the clearBits above.

[goldstein.w.n]

Remove unneeded conflict check

[nikic]

LGTM

llvm/lib/Support/KnownBits.cpp

 //===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
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.
+  // Equivalent of `udiv`. We must have caught this before it was folded.
   if (LHS.isNonNegative() && RHS.isNonNegative())
     return udiv(LHS, RHS, Exact);
 
   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;
+  std::optional<APInt> Res;
   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.
+    APInt Denom = RHS.getSignedMaxValue();
+    APInt Num = LHS.getSignedMinValue();
+    // INT_MIN/-1 would be a poison result (impossible). Estimate the division
+    // as signed max (we will only set sign bit in the result).
+    Res = (Num.isMinSignedValue() && Denom.isAllOnes())
+              ? APInt::getSignedMaxValue(BitWidth)
+              : Num.sdiv(Denom);
+  } else if (LHS.isNegative() && RHS.isNonNegative()) {
+    // Result is negative if Exact OR -LHS u>= RHS.
     if (Exact || (-LHS.getSignedMaxValue()).uge(RHS.getSignedMaxValue())) {
-      Denum = RHS.getSignedMinValue();
-      Num = LHS.getSignedMinValue();
-      ResultSign = false;
+      APInt Denom = RHS.getSignedMinValue();
+      APInt Num = LHS.getSignedMinValue();
+      Res = Denom.isZero() ? Num : Num.sdiv(Denom);
     }
   } else if (LHS.isStrictlyPositive() && RHS.isNegative()) {
-    // Result is non-negative if Exact OR LHS u>= -RHS.
+    // Result is negative if Exact OR LHS u>= -RHS.
     if (Exact || LHS.getSignedMinValue().uge(-RHS.getSignedMinValue())) {
-      Denum = RHS.getSignedMaxValue();
-      Num = LHS.getSignedMaxValue();
-      ResultSign = false;
+      APInt Denom = RHS.getSignedMaxValue();
+      APInt Num = LHS.getSignedMaxValue();
+      Res = Num.sdiv(Denom);
     }
   }
 
-  if (ResultSign) {
-    APInt Res = Num.sdiv(Denum);
-    if (*ResultSign) {
-      unsigned LeadZ = Res.countLeadingZeros();
+  if (Res) {
+    if (Res->isNonNegative()) {
+      unsigned LeadZ = Res->countLeadingZeros();
       Known.Zero.setHighBits(LeadZ);
-      Known.makeNonNegative();
     } else {
-      unsigned LeadO = Res.countLeadingOnes();
+      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);
KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,
                           bool Exact) {
   unsigned BitWidth = LHS.getBitWidth();
   assert(!LHS.hasConflict() && !RHS.hasConflict());
   KnownBits Known(BitWidth);
 
   // We can figure out the minimum number of upper zero bits by doing
   // MaxNumerator / MinDenominator. If the Numerator gets smaller or Denominator
   // gets larger, the number of upper zero bits increases.
-  APInt MinDenum = RHS.getMinValue();
+  APInt MinDenom = RHS.getMinValue();
   APInt MaxNum = LHS.getMaxValue();
-  APInt MaxRes = MinDenum.isZero() ? MaxNum : MaxNum.udiv(MinDenum);
+  APInt MaxRes = MinDenom.isZero() ? MaxNum : MaxNum.udiv(MinDenom);
 
   unsigned LeadZ = MaxRes.countLeadingZeros();
 
   Known.Zero.setHighBits(LeadZ);
   if (Exact) {
     // Odd / Odd -> Odd
-    if (LHS.One[0] && RHS.One[0])
+    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])
+    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::remGetLowBits(const KnownBits &LHS, const KnownBits &RHS) {
   unsigned BitWidth = LHS.getBitWidth();
   if (!RHS.isZero() && RHS.Zero[0]) {
     // rem X, Y where Y[0:N] is zero will preserve X[0:N] in the result.
     unsigned RHSZeros = RHS.countMinTrailingZeros();