MIR move elimination

[nikomatsakis]

Metadata
Point of contact	@Amanieu
Team(s)	compiler, lang, opsem, wg-mir-opt
Goal document	2025h2/mir-move-elimination

Summary

Add a MIR optimization which eliminates move operations. This will require changes to the MIR semantics of move to enable the optimization to cases where a value has had its address taken (LLVM already eliminates moves when this is not the case).

Tasks and status

• Discussion and moral support (lang, compiler )
• Author RFC (@Amanieu)
• Design meeting (opsem, wg-mir-opt )
• RFC decision (lang, compiler )
• Implementation (@Amanieu)

[nikomatsakis]

This issue is intended for status updates only.

For general questions or comments, please contact the owner(s) directly.

[Amanieu]

An RFC draft covering the MIR changes necessary to support this optimization has been written and is currently being reviewed by T-opsem. It has already received one round of review and the feedback has been incorporated in the draft.

[Amanieu]

The RFC draft was reviewed in detail and @RalfJung pointed out that the proposed semantics introduce issues because they rely on "no-behavior" (NB) with regards to choosing an address for a local. This can lead to surprising "time-traveling" behavior where the set of possible addresses that a local may have (and whether 2 locals can have the same address) depends on information from the future. For example:

// This program has DB
let x = String::new();
let xaddr = &raw const x;
let y = x; // Move out of x and de-initialize it.
let yaddr = &raw const y;
x = String::new(); // assuming this does not change the address of x
// x and y are both live here. Therefore, they can't have the same address.
assume(xaddr != yaddr);
drop(x);
drop(y);

// This program has UB
let x = String::new();
let xaddr = &raw const x;
let y = x; // Move out of x and de-initialize it.
let yaddr = &raw const y;
// So far, there has been no constraint that would force the addresses to be different.
// Therefore we can demonically choose them to be the same. Therefore, this is UB.
assume(xaddr != yaddr);
// If the addresses are the same, this next line triggers NB. But actually this next
// line is unreachable in that case because we already got UB above...
x = String::new();
// x and y are both live here.
drop(x);
drop(y);

---

With that said, there is still a possibility of achieving the optimization, but the scope will need to be scaled down a bit. Specifically, we would need to:

• no longer perform a "partial free"/"partial allocation" when initializing or moving out of a single field of a struct. The lifetime of a local starts when any part of it is initialized and ends when it is fully moved out.
• allow a local's address to change when it is re-initialized after having been fully moved out, which eliminates the need for NB.

This reduces the optimization opportunities since we can't merge arbitrary sub-field moves, but it still allows for eliminating moves when constructing a struct from multiple values.

The next step is for me to rework the RFC draft to reflect this.

[Amanieu]

The RFC has just been published as rust-lang/rfcs#3943. It has been significantly reworked since the last draft.

Notable changes:

• Removed the concept of activation/de-activation. Now the semantics don't need to deal with partially allocated locals. This is less powerful optimization-wise but should still cover most cases.
• Added byref/byval to call arguments to clarify how they are passed.
• Added a separate section for the surface language changes to separate it from the MIR changes.
• Added more details on the MIR optimization which eliminates moves.
• Changed the MIR operand evaluation order to be left-to-right, except for destination places which are always evaluated last.
• Added StorageLive back: we need it to mark the location where llvm.lifetime.start should be inserted, which is not the same as the location where a local is initialized. In the opsem, StorageLive doesn't actually allocate the local, that's still done when it is initialized by a write.