Re: Number of Phi-functions in SSA graph

On Friday 25 Mar 2005 2:15 am, Bageshri Sathe wrote:
> I was wondering what is the upper bound on number of phi-functions in a
> minimal SSA graph. Does it depend upon number of program variables or join
> nodes in the CFG or both? Any literature that discusses this? I tried to
> search on web but not sure whether this particular issue is discussed
> anywhere. Any help would be greatly appreciated.


An excellent paper on SSA computation is the following:


%A Gianfranco Bilardi
%A Keshav Pingali
%T The Static Single Assignment Form and its Computation
%R Cornell University Technical Report
%U http://www.cs.cornell.edu/Info/Projects/Bernoulli/papers/ssa.ps
%D |JUL|, 1999
%P 1-37


This presents an optimal algorithm for phi-placement for a single variable
which is linear in the number of edges in the graph. This is an especially
interesting result since phi placement is computed from the dominance
frontier, but the size of the dominance frontier is quadratic in the size of
the program! Bilardi and Pingali's algorithm achieves linearity by
computing only as much of he dominance frontier (DF) as needed,
and precomputing the DF for carefully selected nodes in the graph.


The FermaT Transformation system includes an implementation
of their algorithm, as well as an implementation of their algorithm
for optimal control dependency computation.


http://www.cse.dmu.ac.uk/~mward/fermat.html
http://www.dur.ac.uk/martin.ward/fermat.html


Note: the algorithm is linear and optimal for a *single* variable.
This leads to a quadratic algorithm for phi placement for *all* variables.
I believe it is an open question whether there is a better algorithm
for phi placement for all variables.


--
Martin


Martin.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4

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