Re: Graph Coloring

Robert Sherry <rsherry8@comcast.net> 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
coloring algorithm.


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


    jason.

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