Module 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.

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.

We traverse all assignments x = rvalue and operands.

For each SSA one, 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.

For each non-SSA 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 replaceable 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/RawPtr rvalue. This ensure that we do not spuriously merge borrows that should not be merged. For instance:

_x = &_a;
_a = 0;
_y = &_a; // cannot be turned into `_y = _x`!

On top of that, 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 happens with valtrees that generate a new allocation each time they are used. This is checked by is_deterministic.

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.

Conversely, some constants cannot cross function boundaries, which could happen because of inlining. For instance, constants that contain a fn pointer (AllocId pointing to a GlobalAlloc::Function) point to a different symbol in each codegen unit. To avoid this, when writing constants in MIR, we do not write Consts that contain AllocIds. This is checked by may_have_provenance. See https://github.com/rust-lang/rust/issues/128775 for more information.

Re-exports

use std::borrow::Cow; 🔒

use std::hash::Hash; 🔒

use std::hash::Hash; 🔒

use std::hash::Hasher; 🔒

use either::Either; 🔒

use itertools::Itertools as _; 🔒

use rustc_abi as abi; 🔒

use rustc_abi::BackendRepr; 🔒

use rustc_abi::FIRST_VARIANT; 🔒

use rustc_abi::FieldIdx; 🔒

use rustc_abi::Primitive; 🔒

use rustc_abi::Size; 🔒

use rustc_abi::VariantIdx; 🔒

use rustc_arena::DroplessArena; 🔒

use rustc_const_eval::const_eval::DummyMachine; 🔒

use rustc_const_eval::interpret::ImmTy; 🔒

use rustc_const_eval::interpret::Immediate; 🔒

use rustc_const_eval::interpret::InterpCx; 🔒

use rustc_const_eval::interpret::MemPlaceMeta; 🔒

use rustc_const_eval::interpret::MemoryKind; 🔒

use rustc_const_eval::interpret::OpTy; 🔒

use rustc_const_eval::interpret::Projectable; 🔒

use rustc_const_eval::interpret::Scalar; 🔒

use rustc_const_eval::interpret::intern_const_alloc_for_constprop; 🔒

use rustc_data_structures::fx::FxHasher; 🔒

use rustc_data_structures::graph::dominators::Dominators; 🔒

use rustc_data_structures::hash_table::Entry; 🔒

use rustc_data_structures::hash_table::HashTable; 🔒

use rustc_hir::def::DefKind; 🔒

use rustc_index::bit_set::DenseBitSet; 🔒

use rustc_index::IndexVec; 🔒

use rustc_index::newtype_index; 🔒

use rustc_middle::mir::interpret::AllocRange; 🔒

use rustc_middle::mir::interpret::GlobalAlloc; 🔒

use rustc_middle::ty::layout::HasTypingEnv; 🔒

use rustc_middle::ty; 🔒

use rustc_middle::ty::Ty; 🔒

use rustc_middle::ty::TyCtxt; 🔒

use rustc_middle::ty::TypeVisitableExt; 🔒

use rustc_middle::ty::Unnormalized; 🔒

use rustc_mir_dataflow::Analysis; 🔒

use rustc_mir_dataflow::ResultsCursor; 🔒

use rustc_span::DUMMY_SP; 🔒

use rustc_span::bug; 🔒

use smallvec::SmallVec; 🔒

use tracing::debug; 🔒

use tracing::instrument; 🔒

use tracing::instrument; 🔒

use tracing::trace; 🔒

use crate::ssa::MaybeUninitializedLocals; 🔒

use crate::ssa::SsaLocals; 🔒

use crate::PassPolicy; 🔒

use crate::canonicalization; 🔒

use rustc_middle::mir::visit::*; 🔒

use rustc_middle::mir::*; 🔒

Structs

GVN 🔒

StorageChecker 🔒

StorageRemover 🔒

ValueSet 🔒

Stores and deduplicates pairs of (Value, Ty) into in VnIndex numbered values.

VnIndex 🔒

This represents a Value in the symbolic execution.

VnOpaque 🔒

Marker type to forbid hashing and comparing opaque values. This struct should only be constructed by ValueSet::insert_unique to ensure we use that method to create non-unifiable values. It will ICE if used in ValueSet::insert.

VnState 🔒

Enums

AddressBase 🔒

AddressKind 🔒

Value 🔒

Functions

is_deterministic 🔒

Return true if any evaluation of this constant in the same MIR body always returns the same value, taking into account even pointer identity tests.

may_have_provenance 🔒

Check if a constant may contain provenance information. Can return true even if there is no provenance.

op_to_prop_const 🔒