Chaitin's algorithm is a bottom-up,
graph coloring register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocatio ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
that uses cost/degree as its
spill metric
A spill metric is a heuristic metric used by register allocators to decide which registers to spill. Popular spill metrics are:
* ''cost'' / ''degree'' - introduced in Chaitin's algorithm
* ''cost'' / ''degree2'' - emphasizes the spill's effect ...
. It is named after its designer,
Gregory Chaitin
Gregory John Chaitin ( ; born 25 June 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-t ...
. Chaitin's algorithm was the first
register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocatio ...
algorithm that made use of coloring of the
interference graph
Interference is the act of interfering, invading, or poaching. Interference may also refer to:
Communications
* Interference (communication), anything which alters, modifies, or disrupts a message
* Adjacent-channel interference, caused by extr ...
for both register allocations and spilling.
Chaitin's algorithm was presented on the 1982
SIGPLAN
SIGPLAN is the Association for Computing Machinery's Special Interest Group on programming languages.
Conferences
* Principles of Programming Languages (POPL)
* Programming Language Design and Implementation (PLDI)
* International Symposium on ...
Symposium on Compiler Construction, and published in the symposium proceedings. It was extension of an earlier 1981 paper on the use of graph coloring for register allocation. Chaitin's algorithm formed the basis of a large section of research into register allocators.
References
*
{{algorithm-stub
Graph algorithms