Re: Reg. Alloc. - Graph Coloring

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

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