Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!zaphod.mps.ohio-state.edu!rpi!bu.edu!att!att!ima!esegue!compilers-sender
From: sasmkg@dev.sas.com (Mark Gass)
Newsgroups: comp.compilers
Subject: Re: Reg. Alloc. - Graph Coloring
Summary: "Register Coloring" is not an algorithm
Keywords: optimize, design
Message-ID: <1990Nov02.220306.5661@unx.sas.com>
Date: 2 Nov 90 22:03:06 GMT
References: <9010181425.AA15324@cs.clemson.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: sasmkg@dev.sas.com (Mark Gass)
Organization: SAS Institute Inc.
Lines: 18
Approved: compilers@esegue.segue.boston.ma.us

I don't think that "graph coloring" is a register allocation algorithm.
It is really a graph-theoretic formulation of the register allocation
problem. The statement of the problem says nothing about how you will
solve it. Thus, all papers involving graph coloring are not simply
refinements to Chaitin's ideas. 

The algorithm proposed in "Register Allocation by Priority Based Coloring"
by Chow and Hennessy (SIGPLAN 84 Compiler Construction Conf.) is completely
different from Chaitin's (most notably because it will split live ranges).

I have not seen any empirical studies comparing the two, but I believe
the Chow and Hennessy approach to be generally superior.

Mark Gass         (SASMKG@DEV.SAS.COM)
SAS/C (370) Optimization and Code Generation
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.