🚀 Register Allocation: Faster Compiler via Linear Scan
Discover how rat redesigns a linear scan register allocator—1,392 lines down to 584—improving codegen, cutting compile time, with spilling & coalescing.
A Smaller Register Allocator That Generates Better Code
A register allocator has a deceptively narrow job: map the unlimited virtual registers used by a compiler's intermediate representation to the limited physical registers on a processor. When there aren't enough registers, the compiler has to spill some values to memory and reload them later. Those choices shape both the code that gets emitted and how long the compiler spends compiling.
In rat, a small compiler backend with a partly working C99 frontend, the existing linear-scan allocator worked - but it had grown to 1,392 lines after a pile of fixes. Instead of adding another optimization on top, its author measured which parts actually helped the generated code, then replaced the allocator with a 584-line priority-based version. The new allocator emitted fewer instructions and fewer stores, and it compiled the tested SQLite workload faster at -O0.
What's interesting isn't just the line count. The allocator also avoids several mechanisms you often see in more sophisticated designs, including register eviction and live-range splitting. Here's how its simpler approach works, what it keeps, and where the trade-offs show up.
Why register allocation is a practical trade-off
A compiler's intermediate representation can use as many virtual registers, or vregs, as it wants. The processor can't. On x86-64, the backend has to assign each vreg to an available physical register, or move it to a stack slot. The assignment is only valid when values that are live at the same time don't overwrite each other.
A value is live from the point where it's defined until its last use. If two values are never live at the same time, they can share a physical register. If too many values are live at once, the allocator must spill some of them: store the value to memory and reload it later. Spilling adds instructions and memory traffic, so the spill decisions matter.
There's no simple rule that always produces the best assignment. Finding an optimal assignment is NP-hard, so production compilers rely on heuristics. The real engineering question isn't whether heuristics are imperfect - they are. The question is whether the extra complexity pays off enough to justify the added implementation and maintenance cost.
Calling conventions make the problem trickier. A function call can overwrite caller-saved registers. So if a value has to stay live across a call, the allocator can't leave it in a caller-saved register unless it's saved somewhere else first. Callee-saved registers must be restored before the function returns, which can mean extra prologue/epilogue instructions.
Take a value that stays live across a call:
long g(long);
long h(long x, long y) {
long t = g(x);
return t + y;
}
x is passed to g in rdi, y arrives in rsi, and the return value comes back in rax. The call may clobber caller-saved registers, but y is still needed after the call. In the example, rat puts y in rbx, a callee-saved register, and saves/restores it around the function.
At -O1, the emitted code stays compact:
push rbp
mov rbp, rsp
sub rsp, 0x8
push rbx
mov rbx, rsi
call g
add rax, rbx
pop rbx
leave
ret
Five of the six copies from the pre-allocation representation disappear. The key point is that rat doesn't rely on a special rule like "cross-call values belong in callee-saved registers." Instead, the call makes caller-saved registers unavailable at that point, and normal register selection lands on rbx.
That's a nice property of the model: the effect falls out of how constraints are represented, not from a dedicated special case. It's also not a universal argument against more advanced allocators. Another backend, workload, architecture, or optimization goal might justify more machinery. The only sensible way to decide is to measure whether it helps in your actual system.
The allocator's five stages
Rat processes each function in five stages: calculate live ranges, mark fixed-register constraints, coalesce compatible copies, assign registers, and spill anything that can't be assigned. The pipeline is intentionally one-way. Once a bundle picks a register (or a stack slot), it keeps it for its full lifetime. The allocator doesn't reclaim registers from earlier choices, split live ranges, or rerun the process.
1. Calculate live ranges
Each instruction has two numbered slots: one for reading operands and one for writing results. Instruction i reads at slot 2i and writes at 2i + 1. A value's live range is represented as a sorted list of slot intervals, so one value can have multiple separate live segments.
The read/write split matters for copies. In a copy, the source's lifetime ends at the read slot and the destination's starts at the write slot. They don't overlap, so the two values can share a register - and the copy may disappear after allocation.
For most other instructions, a source stays live through the write slot. That prevents the allocator from placing a result into a register that would overwrite an operand still needed by the instruction.
For control flow, rat computes which vregs are live out of each basic block - values that might be read in a later block. A common implementation uses a bitset per block and iterates until it reaches a fixed point. Rat does something different: it walks backward only along the blocks where each individual vreg is needed, stopping once it reaches a block that defines the value. This makes the work scale with the number of blocks traversed per vreg, rather than multiplying "all blocks by all vregs."
A backward walk builds the live segments and estimates the spill cost. Each definition/use is weighted based on loop depth: straight-line uses get weight 1, uses in a loop get weight 3, and uses in a doubly nested loop get weight 9. The idea is straightforward - spilling that adds work in a hot loop hurts more than spilling that only affects a cold path.
2. Mark fixed-register constraints
Some instructions require specific physical registers because of the calling convention or the instruction set. Rat tracks this with a 64-bit mask for each slot. If a bit is set, the corresponding register is busy at that slot. Rat numbers registers so a single 64-bit value can represent the available set.
Examples include argument registers around calls, caller-saved registers during a call, and rax when it holds a return value. Division has fixed-register requirements too, involving rax, rcx, and rdx. When rat assigns a bundle to a register, it marks that register busy across every segment of the bundle's live range.
These masks cover both explicit physical-register usage and registers already assigned to vregs. For longer ranges, rat uses a summary mask: the union of every 64 consecutive slot masks. That lets the allocator skip over groups of slots that can't change the outcome, instead of checking slot-by-slot every time.
3. Coalesce copies into bundles
If two vregs in the same register class are connected by a copy, and their live ranges don't overlap, rat can combine them into a single bundle. Then the copy becomes redundant and can be removed. Candidates come from ordinary copy instructions and phi nodes, which pick values from different control-flow paths at a join point.
Rat sorts copy candidates by loop depth, handling deeper-loop copies first. The goal is to let hot copies merge before colder candidates reduce the available options. Bundles are tracked with a union-find structure. Before merging, the allocator checks whether the combined live ranges overlap. It also refuses to merge if the result would contain more than 256 segments.
Copies between a vreg and a physical register are treated as hints, not hard merges. A bundle can prefer the physical register referenced by the copy, as long as that register is free across the bundle's live range. This helps preserve useful values already sitting in argument or return registers without turning the hint into an inflexible constraint.
4. Assign registers by priority
Rat assigns each bundle a priority based on its estimated spill weight and the length of its live range:
priority = weight / sqrt(length in slots)Short, hot ranges rise to the top. Long, cold ranges rank lower and are more likely to end up spilled. Using the square root softens the penalty for long lifetimes, so a loop counter that's live for a long time doesn't lose priority as aggressively as it would under a direct division by the full length.
For each bundle, rat first gathers registers that are unavailable anywhere in the bundle's live segments. If the bundle has a hinted register and it's free, rat uses it. Otherwise, it picks the first free register from its configured order. Caller-saved registers come first, which avoids save/restore overhead when a value doesn't actually need to survive a call.
In the example function, the copy hints keep x in rdi and the call result in rax. Since y is live across the call, caller-saved registers are blocked over the relevant slots, so rbx becomes the first suitable option. No special "cross-call rule" is required.
5. Spill and rewrite
If a bundle has no available register, rat assigns it a stack slot for its full lifetime. Spilled bundles are sorted by start position, and stack slots can be reused once the earlier spilled value's lifetime ends.
After that, rat rewrites instructions. A vreg assigned to a register becomes that physical register. For spilled operands, rat inserts a load into a temporary before the instruction; for spilled results, it inserts a store afterward. For integer temporaries it normally uses r10 or r11, and for floating-point temporaries it uses xmm14 or xmm15. If both preferred temporaries are already occupied at that point, it searches for another free register.
Some cases avoid a separate temporary. If there's a copy between a register and a spilled value, that copy already implies a load or store. A call can also read a spilled stack argument directly from its stack slot.
Once rewriting is done, a peephole pass removes redundant loads and stores. For example, if the code stores a value and then immediately loads it back into the same temporary without overwriting that temporary in between, the two memory operations can cancel out.
The decisions that matter most
The quality of the allocator depends less on supporting every clever trick and more on picking a few that actually move the needle. Rat keeps coalescing, physical-register hints, live-range holes, and spill weights. It drops several more complicated features after checking their measured impact.
Live-range holes make code layout useful
A live range doesn't have to cover every instruction between its first definition and last use. It can include holes - places where the value is dead. Because blocks are numbered in code order, skipping a block can leave gaps in the slot sequence.
Those gaps can be used by other values. In the loop example, an offset held in rax is needed inside the loop, but it's dead in an exit block that appears between loop blocks in the code order. In that gap, the expression n * 3 can also use rax, which happens to be the return register. The "free opportunity" comes from accurately tracking liveness and from the way blocks are ordered - no special selection rule required.
The measured impact was real: turning off live-range holes increased emitted instructions by about 10% in the test comparison. Tracking holes adds complexity, but in this case it paid for itself in generated code.
Fixed decisions can produce awkward results
Rat's main simplification is also its main limitation: once a bundle gets a register, rat doesn't evict it later to make room for a later, more valuable bundle. It also doesn't split a long live range so that part can use a register while another part sits on the stack.
That can lead to something that makes local sense but looks awkward globally. In the array-sum loop example, short, hot loop values get registers first. They can take rax and rdi, while the long-lived array pointer and loop bound lose their register hints. Rat then emits three moves outside the loop to relocate those values.
An allocator with eviction could rearrange the assignments and avoid the move chain. But those moves happen outside the hot loop, so their runtime cost is limited. The author's judgment was that saving a few cold instructions wasn't worth adding eviction logic. That's a trade-off, not a claim that eviction is always useless.
Platform rules affect register availability
Register allocation depends on the target's calling convention. On Linux x86-64, rat treats the available XMM registers as caller-saved. That means a floating-point value that must survive a call can't stay in an XMM register in this model - it has to be spilled or otherwise preserved.
Windows uses different XMM rules. The write-up notes that rat's Windows configuration uses only a subset of XMM registers and doesn't use the callee-saved xmm6-xmm15.
This is also why allocator results shouldn't be generalized without target details. The same strategy can behave differently depending on the ABI, the available registers, instruction constraints, and the kinds of code you compile.
What the measurements say - and what they don't
Compared with the previous allocator, the replacement reduced allocator source size by 58%, emitted 3.6% fewer instructions, and emitted 22% fewer stores. On the SQLite workload at -O0, allocator time fell by 77% and total compile time by 43%.
Those numbers are helpful because they cover both implementation size and runtime behavior. They're not a universal benchmark for allocator design. They apply to rat, its test setup, the target architecture, and the measured workload. A different program mix or optimization level could shift the balance.
The feature-by-feature results are especially practical:
| Feature | Change in emitted instructions when disabled | Decision |
|---|---|---|
| Copy coalescing and copy hints | About one-third more | Kept |
| Live-range holes | About 10% more | Kept |
| Spill selection by use weight | About 5.5% more | Kept |
| Physical-register hints | About 1% more | Kept |
| Optimistic second attempt for spilled ranges | About 0.01% more | Dropped |
| Rematerialization | No measurable change | Dropped |
| Spill-slot cache | No measurable change | Dropped |
The optimistic second attempt covered 37% of the old allocator's runtime, while changing emitted instructions by only about 0.01%. That's exactly the kind of result that's easy to miss if you carry a feature forward just because it sounds sophisticated - or because it was added to handle some corner case.
The broader lesson is simple: measure the features where they're supposed to help. Disabling one feature at a time doesn't prove features never interact, and a small test suite can miss important workloads. Still, even limited experiments can give an engineering team evidence about what complexity is actually buying - and what's just consuming compile time and maintenance effort.
Rat's design isn't a drop-in replacement for LLVM's greedy allocator or other production allocators in every situation. It's a concrete example of matching an algorithm to a compiler's actual needs. The author describes it as being in the same family as LLVM's greedy allocator, but without most of the machinery, including eviction and splitting. In this project, the simpler design wins because the measured quality stays good enough.
Conclusion
Rat's register allocator shows that a smaller algorithm can produce better code when its decisions are driven by measurements that actually matter. Rat keeps the pieces that made a measurable difference - coalescing, register hints, live-range holes, and spill weights - and removes machinery that adds time without improving the tested output.
The takeaway isn't "avoid sophisticated allocators." It's to question inherited complexity before extending it. Measure which features help, understand where their costs show up, and pick a design that fits your workload instead of an abstract ideal.
If you're building or maintaining a compiler, start by profiling the allocator and comparing generated code while disabling features one by one. Then read the original rat register allocator write-up for implementation details and references. The next "optimization" might be a better heuristic - or it might be deleting something that never earned its place.