[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

[leonardo-m]

The problem is still present in rustc 1.88.0-nightly (LLVM version: 20.1.2).