[KnownBits] Factor out and improve the lowbit computation for {u,s}div

[goldstein.w.n]

Summary

There are some new cases if the division is exact:

1: If `TZ(LHS) == TZ(RHS)` then the result is always Odd
2: If `TZ(LHS) > TZ(RHS)` then the `TZ(LHS)-TZ(RHS)` bits of the
   result are zero.

Proofs: https://alive2.llvm.org/ce/z/3rAZqF

As well, return zero in known poison cases to be consistent rather
than just working about the bits we are changing.

[foad]

llvm/lib/Support/KnownBits.cpp

757

What does the comment mean? What are we skipping?

759

Seems weird to pass this in by const ref and then immediately copy it. Why not pass it in by value?

763–774

Can I suggest a slightly more unified way of handling both of these cases?

int MinTZ = (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();
int MaxTZ = (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();
if (MinTZ >= 0) {
  // Result has at least MinTZ trailing zeros.
  KnownOut.Zero.setLowBits(MinTZ);
  if (MinTZ == MaxTZ) { // might also need to check this is < BitWidth ???
    // Result has exactly MinTZ trailing zeros.
    KnownOut.One.setBit(MinTZ);
  }
}

840

Nit: could use intersectWith instead of passing in Known.

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

763–774

Can I suggest a slightly more unified way of handling both of these cases?

int MinTZ = (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();
int MaxTZ = (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();
if (MinTZ >= 0) {
  // Result has at least MinTZ trailing zeros.
  KnownOut.Zero.setLowBits(MinTZ);
  if (MinTZ == MaxTZ) { // might also need to check this is < BitWidth ???
    // Result has exactly MinTZ trailing zeros.
    KnownOut.One.setBit(MinTZ);
  }
}

Nice! Just need to add:

if (LHS.One[0])
  Known.One.setBit(0);

Because the rest of the logic relies on knowing LHS and RHS whereas LHS Odd alone is enough to imply the lowbit.

840

Not unionWith?
We need to check conflict as the tests test alot of poison values. I thought it would be cleaner (and less bugprone) to isolate that check to where its needed rather than put it in the common path which would be required if we made unionWith.

[goldstein.w.n]

Simplify + improve logic (thanks foad)

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[nikic]

LGTM

[chapuni]

I am still investigating, though, is this intended as NFC?

llvm/lib/Support/KnownBits.cpp

869

Is it a compatible change?

[nikic]

In D150923#4403054, @chapuni wrote:

I am still investigating, though, is this intended as NFC?

No, this change is not NFC.

[chapuni]

FYI, I met different behavior between amd64-ubuntu and aarch64-ubuntu. Not sure if this triggers.

[goldstein.w.n]

In D150923#4403093, @chapuni wrote:

FYI, I met different behavior between amd64-ubuntu and aarch64-ubuntu. Not sure if this triggers.

Are you seeing a failure potentially as a result of this? If so can you link? Do you want me to revert?

[goldstein.w.n]

llvm/lib/Support/KnownBits.cpp

869

What do you mean by compatible? This change should allow us to compute more low bits than before if that's what you're asking.

[chapuni]

@goldstein.w.n
I am sorry. As far as I have been investigating, this is not the cause but 1st commit to trigger. The failure was hidden when I added debug codes, heisenbug.
The failure can be seen in my internal builders.

The failure is;

• Observable for targeting aarch64. PerfReader.cpp sometimes differs.
• I have not seen for targeting x86-64.
• I have seen for targeting aarch64, on aarch64-linux and cross on x86_64-linux.
  • Differs between aarh64-host and x86_64-host (for targeting aarch64)
  • Differs between stage2 and stage3 on aarch64-linux.

[goldstein.w.n]

In D150923#4405744, @chapuni wrote:

@goldstein.w.n
I am sorry. As far as I have been investigating, this is not the cause but 1st commit to trigger. The failure was hidden when I added debug codes, heisenbug.
The failure can be seen in my internal builders.

The failure is;

• Observable for targeting aarch64. PerfReader.cpp sometimes differs.
• I have not seen for targeting x86-64.
• I have seen for targeting aarch64, on aarch64-linux and cross on x86_64-linux.
  • Differs between aarh64-host and x86_64-host (for targeting aarch64)
  • Differs between stage2 and stage3 on aarch64-linux.

I see, so probably some misuse of knownbits in the aarch64 backend? Are you sure its this exact commit and not the prior one? Also it might be an incorrect "exact" flag on a division.

[chapuni]

@goldstein.w.n I found the issue was due to D141712 and fixed (not by me) in rG282324aa4a6c29d5ce31c66f8def15d9bd8e84e4
Sorry for the noise.

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);
 }
 
+static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS,
+                                  const KnownBits &RHS, bool Exact) {
+
+  if (!Exact)
+    return Known;
+
+  // If LHS is Odd, the result is Odd no matter what.
+  // Odd / Odd -> Odd
+  // Odd / Even -> Impossible (because its exact division)
+  if (LHS.One[0])
+    Known.One.setBit(0);
+
+  int MinTZ =
+      (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();
+  int MaxTZ =
+      (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();
+  if (MinTZ >= 0) {
+    // Result has at least MinTZ trailing zeros.
+    Known.Zero.setLowBits(MinTZ);
+    if (MinTZ == MaxTZ) {
+      // Result has exactly MinTZ trailing zeros.
+      Known.One.setBit(MinTZ);
+    }
+  } else if (MaxTZ < 0) {
+    // Poison Result
+    Known.setAllZero();
+  }
+
+  // In the KnownBits exhaustive tests, we have poison inputs for exact values
+  // a LOT. If we have a conflict, just return all zeros.
+  if (Known.hasConflict())
+    Known.setAllZero();
+
+  return Known;
+}
+
 KnownBits KnownBits::sdiv(const KnownBits &LHS, const KnownBits &RHS,
                           bool Exact) {
   // 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");
if (Res->isNonNegative()) {
       unsigned LeadZ = Res->countLeadingZeros();
       Known.Zero.setHighBits(LeadZ);
     } else {
       unsigned LeadO = Res->countLeadingOnes();
       Known.One.setHighBits(LeadO);
     }
   }
 
-  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
-  }
+  Known = divComputeLowBit(Known, LHS, RHS, Exact);
 
   assert(!Known.hasConflict() && "Bad Output");
   return Known;
 }
 
 KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,
                           bool Exact) {
   unsigned BitWidth = LHS.getBitWidth();
KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,
   // gets larger, the number of upper zero bits increases.
   APInt MinDenom = RHS.getMinValue();
   APInt MaxNum = LHS.getMaxValue();
   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]) {
-      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
-  }
+  Known = divComputeLowBit(Known, LHS, RHS, Exact);
 
   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]) {