llvm / llvm/llvm-project

[ConstraintElim] Fails to prove unsigned absolute difference is below a shared upper bound

Open
#220,803 0 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.