Module rustc_mir_transform::gvn
source · Expand description
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 a 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 Rvalue
s 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
Structs
Enums
- Value 🔒