llvm / llvm/llvm-project

[ConstraintElim] Fails to transfer a truncated unsigned upper bound across zext

Open
#220,805 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 infer that a comparison against the truncated low bits of a wider value also establishes a safe bound against the original wider value after zero extension.

This leaves a redundant bounds check when Rust compares a `u32` index with `slice.len() as u32` and then indexes the slice using the zero-extended index.

### LLVM IR reproducer

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

define i1 @truncated_bound_implies_wide_bound(i32 %i, i64 %len) {
entry:
%truncated.len = trunc i64 %len to i32
%narrow.check = icmp ult i32 %i, %truncated.len
call void @llvm.assume(i1 %narrow.check)

%wide.i = zext i32 %i to i64
%result = icmp ult i64 %wide.i, %len
ret i1 %result
}
```

Run:

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

### Actual result

The final comparison remains. InstCombine canonicalizes it but does not fold it:

```llvm
%wide.i = zext i32 %i to i64
%result = icmp ugt i64 %len, %wide.i
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
```

For unsigned integers, zero-extending the low 32 bits of `len` cannot produce a value greater than `len`:

```text
zext(trunc(len)) <= len
```

The assumption establishes:

```text
i < trunc(len)
```

Because `wide.i` is the zero extension of `i`, it follows that:

```text
wide.i < zext(trunc(len)) <= len
```

Therefore, `wide.i < len`.

### Rust motivation

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

Optimized Rust nightly output retains both:

1. The narrow comparison between `i` and the truncated slice length.
2. A second wide comparison before the load, including the panic path.

The truncating guard can conservatively reject valid indices when the slice length exceeds `u32::MAX`, but it cannot admit an out-of-bounds index. The second check is therefore redundant.

### Related issue

#143778 concerns an unnecessary mask introduced when zero-extending the truncation of the same input value under a constant range assumption.

This report instead concerns transferring a dynamic upper-bound relation from:

```text
i < trunc(len)
```

to:

```text
zext(i) < len
```

Contributor guide

Open the contributing guide

Research direction

Start with the LLVM IR reproducer and run opt with the default O3 pipeline, then compare the individual constraint-elimination, instsimplify, correlated-propagation, and instcombine passes described in the issue. Trace how the assumption i < trunc(len) is handled across zext; done means the final comparison folds to ret i1 true and a regression test covers the case.

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
Clearly specified
Newbie friendliness
65/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.