Re: Easily retargetable register allocators (Mike Percy)
Tue, 1 Oct 91 16:07:09 -0400

          From comp.compilers

Related articles
Easily retargetable register allocators (Jens Hansson) (1991-09-27)
Re: Easily retargetable register allocators (1991-10-01)
Re: Easily retargetable register allocators (1991-10-01)
Re: Easily retargetable register allocators (1991-10-04)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Mike Percy)
Keywords: registers, optimize, legal
Organization: Compilers Central
References: 91-09-083
Date: Tue, 1 Oct 91 16:07:09 -0400 (Jens Hansson) writes:

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

>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 or 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
ISD, Clemson University mspercy@clemson.BITNET
[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]

Post a followup to this message

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