Re: Graph coloring register allocation via iterative scan

sylerugby@yahoo.com
17 Feb 2006 00:09:10 -0500

          From comp.compilers

Related articles
Graph coloring register allocation via iterative scan avayvod@gmail.com (2006-02-03)
Re: Graph coloring register allocation via iterative scan robert.thorpe@antenova.com (Rob Thorpe) (2006-02-06)
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: sylerugby@yahoo.com
Newsgroups: comp.theory,comp.compilers,comp.programming
Date: 17 Feb 2006 00:09:10 -0500
Organization: http://groups.google.com
References: 06-02-018
Keywords: registers
Posted-Date: 17 Feb 2006 00:09:10 EST

Hi,


I just want ot make a small comment on graphs and register allocation.


I read the paper on Linear Scan Register Allocation, and what
immediately astonished me ist that it is in fact a graph coloring
algorithm ! More precisely it is interval graph coloring. All what is
said about the algorithm and its complexity is well known in graph
theory since at least 1970 (the book of Claude Berge: Graphs and
Hypergraphs).


Of course the use of this algorithm in the context of global register
allocation is interesting, as interval graphs model only live ranges in
code without control structures like conditionals and loops (i.e basic
blocks). In fact when the results are good vs Chaitin-Briggs
algorithm, then I would bet that is because few conditionals are
present in the code. Chaitin-Briggs algorithm is a general graph
coloring algorithm. The heuristic in the paper with the SCCs is aimed
at that goal I think.


As a note, interference graphs built in the case of loops (single loop
without conditionals) are circular-arc graphs whose coloring is also
well known in the art (Tucker 1975 and1978 for the coloring, and the
paper on spill code mimisation in PLDI 89 by Bernstein et al. (Golumbic
is one of the authors)for mentioning this, and of course the paper of
Laurie Hendren at CC'92 for register allocation in loops.


I would also like to mention the PhD thesis of Angelika Zobel (1992),
which, if I remember well, tries to modify the code to make the
interference graphs similar to graphs whose coloring is easier and
well-known (like interval or circular-arc graphs). But it is a bit in
the fog of my memory.


For intersection graphs (interval graphs, circle graphs, circular-arc
graphs) it is common place to work on the interval families underlying
the graph structure and not on the graph structure itself. It is
easier.


It would be nice if compiler writers open other books than compiler
books sometimes, espacially when dealing with problems or solutions not
directlly in the field.


Sylvain Lelait


Post a followup to this message

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