SSAbased 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 socalled interference graph:
 A variable corresponds to a node in an undirected graph.
 If two variables are alive at the same time, their nodes are connected by an edge.
This reduction has (at least) two inconvenient consequences:
 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.

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 ncoloring 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 SSAform, a programrepresentation property widely used in modern compilers, this no longer holds. Around 2005, three research groups independently showed that the interference graphs of SSAform programs are chordal. Chordal graphs have two properties that make them especially appealing for register allocation:
 They are optimally colorable in time O(ω(G) ⋅ V). Such a coloring can be computed using a perfect elimination order.
 Chordal graphs are perfect. This implies ω(H) = χ(H) for every induced subgraph H of G.
Both properties correlate tightly to the program:

The dominance relation of the SSAform 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 controlflow graph of the program in an order that is compatible with dominance and assign registers firstcome firstserve.

For every clique in the interference graph, there is a program point in the controlflow 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
 Other people working on that subject: The COMPSYS group, Philip Brisk, Fernando Pereira, Jens Palsberg
 The libFirm compiler features a completely SSAbased backend including an SSAbased register allocator.
 The SSA Register Allocation tutorial given by the people involved in the subject at LCPC 2009.
 Slides of a presentation I gave at the SSA seminar 2009 in Autrans, France.
Publications of our group
Journal Papers
 Optimal Register Allocation for SSAform Programs in polynomial Time
Hack, S. and Goos, G.
Information Processing Letters, 98 (4): 150–155, 2006. [doi] [bib]
Conferences
 PreferenceGuided Register Assignment  CC 2010
Braun, M., Mallon, C. and Hack, S.
Compiler Construction, pages 205–223, Springer, 2010. [doi] [bib]
 Register Spilling and LiveRange Splitting for SSAForm
Programs  CC 2009
Braun, M. and Hack, S.
Compiler Construction, pages 174–189, Springer, 2009. [doi] [bib]
 Register Coalescing by Graph Recoloring  PLDI 2008
Hack, S. and Goos, G.
Conference on Programming Language Design and Implementation, pages 227–237, ACM, 2008. [doi] [bib]
 A Fast CuttingPlane Algorithm for Optimal Coalescing  CC 2007
(Best Paper Award)
Grund, D. and Hack, S.
Compiler Construction, pages 111–125, Springer, 2007. [doi] [bib]
 Register Allocation for Programs in SSAForm  CC 2006
Hack, S., Grund, D. and Goos, G.
Compiler Construction, pages 247–262, Springer, 2006. [doi] [bib]
Technical Reports
 Interference Graphs of Programs in SSA Form
Hack, S.
[pdf] [bib]
 Towards Register Allocation for Programs in SSAForm
Hack, S., Grund, D. and Goos, G.
[pdf] [bib]