Re: Easily retargetable register allocators (Clyde Smith-Stubbs)
Fri, 4 Oct 91 02:48:01 GMT

          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: (Clyde Smith-Stubbs)
Followup-To: comp.patents
Keywords: registers, optimize, legal
Organization: HI-TECH Software, Brisbane, QLD, Australia.
References: 91-09-083 91-10-006
Date: Fri, 4 Oct 91 02:48:01 GMT (Mike Percy) writes:

>An unfortunate thing has occurred here. IBM holds patents on the
>algorithms described therein,

>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.

Whoa, just a minute! Chaitin certainly did not describe a solution to
register allocation, graph colouring or any other NP-complete problem. He
described an heuristic, applicable to a certain class of processors, for
register allocation. It does not guarantee a minimal solution to the
problem. Graph colouring, register allocation or whatever is only
NP-complete if the problem is phrased in terms of an optimal or minimal
solution. There are any number of heuristics that produce approximations
to the "solution" of the problem. Such heuristics may or may not be useful
for finding approximations to the solutions of other NP-complete problems.

However, I agree it should not be patentable. On the upside, I doubt the
patent is worth much, as there are numerous other algorithms to do the
same thing which would not infringe the patent. In addition, Chaitin's
algorithm (which performs register selection after instruction selection)
is not even terribly good for many real-world processors where
insctruction selection and register selection are difficult to separate.

  Clyde Smith-Stubbs | HI-TECH Software, | Voice: +61 7 300 5011 | P.O. Box 103, Alderley, | Fax: +61 7 300 5246
  ...!nwnexus!hitech!clyde | QLD, 4051, AUSTRALIA. | BBS: +61 7 300 5235
[Remember, what's patented is is coloring+spill, not coloring per se. This
is wandering away from compilers, followups elsewhere, please. -John]

Post a followup to this message

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