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 7750c3d))

[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