[KnownBits] Improve `KnownBits::udiv`

[goldstein.w.n]

Summary

We can more precisely determine the upper bits doing `MaxNum /
MinDenum` as opposed to only using the MSB.

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

[RKSimon]

LGTM with a couple of minors

llvm/lib/Support/KnownBits.cpp

604–605

Update comment?

616

Indentation

[goldstein.w.n]

Rebase

[goldstein.w.n]

Fix comments

[goldstein.w.n]

Rebase

[foad]

llvm/lib/Support/KnownBits.cpp

614–626

Common this up with the identical logic in sdiv?

llvm/include/llvm/Support/KnownBits.h

public:
   /// 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);
+  static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS,
+                        bool Exact = false);
 
   /// 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);
 
   /// Compute known bits for umax(LHS, RHS).

llvm/lib/Support/KnownBits.cpp

KnownBits KnownBits::mulhu(const KnownBits &LHS, const KnownBits &RHS) {
   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);
+    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
if (Exact) {
     // Odd / Even -> impossible
     // Even / Even -> unknown
   }
 
   assert(!Known.hasConflict() && "Bad Output");
   return Known;
 }
 
-KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS) {
+KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,
+                          bool Exact) {
   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.
-  unsigned LeadZ = LHS.countMinLeadingZeros();
-  unsigned RHSMaxLeadingZeros = RHS.countMaxLeadingZeros();
+  // 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 MaxNum = LHS.getMaxValue();
+  APInt MaxRes = MinDenum.isZero() ? MaxNum : MaxNum.udiv(MinDenum);
 
-  if (RHSMaxLeadingZeros != BitWidth)
-    LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSMaxLeadingZeros - 1);
+  unsigned LeadZ = MaxRes.countLeadingZeros();
 
   Known.Zero.setHighBits(LeadZ);
+  if (Exact) {
+    // Odd / Odd -> Odd
+    if (LHS.One[0] && RHS.One[0])
+      Known.One.setBit(0);
+    // Even / Odd -> Even
+    else if (LHS.Zero[0] && RHS.One[0])
+      Known.Zero.setBit(0);
+    // Odd / Even -> impossible
+    // Even / Even -> unknown
+  }
+
   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();
     APInt Mask = APInt::getLowBitsSet(BitWidth, RHSZeros);

llvm/test/Analysis/ValueTracking/knownbits-div.ll

;
   %div = sdiv exact i8 %num, %denum
   %and = and i8 %div, 1
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @udiv_high_bits(i8 %x, i8 %y) {
 ; CHECK-LABEL: @udiv_high_bits(
-; CHECK-NEXT:    [[NUM:%.*]] = and i8 [[X:%.*]], -127
-; CHECK-NEXT:    [[DENUM:%.*]] = or i8 [[Y:%.*]], 31
-; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[NUM]], [[DENUM]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[DIV]], 8
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 8
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %num = and i8 %x, 129
   %denum = or i8 %y, 31
   %div = udiv i8 %num, %denum
   %and = and i8 %div, 8
   %r = icmp eq i8 %and, 8
   ret i1 %r
 }

llvm/unittests/Support/KnownBitsTest.cpp

testBinaryOpExhaustive(
       [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
         if (N2.isZero())
           return std::nullopt;
         return N1.udiv(N2);
       },
       checkCorrectnessOnlyBinary);
   testBinaryOpExhaustive(
       [](const KnownBits &Known1, const KnownBits &Known2) {
+        return KnownBits::udiv(Known1, Known2, /*Exact*/ true);
+      },
+      [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
+        if (N2.isZero() || !N1.urem(N2).isZero())
+          return std::nullopt;
+        return N1.udiv(N2);
+      },
+      checkCorrectnessOnlyBinary);
+  testBinaryOpExhaustive(
+      [](const KnownBits &Known1, const KnownBits &Known2) {
         return KnownBits::sdiv(Known1, Known2);
       },
       [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
         if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes()))
           return std::nullopt;
         return N1.sdiv(N2);
       },
       checkCorrectnessOnlyBinary);