make use of LLVM's scoped noalias metadata

@eddyb

Rust could pass along lots of aliasing information to LLVM via the new metadata.

http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata

UPDATE(@eddyb): Currently blocked on an Unsafe Code Guidelines decision, regarding the exact cases we can treat as UB, and optimize - see #16515 (comment) below, and further comments.

While LLVM can and will convert noalias attributes in function signatures into scoped !noalias metadata on instructions, when inlining, we never emit any such metadata ourselves.

Furthermore, the LLVM conversion is conservative (i.e. scoped to the entire callee) in a way that can't easily be generalized intra-function, without deciding on what to define and what to leave as UB.

There's already an LLVM pass which converts the noalias attributes to the new metadata during inlining. It's just not enabled by default now, but you can try it out by passing -C llvm-args="-enable-noalias-to-md-conversion".

I'm aware of that, but we have lots of aliasing information beyond just the outermost pointer in a parameter.

In the following code, one would expect b, c, and d to generate the same code. Instead, a and c generate the same code because the aliasing guarantees of & are not used in c.

#![crate_type = "lib"]

pub unsafe fn a(p: *const usize, g: fn()) -> usize {
    let a = *p;
    g();
    let b = *p;
    a ^ b
}

pub unsafe fn b(p: &usize, g: fn()) -> usize {
    let a = *p;
    g();
    let b = *p;
    a ^ b
}

pub unsafe fn c(p: *const usize, g: fn()) -> usize {
    let p = &*p;

    let a = *p;
    g();
    let b = *p;
    a ^ b
}

pub unsafe fn d(p: *const usize, g: fn()) -> usize {
    let p = &*p;

    b(p, g)
}

Applying the information suggested in this issue manually to the IR fixes the issue.

b:
    pushq   %rax
    callq   *%rsi
    xorl    %eax, %eax
    popq    %rdx
    retq

c:
    pushq   %r14
    pushq   %rbx
    pushq   %rax
    movq    %rdi, %r14
    movq    (%r14), %rbx
    callq   *%rsi
    xorq    (%r14), %rbx
    movq    %rbx, %rax
    addq    $8, %rsp
    popq    %rbx
    popq    %r14
    retq

Triage: #38941 is related, as is #31681

@mahkoh

@mahkoh: I'm interested in looking into this — could you provide any more details on what metadata you added to successfully reduce the code generated for c to that for b and d (and how you tested it)?

Following up on this particular test case, the optimised (opt-level=3) LLVM IR for the bodies of both a and c is:

; a, c
%0 = load i64, i64* %p, align 8
tail call void %g()
%1 = load i64, i64* %p, align 8
%2 = xor i64 %1, %0
ret i64 %2

whereas the ideal IR for c (already generated for b and d) is:

; b, d
tail call void %g()
ret i64 0

If we manually annotate the IR, so that the body of c is:

; c
%0 = load i64, i64* %p, align 8, !alias.scope !0
tail call void %g(), !noalias !0
%1 = load i64, i64* %p, align 8, !alias.scope !0
%2 = xor i64 %1, %0
ret i64 %2

and we add the following domain and scope:

!2 = distinct !{!2} ; domain
!1 = distinct !{!1, !2} ; scope
!0 = distinct !{!1} ; scope list

then, after running LLVM's opt -O3, the body of c is reduced to:

; c
tail call void %g(), !noalias !0
ret i64 0

as we want.

Update: the semantics for aliasing guarantees have not by this time been completely well defined — in particular the above transformation is guaranteed (at least now) to be correct. It's probably necessary to wait before implementing any features based on alias.scope or noalias because of this.

Just in case this is ever useful in the future, I have a branch which optimises the test case using the metadata. Even though it may not be semantically correct, it might be helpful to look at for other alias optimisations in the future.

@varkor

Cc @rust-lang/wg-codegen @rust-lang/compiler This looks like it should be carried to completion by one of us, after @varkor's concern about it being semantically correct or not is addressed.

Indeed, here is a counterexample for that optimization. It passes Miri, so if we want this to be UB, we need an aliasing model that is even more aggressive than Stacked Borrows (and very few unsafe code authors would be happy with that...).

Then how about this? It also passes miri, and fails the assertion in debug mode, but that's optimized away in release mode.

@cuviper

@cuviper that would fail in Miri with -Zmiri-retag-fields. This is currently the last gap I am aware of between Miri and what we tell LLVM.

error: Undefined Behavior: trying to retag from <3260> for Unique permission at alloc1702[0x0], but that tag does not exist in the borrow stack for this location
  --> test.rs:6:16
   |
6  | pub fn use_foo(foo: Foo) {
   |                ^^^
   |                |
   |                trying to retag from <3260> for Unique permission at alloc1702[0x0], but that tag does not exist in the borrow stack for this location
   |                this error occurs as part of FnEntry retag at alloc1702[0x0..0x4]
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <3260> was created by a Unique retag at offsets [0x0..0x4]
  --> test.rs:17:17
   |
17 |         use_foo(std::mem::transmute(pair));
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^
help: <3260> was later invalidated at offsets [0x0..0x4] by a Unique retag
  --> test.rs:17:17
   |
17 |         use_foo(std::mem::transmute(pair));
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: BACKTRACE:
   = note: inside `use_foo` at test.rs:6:16
note: inside `main` at test.rs:17:9
  --> test.rs:17:9
   |
17 |         use_foo(std::mem::transmute(pair));
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

@RalfJung

@RalfJung question: say we don't make it UB. Then, what can we do wrt noalias?

In scenarios like your counterexample, emitting noalias becomes UB. Or at least it would be UB from the point of view of LLVM, I think. Is that okay?

Also, tangentially related to this: I think Jeroen Dobbeleare has made large strides in the provenance model and semantics required for alias analysis inside of LLVM. He's been working on this for the past 2-3 years. Lemme go to the computer and see what I can find.
Am I correct in thinking that LLVM's semantics affect what we consider UB as well?

@RalfJung

@RalfJung working from your example, even this is bad according to miri:

fn noalias(_: &mut u32, _: &mut u32) {}

pub fn use_foo(foo: &mut Foo) {
    let Foo { r1, r2 } = foo;
    noalias(r1, r2);
}

error: Undefined Behavior: not granting access to tag <3104> because incompatible item [Unique for <3105>] is protected by call 944
  --> src/main.rs:6:1
   |
6  | fn noalias(_: &mut u32, _: &mut u32) {}
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not granting access to tag <3104> because incompatible item [Unique for <3105>] is protected by call 944
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <3104> was created by a SharedReadWrite retag at offsets [0x0..0x4]
  --> src/main.rs:10:17
   |
10 |     noalias(r1, r2);
   |                 ^^
help: <3104> was protected due to <3095> which was created here
  --> src/main.rs:10:13
   |
10 |     noalias(r1, r2);
   |             ^^
help: this protector is live for this call
  --> src/main.rs:6:1
   |
6  | fn noalias(_: &mut u32, _: &mut u32) {}
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: backtrace:
   = note: inside `noalias` at src/main.rs:6:1
note: inside `use_foo` at src/main.rs:10:5
  --> src/main.rs:10:5
   |
10 |     noalias(r1, r2);
   |     ^^^^^^^^^^^^^^^
note: inside `main` at src/main.rs:18:9
  --> src/main.rs:18:9
   |
18 |         use_foo(std::mem::transmute(&mut pair));
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

But my change was only in safe code! Which says to me that the unsafe block is unsound, no?

@felix91gr

@felix91gr

In scenarios like your counterexample, emitting noalias becomes UB. Or at least it would be UB from the point of view of LLVM, I think. Is that okay?

Emitting noalias where? noalias is a by-value annotation, and the reason the example is tricky is that it is talking about aliasing of a reference behind a reference.

But in general, yes -- emitting incorrect LLVM annotations, that lead to LLVM UB in programs without Rust UB, is a bug in rustc codegen. I wouldn't say "emitting noalias is UB" (that's a category error -- Rust/LLVM programs have UB, not the act of generating them), but emitting noalias is wrong and the generated LLVM IR is not a correct compilation of the source Rust code (because the target LLVM IR has UB for executions that are fine in the source Rust code).

Am I correct in thinking that LLVM's semantics affect what we consider UB as well?

Well, to an extent, yes, but in general we keep this to a minimum. We'd rather define and design the Rust semantics to make sense on their own, and then find ways to convey the information our choices grant the compiler (i.e., the UB we specify) to LLVM, and work with the LLVM people where that is not yet possible. LLVM is not the only backend Rust will ever have, and LLVM has plenty of idiosyncracies that it inherits from C, which IMO should not affect Rust semantics. But in cases where we think LLVM is designed well, it certainly makes sense to be inspired by its specification. And in cases where LLVM does not give us the freedom we need, sometimes we are forced to choose a Rust semantics that we don't like.

I have seen mentions of those efforts to re-do the noalias/restrict specification in LLVM, and I am curious to see what will come out of them. I am not sure if that is related to what you talk about though -- so far I have seen basically no work at all (except for my own) that talks very much about the provenance model of LLVM. The LangRef does not mention provenance and bugs that obviously violate basically any kind of provenance model remain unfixed for years. I would be delighted to hear that LLVM officially acknowledges the existence of provenance and hope that means there is a chance for these bugs to be finally fixed. :D

@cuviper

even this is bad according to miri:

Yes, here you are explicitly going below the double-indirection -- this is very similar to my example from earlier.

Which says to me that the unsafe block is unsound, no?

"soundness of an unsafe block" is not a well-defined term -- soundness is a term that applies to the safe public API surface of a library. Inside a module that contains any unsafe code, it is fairly common that safe code can introduce UB.

I would be delighted to hear that LLVM officially acknowledges the existence of provenance and hope that means there is a chance for these bugs to be finally fixed. :D

They absolutely do! Down below I'll put links that might interest you in that regard :)

I have seen mentions of those efforts to re-do the noalias/restrict specification in LLVM, and I am curious to see what will come out of them. I am not sure if that is related to what you talk about though -- so far I have seen basically no work at all (except for my own) that talks very much about the provenance model of LLVM. The LangRef does not mention provenance and llvm/llvm-project#34577.

Oh yes. The documentation is lacking, so very much. I was once in a call actually with Jeroen and other folks who work on this, and asked about it. J said that... basically yes, the docs are pretty outdated and incomplete, and that nobody was really working on them 😢

Basically a lot of the current knowledge about these details is living inside oral tradition more than anything else.

that's a category error -- Rust/LLVM programs have UB, not the act of generating them

Whoops. Thank you for correcting me on that :)

Here are the links I promised above.

There is a public Alias Analysis (and pointer provenance) call every 4 weeks. The notes reside here: https://docs.google.com/document/d/17U-WvX8qyKc3S36YUKr3xfF-GHunWyYowXbxEdpHscw/edit#

In the older notes down below, I worked last year or so on tidying them up and in general, in making them more accessible. I have yet to go through the newer ones ^^.

On November last year, Jeroen did a presentation on his (then, current) work on AA and provenance: https://www.youtube.com/watch?v=Uz_Xt-CctKc
I think it's pretty good and that maybe it can help answer a lot of your questions regarding both topics :)

I have to read through the notes again, since now I understand provenance a lot better than I used to.
But going through the most recent notes, there's a lot I see there that reminds me of Gankra's recent writings on provenance. I think Jeroen is working towards a very similar goal, which is super encouraging.

Cheers 🙂

I have seen mentions of those efforts to re-do the noalias/restrict specification in LLVM, and I am curious to see what will come out of them. I am not sure if that is related to what you talk about though -- so far I have seen basically no work at all (except for my own) that talks very much about the provenance model of LLVM. The LangRef does not mention provenance and bugs that obviously violate basically any kind of provenance model remain unfixed for years. I would be delighted to hear that LLVM officially acknowledges the existence of provenance and hope that means there is a chance for these bugs to be finally fixed. :D

While LangRef does not use the term "provenance", it obviously does have provenance, as documented in https://llvm.org/docs/LangRef.html#pointer-aliasing-rules. Of course, the actual rules specified there are both incorrect (the inttoptr rule is unlikely to be tenable and does not match optimizer behavior) and incomplete (no mention of type punning) in the area where provenance semantics are tricky (which is incidentally also the area where all the provenance-related bugs are).

As for Jeroen's full restrict patches, I don't have particularly high hopes for these, because I think he's not approaching their introduction in the best way, which is why this has been stalled for so long. I expect that trying to introduce the new base model before trying to introducing the provenance side channel optimizations would have gone down a lot better, and allowed for earlier testing and evaluation.

@felix91gr

@felix91gr
Thanks for these links!

You might also enjoy my writings on provenance, then. ;) Part 1, Part 2, Part 3.

@nikic

While LangRef does not use the term "provenance", it obviously does have provenance, as documented in https://llvm.org/docs/LangRef.html#pointer-aliasing-rules.

A lot of these could be explained with an "emergent" notion of provenance, where provenance is just used to talk about static analysis facts that can be deduced from the operational semantics. It is not clear to me that this acknowledges the existence of provenance as a concept in the operational semantics. (After all, that document is somewhat similar to C, and I would not say that the C standard acknowledges the existence of provenance.)

@RalfJung

@RalfJung it seems bizarre to me that the example I gave (and the counter example you ran through miri) are "sanctioned" forms of aliasing under stacked borrows. This goes against the commonly taught mental model of "creating (via unsafe) multiple concurrently used unshared borrows to the same data is UB", and precludes optimizations that I think most rust users would expect.

The mental model we teach is an overapproximation of the actual rules, which are still open. The rules proposed by Stacked Borrows already rule out some unsafe code patterns that are frequently found in the wild, meaning Rust programmers expect both less strict rules and even more strict rules. There is a fundamental tension here and we will end up meeting somewhere in the middle. But I doubt we will end up with a model that makes aliasing requirements for nested references. There has not been a credible proposal for how to even do that in a systematic way.

I believe this update posted by Jeroen Dobbelaere after the recent LLVM roundtable is relevant to this thread https://discourse.llvm.org/t/aa-ptr-provenance-full-restrict-llvm-dev-round-table-summary/66722

TLDR: the LLVM machinery to enable full alias analysis and optimizations seems to be closing in to the last stretch.

Jeroen has been working on this feature for the last couple of years, and progress on the review of his patches has been slow.

At the roundtable though, there was unanimous agreement from the participants for the need to add these patches to LLVM, which is very good news to me. There were also reports from Google, who spent time extensively testing the feature, who said that to their eyes it seemed solid.

Anyway, thought it might be useful for some of y'all to have an update on how things are going on the backend side. Have a good weekend! ❤️

(PS: I'm sorry I pinged a lot of you at the wrong thread aaaaa)

Now we just need someone to figure out how that patchset relates to Stacked Borrows. :)

If my understanding of LLVM noalias scopes is correct, using them for Rust is non-trivial, at least with our current aliasing models. This is because determining the exact noaliasing scope of a reference can be non-trivial:

let r = &mut *ptr;
*r = 13;
extern_fn();
*r = 15;

The scope does not necessarily extend all the way to the end of the function because extern_fn may loop forever or unwind, and in those cases both Stacked Borrows and Tree Borrows do allow r to be invalidated by operations in extern_fn (since r is never used again).

Without a more precise description of what exactly the semantics of noalias scopes are in all conceivable corner cases, it's really hard to say how Rust could use them.

Navigation Menu

Repository navigation

make use of LLVM's scoped noalias metadata #16515

16 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

make use of LLVM's scoped noalias metadata #16515

Description

Activity

luqmana commented on Aug 22, 2014

thestinger commented on Aug 22, 2014

mahkoh commented on Nov 19, 2015

steveklabnik commented on Sep 30, 2017

varkor commented on Dec 12, 2017

varkor commented on Dec 12, 2017

varkor commented on Dec 21, 2017

varkor commented on Jan 10, 2018

nox commented on Mar 31, 2018

16 remaining items

RalfJung commented on Sep 1, 2022

cuviper commented on Sep 1, 2022

RalfJung commented on Sep 1, 2022

felix91gr commented on Sep 1, 2022

cuviper commented on Sep 1, 2022

RalfJung commented on Sep 1, 2022

felix91gr commented on Sep 1, 2022

nikic commented on Sep 2, 2022

RalfJung commented on Sep 2, 2022

archshift commented on Sep 3, 2022

RalfJung commented on Sep 3, 2022

felix91gr commented on Nov 25, 2022

RalfJung commented on Dec 5, 2022

RalfJung commented on Dec 14, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions