Re: Coalescing register allocators

rusa@microsoft.com (Bjarne 'Rusa' Steensgaard) writes:
>I am looking for any and all kinds of information on coalescing register
>allocators.


>What we want to avoid is generating code like the following. If the
>X node is assigned the symbolic name r0, the Y node is assigned r1,
>and the gamma node is assigned r2, we will generate code like that.


> if (P) {
> r0 = X; /* code for the X node */
> r2 = r0; /* copying into the gamma node's register */
> } else {
> r1 = Y /* code for the Y node */;
> r2 = r1; /* copying into the gamma node's register */
> }


Chaitin's allocator gets rid of copies like those in your example --
one of the great strengths of his approach (and weaknesses of
competing approaches). Check his papers:


    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"


and


    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"


You should also look at my thesis for more details on how Chaitin's
allocators work and are implemented as well as some improvements.


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


As a completely disinterested party, I wonder what other alternatives
you were considering? And why?


Preston Briggs
--

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