# SSA-based Register Allocation

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:

• 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.
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.

## Publications of our group

### Journal Papers

• Optimal Register Allocation for SSA-form Programs in polynomial Time
Hack, S. and Goos, G.
Information Processing Letters, 98 (4): 150–155, 2006. [doi] [bib]

### Conferences

• Preference-Guided Register Assignment - CC 2010
Braun, M., Mallon, C. and Hack, S.
Compiler Construction, pages 205–223, Springer, 2010. [doi] [bib]
• Register Spilling and Live-Range Splitting for SSA-Form 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 Cutting-Plane 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 SSA-Form - 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 SSA-Form
Hack, S., Grund, D. and Goos, G.
[pdf] [bib]

### PhD Thesis

• Register Allocation for Programs in SSA Form
Hack, S.
Ph.D. Thesis, Universität Karlsruhe, 2007. [url] [bib]