Conference Papers: Register Allocation for Programs in SSA-Form

As register allocation is one of the most important phases in optimizingcompilers, much work has been done to improve its quality and speed.We present a novel register allocation architecture for programs inSSA-form which simplifies register allocation significantly. We investigatecertain properties of SSA-programs and their interference graphs,showing that they belong to the class of chordal graphs. This leadsto a quadratic-time optimal coloring algorithm and allows for decouplingthe tasks of coloring, spilling and coalescing completely. After presentingheuristic methods for spilling and coalescing, we compare our coalescingheuristic to an optimal method based on integer linear programming.