llvm / llvm/llvm-project

[InstCombine] Fold equality with self-dependent select to constant set membership

Open
#223,249 0 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.