Re: Reg. Alloc. - Graph Coloring

preston@titan.rice.edu (Preston Briggs)
Tue, 23 Oct 90 22:18:30 GMT

          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: preston@titan.rice.edu (Preston Briggs)
Keywords: code, optimize
Organization: Rice University, Houston
References: <9010181425.AA15324@cs.clemson.edu> <9010191556.AA11673@dynamo.ecn.purdue.edu>
Date: Tue, 23 Oct 90 22:18:30 GMT

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


Post a followup to this message

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