|Text of Jim Welsh and Atholl Hay: A Model Implementation of Standard P firstname.lastname@example.org (Hans Otten) (2004-07-13)|
|Re: Text of Jim Welsh and Atholl Hay: A Model Implementation of Standa email@example.com (Franck Pissotte) (2004-07-15)|
|Number of Phi-functions in SSA graph firstname.lastname@example.org (Bageshri Sathe) (2005-03-24)|
|Re: Number of Phi-functions in SSA graph email@example.com (Diego Novillo) (2005-03-25)|
|Re: Number of Phi-functions in SSA graph firstname.lastname@example.org (Nathan Moore) (2005-03-25)|
|Re: Number of Phi-functions in SSA graph email@example.com (F. Liekweg) (2005-03-25)|
|Re: Number of Phi-functions in SSA graph Martin.Ward@durham.ac.uk (Martin Ward) (2005-03-31)|
|Re: Number of Phi-functions in SSA graph firstname.lastname@example.org (Jeremy Singer) (2005-04-11)|
|From:||Martin Ward <Martin.Ward@durham.ac.uk>|
|Date:||31 Mar 2005 23:34:33 -0500|
|References:||04-07-030 04-07-041 05-03-086|
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
%D |JUL|, 1999
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.
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.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
Return to the
Search the comp.compilers archives again.