[ValueTracking] deduce `X * Y != 0` if `LowestKnownBit(X) * LowestKnownBit(Y) != 0`
authorNoah Goldstein <goldstein.w.n@gmail.com>
Tue, 16 May 2023 15:37:45 +0000 (10:37 -0500)
committerNoah Goldstein <goldstein.w.n@gmail.com>
Tue, 16 May 2023 23:58:12 +0000 (18:58 -0500)
commit774ecc20e121e238099ef5ef8efad3ed062a4ae5
treef4012369a0bdf5c90e6c6a9b487953da8e4b54f1
parent7f82f108c2ec08636224dd0b58fe7e9021852002
[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
llvm/lib/Analysis/ValueTracking.cpp
llvm/test/Analysis/ValueTracking/known-non-zero.ll