Chaitin's algorithm
Encyclopedia
Chaitin's algorithm is a bottom-up, graph coloring
register allocation
algorithm
that uses cost/degree as its spill metric
. It is named after its designer, Gregory Chaitin
. Chaitin's algorithm was the first register allocation
algorithm that made use of coloring of the interference graph for both register allocations and spilling.
Chaitin's algorithm was presented on the 1982 SIGPLAN
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.
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
register allocation
Register allocation
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that uses cost/degree as its spill metric
Spill metric
A spill metric is a heuristic metric used by register allocators to decide with registers to spill. Popular spill metrics are:* cost / degree - introduced in Chaitin's algorithm* cost / degree2 - emphasizes the spill's effect on neighbours...
. It is named after its designer, Gregory Chaitin
Gregory Chaitin
Gregory John Chaitin is an Argentine-American mathematician and computer scientist.-Mathematics and computer science:Beginning in 2009 Chaitin has worked on metabiology, a field parallel to biology dealing with the random evolution of artificial software instead of natural software .Beginning in...
. Chaitin's algorithm was the first register allocation
Register allocation
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers...
algorithm that made use of coloring of the interference graph for both register allocations and spilling.
Chaitin's algorithm was presented on the 1982 SIGPLAN
SIGPLAN
SIGPLAN is the Association for Computing Machinery's Special Interest Group on programming languages.- Conferences :* Principles of Programming Languages * Programming Language Design and Implementation...
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.