LLVM is unable to eliminate bounds checks with widening multiply

[dhardy]

Demonstration:

pub fn bar(rand: u32, arr: &[u8]) -> u8 {
    let mul = rand as u64 * arr.len() as u64;
    let hi = (mul >> 32) as u32;
    arr[hi as usize]
}

Note that hi must be less than arr.len(). LLVM is unable to prove this, and inserts a bounds check on array access. Extract from the compiled assembly:

	imulq	%rdx, %rsi
	shrq	$32, %rsi
	cmpq	%rdx, %rsi
	jae	.LBB0_2

Application: rust-random/rand#592

(Note: we have multiple implementations of widening multiply here.)

[nikic]

To clarify, the assumption for your particular example is a 32-bit target, right? With 32-bit usize that is.

[nikic]

Possible optimization: https://rise4fun.com/Alive/2Us This converts into an arr.len() != 0 check, as just optimizing the bounds check away entirely is illegal.

[dhardy]

This is just a simplified example — if you follow my link, you'll see we have implementations for sizes up to and including u128 input as well as SIMD types. I believe the point applies to all of these, but haven't tested personally.

[nikic]

Partial fix up at https://reviews.llvm.org/D69686. This should handle the case where the array length is constant (which seems to be the actual motivating case).

[vks]

If arr is changed to be a slice into an array of constant size, the bound checks are eliminated with Rust 1.54. So @nikic's partial fix seems to be working.