[InstCombine] Fold equality with self-dependent select to constant set membership
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
## Description
InstCombine appears to miss:
```text
X == select(X >s 0, C1, C2)
->
(X == C1) || (X == C2)
```
when C1 >s 0 and C2 <=s 0.
Example:
```llvm
define i1 @src(i32 %x) {
%cond = icmp sgt i32 %x, 0
%s = select i1 %cond, i32 2, i32 0
%r = icmp eq i32 %x, %s
ret i1 %r
}
define i1 @tgt(i32 %x) {
%a = icmp eq i32 %x, 0
%b = icmp eq i32 %x, 2
%r = or i1 %a, %b
ret i1 %r
}
```
Alive2: https://alive2.llvm.org/ce/z/LMpt7A
Generalized Alive2 proof: https://alive2.llvm.org/ce/z/ZMrWVm
The source is true exactly for X = 0 or X = 2, so the select can be replaced by a constant set-membership check.
Contributor guide
Research direction
Start in the InstCombine implementation and inspect how equality comparisons involving a self-dependent select are handled. Use the provided @src and @tgt LLVM IR examples and the Alive2 proofs to validate the transformation; done means the source folds to the constant set-membership form for the stated signed conditions.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100