[InstCombine] Add constant combines for `(urem/srem (mul X, Y), (mul X, Z))`
authorNoah Goldstein <goldstein.w.n@gmail.com>
Wed, 15 Mar 2023 21:53:13 +0000 (16:53 -0500)
committerNoah Goldstein <goldstein.w.n@gmail.com>
Thu, 16 Mar 2023 18:01:46 +0000 (13:01 -0500)
commitaba71f37d00cf0c2de0b0d0bd24a3467fe8d697f
tree94eb54711a3e93e9680ae22aff10980c2d6a5f80
parent994cd986f1a366632a16b5ee7408823dd5a8c031
[InstCombine] Add constant combines for `(urem/srem (mul X, Y), (mul X, Z))`

We can handle the following cases + some `nsw`/`nuw` flags:

`(srem (mul X, Y), (mul X, Z))`
    [If `srem(Y, Z) == 0`]
        -> 0
            - https://alive2.llvm.org/ce/z/PW4XZ-
    [If `srem(Y, Z) == Y`]
        -> `(mul nuw nsw X, Y)`
            - https://alive2.llvm.org/ce/z/DQe9Ek
        -> `(mul nsw X, Y)`
            - https://alive2.llvm.org/ce/z/Nr_MdH

    [If `Y`/`Z` are constant]
        -> `(mul/shl nuw nsw X, (srem Y, Z))`
            - https://alive2.llvm.org/ce/z/ccTFj2
            - https://alive2.llvm.org/ce/z/i_UQ5A
        -> `(mul/shl nsw X, (srem Y, Z))`
            - https://alive2.llvm.org/ce/z/mQKc63
            - https://alive2.llvm.org/ce/z/uERkKH

`(urem (mul X, Y), (mul X, Z))`
    [If `urem(Y, Z) == 0`]
        -> 0
            - https://alive2.llvm.org/ce/z/LL7UVR
    [If `srem(Y, Z) == Y`]
        -> `(mul nuw nsw X, Y)`
            - https://alive2.llvm.org/ce/z/9Kgs_i
        -> `(mul nuw X, Y)`
            - https://alive2.llvm.org/ce/z/ow9i8u

    [If `Y`/`Z` are constant]
        -> `(mul nuw nsw X, (srem Y, Z))`
            - https://alive2.llvm.org/ce/z/mNnQqJ
            - https://alive2.llvm.org/ce/z/Bj_DR-
            - https://alive2.llvm.org/ce/z/X6ZEtQ
        -> `(mul nuw X, (srem Y, Z))`
            - https://alive2.llvm.org/ce/z/SJYtUV

The rationale for doing this all in `InstCombine` rather than handling
the constant `mul` cases in `InstSimplify` is we often create a new
instruction because we are able to deduce more `nsw`/`nuw` flags than
the original instruction had.

Reviewed By: MattDevereau, sdesmalen

Differential Revision: https://reviews.llvm.org/D143014
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
llvm/test/Transforms/InstCombine/rem-mul-shl.ll