[InstCombine] Fix buggy `(mul X, Y)` -> `(shl X, Log2(Y))` transform PR62175
authorNoah Goldstein <goldstein.w.n@gmail.com>
Tue, 18 Apr 2023 21:34:02 +0000 (16:34 -0500)
committerNoah Goldstein <goldstein.w.n@gmail.com>
Tue, 18 Apr 2023 22:17:48 +0000 (17:17 -0500)
commitbfe2f5d38bb14bf7ce4f44d3de558fbc076bdc1a
treee440b9cee4d87d6b0a3870016e36398b59e7dc1f
parentd771f54107c4889cde449d2bf5ba13d193017716
[InstCombine] Fix buggy `(mul X, Y)` -> `(shl X, Log2(Y))` transform PR62175

Bug was because we recognized patterns like `(shl 4, Z)` as a power of
2 we could take Log2 of (`2 + Z`), but doing `(shl X, (2 + Z))` can
cause a poison shift.
    https://alive2.llvm.org/ce/z/yuJm_k

The fix is to verify that `Log2(Y)` will be a non-poisonous shift
amount. We can do this with:
    `nsw` flag:
        - https://alive2.llvm.org/ce/z/yyyJBr
        - https://alive2.llvm.org/ce/z/YgubD_
    `nuw` flag:
        - https://alive2.llvm.org/ce/z/-4mpyV
        - https://alive2.llvm.org/ce/z/a6ik6r
    Prove `Y != 0`:
        - https://alive2.llvm.org/ce/z/ced4su
        - https://alive2.llvm.org/ce/z/X-JJHb

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D148609
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
llvm/test/Transforms/InstCombine/div-shift.ll
llvm/test/Transforms/InstCombine/mul-pow2.ll