make use of LLVM's scoped noalias metadata

[thestinger]

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.

[luqmana]

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".

[thestinger]

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

[mahkoh]

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

[steveklabnik]

Triage: #38941 is related, as is #31681

[varkor]

@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)?

[varkor]

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.

[varkor]

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.

[varkor]

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.

[nox]

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.

[varkor]

@nox: in particular, we need some examples of test cases that are improved by some alias.scope annotations, which are also sound. I think after we have some concrete examples, it shouldn't prove too difficult to adapt the previous work.

[Manishearth]

IIRC this is blocked on the unsafe code guidelines folks figuring out where aliasing UB starts? cc @RalfJung

[RalfJung]

Sounds reasonable. ;) I'd be hesitant to commit to anything right now though. However, I am fairly close to having a model that (I think) determines some kind of "lower bound" (in the sense of "we want at least this much UB"), so I could try to understand if the examples you have here work under that model. However, longer-term, it'd also be useful for me to actually understand what LLVM's scoped metadata means in general, and how you plan to emit it, so that we can try to get certainty not just for some examples.

So, looking at #16515 (comment), we seem to be in agreement that a cannot be optimized. b should be optimizable under any model we come up with, I hope. Optimizing c is an explicit goal of the "lower bound" model I have been toying around with at the all-hands (and that I plan to work on more during the summer). d is almost equivalent to c (though it doesn't seem unlikely that function boundaries will have some significance), but with b optimizable the same of course holds for d.

@varkor did you mean to write c at the bottom of #16515 (comment)? I thought b is already optimized right now, without additional metadata?

So, the only "new" example here (that would get optimized now but was not optimized before) is c? I think we want that to happen. And I think for shared references, this should not be too hard. Not sure how important it is that we proceed here?

But please hold on with anything related to mutable references. There are some strange corner cases where optimizing within a function is illegal but after moving some code to a separate function it becomes legal:

fn legal(x: &mut i32) { unsafe {
  let x = x as *mut _ as usize;
  let y1 = &mut *(x as *mut i32);
  let y2 = &mut *(y1 as *mut i32 as usize as *mut i32);
  // these two writes are legal -- y2 is reborrowing from y1, but because 
  // we went though usize we cannot possibly track where they are "derived from"
  *y2 = 4;
  *y1 = 3;
  // Using y2 again here would be UB
} }

fn illegal(x: &mut i32) { unsafe {
  let x = x as *mut _ as usize;
  let y1 = &mut *(x as *mut i32);
  let y2 = &mut *(y1 as *mut i32 as usize as *mut i32);

  bar(y1, y2); // this call must trigger UB
} }
fn bar(y1: &mut i32, y2: &mut i32) {
  // we will certainly want to optimize this
  *y2 = 4;
  *y1 = 3;
}

illegal and legal look like they do the same thing, but we have to rule out illegal and most likely have to allow legal. We want to understand this better before we start optimizing more.

[varkor]

@varkor did you mean to write c at the bottom of #16515 (comment)? I thought b is already optimized right now, without additional metadata?

Yes, I did, thanks — I've fixed the comment.

[RalfJung]

It seems that besides the noalias attribute (that Rust already uses) and the noalias metadata (that this issue proposes to use), there is the llvm.noalias intrinsic. And judging from the PR introducing that intrinsic, the metadata has some issues that are solved by the intrinsic.

This issue is older than the intrinsic. With the intrinsic now being available, do y'all think that the intrinsic should be better suited than the metadata for Rust's purpose, or is the metadata still preferred?

(One of the reasons I am asking is that I hope to start looking at LLVM's noalias stuff from a formal perspective, and it'd be helpful if we didn't have to look at three different mechanisms to do very similar things.)

[nikic]

@RalfJung The llvm.noalias intrinsic never landed. In https://bugs.llvm.org/show_bug.cgi?id=39282 Hal mentioned that somebody is working on this area again, but I haven't heard anything since.

[RalfJung]

The llvm.noalias intrinsic never landed.

Oh, seems I misinterpreted the "Accepted" label then.

In that case, take my question as the hypothetical "if those patches landed, would Rust prefer that over the metadata?"^^

[RalfJung]

An RFC has been posted on the LLVM side for extending the support for restrict/noalias: https://lists.llvm.org/pipermail/llvm-dev/2019-March/131127.html

[cuviper]

Here's the followup to that RFC:
http://lists.llvm.org/pipermail/llvm-dev/2019-October/135667.html
https://reviews.llvm.org/D68484

[workingjubilee]

Seems stalled at the moment.

When there are manipulations to a Rust struct that is otherwise a flat "by value" entity, we could consider emitting appropriate information to hint about aliasing or lack thereof. Currently, LLVM avoids making assumptions that it would in fact make for separate variables, even in the same scope.

[archshift]

@bjorn3 @felix91gr taking this conversation here from #82834.

I was under the impression that if, for example, we have:

pub struct Foo<'a, 'b> {
    r1: &'a mut u32,
    r2: &'b mut u32,
}

pub fn use_foo(foo: &mut Foo) -> u32 {
    *foo.r1 = 1;
    *foo.r2 = 2;
    return *foo.r1;
}

There's no case in which we couldn't elide the final load and optimize the last statement of use_foo to return 1;. But because we don't emit scoped aliasing metadata, we get the following optimized LLVM IR:

define i32 @example::use_foo({ i32*, i32* }* noalias nocapture noundef readonly align 8 dereferenceable(16) %0) unnamed_addr #0 !dbg !5 {
  %2 = bitcast { i32*, i32* }* %0 to i32**, !dbg !10
  %3 = load i32*, i32** %2, align 8, !dbg !10, !nonnull !9, !align !11
  store i32 1, i32* %3, align 4, !dbg !10
  %4 = getelementptr inbounds { i32*, i32* }, { i32*, i32* }* %0, i64 0, i32 1, !dbg !12
  %5 = load i32*, i32** %4, align 8, !dbg !12, !nonnull !9, !align !11, !noundef !9
  store i32 2, i32* %5, align 4, !dbg !12
  %6 = load i32, i32* %3, align 4, !dbg !13
  ret i32 %6, !dbg !14
}

[cuviper]

It seems like that example would really want type-level noalias, with Foo something like { i32* noalias, i32* noalias }.

The optimization does work if you pass Foo by value, but only because we split up the ScalarPair into separate args that can each have noalias. That doesn't work if Foo has more than two fields.

[felix91gr]

@archshift I believe your impression is founded. To my eyes, that is already what the semantics should allow to be optimized.

I'm not as versed as cuviper is in LLVM itself, so I'll let them help you on that front ^^

But I do believe that you're right in that the current language model should already allow for that optimization to happen :)

[RalfJung]

@archshift that case is pretty tricky actually since it involves double-indirection. I would agree that the following is definitely noalias:

pub struct Foo<'a, 'b> {
    r1: &'a mut u32,
    r2: &'b mut u32,
}

pub fn use_foo(foo: &mut Foo) -> u32 {
    let r1 = &mut *foo.r1;
    *r1 = 1;
    *foo.r2 = 2;
    return *r1;
}

but I am fairly sure that there are cases where Stacked Borrows would allow your code to pass.

[RalfJung]

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...).

[cuviper]

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

[RalfJung]

@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));
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

[felix91gr]

@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?

[cuviper]

@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?

[RalfJung]

@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.

[felix91gr]

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.

1. 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 ^^.

2. 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 🙂

[nikic]

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.

[RalfJung]

@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.)

[archshift]

@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.

[RalfJung]

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.

[felix91gr]

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)

[RalfJung]

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