|Graph Coloring firstname.lastname@example.org (Robert Sherry) (2004-02-01)|
|Re: Graph Coloring email@example.com (2004-02-04)|
|Re: graph coloring Robert.Thorpe@antenova.com (Robert Thorpe) (2004-02-08)|
|Re: graph coloring firstname.lastname@example.org (John McEnerney) (2004-02-12)|
|Re: Graph Coloring email@example.com (TOUATI Sid) (2004-02-12)|
|graph coloring firstname.lastname@example.org (Ramesh B S) (1996-03-20)|
|Re: graph coloring email@example.com (David Gillies) (1996-03-22)|
|Re: graph coloring firstname.lastname@example.org (1996-03-25)|
|graph coloring email@example.com (1997-06-13)|
|From:||John McEnerney <firstname.lastname@example.org>|
|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 email@example.com, "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.