Re: Reg. Alloc. - Graph Coloring

sasmkg@dev.sas.com (Mark Gass)
Fri, 02 Nov 90 22:03:06 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: sasmkg@dev.sas.com (Mark Gass)
Summary: "Register Coloring" is not an algorithm
Keywords: optimize, design
Organization: SAS Institute Inc.
References: <9010181425.AA15324@cs.clemson.edu>
Date: Fri, 02 Nov 90 22:03:06 GMT

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

Post a followup to this message

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