Compiler Design Lab

SSA-based Register Allocation

About

Register allocation is one of the most important optimizations in a modern compiler. This is basically because of increasing gap between memory/cache access time and register access time. To quote Hennessy & Patterson in Computer Architecture: A Quantitative Approach:

Because of the central role that register allocation plays, both in speeding up the code and in making other optimizations useful, it is one of the most important—if not the most important—optimizations.

Graph Coloring

A useful abstraction for register allocation is coloring the so-called interference graph:

In the beginning of the 80ies, Chaitin et al. gave a constructive proof that every undirected graph can occur as an interference graph of a program. Since graph coloring is NP-complete, register allocation (in this abstraction) is too.

This reduction has (at least) two inconvenient consequences:

  1. It forces us to use a heuristic to perform register allocation. This heuristic might fail to color the graph with k colors, although χ(G) ≤ k As a result, the heuristic decides to spill some variables to memory. Hence, we inserted costly memory operations although there is a valid register allocation for the program with k registers.

  2. One might think that if maximum number of simultaneously live variables (the register pressure) in a program P is n, then we can find an n-coloring of P's interference graph G. However, this not true. In fact, there exist programs with an arbitrarily large gap between the register pressure and the register demand.

    In terms of graph theory, this is reflected by the inequality χ(G) ≥ ω(G).
    ω(G) is the clique number of the graph. That is the size of the largest clique in G that (roughly) corresponds to the register pressure.
    χ(G) is the chromatic number χ(G) of the graph, i.e. the minimum number of colors needed for a coloring of G.
    Mycielski's construction is one example of how to construct graphs with ω(G)=2 and an arbitrarily high χ(G)

SSA

However, if we require the program to be in SSA-form, a program-representation property widely used in modern compilers, this no longer holds. Around 2005, three research groups independently showed that the interference graphs of SSA-form programs are chordal. Chordal graphs have two properties that make them especially appealing for register allocation:

  1. They are optimally colorable in time O(ω(G) ⋅ |V|). Such a coloring can be computed using a perfect elimination order.
  2. Chordal graphs are perfect. This implies ω(H) = χ(H) for every induced subgraph H of G.

Both properties correlate tightly to the program:

  1. The dominance relation of the SSA-form program induces a perfect elimination order on the program's interference graph.

    As a consequence, the interference graph does not have to be constructed as a data structure. It is sufficient to traverse the control-flow graph of the program in an order that is compatible with dominance and assign registers first-come first-serve.

  2. For every clique in the interference graph, there is a program point in the control-flow graph of the program, where all variables in that clique are simultaneously live.

    As a consequence, one can look at the program and identify all program points where the register pressure is excessive (i.e. larger than the number of available registers = k). By lowering the register pressure at these points to at most k, it is ensured that there is no clique larger than k in the graph. Hence ω(G) ≤ k. Because we have ω(G) = χ(G) for chordal graphs, the graph is colorable with k colors.

Links and Material

Publications of our group

Journal Papers

Conferences

Technical Reports

PhD Thesis