Re: Newbie SSA question

Martin Ward <Martin.Ward@durham.ac.uk> wrote:
>Kevin Tucker (Kevin.Tucker@Microchip.com) writes:
>> The question is, when converting to SSA form, are you actually
>> allocating new variables for each assignment, or are you just "renaming"
>> them for notational purposes?.
>
>If you simply convert to SSA and then back again, then it doesn't matter
>which you do. But you usually convert to SSA form in order to do some
>further optimisations, in which case you can't necessarily just
>"drop the subscripts" to convert back. Translate the phi functions
>to a set of assignments (one on each incoming egde) and then do
>register allocation to eliminate the extra moves. See Section 19.6
>of "Modern Compiler Implementation in C" by Andrew W. Appel.


Indeed, if one has converted the CFG prior to SSA analysis
into "edge-split" form, then any block with phi-functions is
the sole successor of its predecessors, and it's possible to
represent the phi-functions as operations at the ends of those
predecessors. One of the phi-ops serves as a representative
for the group, for use as an operand in later computation.
And the phi-ops all refer to their representative and to
their sibling. This scheme is especially nice when using an
intermediate representation based on a triple table with
fixed-size operations and each operation's index also represents
its value.


For example, instead of the "usual" SSA form:


bb 1: 101: load something
102: jump to 4
bb 2: 103: load something else
104: jump to 4
bb 3: 105: load yet something else
106: jump to 4
bb 4: 107: phi (101, 103, 105)
108: compute an address
109: store (108, 107)


one would use:


bb 1: 101: load something
110: phi (101, representative=110, next=111)
102: jump to 4
bb 2: 103: load something else
111: phi (103, representative=110, next=112)
104: jump to 4
bb 3: 105: load yet something else
112: phi (105, representative=110, next=0)
106: jump to 4
bb 4: 108: compute an address
109: store (108, 110)


I used this kind of representation in my most recent compiler
(C for a forthcoming proprietary processor) and it permits both
very fast compilation as well as simplifying some algorithms.
Once the program is in SSA, it need not necessarily come back out.
The phi-ops just become coalescence points in register assignment.


Regards,


Peter Klausler
Principal Engineer, Cray Inc.
pmk@cray.com

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