Add unreachable hints for length getters?

[newpavlov]

As discussed in this thread, Rust does not provide LLVM any information about possible lengths of slices, vectors, and other types. In some cases it prevents LLVM from applying optimizations since it has to account for invalid lengths.

I suggest updating length getters of slice-like types to something like this:

#[inline]
pub const fn len(&self) -> usize {
    let len = ...;
    let size = core::mem::size_of::<T>();
    // on most arches we can use `isize::MAX as usize`
    // instead of `usize::MAX`, but IIRC not everywhere
    if size != 0 && len > usize::MAX / size {
        unsafe { core::hint::unreachable_unchecked() }
    }
    len
}

[thomcc]

In many cases it would be much better to do this by emitting range metadata info in the compiler -- https://rust-lang.zulipchat.com/#narrow/stream/187780-t-compiler.2Fwg-llvm/topic/Range.20metadata.20for.20.60size_of_val.60.20and.20other.20isize.3A.3AMAX.20limits is a conversation about it (for size_of_val) I started a while ago. If that were done we could consider rewriting <[T]>::len() in terms of size_of_val, although that's not guaranteed to be a win either.

In general assumes (including indirect ones like this) can often impact compile time quite a bit (and sometimes even runtime) negatively, since the compiler doesn't really know how long to keep the conditional expressions that drive it (keep them too long, then it blocks optimizations and perhaps hurts runtime, discard them too soon and it ends up not being available when needed) -- it tends to be better as metadata.

My hunch is that it's unlikely that we'll be able to accept the impact of doing this as a library change on slices.

[newpavlov]

@thomcc
Would it be possible to add range metadata to a variable in library code? For example, using an unsafe intrinsic? Or does it need introduction of special types? Such intrinsic would be useful in user code as well, e.g. block-buffer uses unreachable_unchecked to eliminate unreachable panics.

In the linked discussion @erikdesjardins has expressed concern about range metadata getting eliminated too early to positively impact optimization passes. I guess using #[inline(always)] may help here?

[thomcc]

Would it be possible to add range metadata to a variable in library code

Not really, because slice.len() turns into something special in MIR right away anyway (a Len instruction). IIUC the compiler doesn't ever actually emit calls to the function, it just knows what it does. -- this is likely a good thing FWIW, it gets value out of that knowledge, and should be able to use that to attach the range metadata to the result of the load (which should avoid the concern about it being inlined too soon?)

I don't know that there's a good way to anything like this to libraries. The closest would be the niche RFC. But the concerns of the standard library here are very different than for other library code, and really this is probably not an issue that should be used for discussion of new language features like that anyway.

[newpavlov]

Not really, because slice.len() turns into something special in MIR right away anyway (a Len instruction). IIUC the compiler doesn't ever actually emit calls to the function, it just knows what it does.

IIUC it happens only after the method gets inlined. Otherwise, it's a simple method to which we can add whatever we want, be it unreachable_unchecked or the hypothetical unsafe intrinsic.

P.S.: Feel free to close this issue, if you think that the unreachable_unchecked approach is a non-starter.

[erikdesjardins]

should be able to use that to attach the range metadata to the result of the load

The problem is, there often isn't a load, e.g. whenever a slice is passed directly as an argument: https://godbolt.org/z/z6ocsEfzx. Even if it were temporarily spilled to an alloca, that load would get optimized out by SROA early in the pipeline, dropping the metadata. (If the slice is behind another layer of indirection, e.g. in fn foo(x: &Bar) { x.slice.len() }, then the load will stay around, and metadata ought to help.)

This is not to say that we shouldn't add range metadata, just that I think it won't help that much. I agree that adding metadata has a much better cost/benefit tradeoff vs. adding assumes.

What would really help is range attributes on arguments. If LLVM had that, we could codegen
fn foo(x: &[i32])
as
@foo(ptr <...> %data, i64 range {0, max} %len)
which would cover a lot more cases.

[scottmcm]

What would really help is range attributes on arguments

That'd be a big help for NonZeroU32 and friends too.

[scottmcm]

Cross-linking to a recent Zulip conversation: https://rust-lang.zulipchat.com/#narrow/stream/247081-t-compiler.2Fperformance/topic/range.20metadata.20for.20slice.20len/near/395449552