Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!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: <1990Oct18.200646.9894@rice.edu>
Date: 18 Oct 90 20:06:46 GMT
References: <9010181425.AA15324@cs.clemson.edu>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: preston@titan.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 31
Approved: compilers@esegue.segue.boston.ma.us

In article <9010181425.AA15324@cs.clemson.edu> pkolte@cs.clemson.edu writes:

>Are there any register allocation techniques that do not use some variation
>of graph coloring ?

Sure.  There's a zillion ideas that work ok for allocation in a basic block.
The Dragon Book is a good source, especially the bibliography.  Allocation
across many basic blocks is more difficult, interesting, and profitable.

TN-Binding was developed at CMU as part of the PQCC project and was
apparently used in several projects.  The best description is in Bruce
Leverett's thesis, called (approximately) Register Allocation in an
Optimizing Compiler.  Check the library.

IBM had lots of ideas.  I don't know how many have been widely published.
Names like Beatty and Harbison (Harrison?)  come to mind.  Other work was
done by Tan.

Coloring is attractive in that it offers a nice abstraction, protecting you
from a lot of the grundgy details of the job.  Further, it offers a nice
framework for handling most of these grundgy details when you finally must.

The book isn't closed.  I know of others who are looking for good
alternatives (or perhaps have them).  Some of them may publish.

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