Pangram verdict · v3.3
We believe that this text is a mix of AI and human-written content.
AI likelihood · overall
MixedArticle text · 1,782 words · 6 segments analyzed
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. 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. 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. 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; } 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: 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. 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. 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. 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 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) 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 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. These copies come from: two-address instructions phi 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 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. 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 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: rat sorts the spilled bundles by start. It reuses a stack slot when the last bundle in it has ended. rat rewrites the code. A vreg whose bundle got a register becomes that register. 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.