[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

607–608

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();
+  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

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 KnownUDivExact(KnownAnd);
       KnownBits KnownSDiv(KnownAnd);
       KnownBits KnownSDivExact(KnownAnd);
       KnownBits KnownURem(KnownAnd);
       KnownBits KnownSRem(KnownAnd);
       KnownBits KnownShl(KnownAnd);
       KnownBits KnownLShr(KnownAnd);
       KnownBits KnownAShr(KnownAnd);
 
ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
           KnownMulHU.One &= Res;
           KnownMulHU.Zero &= ~Res;
 
           if (!N2.isZero()) {
             Res = N1.udiv(N2);
             KnownUDiv.One &= Res;
             KnownUDiv.Zero &= ~Res;
 
+            if (N1.urem(N2).isZero()) {
+              KnownUDivExact.One &= Res;
+              KnownUDivExact.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;
ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
       KnownBits ComputedMulHS = KnownBits::mulhs(Known1, Known2);
       EXPECT_TRUE(ComputedMulHS.Zero.isSubsetOf(KnownMulHS.Zero));
       EXPECT_TRUE(ComputedMulHS.One.isSubsetOf(KnownMulHS.One));
 
       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);
+      KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2, false);
       EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero));
       EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One));
 
+      KnownBits ComputedUDivExact = KnownBits::udiv(Known1, Known2, true);
+      EXPECT_TRUE(ComputedUDivExact.Zero.isSubsetOf(KnownUDivExact.Zero));
+      EXPECT_TRUE(ComputedUDivExact.One.isSubsetOf(KnownUDivExact.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));