leading_zeros() return value is still bounds checked

[martin2250]

leading_zeros() can return at most the number of bits of the underlying data type. The compiler does not seem to consider this during optimization.

Code

#![feature(core_intrinsics)]

const LOOKUP: [usize; 65] = [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 13, 13, 13, 13, 13, 12, 12, 12, 11, 11, 10, 10, 9, 8, 7, 6, 5, 4, 3, 0, 0];

pub fn min_selector(i: u64) -> usize {
    let l_z = i.leading_zeros() as usize;
    // unsafe {core::intrinsics::assume(l_z < 65);}
    return LOOKUP[l_z];
}

Tested on rustc 1.51.0 (2fd73fabe 2021-03-23), nightly in the Compiler Explorer with -C opt-level=3.

I expect the unsafe block to have no effect, since u64::leading_zeros() shouldn't return a number greater than 64. Instead, the disassembly shows that there is a bounds check which disappears when the unsafe block is uncommented.

[nikic]

Godbolt: https://rust.godbolt.org/z/5GG6b4e8v

Problem seems to be that LVI doesn't use range metadata on intrinsic calls.

[leonardo-m]

There are many problems like this. That people keep patching in various ways (for the division and rem of NonZeroXX, for binary_search, etc). My opinion is that a system language as Rust needs a principled and user-level type system improvement that allows the compiler analyse, handle and use value ranges for optimization & correctness purposes, both for constant and dynamic ranges.

See also #74014

[nikic]

Upstream fix: llvm/llvm-project@4a3e006

[leonardo-m]

This seems fixed now

[workingjubilee]

Doesn't seem to be on nightly yet. https://rust.godbolt.org/z/Kfo917nTx

[nikic]

Right, this will be pulled in by the next LLVM upgrade.

[nikic]

Fixed by #87570:

define i64 @_ZN4test12min_selector17hce2ef68927145e7fE(i64 %i) unnamed_addr #0 {
start:
  %0 = tail call i64 @llvm.ctlz.i64(i64 %i, i1 false) #2, !range !2
  %1 = getelementptr inbounds [65 x i64], [65 x i64]* bitcast (<{ [520 x i8] }>* @0 to [65 x i64]*), i64 0, i64 %0
  %2 = load i64, i64* %1, align 8
  ret i64 %2
}