Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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) |
| 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]
Return to the
comp.compilers page.
Search the
comp.compilers archives again.