Re: Graph Coloring (Jason Lee Eckhardt)
4 Feb 2004 21:30:07 -0500

          From comp.compilers

Related articles
Graph Coloring (Robert Sherry) (2004-02-01)
Re: Graph Coloring (2004-02-04)
Re: graph coloring (Robert Thorpe) (2004-02-08)
Re: graph coloring (John McEnerney) (2004-02-12)
Re: Graph Coloring (TOUATI Sid) (2004-02-12)
graph coloring (Ramesh B S) (1996-03-20)
Re: graph coloring (David Gillies) (1996-03-22)
Re: graph coloring (1996-03-25)
[1 later articles]
| List of all articles for this month |

From: (Jason Lee Eckhardt)
Newsgroups: comp.compilers
Date: 4 Feb 2004 21:30:07 -0500
Organization: Rice University, Houston, TX
References: 04-02-017
Keywords: registers, optimize
Posted-Date: 04 Feb 2004 21:30:07 EST

Robert Sherry <> wrote:
> I am in the process of developing a new graph coloring
>algorithm that I think is applicable to graphs generated in register
>allocation. It is my understanding that graphs that needed to me
>coloring in a compiler have a significant number of vertices that are
>of high degree and at the same time a significant number of vertices
>of low degree.
> Is this true and can somebody tell me if this is discussed
>in any journal articles?

While I can't give you an article discussing this particular metric,
you could easily measure it for yourself. You will find roughly
30,000 compiler-produced interference graphs at:
 You can write a simple
program in less than an hour to parse the above data to compute the
desired metric and gather statistics.

Of course, the only way to check that your technique will actually
perform well in practice is to implement it in your favorite compiler
and run experiments. This would be relatively straightforward in a
pre-existing register allocator since you would only be replacing the
coloring algorithm.

Should you learn anything insightful from either exercise, you might
consider publishing your findings or posting them here.


Post a followup to this message

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