Cyrill Gössi
SSA Chordality Based Register Allocation

Register allocation based on chordality of SSA-form program interference graphs


This report describes the structure, implementation and performance evaluation of a non-iterative register allocator making use of program properties induced by the Static-Single-Assignment (SSA) form. Most salient, SSA renders a programs interference graph chordal. Since chordal graphs are a subset of perfect graphs and perfect graphs can be recognized and optimally colored in polynomial time, allocating registers for programs in SSA form can be optimally done in polynomial time. Together with the possibility to destroy SSA in a color-preserving manner, those properties allow to diverge from the classical iterative register allocation process, as exploited in our implementation and described in this report.