Landing the MIR move elimination optimization

[Amanieu]

Duration: 1h

Description:

RFC: rust-lang/rfcs#3943
Project goal: rust-lang/goals#396

The prototype implementation at rust-lang/rust#156046 shows promising results, with a 2-7% speedup on the compiler itself. However landing it is challenging because it changes the semantics of some MIR operations.

The session will start with an overview of the optimization and then dive into the potentially contentious topics:

• Assignments now allow overlapping source and destination as long as they are from different allocations.
• Moves of a whole local now effectively act as a StorageDead, meaning that any access to it is UB after the move (e.g. via raw pointers).
• The pass uses a liveness analysis that requires StorageDead on unwind paths to determine whether 2 locals are allowed to share the same address. These need to be preserved through most of the mir-opt pipeline.
• The pass deletes all storage statements and re-construct them from scratch from liveness information.
• Is DSE allowed to shrink the live range of locals?
• Impact on debuginfo statements (which only support a Local instead of a Place for the destination).
• How the coroutine pass can take advantage of this optimization for smaller coroutines.

This session is of interest to @rust-lang/wg-mir-opt and @tmandry (for the impact on the coroutine transform).

[tmandry]

This session is of interest to @rust-lang/wg-mir-opt and @tmandry (for the impact on the coroutine transform).

also cc @dingxiangfei2009 @folkertdev

[tmandry]

Changing MIR move semantics wrt StorageLive is discussed in rust-lang/rust#61849

[steffahn]

My notes during the session:

Presenting RFC document. Questions / sub-discussion arising during that:

[I'm not noting down things that are (basically) already explained in the RFC.]

Questions & answered separated by “|”.

It's currently legal for unsafe code to write into that space after moved out/deinitialized? | Yes, we would change this. Ralf would be fine with this. (Ralf not in the room yet at this point)

How common is this? | There is a motivating example (with "Inner"&"Outer" in the doc). Array array is copied 5 times, LLVM only eliminates 2 of them at the moment. Notably for "let mut x = Outer…" … before inner…

Tyler notes that things are also relevant for coroutines, Amanieu agrees.

Noticeable effect: Moving out of a variable, and back in again, can make its address change. (Initial design avoided this, but becomes too complicated.)

Does normal assignment to (already initialized variable) make the thing dead, then live again (in a way that this can result in the location changing places)? | Unresolved question, we'll come to this later.

Is there any way to extend the semantics to also work with copy(ing), not just move? | It does happen if the copy(able) value has never been borrowed. Otherwise, its lifetime is longer. If some optimization gets rid of a borrow completely, it would also work.

---

Discussion continues after having concluded looking through the document (I only noted down some discussion points that I was able to understand and follow quickly enough.)

There is one issue I have not yet put into the RFC, about dead stores: Looking at example

struct Foo([u8; 100]);

unsafe extern "C" {
    safe fn observe(b: *mut Foo);
    safe fn foo() -> Foo;
}

pub fn example() {
	let mut a;
	let mut b;
    a = foo();
    observe(&raw mut a);
    b = a;
    observe(&raw mut b);
}

in this case, we agreed b is allowed to overlap a because the former's lifetime ends starts after the former begins.

But what if I do:

struct Foo([u8; 100]);

unsafe extern "C" {
    safe fn observe(b: *mut Foo);
    safe fn foo() -> Foo;
}

pub fn example() {
	let mut a;
	let mut b;
	
	b = foo(); // added
	
    a = foo();
    observe(&raw mut a);
    b = a;
    observe(&raw mut b);
}

Dead store elimination may get rid of the first b = foo() assignment… and then a and b become merged even though they co-exist.

---

There is two solutions: Either argue that a and b exist at the same time and thus it's disallowed to merge them.

The other solution: Let it be equivalent to

struct Foo([u8; 100]);

unsafe extern "C" {
    safe fn observe(b: *mut Foo);
    safe fn foo() -> Foo;
}

pub fn example() {
	let mut a;
	let mut b;
	
	b1 = foo(); // added
	
    a = foo();
    observe(&raw mut a);
    b2 = a;
    observe(&raw mut b);
}

(Ralf makes disapproving noises)

It might go against expectations of C programmers. Similar to things that Miri already tried something similar with killing all borrows on assignment (?or something like this?)

---

Some C code we are looking at:

b = &c;
c = 4;
*b == 4

similarly in Rust

b = &raw c;
c = 4;
*b == 4

(I didn't catch the minor discussion around how that relates)

---

The approach that wants to prevent b to change address in the previous example function could include emitting some marker of liveness into mir once again, so that the dead store doesn't fully disappear.

What are cases that actually introduce new UB then? | See "Potentially Breaking Changes" section (first example).

Do we have crater for miri? | Not really..

It feels like we don't need StorageLive and StorageDead anymore? | We do need StorageDead.

Why is there a distinction between "dead" and "not yet initializied"? | It's for LLVM lifetime statements. StorageDead has dual-purpose (for LLVM, and for killing borrows), StorageLive is only for LLVM.

Is StorageLive always immediately before an assignment; if so, could it just be a flag/bit for the assignment itself? | No, StorageLive can also appear on control-flow edges.

Can we wish for a better interface for LLVM so we don't need that additional StorageLive approximation?

Is there a way to get a flag on StorageLive about whether the previous value was initialized? [Unclear question to me... also no answers.]

StorageLive could be replaced by an assignment (initialization) with undefined value?

Towards the end, people are looking at https://perf.rust-lang.org/compare.html?start=9128490ab32b5ab37a4bb9f6667a9ce5d32924c0&end=4eca0f31a0f5e100354734a70c8023dd16a08796&stat=instructions:u