[ER] A harder case of missed array bound test elision

[leonardo-m]

Another common case where LLVM doesn't infer the safety of the array access:

fn copy_to_front_evens(arr: &mut [u32; 100]) {
    let mut pos = 0; // Tortoise
    for i in 0 .. arr.len() { // Hare
        if arr[i] % 2 == 1 {
            arr[pos] = arr[i];
            pos += 1;
        }
    }
}

Compiled with -O it performs a bound test in arr[pos]:

copy_to_front_evens:
    pushq   %rax
    movq    %rdi, %rax
    movl    $1, %ecx
    xorl    %edi, %edi
    jmp .LBB0_1

.LBB0_7:
    addq    $2, %rcx
    cmpq    $101, %rcx
    je  .LBB0_8

.LBB0_1:
    movl    -4(%rax,%rcx,4), %edx
    testb   $1, %dl
    je  .LBB0_4
    cmpq    $99, %rdi
    ja  .LBB0_9
    movl    %edx, (%rax,%rdi,4)
    addq    $1, %rdi

.LBB0_4:
    movl    (%rax,%rcx,4), %edx
    testb   $1, %dl
    je  .LBB0_7
    cmpq    $99, %rdi
    ja  .LBB0_9
    movl    %edx, (%rax,%rdi,4)
    addq    $1, %rdi
    jmp .LBB0_7

.LBB0_8:
    popq    %rax
    retq

.LBB0_9:
    leaq    .L__unnamed_1(%rip), %rdx
    movl    $100, %esi
    callq   *core::panicking::panic_bounds_check@GOTPCREL(%rip)
    ud2

I don't know if a back-end like LLVM is supposed to infer complex situations as this one. Perhaps this is the job of explicit code annotations of pre/post-conditions, loop (in)variants, etc.

[the8472]

Perhaps this is the job of explicit code annotations of pre/post-conditions, loop (in)variants, etc.

The usual hack of adding pos = std::cmp::min(pos, arr.len() - 1); eliminates the bounds check.

[leonardo-m]

Do you mean code like this?

fn copy_to_front_evens2(arr: &mut [u32; 100]) {
    let mut pos = 0; // Tortoise
    for i in 0 .. arr.len() { // Hare
        if arr[i] % 2 == 1 {
            pos = pos.min(arr.len() - 1);
            arr[pos] = arr[i];
            pos += 1;
        }
    }
}

If you mean code like that, then unless I'm missing something it still contains an extra test on pos each loop, so it isn't a significant enough improvement over the original version with a panic.

[the8472]

My bad, I only checked for the absence of the callq.

[clubby789]

@rustbot label +I-slow +A-llvm