[KnownBits] Factor out and improve the lowbit computation for {u,s}div
authorNoah Goldstein <goldstein.w.n@gmail.com>
Tue, 6 Jun 2023 19:06:39 +0000 (14:06 -0500)
committerNoah Goldstein <goldstein.w.n@gmail.com>
Tue, 6 Jun 2023 20:14:10 +0000 (15:14 -0500)
commit85378b7663763e6639123088aa8a82289c62ca0e
tree96f966856a3e43b388c4f5e9f02e824d037b670f
parent809b1d834dfc59575be228cfbccb95b10c2c34e2
[KnownBits] Factor out and improve the lowbit computation for {u,s}div

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.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D150923
llvm/lib/Support/KnownBits.cpp