Opensource internals

Why rustc's GVN Refuses to Merge Two Borrows: Provenance as a Type

7 min read Jay Hubbert

Global value numbering in rustc must never merge two &mut borrows, so every pointer value carries a marker type whose Hash and PartialEq impls ICE - making the mistake impossible.

TL;DR: rustc’s global value numbering (GVN) hash-conses rvalues into value numbers, so two structurally identical &mut x expressions would normally get the same number — and then one would be replaced by the other, which is a miscompile. rustc prevents this by attaching a VnOpaque marker to every pointer value, whose Hash and PartialEq implementations are unreachable!(). The mistake is not “unlikely”, it is impossible.

GVN (global value numbering) is a MIR optimization that finds redundant computations. It works by turning each rvalue into a Value, interning equal values into the same index, and then replacing a use with an earlier definition when that definition dominates the use.

rust 
// compiler/rustc_mir_transform/src/gvn.rs:286-306

/// Stores and deduplicates pairs of `(Value, Ty)` into in `VnIndex` numbered values.
///
/// This data structure is mostly a partial reimplementation of `FxIndexMap<VnIndex, (Value, Ty)>`.
/// We do not use a regular `FxIndexMap` to skip hashing values that are unique by construction,
/// like opaque values, address with provenance and non-deterministic constants.
struct ValueSet<'a, 'tcx> {
    indices: HashTable<VnIndex>,
    hashes: IndexVec<VnIndex, u64>,
    values: IndexVec<VnIndex, Value<'a, 'tcx>>,
    types: IndexVec<VnIndex, Ty<'tcx>>,
}

Notice the comment: values that are “unique by construction” are not hashed. The ValueSet has an insert_unique path for those, which pushes a new index without ever consulting the hash table.

The problem GVN must not have

Consider:

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

The two &_a rvalues are structurally identical. A naive GVN would give them the same value number and rewrite _y = &_a into _y = _x. But between the two borrows, _a was overwritten — so _x and _y point at different things (in the aliasing model, _x refers to the old value of _a). Rewriting would be a miscompile and, under Stacked Borrows, a soundness violation.

The fix could be to include the borrow site in the value. But that is not enough: two borrows from the same site at different times are still different values.

The fix: a marker type that cannot be compared

rustc’s solution is a dedicated marker type:

rust 
// compiler/rustc_mir_transform/src/gvn.rs:196-212

/// 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`.
#[derive(Copy, Clone, Debug, Eq)]
struct VnOpaque;
impl PartialEq for VnOpaque {
    fn eq(&self, _: &VnOpaque) -> bool {
        // ICE if we try to compare unique values
        unreachable!()
    }
}
impl Hash for VnOpaque {
    fn hash<T: Hasher>(&self, _: &mut Hasher) {
        // ICE if we try to hash unique values
        unreachable!()
    }
}

This is a lovely piece of API design. VnOpaque is embedded in the pointer value:

rust 
// compiler/rustc_mir_transform/src/gvn.rs:259-268

/// The address of a place.
Address {
    base: AddressBase,
    // We do not use a plain `Place` as we want to be able to reason about indices.
    // This does not contain any `Deref` projection.
    projection: &'a [ProjectionElem<VnIndex, Ty<'tcx>>],
    kind: AddressKind,
    /// Give each borrow and pointer a different provenance, so we don't merge them.
    provenance: VnOpaque,
},

Because VnOpaque implements Eq but its PartialEq::eq is unreachable!(), any code path that tries to compare two pointer values would panic — in debug builds at least, and in release builds it is unreachable!() which LLVM compiles to unreachable (undefined behaviour) or a trap depending on the panic strategy.

The safety comes from the invariant that pointer values are only ever inserted through insert_unique:

rust 
// compiler/rustc_mir_transform/src/gvn.rs:308-330

which pushes a fresh index without consulting the hash table at all. Two borrows therefore always get different VnIndexes, and the comparison path is never reached.

This is the “make the illegal state unrepresentable” principle applied to an optimization bug class. The alternative — a disambiguator: u32 field that gets hashed — works too, but it is merely unlikely to be wrong; VnOpaque makes it impossible.

But the pointee is still tracked

The trick does not throw away information. The place being borrowed is still part of the value, so GVN can still reason about *&_a:

rust 
// compiler/rustc_mir_transform/src/gvn.rs:482-517

fn new_pointer(&mut self, place: Place<'tcx>, kind: AddressKind) -> Option<VnIndex> {
    ...
    let mut projection = place.projection.iter();
    let base = if place.is_indirect_first_projection() {
        let base = self.locals[place.local]?;
        // Skip the initial `Deref`.
        projection.next();
        AddressBase::Deref(base)
    } else if self.ssa.is_ssa(place.local) {
        // Only propagate the pointer of the SSA local.
        AddressBase::Local(place.local)
    } else {
        return None;
    };

So the value is “the address of local 3’s field 1, with fresh provenance”. Two such values are never equal, but GVN still knows what they point at, which lets it rewrite *&x into x when appropriate.

Constants have the same problem, for a different reason

Not all constants are interchangeable either. A Const::Ty (a valtree) can synthesize a fresh allocation each time it is instantiated, so two uses of the same valtree constant may be different pointers:

rust 
// compiler/rustc_mir_transform/src/gvn.rs:1860-1886

/// 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.
///
/// In other words, this answers: is "cloning" the `Const` ok?
///
/// This returns `false` for constants that synthesize new allocations when they are instantiated.
/// It is `true` for anything else, since a given `AllocId` *does* have a unique runtime value
/// within the scope of a single MIR body.
fn is_deterministic(c: Const<'_>) -> bool {
    // Primitive types cannot contain provenance and always have the same value.
    if c.ty().is_primitive() {
        return true;
    }

    match c {
        // Some constants may generate fresh allocations for pointers they contain,
        // so using the same constant twice can yield two different results.
        // Notably, valtrees purposefully generate new allocations.
        Const::Ty(..) => false,
        // We do not know the contents, so don't attempt to do anything clever.
        Const::Unevaluated(..) => false,
        // When an evaluated constant contains provenance, it is encoded as an `AllocId`.
        // Cloning the constant will reuse the same `AllocId`. If this is in the same MIR
        // body, this same `AllocId` will result in the same pointer in codegen.
        Const::Val(..) => true,
    }
}

and the insertion path branches on it:

rust 
// compiler/rustc_mir_transform/src/gvn.rs:519-533

fn insert_constant(&mut self, value: Const<'tcx>) -> VnIndex {
    if is_deterministic(value) {
        // The constant is deterministic, no need to disambiguate.
        let constant = Value::Constant { value, disambiguator: None };
        self.insert(value.ty(), constant)
    } else {
        // Multiple mentions of this constant will yield different values,
        // so assign a different `disambiguator` to ensure they do not get the same `VnIndex`.
        self.insert_unique(value.ty(), |disambiguator| Value::Constant {
            value,
            disambiguator: Some(disambiguator),
        })
    }
}

The module header explains the third case:

text 
//! # 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`.

Where it lives

  • compiler/rustc_mir_transform/src/gvn.rs — VnOpaque, ValueSet, new_pointer, insert_constant, is_deterministic.

Takeaway

When you have a class of values that must never be equal, do not give them a “probably different” disambiguator. Give them a marker type whose equality is a trap, route them through a separate insertion path, and let the type system carry the invariant. The compiler bug this prevents — merging two mutable borrows — is exactly the kind that survives years of testing, because the trigger is rare and the symptom is a wrong answer rather than a crash.

RustInternalsCompilerMirOptimizationPerformance