[InstCombine] generalize select + select/and/or folding using implied conditions
authorJuneyoung Lee <aqjune@gmail.com>
Sun, 2 May 2021 11:07:25 +0000 (20:07 +0900)
committerJuneyoung Lee <aqjune@gmail.com>
Tue, 4 May 2021 00:42:06 +0000 (09:42 +0900)
commit24ce194cfe493bb743c288ed049fcd86c37aace2
treea722a4500561f5d57df92ae5bce6283d941ea6f0
parent012f01e227eeb071dbce270aa36745fd6ca95af5
[InstCombine] generalize select + select/and/or folding using implied conditions

This patch optimizes the remaining possible cases in D101191 by generalizing isImpliedCondition()-based
foldings.

Assume that there is `op a, (select b, _, _)` where op is one of `and i1`, `or i1` or their select forms.

We can do the following optimization based on the result of `isImpliedCondition(a, b)`:

If a = true implies…
- b = true:
    - select a, (select b, A, B), false => select a, A, false : https://alive2.llvm.org/ce/z/WCnZYh
    - and a, (select b, A, B) => select a, A, false : https://alive2.llvm.org/ce/z/uZhcMG
- b = false:
    - select a, (select b, A, B), false => select a, B, false : https://alive2.llvm.org/ce/z/c2hJpV
    - and a, (select b, A, B) => select a, B, false : https://alive2.llvm.org/ce/z/5ggwMM

If a = false implies…
- b = true:
    - select a, true, (select b, A, B) => select a, true, A : https://alive2.llvm.org/ce/z/tidKvH
    - or a, (select b, A, B) =>  select a, true, A : https://alive2.llvm.org/ce/z/cC-uyb
- b = false:
    - select a, true, (select b, A, B) => select a, true, B : https://alive2.llvm.org/ce/z/ZXpJq9
    - or a, (select b, A, B) => select a, true, B : https://alive2.llvm.org/ce/z/hnDrJj

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D101720
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
llvm/lib/Transforms/InstCombine/InstCombineInternal.h
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll
llvm/test/Transforms/InstCombine/select-safe-impliedcond-transforms.ll