Path: utzoo!utgpu!watserv1!watmath!att!att!ima!esegue!compilers-sender
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Reg. Alloc. - Graph Coloring
Keywords: code, optimize
Message-ID: <1990Oct23.221830.29332@rice.edu>
Date: 23 Oct 90 22:18:30 GMT
References: <9010181425.AA15324@cs.clemson.edu> <9010191556.AA11673@dynamo.ecn.purdue.edu>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: preston@titan.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 40
Approved: compilers@esegue.segue.boston.ma.us

In article <9010191556.AA11673@dynamo.ecn.purdue.edu> hankd@ecn.purdue.edu (Hank Dietz) writes:

>[6]	(A cheap approximate global technique.)  The interference
>	graph coloring that is most often credited to Chaitin.
>	Actually, Chaitin's primary contribution appears to have been
>	the node-removal coloring scheme

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.

	Register Allocation via Coloring
	Chaitin, Auslander, Chandra, Cocke, Hopkins, Markstein
	Computer Languages 6 (1981)
	pp. 47-57

	Register Allocation and Spilling via Coloring
	Chaitin
	Proceedings of the Sigplan '82 Symposium on Compiler Construction
	pp. 98-105

I agree that the 2nd paper is mainly concerned with the node removal
technique; but it also makes some points about implementation (that are
unfortunately missed at times).  However, the 1st paper makes many
contributions:
	refinements leading to the ultimate notion of interference
	implementation concerns
	handling machine details

and certainly others I've forgotten.  Many implementors would benefit
from a careful rereading of this paper.

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