Merging Codegen Units by Overlap: How rustc Decides What Goes in the Same .o File

TL;DR: -Ccodegen-units=16 does not mean “split into 16 equal pieces”. rustc first groups items by their characteristic DefId, producing as many groups as there are items, and then merges groups until the count fits. The merge picks, at each step, the pair with the largest overlap of inlined items — because duplicated inlined code is what makes LLVM’s job harder.

Code generation units (CGUs) are the compilation units LLVM sees. More CGUs means more parallelism but worse code, because code that gets inlined across a CGU boundary has to be duplicated rather than shared.

Step one: characteristic DefId

// compiler/rustc_monomorphize/src/partitioning.rs:219-281

for mono_item in mono_items {
    // Handle only root (GloballyShared) items directly here. Inlined (LocalCopy) items
    // are handled at the bottom of the loop based on reachability, with one exception.
    // The #[lang = "start"] item is the program entrypoint, so there are no calls to it in MIR.
    // So even if its mode is LocalCopy, we need to treat it like a root.
    match mono_item.instantiation_mode(cx.tcx) {
        InstantiationMode::GloballyShared { .. } => {}
        InstantiationMode::LocalCopy => continue,
    }

    let characteristic_def_id = characteristic_def_id_of_mono_item(cx.tcx, mono_item);
    let is_volatile = is_incremental_build && mono_item.is_generic_fn();

    let cgu_name = match characteristic_def_id {
        Some(def_id) => compute_codegen_unit_name(
            cx.tcx,
            cgu_name_builder,
            def_id,
            is_volatile,
            cgu_name_cache,
        ),
        None => fallback_cgu_name(cgu_name_builder),
    };

The “characteristic DefId” is the item whose source the monomorphised item came from — the generic function it was instantiated from. Items instantiated from the same generic function are put in the same CGU, because they will want to inline each other.

Note the is_volatile flag: in an incremental build, a generic function’s CGU is marked volatile so that changing the generic invalidates it.

Step two: the merge

// compiler/rustc_monomorphize/src/partitioning.rs:330-382

// If N is the maximum number of CGUs, and the CGUs are sorted from largest
// to smallest, we repeatedly find which CGU in codegen_units[N..] has the
// greatest overlap of inlined items with codegen_units[N-1], merge that
// CGU into codegen_units[N-1], then re-sort by size and repeat.
//
// We use inlined item overlap to guide this merging because it minimizes
// duplication of inlined items, which makes LLVM be faster and generate
// better and smaller machine code.
//
// Why merge into codegen_units[N-1]? We want CGUs to have similar sizes,
// which means we don't want codegen_units[0..N] (the already big ones)
// getting any bigger, if we can avoid it. When we have more than N CGUs
// then at least one of the biggest N will have to grow. codegen_units[N-1]
// is the smallest of those, and so has the most room to grow.
let max_codegen_units = cx.tcx.sess.codegen_units().as_usize();
while codegen_units.len() > max_codegen_units {
    // Sort small CGUs to the back.
    codegen_units.sort_by_key(|cgu| cmp::Reverse(cgu.size_estimate()));

    let cgu_dst = &codegen_units[max_codegen_units - 1];

    // Find the CGU that overlaps the most with `cgu_dst`. In the case of a
    // tie, favour the earlier (bigger) CGU.
    let mut max_overlap = 0;
    let mut max_overlap_i = max_codegen_units;
    for (i, cgu_src) in codegen_units.iter().enumerate().skip(max_codegen_units) {
        if cgu_src.size_estimate() <= max_overlap {
            // None of the remaining overlaps can exceed `max_overlap`, so
            // stop looking.
            break;
        }

        let overlap = compute_inlined_overlap(cgu_dst, cgu_src);
        if overlap > max_overlap {
            max_overlap = overlap;
            max_overlap_i = i;
        }
    }

    let mut cgu_src = codegen_units.swap_remove(max_overlap_i);
    let cgu_dst = &mut codegen_units[max_codegen_units - 1];

    // Move the items from `cgu_src` to `cgu_dst`. Some of them may be
    // duplicate inlined items, in which case the destination CGU is
    // unaffected. Recalculate size estimates afterwards.
    cgu_dst.items_mut().append(cgu_src.items_mut());
    cgu_dst.compute_size_estimate();

Four design decisions, each explained in the comments:

1. The destination is always codegen_units[N-1] — the smallest of the N keepers. Merging into the smallest unit keeps the sizes balanced: the big ones do not grow, and the one that grows has the most headroom.

2. The metric is inlined-item overlap, not size and not call count. Duplicated inlined code is the thing that hurts LLVM: it inflates the IR, defeats cross-CGU inlining, and produces worse machine code.

3. The search can stop early. If a candidate CGU’s size estimate is already below the best overlap found so far, it cannot possibly beat it (overlap is bounded by the smaller size), so the scan breaks. That turns an O(n²) scan into something much cheaper in practice.

4. swap_remove instead of remove: O(1) instead of O(n), and the order of the remaining CGUs does not matter because they are re-sorted at the top of each iteration anyway.

Why not just make 16 equal CGUs?

Because there is no natural “equal split”. The items in a crate have wildly different sizes, and the interesting structure is which items inline each other. A partition that respects the inlining structure beats a partition that respects the item count.

Internalization

After partitioning, symbols that are only used within one CGU can be internalized (made non-exported), which lets the linker and LLVM work better. This is why CGU names matter: the name encodes the characteristic DefId, so the symbol naming is stable across builds.

Where it lives

• compiler/rustc_monomorphize/src/partitioning.rs — the whole algorithm.
• compiler/rustc_codegen_ssa/src/base.rs — the incremental reuse of CGUs.

Note the file location: partitioning moved out of rustc_codegen_ssa into rustc_monomorphize, because partitioning is a monomorphisation concern, not a codegen concern. The compiler front-end decides what exists and where it goes; the backend just compiles what it is handed.

Takeaway

This is a nice example of a heuristic that is not “make the groups equal”. The thing you actually care about — LLVM’s ability to inline without duplicating work — is a graph property (which items want to be near which), and the partition should respect the graph, with size balance as a secondary constraint. The code even says so: “We use inlined item overlap to guide this merging because it minimizes duplication of inlined items, which makes LLVM be faster and generate better and smaller machine code.”