Re: Graph coloring register allocation via iterative scan

"dkoes" <koes@cmu.edu>
11 Mar 2006 23:36:33 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: Graph coloring register allocation via iterative scan vmakarov@redhat.com (Vladimir Makarov) (2006-02-07)
Re: Graph coloring register allocation via iterative scan avayvod@gmail.com (Whywhat) (2006-02-11)
Re: Graph coloring register allocation via iterative scan vmakarov@redhat.com (Vladimir Makarov) (2006-02-14)
Re: Graph coloring register allocation via iterative scan sylerugby@yahoo.com (2006-02-17)
Re: Graph coloring register allocation via iterative scan Sid.Touati@inria.fr (Sid Touati) (2006-02-20)
Re: Graph coloring register allocation via iterative scan u.hobelmann@web.de (Ulrich Hobelmann) (2006-02-24)
Re: Graph coloring register allocation via iterative scan koes@cmu.edu (dkoes) (2006-03-11)
| List of all articles for this month |

From: "dkoes" <koes@cmu.edu>
Newsgroups: comp.theory,comp.compilers,comp.programming
Date: 11 Mar 2006 23:36:33 -0500
Organization: http://groups.google.com
References: 06-02-01806-02-115
Keywords: registers, optimize

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


Post a followup to this message

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