Re: Reg. Alloc. - Graph Coloring

siritzky@apollo.hp.com (Brian Siritzky)
Thu, 25 Oct 90 10:50:35 EDT

          From comp.compilers
Related articles
Reg. Alloc. - Graph Coloring pkolte@cs.clemson.edu (1990-10-18)
Re: Reg. Alloc. - Graph Coloring preston@titan.rice.edu (1990-10-18)
Re: Reg. Alloc. - Graph Coloring hankd@ecn.purdue.edu (1990-10-19)
Re: Reg. Alloc. - Graph Coloring preston@titan.rice.edu (1990-10-23)
Re: Reg. Alloc. - Graph Coloring siritzky@apollo.hp.com (1990-10-25)
Re: Reg. Alloc. - Graph Coloring preston@titan.rice.edu (1990-10-26)
Re: Reg. Alloc. - Graph Coloring sasmkg@dev.sas.com (1990-11-02)
| List of all articles for this month |
Newsgroups: comp.compilers
From: siritzky@apollo.hp.com (Brian Siritzky)
Keywords: optimize, design
Organization: Compilers Central
Date: Thu, 25 Oct 90 10:50:35 EDT

In-reply-to: preston@titan.rice.edu's message of 23 Oct 90 22:18 GMT


> I think you've probably understated Chaitin's contribution. He (and others)
> built the first graph coloring register allocator. They also published the
> first 2 papers describing such a beast. Chaitin was listed first in an
> otherwise alphabetical author list and was the only author on the second
> paper.


I beg to differ:


The first reference I have found applying graph coloring to the
register allocation problem is in the book "On Programming -- An
Interim Report on the SETL Project" by Jack Schwartz, 1975. Chaitin's
paper is 1982. ^^^^


On page 485 Schwartz gives the graph coloring algorithm for register
allocation, attributing ("The first algorithm due to J. Cocke ...") it to
Cocke. I would guess that the algorithm he described is in an even earlier
SETL Newsletter, but I don't have access to them to check.


Brian Siritzky (508) 256-6600 x5445 Hewlett-Packard, Apollo Systems Division
siritzky@apollo.hp.com
--

Post a followup to this message

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