Rust: Missed optimization to elide bounds check

[a2aaron]

Context: this bug was reduced from indexing into a nested array, but this shows the same problem.

pub fn get(array: &[u8; 8], x: usize, y: usize) -> u8 {
    if x > 7 || y > 7 {
        0
    } else {
        array[y]
    }
}

(Playground link)

Rust doesn't elide the bounds check on array[y], even though it's impossible for y to be out of range due to the if condition. Rust does elide the bounds check when the if condition is just if y > 7, however.

Here is the generated ASM for the above code:

playground::get:
    pushq   %rax
    orq %rdx, %rsi
    cmpq    $7, %rsi
    jbe .LBB0_2
    xorl    %eax, %eax
    popq    %rcx
    retq

.LBB0_2:
    cmpq    $7, %rdx
    ja  .LBB0_5
    movb    (%rdi,%rdx), %al
    popq    %rcx
    retq

.LBB0_5:
    leaq    .Lanon.357673f8919c00a2ec2e627b7663c19f.1(%rip), %rax
    movl    $8, %esi
    movq    %rdx, %rdi
    movq    %rax, %rdx
    callq   *core::panicking::panic_bounds_check@GOTPCREL(%rip)
    ud2

.Lanon.357673f8919c00a2ec2e627b7663c19f.0:
    .ascii  "src/lib.rs"

.Lanon.357673f8919c00a2ec2e627b7663c19f.1:
    .quad   .Lanon.357673f8919c00a2ec2e627b7663c19f.0
    .asciz  "\n\000\000\000\000\000\000\000\005\000\000\000\t\000\000"

and here is the generated ASM when we change the if to just be if y > 7

playground::get:
    cmpq    $7, %rdx
    jbe .LBB0_2
    xorl    %eax, %eax
    retq

.LBB0_2:
    movb    (%rdi,%rdx), %al
    retq

Meta

This occurs in both the latest versions of stable (1.44.1) and nightly (1.46.0-nightly (2020-06-26 7750c3d46bc19784adb1))

[a2aaron]

It seems that the bounds check does get elided if I split up the if expression.

pub fn get(board: &[u8; 8], x: usize, y: usize) -> u8 {
    if x > 7 {
        0
    } else if y > 7 {
        0
    } else {
        board[y]
    }
}

This generates

playground::get:
    orq %rdx, %rsi
    cmpq    $7, %rsi
    jbe .LBB0_2
    xorl    %eax, %eax
    retq

.LBB0_2:
    movb    (%rdi,%rdx), %al
    retq

[leonardo-m]

And it seems it needs two unlikely to produce the right happy path:

pub fn get4(array: &[u8; 8], x: usize, y: usize) -> u8 {
    if unlikely(x > 7) {
        0
    } else if unlikely(y > 7) {
        0
    } else {
        array[y]
    }
}

get4:
        or      rsi, rdx
        cmp     rsi, 7
        ja      .LBB1_1
        mov     al, byte ptr [rdi + rdx]
        ret
.LBB1_1:
        xor     eax, eax
        ret

[bugadani]

The assume intrinsic also seems to not work if a logical expression is used, maybe it's related?

I.e. assume(0<a && a < 42) does not make subsequent bounds checks go away but 2 assumes do.

[nikic]

Godbolt: https://rust.godbolt.org/z/xYEszA

The problem is that the condition is converted to (x | y) > 7, at which point implication no longer works. It should be straightforward to teach LVI about this special case.

[nikic]

https://reviews.llvm.org/D82715

[nikic]

Fix has landed upstream, we'll pull it in with the LLVM 11 upgrade.

[nikic]

This if fixed in 1.47 with the LLVM 11 upgrade. It's probably worthwhile to add a codegen test, as bounds check optimization tends to be a bit fragile.

[bugadani]

Great, thanks! I can handle the test