Re: graph coloring

John McEnerney <>
12 Feb 2004 11:00:15 -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: John McEnerney <>
Newsgroups: comp.compilers
Date: 12 Feb 2004 11:00:15 -0500
Organization: Road Runner High Speed Online
References: 04-02-017 04-02-080
Keywords: registers, optimize
Posted-Date: 12 Feb 2004 11:00:15 EST

On 2/8/04 8:58 PM, in article 04-02-080@comp.compilers, "Robert Thorpe"
<> wrote:

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

IBM has a patent on the Chaitin algorithm for register allocation and
spilling via graph coloring. (As contrasted with e.g. Chow's
Priority-based Coloring which is quite a different beast) That patent
probably does expire soon, as the original paper was published in

Rice University holds a patent for the Preston Briggs enhancement
(where you defer actual spilling to the color phase in case the
putative spill is not actually necessary). Most implementations of the
Chaitin allocator are also using Briggs' enhancements, but most people
are unaware that it is also patented.
[Chaitin's patent is 4,571,678, issued Feb 18 1986, so a 17 year term
would have expired last year. The second patent by Briggs, Keith
Cooper, Ken Kennedy, and Linda Torczon is 5,249,295 issued in 1993 so
it's still in force. -John]

Post a followup to this message

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