llvm / llvm/llvm-project

[InstSimplify] Fails to fold llvm.ctpop(x) <= x, leaving redundant bounds checks

Open
#220,800 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

### Summary

LLVM does not fold the scalar invariant `llvm.ctpop(x) <= x` for unsigned integers. This also prevents transitive range proofs such as:

```text
x < len
ctpop(x) <= x
----------------
ctpop(x) < len
```

In Rust, this leaves a redundant slice bounds comparison and panic path when `count_ones()` is used as an index after the original integer has already been checked against the slice length.

### Minimal LLVM IR reproducer

```llvm
declare i64 @llvm.ctpop.i64(i64)

define i1 @ctpop_le_input(i64 %x) {
entry:
%count = call i64 @llvm.ctpop.i64(i64 %x)
%result = icmp ule i64 %count, %x
ret i1 %result
}
```

Run:

```console
$ opt -passes='default' -S repro.ll -o -
```

The comparison remains:

```llvm
define i1 @ctpop_le_input(i64 %x) local_unnamed_addr {
entry:
%count = tail call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 %x)
%result = icmp ule i64 %count, %x
ret i1 %result
}
```

I also tested `instsimplify`, `constraint-elimination`, `correlated-propagation`, and `instcombine` individually. The comparison remains with LLVM 22.1.0, LLVM 23.1.0, current Compiler Explorer `opt (trunk)`, and `opt (assertions trunk)` as of 2026-09-03.

### Expected result

```llvm
ret i1 true
```

If `x` contains `k` set bits, then `x` is the sum of `k` distinct non-negative powers of two. Every set bit contributes at least one, so `x >= k = ctpop(x)`. This also holds for `x == 0`.

### Bounds-check consequence

This extended reproducer also remains unfolded:

```llvm
declare void @llvm.assume(i1 noundef)
declare i64 @llvm.ctpop.i64(i64)

define i1 @ctpop_below_bound(i64 %x, i64 %len) {
entry:
%x.in.bounds = icmp ult i64 %x, %len
call void @llvm.assume(i1 %x.in.bounds)

%count = call i64 @llvm.ctpop.i64(i64 %x)
%result = icmp ult i64 %count, %len
ret i1 %result
}
```

A motivating Rust example is:

```rust
#[no_mangle]
pub fn popcount_index(slice: &[u8], x: usize) -> u8 {
if x < slice.len() {
slice[x.count_ones() as usize]
} else {
0
}
}
```

On x86-64, optimized Rust nightly output first checks `x < len`, but then still compares the popcount result against `len` and keeps the panic path:

```asm
cmp rdx, rsi
jae .Loutside
# compute popcount into rax
cmp rax, rsi
jae .Lpanic_bounds_check
movzx eax, byte ptr [rdi + rax]
```

The equivalent `get_unchecked` version omits the second comparison and panic path.

### Related issue

#210673 is related but appears distinct. It concerns deriving the constant bound `ctpop(x) <= 8` from `x < 256` after SimplifyCFG converts control flow to a select.

This report concerns the operand-relative invariant `ctpop(x) <= x`; even the direct comparison in the minimal reproducer is not folded.

Contributor guide

Open the contributing guide

Research direction

Start by running the minimal reproducer with opt and inspect the named InstSimplify, constraint-elimination, CorrelatedPropagation, and InstCombine passes. The change is complete when the direct ctpop comparison folds to ret i1 true and the extended example can use the assumed x < len to prove ctpop(x) < len without the redundant check.

Written by the indexing model from the issue text.

Assessment

Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.