Fields should not alias Vec content.

[nbp]

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.

Meta

Tested with both rustc --version --verbose:

rustc 1.42.0 (b8cedc004 2020-03-09)
binary: rustc
commit-hash: b8cedc00407a4c56a3bda1ed605c6fc166655447
commit-date: 2020-03-09
host: x86_64-unknown-linux-gnu
release: 1.42.0
LLVM version: 9.0

and

rustc 1.44.0-nightly (7f3df5772 2020-04-16)
binary: rustc
commit-hash: 7f3df5772439eee1c512ed2eb540beef1124d236
commit-date: 2020-04-16
host: x86_64-unknown-linux-gnu
release: 1.44.0-nightly
LLVM version: 9.0

edit: remove the -Zmutable_noalias as this seems to optimize this minimized test case. #71354 (comment)

[RalfJung]

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.

[hanna-kruppe]

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.

[nox]

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

[hanna-kruppe]

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.

[RalfJung]

I remember discussing Unique and Vec before with @Gankra; there should be an issue with more discussion somewhere but I do not know where...

[Gankra]

yeah it's been a longstanding issue but aiui there aren't any interesting insights beyond "yep sure would be nice if we could tell llvm about it".

[jrmuizel]

Here's an example of multiple vectors preventing optimization:

pub fn foo(v: &mut Vec<usize>, k: &mut Vec<usize>) -> usize {
    assert!(v.len() > 2 && k.len() > 2);
    v[0] += 1;
    k[0] += 1;
    v[0] += 1;
    k[0]
}

and a local Vec who's address escapes:

#[inline(never)]
fn black_box<T>(x: T) {
    unsafe { std::ptr::read_volatile(&x); }
}

pub fn foo() -> usize {
    let v = vec![1];
    black_box(&v);
    v[0]
}

Neither is as optimized as Rust allows.