Re: Learning about Graph Coloring

benjamin.vitale@acadiau.ca (Benjamin Vitale) writes:


>Can anyone suggest some simple introductory information on algorithms
>for the graph coloring problem. A colleague is writing a survey paper
>on RISC compiler optimization and is having trouble finding resources.


Do you want to color graphs or allocate registers? I assume the latter.
Here's a bunch of papers


The first paper describing a complete allocator based on graph
coloring was


    title="Register Allocation via Coloring",
    author="Gregory J. Chaitin and Marc A. Auslander and Ashok K. Chandra and
                    John Cocke and Martin E. Hopkins and Peter W. Markstein",
    journal="Computer Languages",
    volume=6,
    year=1981,
    month=jan,
    pages="47--57"




A second paper describes an improved coloring heuristic


    title="Register Allocation and Spilling via Graph Coloring",
    author="Gregory J. Chaitin",
    journal=sigplan,
    year=1982,
    month=jun,
    volume=17,
    number=6,
    note=pldi82,
    pages="98--105"


(It was presented at the 1982 Compiler Construction Conference, now called
the Conference for Programming Language Design and Implementation, or
PLDI. The proceedings were printed as an issue of SIGPLAN Notices.)




My thesis describes improvements and extensions to Chaitin's work.
Basically, you don't want to use Chaitin's coloring heuristic. Instead
use mine (which relies heavily on Chaitin's work).


    author="Preston Briggs",
    title="Register Allocation via Graph Coloring",
    school="Rice University",
    year=1992,
    month=apr


Some of the results have been published separately


    title="Coloring Heuristics for Register Allocation",
    author="Preston Briggs and Keith D. Cooper and Ken Kennedy
                and Linda Torczon",
    journal=sigplan,
    year=1989,
    month=jul,
    volume=24,
    number=7,
    note=pldi89,
    pages="275--284"


    title="Coloring Register Pairs",
    author="Preston Briggs and Keith D. Cooper and Linda Torczon",
    pages="3--13",
    journal=loplas,
    year=1992,
    month=mar,
    volume=1,
    number=1


    title="Rematerialization",
    author="Preston Briggs and Keith D. Cooper and Linda Torczon",
    pages="311--321",
    journal=sigplan,
    year=1992,
    month=july,
    volume=27,
    number=7,
    note=pldi92




Chow's thesis and a PLDI paper with Hennessy describe his approach to
the problem. The paper below is the best reference to their work.


    title="The Priority-Based Coloring Approach to Register Allocation",
    author="Fred C. Chow and John L. Hennessy",
    pages="501--536",
    journal=toplas,
    year=1990,
    month=oct,
    volume=12,
    number=4
--

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