Path: utzoo!attcan!uunet!wuarchive!cs.utexas.edu!sun-barr!olivea!mintaka!spdcc!ima!esegue!compilers-sender
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Reg. Alloc. - Graph Coloring
Keywords: optimize, design
Message-ID: <1990Oct26.140411.7678@rice.edu>
Date: 26 Oct 90 14:04:11 GMT
References: <9010251440.AA25798@xuucp.ch.apollo.com>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: preston@titan.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 34
Approved: compilers@esegue.segue.boston.ma.us

I wrote:
>> 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.

and
In article <9010251440.AA25798@xuucp.ch.apollo.com> siritzky@apollo.hp.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
>Cocke.

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.

-- 
Preston Briggs
preston@titan.rice.edu
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.