The interference graph for a program represented in SSA Form is chordal. There
are, in fact, a large number of SSA-based intermediate representations whose
interference graphs provably belong to many, but not all, subclasses of chordal
graphs. Firstly, this talk will characterize precisely which subclasses of
chordal graphs can be the interference graph of a procedure converted to an
SSA-based intermediate representation. Secondly, this talk will examine the
possibility of extending these results into the interprocedural domain. As long
as function pointers are resolved in advance, and variables cannot reside in
registers across procedure calls, it is possible to convert any whole program
to an interprocedural SSA-based intermediate representation whose
interprocedural interference graph belongs to any of the same subclasses of
chordal graphs that can be the interference graph of a procedure. This
landscape of intra- and inter-procedural SSA-based representations is the
frontier for future work on SSA-based register allocation.