Rust: Fields should not alias Vec content.

Created on 20 Apr 2020 · 6Comments · Source: rust-lang/rust

I tried this code ( https://rust.godbolt.org/z/GuvQi9 ), which mutates a field while reading the content of a buffer.

use std::vec::Vec;

pub fn foo(v: &mut Vec<usize>) -> usize {
    assert!(v.len() > 2);
    let s1 = v.pop().unwrap();
    let s2 = v.pop().unwrap();
    s1 + s2
}

Here the assertion is capable of removing the branches which are within the pop function, to make a branch-less function apart from the assertion code:

        […]
        mov     rcx, qword ptr [rdi + 16]
        […]
        lea     rax, [rcx - 1]
        mov     qword ptr [rdi + 16], rax
        […]
        lea     rsi, [rcx - 2]
        mov     qword ptr [rdi + 16], rsi
        […]

However, the generated code still contains a spill of the len field of the vector for each pop-ed value which is used. The reason is that LLVM does not know whether the read type can alias or not the field which is being written to. This aliasing reason is inconsistent with the fact that the len field from which the value which is written back to memory is aliased in the rcx register.

I would have expected the generated code to contain a single update of the len field, instead of 2.

Testing with -C opt-level=3 does not change the result.

Most helpful comment

You're right, it does help. But AFAICT this is because it establishes that nothing can alias the Vec's fields. That doesn't help when the Vec isn't stored behind a mutable reference (e.g. it's a local and its address escapes) or if you need to know vec1[i] can't alias vec2[j] for two separate vectors. Those kinds of scenarios require aliasing information attached to the Vec's data pointer.

hanna-kruppe on 21 Apr 2020

👍2

All 6 comments

I think this would require making the Unique that Vec uses internally actually mean something (AFAIK currently it does not). One issue here is figuring out what exactly the semantics of Unique in Rust should be, and if we can make it so that it can map to noalias in LLVM (which might help here -- that would be a good experiment to make).

The currently proposed aliasing model is Stacked Borrows, but so far it cannot handle Unique.

RalfJung on 20 Apr 2020

There's the additional challenge that LLVM currently lacks a sound encoding (other than dropping the aliasing information entirely) of "scoped" noalias information other than noalias-on-function-arguments. It's a difficult problem and while a promising approach tailored to C restrict might become reality in the medium-term future, I'm not even sure if the approach taken for fine-grained restrict will help us with our eventual Rust aliasing model. If we need something different, the fact that fine-grained restrict took so long to soundly encode in LLVM IR makes me skeptical if we can implement "Rust AA" in a reasonable time frame.

hanna-kruppe on 20 Apr 2020

👍1

AFAICT, -Z mutable_noalias does merge the 2 decrements, doesn't it?

example::foo:
        push    rax
        mov     rcx, qword ptr [rdi + 16]
        cmp     rcx, 3
        jb      .LBB5_2
        mov     rdx, qword ptr [rdi]
        mov     rax, qword ptr [rdx + 8*rcx - 8]
        lea     rsi, [rcx - 2]
        mov     qword ptr [rdi + 16], rsi
        add     rax, qword ptr [rdx + 8*rcx - 16]
        pop     rcx
        ret
.LBB5_2:
        call    std::panicking::begin_panic
        ud2