Annotate number range for llvm

1

The desire for somehow expressing at compile time that a number is in a certain range is clear from the many issues surrounding the topic. Steps are being taken towards a future where they are a reality.

Until we are that far, we can write or generate specific solutions. Let us create a new type that wraps a u32 and ensures that the value inside is always less than 10. We will use this type to index an array of which we know the length to try and skip array bound checks.

pub struct U32Lt10(u32);

impl U32Lt10 {
    #[inline]
    pub fn new(val: u32) -> Option<Self> {
        if val < 10 {
            Some(U32Lt10(val))
        } else {
            None
        }
    }
    
    #[inline]
    pub fn get(&self) -> u32 {
        // Try to let the compiler know at the call site that the value 
        // returned is always < 10.
        unsafe {
            if self.0 < 10 {
                self.0
            } else {
                std::hint::unreachable_unchecked()
            }
        }
    }
}

pub fn get_it_now(arr: &[u8; 20], idx: U32Lt10) -> u8 {
    // We know idx is always less than 10. We also know arr.len() is 20. Thus 
    // idx is always les than arr.len() and we do not need to check the bounds!
    arr[idx.get() as usize]
}
assembly output 
playground::get_it_now:
	pushq	%rax
	movl	%esi, %eax
	movl	%esi, %esi
	cmpl	$19, %eax
	ja	.LBB0_2
	movb	(%rdi,%rsi), %al
	popq	%rcx
	retq

.LBB0_2:
	leaq	.Lanon.a49c2988708a5d4fee9536100b6bda03.0(%rip), %rdi
	movl	$20, %edx
	callq	*core::panicking::panic_bounds_check@GOTPCREL(%rip)
	ud2

str.0:
	.ascii	"src/lib.rs"

.Lanon.a49c2988708a5d4fee9536100b6bda03.0:
	.quad	str.0
	.quad	10
	.long	30
	.long	5

playground

We try very hard in the implementation of U32Lt10::get to let the compiler know that the value it returns is in fact: less than 10. Despite our efforts, when we compile this down to ASM it still performs the check and generates the out of bounds panicking code. Of course we can rewrite the get_it_now function to use the unsafe get_unchecked but we would really rather have the compiler determine that it is safe to omit the check.

I am not familiar with the exact workings of the rust compiler but I think in some places, it supplies llvm range metadata. Just not where we need it.

Does anyone know if what I expect from the compiler is reasonable, why the range meta data is not emitted or if there is a technique to accomplish what I'm trying to do?

2

The compiler is not really determining safety if it has to rely on that unreachable_unchecked()! I would just use get_unchecked() and be done with it.

If you're willing to use nightly, you might have better results with initrinsics::assume, but even then LLVM seems to have trouble preserving range info. We have a similar issue with NonZero types:

1 Like
3

Else-unreachable like that seems to generally not work for two-stage branches -- AFAICT something fairly early in LLVM just says "oh, that side's impossible? Great, I'll remove it and the condition"

1 Like
4

I would feel so sad and lost without you guys. Thanks for the pointers!

5

The core::intrinsics::assume does work for the example from this post. Reading through the issue @cuviper linked, @hanna-kruppe mentions this:

Why that is difficult is a big topic and I'm not even sure what factors dominate, but for example we both know the downsides of putting lots of explicit instructions asserting these fact into the instruction stream (e.g. via calls to llvm.assume ).

I do not know what the downside that he refers to is. When looking at the source of the NonZero* types in libcore I don't see any use of intrinsics::assume in the get functions. What is the rationale behind this?

6

Ah I found a comment on this pr where someone actually add the the assume instrinsic on the NonZero getters:

I am hesitant to add assumes in random places because they add more IR (particularly if they're in a very common, small and usually-inlined function like this) and they can, unfortunately, also block some optimizations.

1 Like
7

The LLVM reference warns about optimization effects too:
https://llvm.org/docs/LangRef.html#llvm-assume-intrinsic

2 Likes