Module move_elimination 

Eliminates copies and moves by unifying MIR places whose allocation ranges are disjoint.

See RFC 3943 for the local-lifetime semantics that make this optimization possible.

Motivation

MIR building can insert a lot of redundant copies, and Rust code in general often tends to move values around a lot. The result is a lot of assignments of the form dest = {move} src; in MIR. MIR building for constants in particular tends to create additional locals that are only used inside a single block to shuffle a value around unnecessarily.

Additionally, Rust constructs nested aggregates by repeatedly moving values into fields. For example, a function may build an inner value in a local, move it into an outer aggregate, then move that aggregate into the caller’s destination. If these intermediate source and destination places have different addresses, each layer needs an actual copy or move of the bytes.

LLVM cannot remove these copies when both the source and destination addresses are observed because merging the allocations would be an observable change: the program could see that two addresses which were previously distinct have become the same. This pass removes the copies earlier, while MIR still has the information needed to prove that the two allocation ranges do not overlap.

Optimization

The basis of this optimization is place unification. If the source and destination of an assignment have the same address, then the assignment is a no-op. The same idea applies to aggregate construction: if a field operand is already located at the corresponding field of the destination, then the aggregate assignment does not need to copy those fields.

The pass represents each unification as a mapping from a local to the place that should replace it. Mappings are transitive, so _3 can be resolved through _2.1 to _1.0.1 if earlier mappings established those relationships.

The mapping is built by scanning the MIR for assignment statements. For simple Use assignments, it tries to unify the source and destination places. For Aggregate assignments, it tries to map each field operand to the corresponding field in the assignment destination. Once all mappings have been chosen, they are applied with one rewrite pass over the body.

Constraints

Adding a mapping must preserve these conditions:

• At least one side of the candidate pair must be a bare local. The pass can map a local to a place with projections, but it cannot map between two places that both already have projections.

• Any projections in the mapped place must be stable everywhere the local is used. Deref and Index projections are rejected because they may refer to different memory at different points in the function.

• The allocation ranges of the source and destination places must not overlap. This is checked using PreciseLiveness, which computes the points where each local must have a distinct allocation. The non-overlap proof is required so that the operational semantics can allow both places to have the same address.

• Special-use locals such as arguments and the return place must keep their roles. Temps may be mapped into an argument or return place, but two special-use locals are not mapped into each other.

• Some locals are used in contexts where projections cannot be added, such as Index projections. These locals may only be replaced by another bare local.

Storage reconstruction

The original StorageLive and StorageDead statements no longer describe the merged liveness produced by unification, so they are removed and rebuilt from the liveness matrix when lifetime markers are emitted. This is done for all locals, even ones that have not been merged, which has the additional benefit of tightening the storage lifetime passed to LLVM.

Aliasing fixup

MIR assignments currently require source and destination places not to overlap for types that are not treated as scalars in codegen. After local unification, some assignments may violate that invariant, so a final phase rewrites them into a form codegen can handle. For each assignment:

• Self-assignments, such as _1 = _1, are deleted.

• Simple Use assignments whose source and destination overlap but are not identical are routed through a temporary: the source is read into the temporary first, and the temporary is then moved into the destination.

• Aggregate assignments with any operand that aliases the destination are decomposed into per-field assignments. Field self-assignments are dropped. Other aliasing fields are read into temporaries first, then all destination fields are written. For enum aggregates the discriminant is set after fields are written.

• Other rvalues, such as Repeat and Cast, are hoisted into a temporary if any place they access aliases the destination.

• Rvalues that operate only on scalar types, such as binary and unary ops, Discriminant, Ref, and RawPtr, are left untouched because their codegen does not rely on the no-aliasing assumption.

Re-exports

use std::range::RangeInclusive; 🔒

use rustc_abi::ExternAbi; 🔒

use rustc_abi::FieldIdx; 🔒

use rustc_abi::VariantIdx; 🔒

use rustc_const_eval::util::most_packed_projection; 🔒

use rustc_data_structures::fx::FxHashMap; 🔒

use rustc_index::IndexVec; 🔒

use rustc_index::bit_set::DenseBitSet; 🔒

use rustc_index::interval::SparseIntervalMatrix; 🔒

use rustc_middle::mir::visit::MutVisitor; 🔒

use rustc_middle::mir::visit::NonUseContext; 🔒

use rustc_middle::mir::visit::PlaceContext; 🔒

use rustc_middle::mir::visit::VisitPlacesWith; 🔒

use rustc_middle::mir::visit::Visitor; 🔒

use rustc_middle::ty::Ty; 🔒

use rustc_middle::ty::TyCtxt; 🔒

use rustc_mir_dataflow::impls::DefUse; 🔒

use rustc_mir_dataflow::impls::SplitPointEffect; 🔒

use rustc_mir_dataflow::impls::SplitPointIndex; 🔒

use rustc_mir_dataflow::impls::VisitAllocatedLocalsWith; 🔒

use rustc_mir_dataflow::impls::dump_liveness_matrix; 🔒

use rustc_mir_dataflow::impls::liveness_matrix; 🔒

use rustc_mir_dataflow::points::DenseLocationMap; 🔒

use rustc_mir_dataflow::Analysis; 🔒

use rustc_mir_dataflow::Backward; 🔒

use rustc_mir_dataflow::GenKill; 🔒

use rustc_mir_dataflow::ResultsVisitor; 🔒

use rustc_mir_dataflow::visit_results; 🔒

use tracing::debug; 🔒

use tracing::trace; 🔒

use crate::PassPolicy; 🔒

use crate::patch::MirPatch; 🔒

use rustc_middle::mir::*; 🔒

Structs

AliasFixup 🔒

InitializedBeforeUse 🔒

Backward dataflow analysis which answers the question: from this point, is there a path whose first access to a local is an initialization?

MoveElimination 🔒

PlaceUnification 🔒

PlaceUpdater 🔒

UnprojectableLocals 🔒

Set of locals which can only be replaced with another local, instead of an arbitrary place. This is usually because it is used directly as a Local outside of a place (e.g. Index projections).

Enums

RangeBoundary 🔒

Live range boundary within a block which indicates where a storage statement should be inserted.

Functions

apply_alias_fixup 🔒

apply_mappings 🔒

check_projections 🔒

Since we are replacing all uses of a local with another place, we need to ensure that the projections on that place are stable no matter where it is used in the body. Additional this local may be used in debuginfo, so ensure that the projections are compatible with usage in debuginfo.

find_rust_call_tuples 🔒

Search for tuple locals passed to calls using the “rust-call” ABI.

get_or_split_edge 🔒

Helper function to split a critical edge if necessary.

places_directly_alias 🔒

Returns whether 2 places alias, ignoring indirect places.

reconstruct_storage 🔒

Re-constructs storage statements for all locals.

split_range_by_block 🔒

Splits a live interval at block boundaries, returning the location at which storage statements need to be inserted at the start and end of the range.