[InstSimplify] Fails to fold llvm.ctpop(x) <= x, leaving redundant bounds checks
- 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
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