Re: Graph Coloring and Register Allocation

anton@mips.complang.tuwien.ac.at (Anton Ertl)
21 Dec 2003 23:11:35 -0500

          From comp.compilers

Related articles
Graph Coloring and Register Allocation rsherry8@comcast.net (Robert Sherry) (2003-12-20)
Re: Graph Coloring and Register Allocation danwang74@hotmail.com (Daniel C. Wang) (2003-12-21)
Re: Graph Coloring and Register Allocation anton@mips.complang.tuwien.ac.at (2003-12-21)
Re: Graph Coloring and Register Allocation richard@imagecraft.com (Richard F. Man) (2003-12-21)
Re: Graph Coloring and Register Allocation touati@prism.uvsq.fr (TOUATI Sid) (2003-12-23)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: 21 Dec 2003 23:11:35 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 03-12-117
Keywords: registers, optimize
Posted-Date: 21 Dec 2003 23:11:35 EST

You write:
> I am currently developing a new graph coloring algorithm which I
>believe is well suited for use in compilers. These graphs come up in
>the register allocation problem. I believe that these graphs tend to
>have a lot of vertices of high degree (nearly n where n is the number
>of vertices in the graph), as well vertices with very low degrees. I
>believe this is true because most variables will be live throughout
>the subroutine ( or block ) and compiler generated temporaries will
>have a very short life. I am looking for a Journal article that
>states this is the case.


Don't know about that (maybe in one of the papers or books by Briggs,
Cooper and/or Torcson), but you can find a database of 27922 graphs
produced by a real compiler for real programs through
http://www.cs.princeton.edu/~appel/graphdata/


However, when we reviewed a paper that based its empirical evaluation
just on colouring these graphs, we complained about the missing
connection to metrics we (compiler construction people) care about, in
particular, spill cost. We still accepted the paper, though.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html


Post a followup to this message

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