Module rustc_mir_transform::gvn

Global value numbering.

MIR may contain repeated and/or redundant computations. The objective of this pass is to detect such redundancies and re-use the already-computed result when possible.

In a first pass, we compute a symbolic representation of values that are assigned to SSA locals. This symbolic representation is defined by the Value enum. Each produced instance of Value is interned as a VnIndex, which allows us to cheaply compute identical values.

From those assignments, we construct a mapping VnIndex -> Vec<(Local, Location)> of available values, the locals in which they are stored, and the assignment location.

In a second pass, we traverse all (non SSA) assignments x = rvalue and operands. For each one, we compute the VnIndex of the rvalue. If this VnIndex is associated to a constant, we replace the rvalue/operand by that constant. Otherwise, if there is an SSA local y associated to this VnIndex, and if its definition location strictly dominates the assignment to x, we replace the assignment by x = y.

By opportunity, this pass simplifies some Rvalues based on the accumulated knowledge.

Operational semantic

Operationally, this pass attempts to prove bitwise equality between locals. Given this MIR:

_a = some value // has VnIndex i
// some MIR
_b = some other value // also has VnIndex i

We consider it to be replacable by:

_a = some value // has VnIndex i
// some MIR
_c = some other value // also has VnIndex i
assume(_a bitwise equal to _c) // follows from having the same VnIndex
_b = _a // follows from the `assume`

Which is simplifiable to:

_a = some value // has VnIndex i
// some MIR
_b = _a

Handling of references

We handle references by assigning a different “provenance” index to each Ref/AddressOf rvalue. This ensure that we do not spuriously merge borrows that should not be merged. Meanwhile, we consider all the derefs of an immutable reference to a freeze type to give the same value:

_a = *_b // _b is &Freeze
_c = *_b // replaced by _c = _a

Determinism of constant propagation

When registering a new Value, we attempt to opportunistically evaluate it as a constant. The evaluated form is inserted in evaluated as an OpTy or None if evaluation failed.

The difficulty is non-deterministic evaluation of MIR constants. Some Const can have different runtime values each time they are evaluated. This is the case with Const::Slice which have a new pointer each time they are evaluated, and constants that contain a fn pointer (AllocId pointing to a GlobalAlloc::Function) pointing to a different symbol in each codegen unit.

Meanwhile, we want to be able to read indirect constants. For instance:

static A: &'static &'static u8 = &&63;
fn foo() -> u8 {
    **A // We want to replace by 63.
}
fn bar() -> u8 {
    b"abc"[1] // We want to replace by 'b'.
}

The Value::Constant variant stores a possibly unevaluated constant. Evaluating that constant may be non-deterministic. When that happens, we assign a disambiguator to ensure that we do not merge the constants. See duplicate_slice test in gvn.rs.

Second, when writing constants in MIR, we do not write Const::Slice or Const that contain AllocIds.

Structs

• GVN
• StorageRemover 🔒
• VnIndex 🔒
• VnState 🔒

Enums

• AddressKind 🔒
• AggregateTy 🔒
  Computing the aggregate’s type can be quite slow, so we only keep the minimal amount of information to reconstruct it when needed.
• Value 🔒

Functions

• op_to_prop_const 🔒
• propagate_ssa 🔒