---
title: "rat's register allocator"
slug: rats-register-allocator
url: https://listedarticles.com/articles/rats-register-allocator
canonical_url: https://hexrat.cc/pages/blog/2026_10_07
content_type: blog_post
language: en
published_at: 2026-10-07T00:00:00.000Z
updated_at: 2026-10-08T02:11:31.918Z
authored_by: human
publisher: "hexrat.cc"
publisher_url: https://hexrat.cc/
topics: ["Systems Programming", "Programming", "Performance"]
license: all-rights-reserved
word_count: 2427
reading_minutes: 11
citation: "hexrat.cc. \"rat's register allocator.\" 7 Oct 2026. https://hexrat.cc/pages/blog/2026_10_07 (all-rights-reserved)"
# The full text follows. The web page shows an extract and sends readers
# to the source above; quote the citation and link the canonical URL.
---

# rat's register allocator

> The author of the rat compiler backend explains replacing a 1,392-line linear scan register allocator with a 584-line priority bin-packing allocator that produces better x86-64 code. The post walks through live ranges, fixed registers, coalescing, register picking and spilling, then measures what each feature was worth, finding that cheap techniques like coalescing and hints matter most.

# rat's register allocator

October 7th, 2026

[rat](https://github.com/hexratcc/rat) is my smallish compiler backend (with a semi-working
C99 frontend). Its x86-64 code generator
translates the [intermediate representation](https://en.wikipedia.org/wiki/Intermediate_representation) (IR) into x86-64 instructions. These use an unlimited number of virtual
registers (vregs). The register allocator maps each vreg to a physical register: a general-purpose register (12 can
be used) or an xmm register (14 on Linux[1](#fn1)). When no register is free,
it maps the vreg to a stack slot.

For a long time rat used a [linear scan](https://dl.acm.org/doi/10.1145/330249.330250) allocator, which visits live ranges in program order. It worked, but it grew one fix at a time, to
1392 lines. So I measured which of its parts helped, threw the rest away and wrote a priority bin-packing
allocator in 584 lines. It visits live ranges by importance and puts each one in the first register where it
fits. It is the same family as LLVM's
[greedy allocator](https://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html), minus most of the hard parts, and it makes
[better code](#numbers).

A value is **live** from where it is written to where it is last read. Two values can share a register
only if they are never live at the same time.

When too many values are live at one point, some go to memory: they are **spilled**. A spill
costs a store and a load. The best assignment is NP-hard to find[2](#fn2),
so all practical allocators use heuristics.

The [calling convention](https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI) adds two rules. A call can overwrite the **caller-saved** registers
(`rax rcx rdx rsi rdi r8-r11` and all xmm registers on Linux). A function must restore the
**callee-saved** registers (`rbx rbp r12-r15`) before it returns. As an example, this
function keeps `y` live across a call:

```
long g(long);
long h(long x, long y) {
	long t = g(x);
	return t + y;
}
```

Before allocation, `rdi`, `rsi` and `rax` are fixed by the calling
convention, and `v1`-`v4` are vregs:

```
0  v1 = copy rdi      ; x
1  v2 = copy rsi      ; y
2  rdi = copy v1      ; argument of g
3  call g             ; clobbers caller-saved
4  v3 = copy rax      ; t
5  v4 = copy v3
6  v4 = add v4, v2
7  rax = copy v4
8  ret
```

x86 `add` writes over its first operand (two-address), so instruction 5 copies `t`
first. After allocation, at -O1:

```
push rbp
mov  rbp, rsp
sub  rsp, 0x8
push rbx              ; rbx is callee-saved: save it
mov  rbx, rsi         ; y
call g                ; x is already in rdi
add  rax, rbx         ; t stays in rax
pop  rbx
leave
ret
```

Five of the six copies are gone, and `y` went to a callee-saved register. No code in the
allocator says "put values that cross a call in callee-saved registers". It falls out of the design, and
that is my favourite part.

### Five steps

The allocator runs five steps per function:

1. [Live ranges](#live-ranges): number the instructions and find where each vreg is live.
2. [Fixed registers](#fixed-registers): mark where the code uses physical registers
   directly.
3. [Coalescing](#coalescing): join vregs that a copy connects into one group (a
   **bundle**[3](#fn3)), so the copy can go away.
4. [Picking registers](#picking-registers): give each bundle a register, most important
   first.
5. [Spilling](#spilling): give stack slots to bundles with no register, then
   rewrite the code.

Each bundle keeps its register or stack slot for its full lifetime. The allocator never:

* takes a register back from a bundle (no eviction)
* [splits](https://en.wikipedia.org/wiki/Register_allocation#Split_allocation) a range between a register and memory
* runs a step two times

These parts make real allocators big. My [measurements](#numbers) say rat does
not miss them much.

### Live ranges

#### Slots

Instruction `i` gets two slots: it reads its operands at `2i` and writes its results
at `2i+1`. A live range is a sorted list of `[start, end]` slot segments.

Where a source ends depends on the instruction:

* **Copies:** the source ends at the read slot, and the destination starts at the write
  slot. In instruction 2, `rdi = copy v1`, `v1` ends at slot
  4 and `rdi` starts at slot 5. They do not
  overlap, so they can share a register and the copy becomes a no-op.
* **Other instructions:** a source stays live through the write slot, so a result never overwrites a
  different operand. `v2` is written by instruction 1 and last read by the
  `add` at instruction 6, so it lives in `[3, 13]`.

#### Live-out sets

rat finds the vregs that are **live-out** of each block: a later block can still read them. Many
compilers do this with one bitset per block and a
[fixed-point loop](https://en.wikipedia.org/wiki/Live-variable_analysis). rat does
one vreg at a time instead:

1. The vreg is live into each block that reads it before it writes it.
2. From each such block, a worklist goes back through the predecessors and marks the vreg live-out in
   each.
3. The walk stops at a block that defines the vreg.

The cost grows with the blocks where each vreg is live, not with
`blocks * vregs`.[4](#fn4)

#### Segments and weights

Then rat walks each block backward from its live-out set and makes the segments. The same walk sums a
**weight** per vreg: the cost of its spill.

Each def and each use adds `3d`, where `d` is the loop depth (up to 11):

| def or use in | adds |
| --- | --- |
| straight-line code | 1 |
| a loop | 3 |
| a doubly nested loop | 9 |

#### Holes

A live range can have **holes**, gaps where the vreg is dead. Blocks are numbered in code order, so a range
that skips a block has a hole there:

```
long f(long* a, long n) {
	for(long i = 0; i < n; ++i)
		if(a[i] < 0)
			a[i] = 0;
	return n * 3;
}
```

The exit block sits between the loop blocks:

```
mov  eax, 0x0         ; offset 8*i, rax in the loop
cmp  rdx, rdi
jl   loop
exit:
lea  rax, [rdi+rdi*2] ; n*3 in the hole of rax
ret
loop:
mov  rcx, r8
add  rcx, rax
...
add  rax, 0x8
cmp  rdx, rdi
jl   loop
jmp  exit
```

The offset in `rax` is dead in the exit block, so `n*3` (one
[`lea`](https://www.felixcloutier.com/x86/lea)) can use `rax`,
which is also the return register. A free win from block order.

### Fixed registers

rat numbers its registers 1 to 40, so one `U64` holds a set of them. Each slot gets one mask,
`busy[slot]`. A set bit means that register is busy at that slot.

The same backward walk marks the physical registers the code uses directly:

| use | register | busy |
| --- | --- | --- |
| incoming argument | argument register | until the copy that reads it |
| call argument | argument register | from the copy that sets it to the call |
| call | all caller-saved | in the two slots of the call |
| return value | `rax` | from the call to the copy that reads it |
| [division](https://www.felixcloutier.com/x86/idiv) | `rax rcx rdx` | reads `rax rcx`, writes `rax rdx` |

The masks and ranges of `h`:

```
instr   0  1  2  3  4  5  6  7  8
slot    rw rw rw rw rw rw rw rw rw
rdi     #. .. .#### .. .. .. .. ..
rsi     ####. .. ## .. .. .. .. ..
rax     .. .. .. ####. .. .. .####
others  .. .. .. ## .. .. .. .. ..
v1 x    .======. .. .. .. .. .. ..
v2 y    .. .================ .. ..
v3+v4 t .. .. .. .. .=========. ..
```

`r` and `w` are the read and write slots. `#` is busy, `=` is a
live range and `.` is free. A bar continues across the gap between instructions. "others" is
every other caller-saved register.

When a bundle gets a register, rat sets that register's bit in every slot of its live range. After that,
vregs and fixed registers are bits in the same masks. Each group of 64 slots also has a summary mask, the
OR of its 64 masks, so a long range can skip 64 slots at a time.

### Coalescing

A copy between two vregs of the same class is a candidate for
[coalescing](https://en.wikipedia.org/wiki/Register_allocation#Coalescing). These
copies come from:

* two-address instructions
* [phi nodes](https://en.wikipedia.org/wiki/Static_single-assignment_form): a
  value that comes from different blocks at a join point

If the two live ranges do not overlap, the vregs become one bundle. It has the merged segments and the summed
weight. rat deletes a copy inside one bundle. In
`h`, `v3` is `[9, 10]` and `v4` is `[11, 14]`, so
they merge.

* rat sorts the copies by loop depth, deepest first. Hot copies merge before cold copies can block them.
* The bundles are kept in a [union-find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).
* A merge first walks both segment lists to check for overlap. rat skips a merge when the two bundles
  together have more than 256 segments.

A copy between a vreg and a physical register sets a **hint** instead: the bundle prefers that register
if it is free.

### Picking registers

Each bundle gets a priority:

```
priority = weight / sqrt(length in slots)
```

* Short, hot ranges come first: they matter most and are the easiest to place.
* Long, cold ranges come last and get spilled.
* `sqrt` keeps a long loop counter from losing too much priority.

rat calls `pick` on each bundle in priority order:

```
// cls: register class, gp or xmm
PhysReg pick(VReg v) {
	U64 blocked = ~allocatable[cls];
	for(auto [start, end] : segs[v])
		for(I32 s = start; s <= end; ++s)
			blocked |= busy[s]; // or 64 at a time
	if(hint[v] != kNoReg && !(blocked >> hint[v] & 1))
		return hint[v];
	// caller-saved first, callee-saved last
	return firstFree(order[cls], blocked);
}
```

#### Picking in `h`

| bundle | hint | gets |
| --- | --- | --- |
| `v1` | `rdi` | `rdi` |
| `v3+v4` | `rax` | `rax` |
| `v2` | `rsi` | `rbx` |

In the diagram, `rdi` is busy only before and after `v1`, so `v1` gets it.
Both copies become `mov rdi, rdi`, and the
[peephole pass](https://en.wikipedia.org/wiki/Peephole_optimization) deletes them after
allocation.

`v2` crosses the call. Every caller-saved register is busy in the call slots, so the first free
register is `rbx`, the first callee-saved one. The prologue saves
only the callee-saved registers rat used.

On Linux, no xmm register is callee-saved, so a float that crosses a call always goes to
the stack.

### Spilling

A bundle with no free register is spilled for its full lifetime. Then:

1. rat sorts the spilled bundles by start. It reuses a stack slot when the last bundle in it has ended.
2. rat rewrites the code. A vreg whose bundle got a register becomes that register.
3. Before each instruction, rat loads each spilled operand into a temporary register. After it, rat stores
   each spilled result.

The temporary is `r10` or `r11` (`xmm14` or `xmm15` for floats).
No bundle ever gets these. If both are busy, rat takes the first register free at that
instruction.

Two cases need no temporary. A copy between a register and a spilled bundle becomes the load or the store
itself. A call reads a spilled stack argument from its stack slot directly.

In `p`, 14 values are live at once:

```
void p(long* a) {
	long x0 = a[0], x1 = a[1], ..., x13 = a[13];
	a[0] = x0 * x13; a[1] = x1 * x12; a[2] = x2 * x11;
	a[3] = x3 * x10; a[4] = x4 * x9;  a[5] = x5 * x8;
	a[6] = x6 * x7;
}
```

16 registers minus `rsp`, `rbp`, `r10`, `r11` and
`rdi` (which holds `a`) leaves 11 for 14 values. `x0`-`x6` also
hold the products (two-address
[`imul`](https://www.felixcloutier.com/x86/imul)), so they have more
uses. Of `x7`-`x13`, the three with the longest ranges go to the stack.

Before the peephole pass:

```
mov  r12, [rdi+0x30]  ; x6, in a register
mov  r10, [rdi+0x38]  ; x7, spilled
mov  [rbp-0x8], r10
mov  r10, [rdi+0x40]  ; x8, spilled
mov  [rbp-0x10], r10
mov  r10, [rdi+0x48]  ; x9, spilled
mov  [rbp-0x18], r10
...
mov  r10, [rbp-0x18]  ; reload x9
imul r9, r10
mov  r10, [rbp-0x10]  ; reload x8
imul rbx, r10
mov  r10, [rbp-0x8]   ; reload x7
imul r12, r10
```

No instruction between the store of `x9` and its reload writes `r10`. So the peephole
pass deletes the reload. Then nothing reads that stack slot, so it also deletes the store.

### It can be dumb

Without eviction, an early decision is final. Here is the case that annoys me most:

```
long sum(long* a, long n) {
	long s = 0;
	for(long i = 0; i < n; ++i)
		s += a[i];
	return s;
}
```

rat compiles it to:

```
mov  r9, rdi          ; a: rdi was taken by a[i]
mov  r8, rsi          ; n: rsi was taken by s
...
exit:
mov  rax, rsi         ; s: rax was taken by a+8*i
ret
loop:
mov  rax, r9
add  rax, rcx         ; rax = a + 8*i
mov  rdi, [rax]       ; rdi = a[i]
add  rsi, rdi
...
```

The loop values are short and hot, so they go first:

1. The address `a+8*i` takes `rax`.
2. `s` loses its hint `rax` and takes `rsi`.
3. `a[i]` takes `rdi`.
4. `a` and `n` come last and lose their hints too.

The result is three movs, all outside the loop.[5](#fn5) An allocator with
eviction would fix this chain. I decided three cold movs are not worth the extra code.

### Numbers

Against the old allocator:

| metric | change |
| --- | --- |
| allocator source | -58% |
| instructions emitted | -3.6% |
| stores emitted | -22% |
| allocator time, [sqlite](https://www.sqlite.org/amalgamation.html) at -O0 | -77% |
| total compile time, sqlite at -O0 | -43% |

#### What each feature was worth

Before the rewrite, I turned off each old feature in turn and measured the
code. This was the most useful hour of the project:

| feature | instructions saved | new allocator |
| --- | --- | --- |
| copy coalescing and copy hints | about a third | kept |
| live range holes | 10% | kept |
| spill choice by use weight | 5.5% | kept |
| hints to physical registers | 1% | kept |
| optimistic second try at spilled ranges (37% of allocator time) | 0.01% | dropped |
| [rematerialization](https://en.wikipedia.org/wiki/Rematerialization) (recompute instead of reload) | not measurable | dropped |
| spill slot cache | not measurable | dropped |

### Wrapping up

No eviction, no splitting, no second pass, and the new allocator still beats the old one. Most of the
quality comes from cheap things: coalescing, hints, holes and use weights.

The lesson for me: measure the old code before I port it. Much of the old allocator did nothing.

### References

* Poletto and Sarkar, [Linear scan   register allocation](https://dl.acm.org/doi/10.1145/330249.330250): the base of the old allocator.
* Max Bernstein, [Linear scan register   allocation on SSA](https://bernsteinbear.com/blog/linear-scan/) and [Linear scan with lifetime holes](https://bernsteinbear.com/blog/linear-scan-lifetime-holes/): a readable pair of posts.
* Jakob Stoklund Olesen,
  [Greedy   register allocation in LLVM 3.0](https://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html): the big version of this idea, with eviction and splitting.
* Chris Fallin, [Cranelift,   part 4: a new register allocator](https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/): a long, good read on bundles.
* Matt Keeter, [The solid-state   register allocator](https://www.mattkeeter.com/blog/2022-10-04-ssra/): even smaller, it runs in one backward pass.

### Notes

1. On Windows, only `xmm0`-`xmm3` can be used. `xmm4` and
   `xmm5` are the spill temporaries, and rat does not use the callee-saved
   `xmm6`-`xmm15`. [[back]](#ref1)
2. [Chaitin et al.](https://en.wikipedia.org/wiki/Chaitin%27s_algorithm)
   showed that any graph can be the interference graph of some program. So register allocation is at least as
   hard as graph coloring. [[back]](#ref2)
3. Cranelift's [regalloc2](https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/) uses the same word for the same idea. [[back]](#ref3)
4. Each block stores the last vreg that marked it, so the walk never clears a visited
   array. [[back]](#ref4)
5. The mov inside the loop, `mov rax, r9`, has a different
   cause. It is the two-address copy for the add, and it always stays. [[back]](#ref5)