Chaitin Algorithm

The Chaitin algorithm (also known as the Chaitin-Briggs allocator) is a heuristic graph-coloring method for register allocation introduced by Greg Chaitin in 1981. The algorithm recognizes that graph coloring is NP-complete and instead exploits the structure of real-world interference graphs: it iteratively removes vertices of degree less than the number of available registers, which are guaranteed to be colorable, then colors the remaining core and reinserts removed vertices in reverse order. When the remaining core contains only high-degree vertices, the algorithm selects a vertex to spill to memory, removing it from the graph and continuing. The technique was refined by Preston Briggs to reduce unnecessary spills through coalescing — merging vertices that are connected by register-to-register moves. The Chaitin-Briggs allocator remains the conceptual foundation of modern register allocation, even as research has moved toward integer linear programming and linear scan approaches.