Path: utzoo!attcan!uunet!aplcen!samsung!cs.utexas.edu!yale!mintaka!spdcc!ima!esegue!compilers-sender
From: siritzky@apollo.hp.com (Brian Siritzky)
Newsgroups: comp.compilers
Subject: Re: Reg. Alloc. - Graph Coloring
Keywords: optimize, design
Message-ID: <9010251440.AA25798@xuucp.ch.apollo.com>
Date: 25 Oct 90 14:50:35 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: siritzky@apollo.hp.com (Brian Siritzky)
Organization: Compilers Central
Lines: 25
Approved: compilers@esegue.segue.boston.ma.us

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
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.