Bounds check eliminated only when array length is a constant

[DaniPopes]

I tried this code (godbolt):

#[no_mangle]
pub fn shift_left(arr: &mut [u64], n: usize) {
    let len = arr.len();
    if n >= len {
        arr.fill(0);
    } else {
        let c = len - n;
        for i in 0..c {
            arr[i] = arr[i + n];
        }
        arr[c..].fill(0);
    }
}

#[no_mangle]
pub fn shift_left_4(arr: &mut [u64; 4], n: usize) {
    shift_left(arr, n);
}

I expected to see this happen: no bound checks in both functions

Instead, this happened: bounds check present in the generic shift_left (the arr[i + n])

Meta

rustc --version --verbose:

rustc 1.89.0-nightly (5e16c6620 2025-05-24)
binary: rustc
commit-hash: 5e16c662062fd6dee91f0fe2a1580483488d80cf
commit-date: 2025-05-24
host: x86_64-unknown-linux-gnu
release: 1.89.0-nightly
LLVM version: 20.1.5

Backtrace

<backtrace>

[asquared31415]

This has to do with the fact that the compiler cannot prove that overflow does not happen during calculation of i + n, and so it cannot prove that the index will actually be in bounds.

[ds84182]

fwiw this can be written without the bounds check by using Cell & what I call "pattern marching": https://godbolt.org/z/jqo5PhYWv

untested but it should give the same result.

[workingjubilee]

i must be less than c, which must be less than len - n, which must be nonzero and will not underflow because we checked if n >= len. it seems like that should be sufficient information, in theory, @asquared31415?

[asquared31415]

Mathematically there is enough information, but using i.unchecked_add(n) in place of i + n allows the bounds check to be elided. I was unable to come up with a counterexample that would actually cause overflow, perhaps this is a missed optimization on LLVM's side?

So perhaps treat "the compiler cannot prove" in my previous statement as "the compiler is not proving"

[asquared31415]

I believe that Alive2 might be able to tell you what LLVM thinks is going on, but I only have a small amount of experience with LLVM IR and I was not able to coerce alive2 to compile the example code on llvm's compiler explorer (a mysterious "compiler returned 1" with no message). In theory if you got the original code compiling and asked it if the transformation to i.unchecked_add(n) was valid, it would say no and give you the counterexample that LLVM believes exists.

[asquared31415]

Reduced and annotated example with a summary of my findings:

#[no_mangle]
pub fn src(arr: &mut [u8], n: usize) {
    let len = arr.len();
    if len > n {
        // because len > n as checked above, then c is at least 1
        // and overflow cannot have occurred when calculating (len - n)
        let c = len - n;
        for i in 0..c {
            // 0 <= i < c
            // 0 <= i < len - n
            // n <= i + n < len
            // if overflow did not happen on (len - n) then
            // overflow cannot have happened on (len - n) + n
            // therefore the final index calculation cannot overflow
            // and will be strictly less than the length
            let idx = i + n;
            // however replacing the calculation of idx with an unchecked addition
            // somehow lets the compiler reason that the index is indeed always in bounds
            // UNCOMMENT ME vvvvvvv
            //let idx = unsafe { i.unchecked_add(n) };

            // a bounds check is generated on this access when `idx` is calculated as `i + n`
            core::hint::black_box(arr[idx]);
        }
    }
}

additionally, restructuring the loop such that it loops over the final calculated indices directly rather than calculating them within the loop appears to help LLVM reason about bounds checks. unfortunately this is not reasonable in the original example.