Re: Easily retargetable register allocators

e86jh@efd.lth.se (Jens Hansson) writes:


>I am working on a machine independent or easily retargetable register
>allocator, alternatively a register allocator generator, for my M.Sc.
>project.


>Chaitin, Auslander, Chandra, Cocke, Hopkins, Markstein,
> "Register Allocation via Coloring",
> Computer Languages 6 (1981), pp. 47 - 57.


>Chaitin, "Register Allocation and Spilling via Graph Coloring",
> ACM SIGPLAN Notices, 17, 6 (June 1982), (Proceedings of the SIGPLAN 82
> Symposium on Compiler Construction), pp. 201 - 207.


An unfortunate thing has occurred here. IBM holds patents on the
algorithms described therein, as Chaitin et. al were IBM employees at
the time, working on the PL/I compiler for the /370 mainframes. This
was brought up recently in comp.patents (or maybe misc.int-property or
misc.legal.computing). A few other compiler techniques were listed as
patented (some code movement stuff, and probably other stuff as well).


What kills me is that while using GC to do RA is certainly clever and
useful, does it deserve a patent? I think not. Register allocation (and
the more general quadratic assignment problem) is NP-complete. Graph
coloring is NP-complete. Since there is, by definition, some
transformation that can convert one NP-complete problem into any other
given NP-complete problem, Chaitin simply described a transform that had
to exist, again by definition. It's not even a particularly complex
transform! Certainly not worthy of a patent.


"I don't know about your brain, but mine is really...bossy."
Mike Percy grimlok@hubcap.clemson.edu
ISD, Clemson University mspercy@clemson.BITNET
(803)656-3780 mspercy@clemson.clemson.edu
[Chaitin's patent 4,571,678 is not on graph coloring per se, but on the
version of it that includes spilling. Make of that what you will. His
earlier article puts the basic coloring scheme into the putlib domain. -John]
--

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