|Graph Coloring email@example.com (Robert Sherry) (2004-02-01)|
|Re: Graph Coloring firstname.lastname@example.org (2004-02-04)|
|Re: graph coloring Robert.Thorpe@antenova.com (Robert Thorpe) (2004-02-08)|
|Re: graph coloring email@example.com (John McEnerney) (2004-02-12)|
|Re: Graph Coloring firstname.lastname@example.org (TOUATI Sid) (2004-02-12)|
|graph coloring email@example.com (Ramesh B S) (1996-03-20)|
|Re: graph coloring firstname.lastname@example.org (David Gillies) (1996-03-22)|
|Re: graph coloring email@example.com (1996-03-25)|
|[1 later articles]|
|From:||firstname.lastname@example.org (Jason Lee Eckhardt)|
|Date:||4 Feb 2004 21:30:07 -0500|
|Organization:||Rice University, Houston, TX|
|Posted-Date:||04 Feb 2004 21:30:07 EST|
Robert Sherry <email@example.com> 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:
www.cs.princeton.edu/~appel/graphdata/ 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
Should you learn anything insightful from either exercise, you might
consider publishing your findings or posting them here.
Return to the
Search the comp.compilers archives again.