October 7th, 2026
\nrat is my smallish compiler backend (with a semi-working\nC99 frontend). Its x86-64 code generator\ntranslates the intermediate representation (IR) into x86-64 instructions. These use an unlimited number of virtual\nregisters (vregs). The register allocator maps each vreg to a physical register: a general-purpose register (12 can\nbe used) or an xmm register (14 on Linux1). When no register is free,\nit maps the vreg to a stack slot.
\nFor 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\n1392 lines. So I measured which of its parts helped, threw the rest away and wrote a priority bin-packing\nallocator in 584 lines. It visits live ranges by importance and puts each one in the first register where it\nfits. It is the same family as LLVM's\ngreedy allocator, minus most of the hard parts, and it makes\nbetter code.
\nA value is live from where it is written to where it is last read. Two values can share a register\nonly if they are never live at the same time.
\nWhen too many values are live at one point, some go to memory: they are spilled. A spill\ncosts a store and a load. The best assignment is NP-hard to find2,\nso all practical allocators use heuristics.
\nThe calling convention adds two rules. A call can overwrite the caller-saved registers\n(rax rcx rdx rsi rdi r8-r11 and all xmm registers on Linux). A function must restore the\ncallee-saved registers (rbx rbp r12-r15) before it returns. As an example, this\nfunction keeps y live across a call:
long g(long);\nlong h(long x, long y) {\n long t = g(x);\n return t + y;\n}Before allocation, rdi, rsi and rax are fixed by the calling\nconvention, and v1-v4 are vregs:
0 v1 = copy rdi ; x\n1 v2 = copy rsi ; y\n2 rdi = copy v1 ; argument of g\n3 call g ; clobbers caller-saved\n4 v3 = copy rax ; t\n5 v4 = copy v3\n6 v4 = add v4, v2\n7 rax = copy v4\n8 retx86 add writes over its first operand (two-address), so instruction 5 copies t\nfirst. After allocation, at -O1:
push rbp\nmov rbp, rsp\nsub rsp, 0x8\npush rbx ; rbx is callee-saved: save it\nmov rbx, rsi ; y\ncall g ; x is already in rdi\nadd rax, rbx ; t stays in rax\npop rbx\nleave\nretFive of the six copies are gone, and y went to a callee-saved register. No code in the\nallocator says "put values that cross a call in callee-saved registers". It falls out of the design, and\nthat is my favourite part.
The allocator runs five steps per function:
\nFixed 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.
Each bundle keeps its register or stack slot for its full lifetime. The allocator never:
\nThese parts make real allocators big. My measurements say rat does\nnot miss them much.
\nInstruction i gets two slots: it reads its operands at 2i and writes its results\nat 2i+1. A live range is a sorted list of [start, end] slot segments.
Where a source ends depends on the instruction:
\nCopies: 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\n4 and rdi starts at slot 5. They do not\noverlap, 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\nadd at instruction 6, so it lives in [3, 13].
rat finds the vregs that are live-out of each block: a later block can still read them. Many\ncompilers do this with one bitset per block and a\nfixed-point loop. rat does\none vreg at a time instead:
\nFrom each such block, a worklist goes back through the predecessors and marks the vreg live-out in
each.
The cost grows with the blocks where each vreg is live, not with\nblocks * vregs.4
Then rat walks each block backward from its live-out set and makes the segments. The same walk sums a\nweight per vreg: the cost of its spill.
\nEach 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 |
A live range can have holes, gaps where the vreg is dead. Blocks are numbered in code order, so a range\nthat skips a block has a hole there:
\nlong f(long* a, long n) {\n for(long i = 0; i < n; ++i)\n if(a[i] < 0)\n a[i] = 0;\n return n * 3;\n}The exit block sits between the loop blocks:
\nmov eax, 0x0 ; offset 8*i, rax in the loop\ncmp rdx, rdi\njl loop\nexit:\nlea rax, [rdi+rdi*2] ; n*3 in the hole of rax\nret\nloop:\nmov rcx, r8\nadd rcx, rax\n...\nadd rax, 0x8\ncmp rdx, rdi\njl loop\njmp exitThe offset in rax is dead in the exit block, so n*3 (one\nlea) can use rax,\nwhich is also the return register. A free win from block order.
rat numbers its registers 1 to 40, so one U64 holds a set of them. Each slot gets one mask,\nbusy[slot]. A set bit means that register is busy at that slot.
The same backward walk marks the physical registers the code uses directly:
\n| 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\nslot rw rw rw rw rw rw rw rw rw\nrdi #. .. .#### .. .. .. .. ..\nrsi ####. .. ## .. .. .. .. ..\nrax .. .. .. ####. .. .. .####\nothers .. .. .. ## .. .. .. .. ..\nv1 x .======. .. .. .. .. .. ..\nv2 y .. .================ .. ..\nv3+v4 t .. .. .. .. .=========. ..r and w are the read and write slots. # is busy, = is a\nlive range and . is free. A bar continues across the gap between instructions. "others" is\nevery 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,\nvregs and fixed registers are bits in the same masks. Each group of 64 slots also has a summary mask, the\nOR of its 64 masks, so a long range can skip 64 slots at a time.
\nA copy between two vregs of the same class is a candidate for\ncoalescing. These\ncopies come from:
\nphi nodes: 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\nweight. rat deletes a copy inside one bundle. In\nh, v3 is [9, 10] and v4 is [11, 14], so\nthey merge.
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\nif it is free.
\nEach bundle gets a priority:
\npriority = weight / sqrt(length in slots)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\nPhysReg pick(VReg v) {\n U64 blocked = ~allocatable[cls];\n for(auto [start, end] : segs[v])\n for(I32 s = start; s <= end; ++s)\n blocked |= busy[s]; // or 64 at a time\n if(hint[v] != kNoReg && !(blocked >> hint[v] & 1))\n return hint[v];\n // caller-saved first, callee-saved last\n return firstFree(order[cls], blocked);\n}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.\nBoth copies become mov rdi, rdi, and the\npeephole pass deletes them after\nallocation.
v2 crosses the call. Every caller-saved register is busy in the call slots, so the first free\nregister is rbx, the first callee-saved one. The prologue saves\nonly the callee-saved registers rat used.
On Linux, no xmm register is callee-saved, so a float that crosses a call always goes to\nthe stack.
\nA bundle with no free register is spilled for its full lifetime. Then:
\nBefore 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).\nNo bundle ever gets these. If both are busy, rat takes the first register free at that\ninstruction.
Two cases need no temporary. A copy between a register and a spilled bundle becomes the load or the store\nitself. A call reads a spilled stack argument from its stack slot directly.
\nIn p, 14 values are live at once:
void p(long* a) {\n long x0 = a[0], x1 = a[1], ..., x13 = a[13];\n a[0] = x0 * x13; a[1] = x1 * x12; a[2] = x2 * x11;\n a[3] = x3 * x10; a[4] = x4 * x9; a[5] = x5 * x8;\n a[6] = x6 * x7;\n}16 registers minus rsp, rbp, r10, r11 and\nrdi (which holds a) leaves 11 for 14 values. x0-x6 also\nhold the products (two-address\nimul), so they have more\nuses. Of x7-x13, the three with the longest ranges go to the stack.
Before the peephole pass:
\nmov r12, [rdi+0x30] ; x6, in a register\nmov r10, [rdi+0x38] ; x7, spilled\nmov [rbp-0x8], r10\nmov r10, [rdi+0x40] ; x8, spilled\nmov [rbp-0x10], r10\nmov r10, [rdi+0x48] ; x9, spilled\nmov [rbp-0x18], r10\n...\nmov r10, [rbp-0x18] ; reload x9\nimul r9, r10\nmov r10, [rbp-0x10] ; reload x8\nimul rbx, r10\nmov r10, [rbp-0x8] ; reload x7\nimul r12, r10No instruction between the store of x9 and its reload writes r10. So the peephole\npass deletes the reload. Then nothing reads that stack slot, so it also deletes the store.
Without eviction, an early decision is final. Here is the case that annoys me most:
\nlong sum(long* a, long n) {\n long s = 0;\n for(long i = 0; i < n; ++i)\n s += a[i];\n return s;\n}rat compiles it to:
\nmov r9, rdi ; a: rdi was taken by a[i]\nmov r8, rsi ; n: rsi was taken by s\n...\nexit:\nmov rax, rsi ; s: rax was taken by a+8*i\nret\nloop:\nmov rax, r9\nadd rax, rcx ; rax = a + 8*i\nmov rdi, [rax] ; rdi = a[i]\nadd rsi, rdi\n...The loop values are short and hot, so they go first:
\na+8*i takes rax.s loses its hint rax and takes rsi.a[i] takes rdi.a and n come last and lose their hints too.The result is three movs, all outside the loop.5 An allocator with\neviction would fix this chain. I decided three cold movs are not worth the extra code.
\nAgainst the old allocator:
\n| metric | change |
|---|---|
| allocator source | -58% |
| instructions emitted | -3.6% |
| stores emitted | -22% |
| allocator time, sqlite at -O0 | -77% |
| total compile time, sqlite at -O0 | -43% |
Before the rewrite, I turned off each old feature in turn and measured the\ncode. This was the most useful hour of the project:
\n| 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 (recompute instead of reload) | not measurable | dropped |
| spill slot cache | not measurable | dropped |
No eviction, no splitting, no second pass, and the new allocator still beats the old one. Most of the\nquality comes from cheap things: coalescing, hints, holes and use weights.
\nThe lesson for me: measure the old code before I port it. Much of the old allocator did nothing.
\nJakob Stoklund Olesen,
Greedy register allocation in LLVM 3.0: the big version of this idea, with eviction and splitting.
On Windows, only xmm0-xmm3 can be used. xmm4 and
xmm5 are the spill temporaries, and rat does not use the callee-saved\n xmm6-xmm15. [back]
showed that any graph can be the interference graph of some program. So register allocation is at least as\n hard as graph coloring. [back]
Each block stores the last vreg that marked it, so the walk never clears a visited
array. [back]
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]