Re: graph coloring

>Ramesh B S wrote:
>> Are there any standard compilers that use any of the graph coloring
>> techniques (like live range analysis, hierarchical coloring etc) to
do
>> register allocation?
>
> Sure, there's lots of production compilers that use graph coloring
>register allocators. I know from first hand experience that the HP
>PA-Risc and IBM XL-series compilers use graph coloring techniques that
>essentially boil down to Chaitin's method. However, I think gcc does
>not in order to avoid any conflict with IBM's patent on the technique.
>Maybe someone can confirm this.


Not any longer. IBM AFAIK don't have patents on graph coloring per se,
but patents on some rules for make the algorithm practical.


IBM have licensed the patents to the FSF, so GCC now uses it.


I think the most critical patent expires soon anyway.








Hmm, I've now reached that stage in a post where I know I have to
write a bit more or John's scripts will chuck out my message for
quoting too much text. So I'll say a bit more:


Last time I looked SGI Open64 uses Chow-Hennessey.


Graph coloring methods don't seem to be that much more efficient than
other slightly simpler methods from what I've seen.


Exactly how and where spilling is done is very important.


I've only ever looked at the old and new register allocators in GCC,
despite both being based on simple principles both are evilly complex
in practice.

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