[X86] Invert transforming `(x * (Pow2_Ceil(C1) - (1 << C0))) & C1` -> `(-x << C0...
authorNoah Goldstein <goldstein.w.n@gmail.com>
Sat, 13 May 2023 17:58:03 +0000 (12:58 -0500)
committerNoah Goldstein <goldstein.w.n@gmail.com>
Sat, 13 May 2023 19:35:57 +0000 (14:35 -0500)
commit6c3bf364bf95209925b1e884077ec79cca274dc7
treecdf0e5e7b70a6d9552648cf38c5ba1a7527ca332
parent36cfea5a98fd09e61f91937547c7796318f2c026
[X86] Invert transforming `(x * (Pow2_Ceil(C1) - (1 << C0))) & C1` -> `(-x << C0) & C1`

We can detect the case under the following circumstances:
Take `(Pow2_Ceil(C1) - (1 << C0))` as `C2`.
    1) `C2` is NOT a power of 2.
    2) `C2 + LeastSignificantBit(C2)` is a nonzero power of 2.
    3) `C2 u>= C1`

The motivation is the middle end transforms:
    `(-x << C0) & C1`
to
    `(x * (Pow2_Ceil(C1) - (1 << C2))) & C1`

As it saves IR instructions. On X86 the two instruction, `sub` and
`shl`, and better than the `mul` so we want to undo the transform.

This comes up when shifting a bit-mask by a byte-misalignment i.e:
    `y << ((-(uintptr)x * 8) & 63)`

Alive2 Proofs (including all cases with undefs in the vector):
https://alive2.llvm.org/ce/z/f-65b6

Reviewed By: RKSimon, pengfei

Differential Revision: https://reviews.llvm.org/D150294
llvm/lib/Target/X86/X86ISelLowering.cpp
llvm/test/CodeGen/X86/undo-mul-and.ll