Register allocation by graph coloring

In Computer Science, register allocation by graph coloring is a graph theoretic solution to the register allocation problem.

The Register Allocation Problem

Main Article: register allocation

Typically, a compiler will translate a source written in a high-level language (HLL) to a target in assembly language or machine code. There are a few critical differences between the source and target langauges. In particular, HLLs allow for a large or unlimited number of variables, while the typical microprocessor only allows for efficient access to a small number of variables, called registers, and inefficient access to main memory. For efficiency reasons, there is incentive to place as many variables as possible into registers, and as few as possible into memory.

Since only a small percentage of the variables within a computer program are used at one time, there is an opportunity to place multiple variables into the same register---but only if those variables are not used at the same time.

More formally, if at any point during program execution two variables each hold some value that will later be read by a future operation, then those two variables are said to interfere. Unfortunately, it is not always possible to determine if two variables interfere (a consequence of the halting problem), and thus a compiler must act conservatively and assume that they do interfere unless they can be shown not to.

The register allocation problem is to assign a register or memory location to each variable in a computer program, in such a way that no two interfering variables share a register or memory location. A trivial solution to the register allocation problem is to assign each variable a distinct memory location using a stack frame. Although this solution produces correct results, they are generally quite inefficient in computation time and memory space.

The Interference Graph

The register allocation problem can be viewed as a graph coloring problem as follows: every variable in a program is treated as a vertex in an undirected graph, and two verteces are connected by an edge iff their corresponding variables interfere. This graph is called the interference graph, and a complete vertex coloring of this graph can be viewed as a register allocation, with each register represented by a vertex color.

Determining a $k$-coloring for a graph is NP-Hard. Nonetheless, the compiler must solve such a problem. Thus, a compiler uses a heuristic algorithm to produce a sub-optimal solution to the vertex coloring problem, attempting to minimize the number of colors used. If, ultimately, the number of colors needed is greater than the number of registers in the target language, then the graph must be transformed to reduce the number of necessary colors. A compiler accomplishes this by spilling one or more variables, storing them in a memory location instead of a register.

The Algorithm

Similar work was done by Lavrov in 1961, though his work was on a related problem of memory allocaation. The use of graph coloring to solve register allocation was first presented by Chaitin in 1982, and was later improved in the PhD dissertation of Briggs in 1992. Here is a description of Briggs' algorithm:

To determine a k-coloring for a computer program,

1. Compute an interference graph for the program
2. Repeatedly simplify the graph until it is empty,
   1. If there are verteces with degree less than k, then
      1. Choose the vertex with the smallest degree, call it V
   2. Otherwise,
      1. Choose the vertex that is most favorable to spill, call it V
   3. Remove V from the interference graph and place it onto the stack.
3. Repeatedly select a vertex vertex V by popping it frmo the stack, until the stack is empty,
   1. Add V and its edges back to the interference graph
   2. If possible, select a non-interfering color for V, based upon the partially reconstructed graph
   3. Otherwise, leave that vertex uncolored for now, and continue
4. If any vertex remained uncolored, then the coloring has failed, and
   1. Insert "spill code" into the program for each uncolored node, hopefully reducing the complexity of the problem
   2. Repeat the whole process.

See Also

• compiler
• high-level language
• formal language
• memory hierarchy
• register
• graph coloring

References

• "Register Allocation via Graph Coloring", Preston Briggs, 1992, http://citeseer.ist.psu.edu/briggs92register.html