Chaitin's algorithm

Chaitin's algorithm is a register allocation algorithm used in compilers. It works bottom-up and treats allocation as a graph coloring problem on an interference graph, using the ratio of cost to degree as its spill metric when it must decide which value to move out of a register. It is named after its designer, Gregory Chaitin, and was the first register allocation algorithm to use coloring of the interference graph for both allocating registers and choosing which values to spill. It was presented at the 1982 SIGPLAN Symposium on Compiler Construction and published in the symposium proceedings, as an extension of an earlier 1981 paper by Chaitin on using graph coloring for register allocation. Chaitin's algorithm formed the basis of a large body of later research into register allocators.