Re: graph coloring

John McEnerney <jmcenerney@austin.rr.com>
12 Feb 2004 11:00:15 -0500

          From comp.compilers

Related articles
Graph Coloring rsherry8@comcast.net (Robert Sherry) (2004-02-01)
Re: Graph Coloring jle@forest.owlnet.rice.edu (2004-02-04)
Re: graph coloring Robert.Thorpe@antenova.com (Robert Thorpe) (2004-02-08)
Re: graph coloring jmcenerney@austin.rr.com (John McEnerney) (2004-02-12)
Re: Graph Coloring touati@prism.uvsq.fr (TOUATI Sid) (2004-02-12)
graph coloring bsr@cs.clemson.edu (Ramesh B S) (1996-03-20)
Re: graph coloring dgillies@hpax.cup.hp.com (David Gillies) (1996-03-22)
Re: graph coloring napi@ms.mimos.my (1996-03-25)
graph coloring meleis@ece.neu.edu (1997-06-13)
| List of all articles for this month |

From: John McEnerney <jmcenerney@austin.rr.com>
Newsgroups: comp.compilers
Date: 12 Feb 2004 11:00:15 -0500
Organization: Road Runner High Speed Online http://www.rr.com
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"
<Robert.Thorpe@antenova.com> 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
1980.


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.