Missed bounds check elimination

[ericlagergren]

On Rust 1.79.0.

pub const fn missing_bce(v: &[u32]) -> u32 {
    if v.is_empty() {
        return 0;
    }
    let mut sum = 0;
    let mut i = v.len() - 1;
    while i > 0 {
        sum += v[i];
        i -= 1;
    }
    sum
}

https://godbolt.org/z/xxjKd5anW

The compiler should be able to elide the bounds check for v[i] since i is always in [0, v.len()-1].

[tgross35]

@rustbot label +A-codegen +C-optimization +T-compiler +I-slow -needs-triage

[tgross35]

From a quick glance at the IR it looks like the bounds checks exist for both in MIR but get removed before the IR, so maybe mir opts gets one but not the other? Cc @rust-lang/wg-mir-opt if somebody wants to take a closer look.

[dianqk]

The bounds checks of has_bce are eliminated in LLVM InstCombine: https://godbolt.org/z/38EaT1n73. IIUC, mir-opt currently does not perform similar optimizations (e.g. CorrelatedValuePropagationPass). Or rather, some range analysis optimizations.

@rustbot label +A-LLVM

[enqueueDequeue]

May I point that the code shown is summing upto index 0 but not index 0, which I think is the reason why there's a bound check.

[ericlagergren]

May I point that the code shown is summing upto index 0 but not index 0, which I think is the reason why there's a bound check.

Why would that cause a bounds check?

It should be trivial for the compiler to prove that 0 < i < s.len() and elide the bounds checks.

[enqueueDequeue]

I'm saying that a break after the index update is causing a bound check

// This code is equivalent to the first snippet
// And also causes a bound check instruction to be present in the assembly
loop {
    sum += v[i];
    i -= 1;
    if i == 0 {
        break;
    }
}

where as, a break before the index update is not causing a bound check

loop {
    sum += v[i];
    if i == 0 {
        break;
    }
    i -= 1;
}