Re: Register allocation patent

stevec@pact.srf.ac.uk (Stephen Clarke) writes:
>What is the status of IBM's patent on register allocation and spilling
>via graph coloring? Most people seem to reference Chaitin's work when
>describing their register allocators, including numerous commercial
>companies; is the patent unenforceable?


IBM's US patent on register allocation via graph coloring #4,571,678
was issued in Feb. 1986, so the patent will remain in effect for a bit
more seven years (a US patent has a 17 year life). There are at least
two other US patents on register allocation. Rice University has
patent #5,249,295 issued in Sept. 1993 on the optimistic graph
coloring method invented by Briggs et al. Intel has patent #5,367,684
issued in Nov. 1994 on a matrix method that combines some of the
attributes of Chaitin's method with those of Chow and Hennessy's
priority-based coloring method. To my knowledge this work by Kevin J.
Smith at Intel is not reported elsewhere.


Note that the priority-based coloring method by Chow and Hennessy is
used commercially and (to my knowledge) is not patented. Also the
hierarchical graph coloring method by Callahan and Koblenz is used
commercially and (to my knowledge) is not patented.


There are often lawful ways of avoiding a patent. At first the GCC
register allocator seemed rather odd to me. GCC first does a local
non-graph-coloring register allocation. This is followed by a global
graph-coloring allocation that, unlike a Chaitin-style graph-coloring
allocation, spills a real register rather than a symbolic register.
When I became aware of the IBM patent I surmised that the GCC method
may have been selected to avoid the IBM patent. Incidentally, an
evaluation by Foster and Grossman [IEEE Southeastcon, April, 1992] and
our own evaluation show that the GCC allocator is competitive with the
Chaitin-style approach.




Kent Wilken
ECE Department, UC Davis
wilken@ece.ucdavis.edu


[Disclaimer: I am not an attorney and this post does not constitute
legal advise.]
--

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