end(X) Doesn't Live in the CFG: How rustc Splits Region Values Into Three Dimensions

TL;DR: To ask “does 'a outlive 'b?”, the borrow checker needs a way to refer to the end of a universally quantified region 'b. The obvious encoding is a distinguished point in the CFG — but that would break the interval-set compression that region liveness depends on. rustc instead keeps three independent sparse dimensions per region (program points, free regions, placeholders), and end(X) is simply “X is in the free-region row”.

Region inference produces, for each region, the set of program points where the region is live. That’s the classic picture: a region is a set of CFG points.

But the borrow checker also has to answer questions of the form “does 'a outlive 'b?” where both are named lifetime parameters. To express that, you need a marker for the end of 'b — a distinguished point that says “‘b’ is over here”. And here the design gets interesting.

The naive encoding and why it hurts

If end(X) is a program point, then every region value has to contain the end markers of every region it outlives. A region that outlives five named lifetimes carries five extra points in its set.

That sounds cheap. It is not, because region liveness is stored as an interval set, and the whole reason it is an interval set is that the liveness of a region is contiguous:

// compiler/rustc_index/src/interval.rs:19-24

#[derive(Debug, Clone)]
pub struct IntervalSet<I> {
    // Start, end (both inclusive)
    map: SmallVec<[(u32, u32); 2]>,
    domain: usize,
    _data: PhantomData<I>,
}

Two intervals inline, a SmallVec that spills to the heap only if you have more than two runs. If you inject a handful of scattered “end marker” points into every region’s set, you shatter those runs: a region that used to be two intervals becomes ten, the SmallVec spills, and every union gets more expensive.

The other problem is space. The point index space would grow by the number of named lifetimes, and every region’s interval set would grow with it, even the regions that have nothing to do with those lifetimes.

The actual representation

rustc splits the value into three independent dimensions:

// compiler/rustc_borrowck/src/region_infer/values.rs:267-276

pub(crate) struct RegionValues<'tcx, N: Idx> {
    location_map: Rc<DenseLocationMap>,
    placeholder_indices: PlaceholderIndices<'tcx>,
    points: SparseIntervalMatrix<N, PointIndex>,
    free_regions: SparseBitMatrix<N, RegionVid>,

    /// Placeholders represent bound regions -- so something like `'a`
    /// in `for<'a> fn(&'a u32)`.
    placeholders: SparseBitMatrix<N, PlaceholderIndex>,
}

Three matrices:

• points — where in the CFG the region is live. Interval sets, because this dimension is contiguous.
• free_regions — which named lifetimes the region outlives. A bit matrix, because this dimension is sparse and scattered by nature.
• placeholders — which higher-ranked binders the region outlives.

Each dimension uses the representation that fits its data. That is the whole trick: the CFG dimension gets interval compression, and the “outlives named lifetime X” dimension gets a sparse bit matrix, and neither pays for the other’s shape.

end(X) becomes free

Now look at how free regions are seeded:

// compiler/rustc_borrowck/src/region_infer/region_context.rs:143-175

// Initializes the region variables with their initial live points.
for (region, definition) in definitions.iter_enumerated() {
    let scc = constraint_sccs.scc(region);

    // For each universally quantified region (lifetime parameter). The
    // first N variables always correspond to the regions appearing in
    // the function signature (both named and anonymous) and in where-clauses.
    match definition.origin {
        // For each free, universally quantified region X:
        NllRegionVariableOrigin::FreeRegion => {
            // Add `end(X)` into the set for X.
            scc_values.add_free_region(scc, region);
        }

        NllRegionVariableOrigin::Placeholder(placeholder) => {
            scc_values.add_placeholder(scc, placeholder);
        }

        NllRegionVariableOrigin::Existential { .. } => {
            // For existential, regions, nothing to do.
        }
    }

The comment says “Add end(X) into the set for X” — but the implementation is add_free_region, which sets a bit in the free_regions matrix. There is no point, no offset, no sentinel. end(X) is the presence of X in the free-region row of that SCC.

And the consumption side reads it back out of the same dimension:

// compiler/rustc_borrowck/src/region_infer/region_context.rs:1466-1474

/// Checks the final value for the free region `fr` to see if it
/// grew too large. In particular, examine what `end(X)` points
/// wound up in `fr`'s final value; for each `end(X)` where `X !=
/// fr`, we want to check that `fr: X`. If not, that's either an
/// error, or something we have to propagate to our creator.

The prose still talks about “end(X) points”, because that is the mental model from the classic papers. But the data structure has no such thing anymore: universal_regions_outlived_by is a bit-matrix row lookup.

// compiler/rustc_borrowck/src/region_infer/region_context.rs:1510-1513

// Find every region `o` such that `fr: o`
// (because `fr` includes `end(o)`).
for shorter_fr in self.scc_values.universal_regions_outlived_by(longer_fr_scc) {

Why the union has to touch all three dimensions

The propagation step unions all three:

// compiler/rustc_borrowck/src/region_infer/values.rs:298-304

pub(crate) fn add_region(&mut self, r_to: N, r_from: N) -> bool {
    self.points.union_rows(r_from, r_to)
        | self.free_regions.union_rows(r_from, r_to)
        | self.placeholders.union_rows(r_from, r_to)
}

The | matters: all three unions must happen, and the result is “did anything change”, which is what the SCC propagation loop uses to decide whether the propagation is finished. (It always unions, in the one-pass SCC algorithm — but the boolean is used elsewhere, for example when deciding whether a region’s value actually grew.)

The same split shows up in the diagnostic path

The blame machinery needs to walk the “outlives” relation too, and it uses the same matrix:

// compiler/rustc_borrowck/src/region_infer/region_context.rs:1510-1513

Once you see the dimension split, the awkwardness of the old design disappears: “which regions does this one outlive?” is a bit-matrix row scan, which is exactly as cheap as it should be.

Where it lives

• compiler/rustc_borrowck/src/region_infer/values.rs — RegionValues and the three matrices.
• compiler/rustc_borrowck/src/region_infer/region_context.rs — seeding and consumption of the free-region dimension.
• compiler/rustc_index/src/interval.rs — SparseIntervalMatrix.
• compiler/rustc_data_structures/src/sparse.rs — the sparse bit matrix.

Takeaway

This is a general technique worth stealing: when a data structure needs to carry two kinds of facts that have different shapes — one dense and contiguous, one sparse and scattered — do not force them into one representation. Split the space, give each part the encoding that suits it, and then define the “cross-cutting” queries (like “is X in my set?”) in terms of the part that owns X.

The payoff is that end(X) costs zero extra points in the CFG, so the interval sets that make region inference fast stay small.