Interprocedural register allocation

I have a question about using graph coloring for doing interprocedural
register allocation. Allow me to quote from Stenkiste & Hennessy "A
Simple Interprocedural Register Allocation Algorithm" (TOPLAS Jan 89):




" Suppose the program did not have recursion; then we could construct
" programwide interference graph. This graph contains a node for every
" live range of every variable in the program, and two nodes are
" connected with an arc if the corresponding variables can be live at
" the same time. The interference graph for the program can be derived
" from the interference graph for the individual procedures (constructed
" in a standard coloring-based intraprocedural allocator) and the
" program call graph. [stuff omitted]
" Unfortunately, [....] this approach is computationally unacceptable.
" The interference graph for a large program whould be enormous -- the
" locals of a procedure active at a call site would interfere with all
" the locals of all the procedures that could be activated by the call.
" For the program opt [one of their Lisp benchmarks] (which has 220
" procedures and 3500 lines of source code), the interference graph
" would contain over 500 nodes (number of live ranges) and more than
" 50000 arcs! A straightforward application of graph coloring to the
" interprocedural register allocation problem appears impractical.




Now my question is this: Although this method appears impractical to
Stenkiste and Hennessy, has someone actually tried it? What is it
that makes it so obviously impractical? 500 live ranges, with an
average of 100 neighbours in the interference graph, does not seem like
enormous numbers to me.


-- Thomas Johnsson (johnsson@cs.glasgow.ac.uk)

Return to the comp.compilers page.
Search the comp.compilers archives again.