Coalescing register allocators

I am looking for any and all kinds of information on coalescing register
allocators. In a prototype compiler we are developing, we only represent
how values flow around in the program; control structure is eliminated.
An if-statement in the source program (C code) becomes a set of selectors
between values flowing in from different sides at the join point:
The statement
        if (P) then a = X; else a = Y;
will be represented by the following graph:
            _ _ _
          / \ / \ / \
        | P | | X | | Y |
          \_/ \_/ \_/
            | \ /
            | _|_|_
            | / \
            |_____| gamma |
                          \_____/
                                |
                                |
The gamma node is selecting between the 4 and the 5 node depending on the
value computed by the P node.


After performing optimizations on this program representation, we have to
generate sequential code for the program. My question is related to the
allocation of registers in the code generation phase.


The first phase of the register allocator should assign some symbolic name
to each node in the graph. The coalescing register allocator algorithm that
I am looking for should assign the same symbolic name to the gamma node,
the X node, and the Y node, to avoid copying in the generated code. 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 */
        }


Thanks for any help with this problem,


Bjarne Steensgaard
Microsoft Research
--

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