Bound check for multiplication in for loops

[tesuji]

Bound checking happens when I using x + y * HEIGHT formula to
calculate the coordinate in an array. The generated code is
saved on Godbolt: https://rust.godbolt.org/z/76qEhK.

I tried this code:

const WIDTH: usize = 64;
const HEIGHT: usize = 32;
const DISPLAY_SIZE: usize = WIDTH * HEIGHT;

pub struct Display([u8; DISPLAY_SIZE]);

impl Display {
    pub fn draw(&mut self, (x, y): (u8, u8)) -> bool {
        let mut collision = false;
        let (x, y) = (usize::from(x) % WIDTH, usize::from(y) % HEIGHT);
        for y in y..HEIGHT {
            let coord = x + y * WIDTH;
            collision |= self.0[coord] != 0;
        }
        collision
    }
}

I expected to see this happen: No bound checks in generated code.

Instead, this happened: There are bound checks.
Note that bound checks doesn't happen if I don't use for loop and just use a immutable y value.

Meta

rustc --version --verbose:

rustc 1.51.0-nightly (4253153db 2021-01-17)
binary: rustc
commit-hash: 4253153db205251f72ea4493687a31e04a2a8ca0
commit-date: 2021-01-17
host: x86_64-unknown-linux-gnu
release: 1.51.0-nightly
LLVM version: 11.0.1

[tesuji]

The code in C with both gcc and clang optimized well but not in Rust ? https://rust.godbolt.org/z/voMWdc.

The code in C:

#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>

const size_t WIDTH = 64;
const size_t HEIGHT = 32;
const size_t DISPLAY_SIZE = WIDTH * HEIGHT;

bool draw(uint8_t x, uint8_t y) {
    x = (size_t)(x) % WIDTH;
    y = (size_t)(y) % HEIGHT;
    for (; y < HEIGHT; ++y)
    {
        size_t coord = x + y * WIDTH;
        if (coord >= DISPLAY_SIZE) {
            return false;
        }
    }
    return true;
}

Gcc and clang just straights to generate return true for draw function.

[tesuji]

Comparing llvm-ir outputs between clang and rust: https://rust.godbolt.org/z/soE8d3.
Somehow clang (front-end) just generates ret i1 true.

I wonder if implement the same optimization pass in MIR
@rustbot label A-mir-opt

[leonardo-m]

For a more fair comparison you can add the array update in the C code too, to make the two Rust/C versions as close as possible.

[leonardo-m]

Something like this (untested):

const WIDTH: usize = 64;
const HEIGHT: usize = 32;
const DISPLAY_SIZE: usize = WIDTH * HEIGHT;

pub fn draw(data: &[u8; DISPLAY_SIZE], x: u8, y: u8) -> bool {
    let x2 = usize::from(x) % WIDTH;
    let y2 = usize::from(y) % HEIGHT;
    let mut collision = false;
    for y3 in y2 .. HEIGHT {
        let coord = x2 + y3 * WIDTH;
        collision |= data[coord] != 0;
    }
    return collision;
}

#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdlib.h>

const size_t WIDTH = 64;
const size_t HEIGHT = 32;
const size_t DISPLAY_SIZE = WIDTH * HEIGHT;

bool draw(const uint8_t* data[DISPLAY_SIZE], const uint8_t x, const uint8_t y) {
    const size_t x2 = ((size_t)x) % WIDTH;
    const size_t y2 = ((size_t)y) % HEIGHT;
    bool collision = false;
    for (size_t y3 = y2; y3 < HEIGHT; y3++) {
        const size_t coord = x2 + y3 * WIDTH;
        if (coord < DISPLAY_SIZE) {
            collision |= data[coord] != 0;
        } else {
            exit(1);
        }
    }
    return collision;
}

[tesuji]

For a more fair comparison you can add the array update in the C code too, to make the two Rust/C versions as close as possible.

The problem for bound checks in Rust is that the compiler couldn't prove that x + y*WIDTH < DISPLAY_SIZE,
while clang/gcc can do that. This godbolt link demonstrates the issue fairer: https://rust.godbolt.org/z/soE8d3

[oli-obk]

cc @felix91gr I guess this is a good test case for value range analysis on MIR?

[felix91gr]

@oli-obk definitely!

... hmm, I'll open an issue on this. We'd better start listing the use, test and edge cases we notice :)

[tesuji]

Updating to LLVM 15 in Rust 1.65 fixed the issue: https://rust.godbolt.org/z/55GoEW5df