[ConstraintElim] Fails to prove unsigned absolute difference is below a shared upper bound
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
### Summary
LLVM fails to prove that the unsigned absolute difference of two values is below a shared strict upper bound.
This leaves a redundant bounds check and panic path in optimized Rust code using `usize::abs_diff`.
### LLVM IR reproducer
```llvm
declare void @llvm.assume(i1 noundef)
define i1 @abs_diff_is_in_bounds(i64 %i, i64 %j, i64 %len) {
entry:
%i.in.bounds = icmp ult i64 %i, %len
call void @llvm.assume(i1 %i.in.bounds)
%j.in.bounds = icmp ult i64 %j, %len
call void @llvm.assume(i1 %j.in.bounds)
%i.lt.j = icmp ult i64 %i, %j
%j.minus.i = sub nuw i64 %j, %i
%i.minus.j = sub nuw i64 %i, %j
%diff = select i1 %i.lt.j, i64 %j.minus.i, i64 %i.minus.j
%result = icmp ult i64 %diff, %len
ret i1 %result
}
```
Run:
```console
$ opt -passes='default' -S repro.ll -o -
```
### Actual result
The final comparison remains:
```llvm
%result = icmp ult i64 %diff, %len
ret i1 %result
```
This reproduces with LLVM 23.1.0, current Compiler Explorer `opt (trunk)`, and `opt (assertions trunk)` as of 2026-09-03.
I also tested `constraint-elimination`, `instsimplify`, `correlated-propagation`, and `instcombine` individually; none proves the comparison.
### Expected result
```llvm
ret i1 true
```
The assumptions establish:
```text
i < len
j < len
```
The selected value is the unsigned absolute difference, so:
```text
abs_diff(i, j) <= max(i, j) < len
```
One of the two `sub nuw` instructions may produce poison, but only when it is the unselected operand. On every defined execution, the selected subtraction is the non-underflowing one.
### Rust motivation
```rust
#[no_mangle]
pub fn abs_diff_index(slice: &[u8], i: usize, j: usize) -> u8 {
if i < slice.len() && j < slice.len() {
slice[i.abs_diff(j)]
} else {
0
}
}
```
Optimized Rust nightly output still compares the absolute difference against the slice length and retains a call to `panic_bounds_check`.
The equivalent `get_unchecked` version does not require that second comparison.
### Related issue
#59894 concerns recognizing `sub(max(x, y), min(x, y))` as an absolute-difference SelectionDAG node.
That is distinct from proving a range relation from two values sharing an upper bound.
Contributor guide
Research direction
Start by running the provided opt -passes='default' command on the LLVM IR reproducer and inspect constraint-elimination, instsimplify, correlated-propagation, and instcombine individually. Done means the final comparison folds to ret i1 true and the Rust abs_diff_index example no longer retains the redundant bounds check or panic path.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100