|Reg. Alloc. - Graph Coloring email@example.com (1990-10-18)|
|Re: Reg. Alloc. - Graph Coloring firstname.lastname@example.org (1990-10-18)|
|Re: Reg. Alloc. - Graph Coloring email@example.com (1990-10-19)|
|Re: Reg. Alloc. - Graph Coloring firstname.lastname@example.org (1990-10-23)|
|Re: Reg. Alloc. - Graph Coloring email@example.com (1990-10-25)|
|Re: Reg. Alloc. - Graph Coloring firstname.lastname@example.org (1990-10-26)|
|Re: Reg. Alloc. - Graph Coloring email@example.com (1990-11-02)|
|From:||firstname.lastname@example.org (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Fri, 26 Oct 90 14:04:11 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
In article <9010251440.AA25798@xuucp.ch.apollo.com> email@example.com (Brian Siritzky) writes:
>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
The 1st Chaitin paper appeared in 1981. John Cocke was a coauthor.
Ershov talked about finding opportunities for overlapping storage
using graph coloring (and other NP-Complete problems) long ago,
perhaps 1967. Janet Fabri did further work in this area.
Cocke and Schwartz talked about it some.
But Chaitin et al. built it. That means they worked out all the
gory details that made it practical and interesting.
I think that's a significant contribution.
Return to the
Search the comp.compilers archives again.