Module regalloc 

SSA register allocation: virtual registers to physical registers and stack slots.

The input is a MIR function in SSA form (one definition per virtual register, every use dominated by its definition) in which physical registers appear only in short, block-local ranges: the copies into and out of argument and result registers around calls and returns, the operands of fixed-register instructions (idiv’s rdx:rax, a shift’s cl), and the entry block’s incoming arguments. Instruction selection (isel) produces exactly this. The output is the same function on physical registers, ready for emit.

Algorithm

1. Liveness by SSA path exploration: from each use outside its definition’s block, walk predecessors up to the definition, marking the value live-in on the way. Cost is the size of the live sets, with an explicit budget. It runs once: definitions and uses come from an index built in one walk, and spill rounds update it (below).
2. Constraints in one backward walk per block: which uses are last uses, which physical registers are live after each instruction, and, for each value, every register written while it is live (a call’s clobbers, a fixed-register definition), so the value never sits in one of them.
3. Coloring in dominance order. In strict SSA, two values that interfere have one definition dominating the other, and the first is live where the second is defined; so walking blocks in reverse postorder and giving each value at its definition a register no live value holds is a correct coloring, with no interference graph. Block parameters get registers at their block’s start; the parallel copy on each edge is resolved at emission by the move resolver.
4. Coalescing. Values joined by a copy, a two-address tie, or a block parameter and its arguments form affinity classes (union-find); a value takes its class’s register, its tied operand’s register, or the physical register it is copied to or from, whenever that register is free, so the copy, the tie, or the edge move disappears. It is best effort: a value that interferes with its class takes another register and keeps its move.
5. Spilling when no register is free at a definition: the value with the lowest weight (uses per instruction spanned) among the definition and the values occupying a usable register is spilled for its whole life (spill everywhere: no live-range splitting). A spilled constant or address is rematerialized at each use instead of stored; any other value is stored to a spill slot after its definition and reloaded into a short-lived temporary before each use that cannot read the slot directly (x86-64 reads one memory operand per instruction, and branch arguments and copies read slots as they are). A spilled block parameter simply lives in its slot. Coloring then reruns; temporaries are never spilled, so each round spills at least one more long-lived value, and after MAX_ROUNDS every remaining long-lived value is spilled, which always succeeds.
6. Incremental updates between rounds. Spill code changes liveness in a way that can be stated exactly: every spilled value leaves every live-in set (it is gone, or lives only from its definition to the store after it); each reload temporary lives from just before its user to the user; and spill code reads and writes no physical register. So the live sets, last uses, and fixed-register facts are updated in time proportional to the live sets and the spill code, the affinities only at the instructions that now read a temporary, and only the blocks that received spill code are rebuilt: a round costs one coloring walk, not a liveness analysis.

Callee-saved registers are used like any other; a value live across a call can only sit in one (the call clobbers the rest), and the frame saves exactly the callee-saved registers the function writes.

Stack maps need nothing from the allocator: instruction selection stores each GC reference of a safepoint into a dedicated root slot before the call and reloads the relocated value after it, so no reference is in a register while the collector runs, and the slots are recorded on the call (Function::set_call_site).

Structs

Allocation

What the allocator did.

Options

Allocation settings.

Enums

Location

Where a virtual register lives for its whole life after allocation.

RegAllocError

Why a function could not be allocated.

Constants

DEFAULT_LIVE_BUDGET

The default budget on live-set entries (one per value live into a block): 16 Mi entries, 64 MiB.

MAX_ROUNDS

After this many rounds that still spill, every long-lived value is spilled at once, which always allocates.

Functions

allocate

Allocates registers for f in place with the default Options.

allocate_with

Allocates registers for f in place.