本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

rat’s minimal register allocator

rat’s register allocator October 7th, 2026 rat is my smallish compiler backend (with a semi-working C99 frontend). Its x86-64 code generator translates the 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 Linux1). When no register is free, it maps the vreg to a stack slot.

rat 的寄存器分配器，2026 年 10 月 7 日。rat 是我那个小巧的编译器后端（带有一个半成品 C99 前端）。它的 x86-64 代码生成器将中间表示（IR）转换为 x86-64 指令。这些指令使用无限数量的虚拟寄存器（vregs）。寄存器分配器将每个 vreg 映射到一个物理寄存器：通用寄存器（可使用 12 个）或 xmm 寄存器（Linux 上为 14 个）。当没有空闲寄存器时，它会将 vreg 映射到栈槽。

For a long time rat used a linear scan 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, minus most of the hard parts, and it makes better code.

长期以来，rat 一直使用线性扫描分配器，按程序顺序访问活跃范围。它能工作，但随着不断修补，代码增长到了 1392 行。因此，我评估了哪些部分是有用的，丢弃了其余部分，并用 584 行代码编写了一个优先级装箱分配器。它按重要性访问活跃范围，并将每个范围放入第一个适合的寄存器中。它与 LLVM 的贪婪分配器属于同一家族，去掉了大部分复杂部分，且生成的代码更好。

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 find2, so all practical allocators use heuristics.

一个值从写入处到最后一次读取处是活跃的。只有当两个值不同时活跃时，它们才能共享一个寄存器。当某一点有太多值活跃时，一些值会进入内存：它们被溢出（spilled）。溢出需要一次存储和一次加载。寻找最佳分配方案是 NP 难问题，因此所有实际的分配器都使用启发式算法。

The calling convention 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; }

调用约定增加了两条规则。调用可以覆盖调用者保存的寄存器（Linux 上的 rax、rcx、rdx、rsi、rdi、r8-r11 以及所有 xmm 寄存器）。函数必须在返回前恢复被调用者保存的寄存器（rbx、rbp、r12-r15）。例如，此函数在调用期间保持 y 活跃：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.

在分配之前，rdi、rsi 和 rax 由调用约定固定，v1-v4 是 vregs：0 v1 = copy rdi ; x 1 v2 = copy rsi ; y 2 rdi = copy v1 ; g 的参数 3 call g ; 破坏调用者保存的寄存器 4 v3 = copy rax ; t 5 v4 = copy v3 6 v4 = add v4, v2 7 rax = copy v4 8 ret。x86 add 指令会覆盖其第一个操作数（双地址），因此指令 5 先复制 t。

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.

分配后，在 -O1 下：push rbp mov rbp, rsp sub rsp, 0x8 push rbx ; rbx 是被调用者保存的：保存它 mov rbx, rsi ; y call g ; x 已经在 rdi 中 add rax, rbx ; t 保留在 rax 中 pop rbx leave ret。六次复制中有五次消失了，y 进入了一个被调用者保存的寄存器。分配器中没有任何代码写着“将跨越调用的值放入被调用者保存的寄存器中”。这是设计自然产生的结果，也是我最喜欢的部分。

Five steps The allocator runs five steps per function: Live ranges: number the instructions and find where each vreg is live. Fixed registers: mark where the code uses physical registers directly. Coalescing: join vregs that a copy connects into one group (a bundle3), so the copy can go away. Picking registers: give each bundle a register, most important first. Spilling: give stack slots to bundles with no register, then rewrite the code.

五个步骤：分配器对每个函数运行五个步骤：活跃范围：对指令编号并找出每个 vreg 在何处活跃。固定寄存器：标记代码直接使用物理寄存器的位置。合并：将由 copy 连接的 vregs 加入一个组（bundle3），以便消除 copy。选择寄存器：为每个 bundle 分配一个寄存器，最重要的优先。溢出：为没有寄存器的 bundle 分配栈槽，然后重写代码。

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 a range between a register and memory runs a step two times These parts make real allocators big. My measurements say rat does not miss them much.

每个 bundle 在其整个生命周期内保持其寄存器或栈槽。分配器从不：从 bundle 中收回寄存器（无驱逐）、在寄存器和内存之间拆分范围、重复运行某个步骤。这些部分使实际的分配器变得庞大。我的测量结果表明，rat 并不太需要它们。

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.

活跃范围槽位：指令 i 获得两个槽位：它在 2i 处读取操作数，在 2i+1 处写入结果。活跃范围是一个 [开始, 结束] 槽位段的排序列表。源的结束位置取决于指令：Copies：源在读取槽位结束，目标在写入槽位开始。在指令 2 中，rdi = copy v1，v1 在槽位 4 结束，rdi 在槽位 5 开始。它们不重叠，因此可以共享一个寄存器，copy 变为无操作。

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].

其他指令：源在写入槽位期间保持活跃，因此结果永远不会覆盖不同的操作数。v2 由指令 1 写入，最后由指令 6 的 add 读取，因此它活跃于 [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. rat does one vreg at a time instead: The vreg is live into each block that reads it before it writes it. From each such block, a worklist goes back through the predecessors and marks the vreg live-out in each. 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

Live-out 集合：rat 找出每个块的 live-out vregs：后续块可能仍会读取它们。许多编译器使用每个块一个位集和不动点循环来完成此操作。rat 则改为一次处理一个 vreg：vreg 在每个读取它之前写入它的块中是活跃的。从每个这样的块开始，工作列表通过前驱节点向回遍历，并标记每个块中的 vreg 为 live-out。遍历在定义 vreg 的块处停止。成本随每个 vreg 活跃的块数量增长，而不是随块数 * vregs 增长。

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

段和权重：然后 rat 从 live-out 集合开始向后遍历每个块并创建段。同样的遍历会累加每个 vreg 的权重：即其溢出成本。每个定义和使用增加 3d，其中 d 是循环深度（最高 11）：在直线代码中添加 1，循环中添加 3，双重嵌套循环中添加 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 8i, rax in the loop cmp rdx, rdi jl loop exit: lea rax, [rdi+rdi2] ; n3 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 n3 (one lea) can use rax, which is also the return register. A free win from block order.

空洞：活跃范围可以有空洞，即 vreg 不活跃的间隙。块按代码顺序编号，因此跳过一个块的范围在那里有一个空洞：long f(long* a, long n) { for(long i = 0; i < n; ++i) if(a[i] < 0) a[i] = 0; return n * 3; } 退出块位于循环块之间：mov eax, 0x0 ; 偏移量 8i, rax 在循环中 cmp rdx, rdi jl loop exit: lea rax, [rdi+rdi2] ; n3 在 rax 的空洞中 ret loop: mov rcx, r8 add rcx, rax … add rax, 0x8 cmp rdx, rdi jl loop jmp exit。rax 中的偏移量在退出块中是死的，因此 n3（一个 lea）可以使用 rax，它也是返回寄存器。这是块顺序带来的免费收益。

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 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 … ####.

固定寄存器：rat 将其寄存器编号为 1 到 40，因此一个 U64 可以容纳它们的一个集合。每个槽位获得一个掩码，busy[slot]。设置的位意味着该寄存器在该槽位忙碌。同样的向后遍历标记了代码直接使用的物理寄存器：使用寄存器忙碌，传入参数：参数寄存器直到读取它的 copy，调用：参数寄存器从设置它的 copy 到调用，调用：所有调用者保存的寄存器在调用的两个槽位中，返回值：rax 从调用到读取它的 copy，除法：rax rcx rdx 读取 rax rcx，写入 rax rdx。h 的掩码和范围：instr 0 1 2 3 4 5 6 7 8 slot rw rw rw rw rw rw rw rw rw rdi #…#### … .. .. rsi ####. .. ## … .. .. rax … ####.