Rat's Register Allocator

rat is a small x86-64 compiler backend whose register allocator was rewritten from a 1,392-line linear-scan allocator into a 584-line priority bin-packing (greedy) allocator. Virtual registers are grouped into bundles by coalescing copies, weighed by spill cost (uses and defs scaled by loop depth), and assigned registers most-important-first into the first register that fits. The allocator runs five one-shot steps per function - compute live ranges, mark fixed physical-register uses, coalesce copies into bundles, pick registers, then spill and rewrite - never evicting, splitting ranges, or repeating a step. Live ranges are tracked in 2i/2i+1 instruction slots with holes for gaps; live-out is computed per vreg with a backward predecessor walk. Crossing-call values tend to land in callee-saved registers naturally; on Linux floats that cross calls go to the stack because no xmm registers are callee-saved.

Spills are assigned stack slots with reuse by sorted starts and rewritten code that loads spilled operands into temporaries (r10/r11 or xmm14/xmm15) as needed; peephole passes remove redundant reloads/stores. The simpler design yields better or comparable code and much lower complexity: allocator source -58%, emitted instructions -3.6%, stores -22%, allocator time -77%, total compile time -43% (sqlite, -O0). Experiments showed most quality gains came from cheap techniques - coalescing, holes, use-weighted spills and hints - allowing removal of expensive features like rematerialization and second-pass retries.