[InstCombine] Add transform `(icmp pred (shl {nsw and/or nuw} X, Y), C)` -> `(icmp...
authorNoah Goldstein <goldstein.w.n@gmail.com>
Mon, 5 Jun 2023 07:37:08 +0000 (02:37 -0500)
committerNoah Goldstein <goldstein.w.n@gmail.com>
Mon, 5 Jun 2023 18:01:03 +0000 (13:01 -0500)
commit73ce343125c5c86373ac3f883932f4ddbc2d307a
treeb2c9a9017ab6859ff1a890e142c3d79975684d09
parente8e8528085ebdb2fb4395f07abdf6bcaf0348630
[InstCombine] Add transform `(icmp pred (shl {nsw and/or nuw} X, Y), C)` -> `(icmp pred X, C)`

Three new transforms:
    1) `(icmp pred (shl nsw nuw X, Y), C)` [if `C <= 0`] -> `(icmp pred X, C)`
        - ugt: https://alive2.llvm.org/ce/z/K_57J_
        - sgt: https://alive2.llvm.org/ce/z/BL8u_a
        - sge: https://alive2.llvm.org/ce/z/yZZVYz
        - uge: https://alive2.llvm.org/ce/z/R4jwwJ
        - ule: https://alive2.llvm.org/ce/z/-gbmth
        - sle: https://alive2.llvm.org/ce/z/ycZVsh
        - slt: https://alive2.llvm.org/ce/z/4MzHYm
        - sle: https://alive2.llvm.org/ce/z/fgNfex
        - ult: https://alive2.llvm.org/ce/z/cXfvH5
        - eq : https://alive2.llvm.org/ce/z/sZh_Ti
        - ne : https://alive2.llvm.org/ce/z/UrqSWA

    2) `(icmp eq/ne (shl {nsw|nuw} X, Y), 0)` -> `(icmp eq/ne X, 0)`
        - eq+nsw: https://alive2.llvm.org/ce/z/aSJN6D
        - eq+nuw: https://alive2.llvm.org/ce/z/r2_-br
        - ne+nuw: https://alive2.llvm.org/ce/z/RkETtu
        - ne+nsw: https://alive2.llvm.org/ce/z/8iSfW3

    3) `(icmp slt (shl nsw X, Y), 0/1)` -> `(icmp pred X, 0/1)`
       `(icmp sgt (shl nsw X, Y), 0/-1)` -> `(icmp pred X, 0/-1)`
        - slt: https://alive2.llvm.org/ce/z/eZYRan
        - sgt: https://alive2.llvm.org/ce/z/QQeP26

    Transform 3) is really sle/slt/sge/sgt with 0, but sle/sge
    canonicalize to slt/sgt respectively so its implemented as such.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D145341
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
llvm/test/Transforms/InstCombine/icmp-shl.ll