LLVM cannot prove that index is in bounds

[tesuji]

Current status: Waiting for llvm/llvm-project#90417

When trying to get rid of unsafe code in commit 57d25179e6751854c298313070adc4ac4454e230 in #81427.
I found a case that GCC can prove that the slice index in bound but LLVM cannot.

I tried this code (see generated assembly at godbolt https://godbolt.org/z/dTraGe):

pub fn eat_digits<const N: usize>(s: &[u8; N]) -> bool {
    let mut i = 0;
    while i < N {
        let c = s[i];
        if b'0' <= c && c <= b'9' {
            i += 1;
        } else {
            break;
        }
    }
    i <= N
}

pub fn foo(s: &[u8; 1234]) -> bool {
    eat_digits(s)
}

I expected to see this happen: Compiler optimizes eat_digits to only true.

Instead, this happened: LLVM cannot prove that, which leads to bounds check with s[..i].

Note that for the C version (more or less), gcc can optimize the code to ret true:

#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>

#define N 1234

bool eat_digits(uint8_t s[N]) {
    size_t i = 0;
    while (i < N) {
        uint8_t c = s[i];
        if ('0' <= c && c <= '9') {
            i += 1;
        } else {
            break;
        }
    }
    return i <= N;
}

Meta

rustc --version --verbose:

rustc 1.51.0-nightly (d1aed50ab 2021-01-26)
binary: rustc
commit-hash: d1aed50ab81df3140977c610c5a7d00f36dc519f
commit-date: 2021-01-26
host: x86_64-unknown-linux-gnu
release: 1.51.0-nightly
LLVM version: 11.0.1
Compiler returned: 0

@rustbot label A-LLVM I-slow T-compiler

[nagisa]

Doesn't optimize to ret true when compiling the C reproducer with clang either.

[klensy]

More: even if using iterators that can produce non increasing number of elements, rust (or llvm, don't know which part) can't prove bounds.

https://rust.godbolt.org/z/4qn4Pf

[jrmuizel]

I filed https://bugs.llvm.org/show_bug.cgi?id=49389

[jrmuizel]

The upstream llvm bug seems to be fixed.