Re: Graph coloring register allocation via iterative scan

Sid Touati <Sid.Touati@inria.fr>
20 Feb 2006 21:43:24 -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: Sid Touati <Sid.Touati@inria.fr>
Newsgroups: comp.theory,comp.compilers,comp.programming
Date: 20 Feb 2006 21:43:24 -0500
Organization: I.N.R.I.A Rocquencourt
References: 06-02-018 06-02-115
Keywords: registers

Completely agreed, the linear scan register allocation didn't bring
anything new from the computer science perspective, and any person
aware about graph theory knows this.


Since many people working on code optimization are mainly interested in
computer engineering aspects, the linear scan register allocation seems
a new method to them, which is not really the case.


S




sylerugby@yahoo.com a écrit :
> 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
> directly in the field.


Post a followup to this message

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