[ValueTracking] deduce `X * Y != 0` if `LowestKnownBit(X) * LowestKnownBit(Y) != 0`

For `X * Y`, if there exists a subset of `X` and subset of `Y` s.t `sX * sY != 0`,
then `X * Y != 0`.
    - See first proof: https://alive2.llvm.org/ce/z/28C9CG
    - NB: This is why the previous Odd case works.

In knownbits we could exhaustively hunt for such a subset, but
`LSB(X)` and `LSB(Y)` actually works. If `LSB(X) * LSB(Y) != 0`, then
`X * Y != 0`
    - See proof: https://alive2.llvm.org/ce/z/p5wWid

In `isKnownNonZero` we can use this as if the `LowestKnownOne(X) *
LowestKnownOne(Y) != 0`, then `X * Y != 0`, and we don't need to try
and other subsets.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D150425

1 files changed, 7 insertions, 1 deletions

diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index 1085be6..2862e42 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -2884,7 +2884,13 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth,
       return XKnown.isNonZero() ||
              isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q);
 
-    return KnownBits::mul(XKnown, YKnown).isNonZero();
+    // If there exists any subset of X (sX) and subset of Y (sY) s.t sX * sY is
+    // non-zero, then X * Y is non-zero. We can find sX and sY by just taking
+    // the the lowest known One of X and Y. If they are non-zero, the result
+    // must be non-zero. We can check if LSB(X) * LSB(Y) != 0 by doing
+    // X.CountLeadingZeros + Y.CountLeadingZeros < BitWidth.
+    return (XKnown.countMaxTrailingZeros() + YKnown.countMaxTrailingZeros()) <
+           BitWidth;
   }
   case Instruction::Select:
     // (C ? X : Y) != 0 if X != 0 and Y != 0.