Register Allocation for Programs in SSA-Form

Despite the everlasting interest in this topic and associated publications it
was - more or less - considered solved and stable. In this talk we summarize a
new approach that relies on the compiler using static single assignment form
(SSA). That way certain properties (chordal Graphs) allow to perform the actual
(optimal) assignment of registers in linear time. This in turn leads to a
complete restructuring and simplification of the whole register allocation phase.

The talk will present basic notions, the SSA approach, and will contrast it to
the classical way of register allocation. Emphasis is rather put on intuition
and comparison than on details of single sub-problems.