|Graph Coloring email@example.com (Robert Sherry) (2004-02-01)|
|Re: Graph Coloring firstname.lastname@example.org (2004-02-04)|
|Re: graph coloring Robert.Thorpe@antenova.com (Robert Thorpe) (2004-02-08)|
|Re: graph coloring email@example.com (John McEnerney) (2004-02-12)|
|Re: Graph Coloring firstname.lastname@example.org (TOUATI Sid) (2004-02-12)|
|graph coloring email@example.com (Ramesh B S) (1996-03-20)|
|Re: graph coloring firstname.lastname@example.org (David Gillies) (1996-03-22)|
|Re: graph coloring email@example.com (1996-03-25)|
|graph coloring firstname.lastname@example.org (1997-06-13)|
|From:||John McEnerney <email@example.com>|
|Date:||12 Feb 2004 11:00:15 -0500|
|Organization:||Road Runner High Speed Online http://www.rr.com|
|Posted-Date:||12 Feb 2004 11:00:15 EST|
On 2/8/04 8:58 PM, in article firstname.lastname@example.org, "Robert Thorpe"
> 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]
Return to the
Search the comp.compilers archives again.