llvm / llvm/llvm-project

[InstCombine] Suboptimal lowering for monotonic power-of-two eq/ne chains

Open
#195,880 1 comment 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

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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.