Re: graph coloring

"Robert Thorpe" <>
8 Feb 2004 21:58:30 -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)
graph coloring (1997-06-13)
| List of all articles for this month |

From: "Robert Thorpe" <>
Newsgroups: comp.compilers
Date: 8 Feb 2004 21:58:30 -0500
Organization: Compilers Central
References: 04-02-017
Keywords: registers, optimize
Posted-Date: 08 Feb 2004 21:58:30 EST

>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
>> 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.

Post a followup to this message

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