Re: Graph coloring register allocation via iterative scan

Regarding the original request for a comparison between linear scan
and graph coloring allocators, I've collated Regarding the original
request for a comparison between linear scan and graph coloring
allocators, I've collated some data I had comparing gcc's default
allocator to the now defunct graph allocator. Of course, the default
allocator isn't a linear scan allocator, but I thought the comparison
might be informative. The report, "A Comparison of Allocators", can
be found at http://www.cs.cmu.edu/~dkoes/research.html


The graph coloring aspect of register allocation is something of a red
herring. It's easy for interference graphs from a single basic block
or code in SSA form. There are several theory-centric papers that
prove things about the colorability of structured programs (i.e.
goto-free C) because they have bounded tree-width (Bodlaender,
Gustedt, and Telle. Linear-time reigster allocation for a fixed number
of registers; Thorup. All structured programs have small tree width
and good register allocation). From a practical aspect, these results
aren't very useful. The traditional graph coloring algorithm
(originally due to Kempe) can correctly determine the colorability of
an interference graph 99% of the time.


What matters in getting a quality register allocation (especially when
there are only a small number of registers such as with x86), is what
you do when the interference graph is not colorable. If the graph is
not colorable and spilling is necessary, then the problem becomes
NP-complete, even for allocating a single block (V. Liberatore,
M. Farach, and U. Kremer. Hardness and algorithms for local register
allocation.).


For more detail into how graph coloring isn't very helpful to register
allocation, see "An Analysis of Graph Coloring Register Allocation"
also at http://www.cs.cmu.edu/~dkoes/research.html


-Dave

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