[InstCombine] Suboptimal lowering for monotonic power-of-two eq/ne chains
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
LLVM seems to miss a compact branchless lowering for a predicate that rejects a small set of powers of two.
Quite typical example:
```rust
#[unsafe(no_mangle)]
pub fn src(bw: u32) -> bool {
bw != 8 && bw != 16 && bw != 32 && bw != 64 && bw != 128 && bw != 256 // .. && bw !- N ^ 2
}
```
or
```rust
#[unsafe(no_mangle)]
pub fn src(bw: u32) -> bool {
bw == 8 || bw == 16 || bw == 32 // ... || bw == N ^ 2
}
```
Current compiles to
```asm
lea eax, [rdi - 1]
mov ecx, edi
xor ecx, eax
cmp ecx, eax
jbe .LBB1_3
rep bsf eax, edi
add eax, -3
cmp eax, 5
jae .LBB1_3
xor eax, eax
ret
.LBB1_3:
cmp edi, 256
setne al
ret
```
But I expected:
```asm
lea eax, [rdi - 8]
cmp eax, 249
setae al
lea ecx, [rdi - 1]
test ecx, edi
setne cl
or al, cl
ret
```
Why this is valid?
```rust
bw != 8 && bw != 16 && bw != 32 && bw != 64 && bw != 128 && bw != 256
```
can be expressed as:
```rust
bw є [8, 256] || !bw.is_pow_of_2_non_zero(x) // or bw.is_pow_of_2 if bw є [0, ..)
```
which in unsigned integer arithmetic becomes:
```rust
(bw - 8 >u 256 - 8) || ((bw & (bw - 1)) != 0)
```
rust eqivalent:
```rust
#[unsafe(no_mangle)]
pub fn dst(bw: u32) -> bool {
let out_of_range = bw.wrapping_sub(8) > 256 - 8;
let not_power_of_two_nz = (bw & bw.wrapping_sub(1)) != 0;
out_of_range | not_power_of_two_nz
}
```
Godbolt example: https://godbolt.org/z/5hhqe5n8s
alivee2 proof: https://alive2.llvm.org/ce/z/FBgYiS
Contributor guide
Research direction
Start in LLVM's InstCombine area and reproduce the reported power-of-two equality-chain cases from the Rust examples, using the Godbolt output and Alive2 proof as references. Investigate how these predicates are currently lowered and define completion as a compact branchless lowering that preserves the demonstrated semantics.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100