Missed optimization opportunity on checking integer bounds

[EFanZh]

I tried this code:

Example 1:

pub fn foo(n: usize, s: &[u32]) {
    assert!(n <= 40);

    for _ in s {
        std::hint::black_box(());
    }

    for i in 0..n {
        assert!(i < 40); // Not optimized.
    }
}

Example 2:

pub fn foo(n: usize) {
    assert!(n <= 40);

    for i in 0..n {
        assert!(i < 40); // Not optimized.

        if i % 2 == 0 {
            std::hint::black_box(());
        }
    }
}

I expected to see this happen: With -C opt-level=3 option, assert!(i < 40); gets optimized away.

Instead, this happened: The generated assembly still contains codes for i < 40 assertion failure. See https://godbolt.org/z/de6WcGc16 and https://godbolt.org/z/e4GYrfTEq.

For the first example. If I comment the black_box, the compiler will be able to do the optimization:

pub fn foo(n: usize, s: &[u32]) {
    assert!(n <= 40);

    for _ in s {
        // std::hint::black_box(());
    }

    for i in 0..n {
        assert!(i < 40);
    }
}

For the second example, If I change the condition of the if statement to true, the compiler will be able to do the optimization:

pub fn foo(n: usize) {
    assert!(n <= 40);

    for i in 0..n {
        assert!(i < 40);

        if true {
            std::hint::black_box(());
        }
    }
}

Meta

rustc --version --verbose:

rustc 1.70.0-nightly (171693274 2023-03-14)
binary: rustc
commit-hash: 1716932743a7b3705cbf0c34db0c4e070ed1930d
commit-date: 2023-03-14
host: x86_64-unknown-linux-gnu
release: 1.70.0-nightly
LLVM version: 15.0.7
Compiler returned: 0

[scottmcm]

For the first example. If I comment the black_box, the compiler will be able to do the optimization:

black_box exists to make optimizations stop working, so generally "I used black_box and it optimized less" is not a bug.

Do you have an example of real (aka not using black_box) code instead? Otherwise I'm inclined to close this.

[EFanZh]

Yes, the example above is a simplified version of my original code. black_box is just a placeholder for some unspecified operations. My original code is for solving a LeetCode problem: https://github.com/EFanZh/LeetCode/blob/master/src/problem_1439_find_the_kth_smallest_sum_of_a_matrix_with_sorted_rows/binary_heap.rs. I added an assertion and hoped the compiler would use the hint to skip some bound checking, but it did not.

I can rewrite the examples without using black_box (See https://godbolt.org/z/Yxeh6aGan and https://godbolt.org/z/rj6G1Ps9W):

pub fn foo(n: usize, s: &[&[u32]]) {
    assert!(n <= 40);

    s.iter().map(|x| x[0]).sum::<u32>();

    for i in 0..n {
        assert!(i < 40); // Not optimized.
    }
}

pub fn foo(s: &[&[u32]]) {
    let n = s.len();

    assert!(n <= 40);

    for i in 0..n {
        assert!(i < 40); // Not optimized.

        if i % 2 == 0 {
            s[i][0];
        }
    }
}

Also, about using black_box, the idea is that according to the reference rules of Rust, no matter what it actually does, the relation of i and n should not be affected. But it seems the compiler loses the information somehow.

[DianQK]

This works (again) after LLVM 17, using opt(trunk) validation: https://llvm.godbolt.org/z/xvT6Wbq7o. Related commits: https://github.com/llvm/llvm-project/commit/8028263c41e335bc96c40402f8ab44ad405023de. Similar issues can be found in the commit.