llvm / llvm/llvm-project

[ConstraintElim] Fails to prove a non-wrapping unsigned midpoint is below a shared upper bound

Open
#220,804 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 non-wrapping unsigned midpoint of two values is below their shared strict upper bound.

This leaves a redundant Rust slice bounds check after `usize::midpoint`.

### LLVM IR reproducer

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

define i1 @midpoint_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)

%sum = add nuw i64 %i, %j
%midpoint = lshr i64 %sum, 1

%result = icmp ult i64 %midpoint, %len
ret i1 %result
}
```

Run:

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

### Actual result

The final comparison remains:

```llvm
%result = icmp ult i64 %midpoint, %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
```

On every defined execution, `add nuw` establishes that the addition did not wrap. The assumptions establish:

```text
i < len
j < len
```

Therefore:

```text
floor((i + j) / 2) <= max(i, j) < len
```

### Rust motivation

```rust
#[no_mangle]
pub fn midpoint_index(slice: &[u8], i: usize, j: usize) -> u8 {
if i < slice.len() && j < slice.len() {
slice[i.midpoint(j)]
} else {
0
}
}
```

Optimized Rust nightly output still compares the midpoint against the slice length and retains a call to `panic_bounds_check`.

The equivalent `get_unchecked` version omits that second comparison.

### Related issues

#43003 and #100875 concern instruction selection and general code generation for `std::midpoint`.

#91527 concerns the different relation `x / 2 <= x - x / 2`.

None of these covers deriving an upper bound for an average from bounds on both operands.

Contributor guide

Open the contributing guide

Research direction

Start by running the supplied repro.ll command with opt -passes='default' and confirm that the final midpoint comparison remains. Read the ConstraintElim pass behavior, then compare it with the individually tested instsimplify, correlated-propagation, and instcombine passes. Done means the defined IR returns true without the redundant comparison and the Rust motivation no longer retains the extra bounds check.

Written by the indexing model from the issue text.

Assessment

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.