Re: Number of Phi-functions in SSA graph

Martin Ward <Martin.Ward@durham.ac.uk>
31 Mar 2005 23:34:33 -0500

          From comp.compilers

Related articles
Text of Jim Welsh and Atholl Hay: A Model Implementation of Standard P msxhans@yahoo.com (Hans Otten) (2004-07-13)
Re: Text of Jim Welsh and Atholl Hay: A Model Implementation of Standa franck.pissotte@alussinan.org (Franck Pissotte) (2004-07-15)
Number of Phi-functions in SSA graph bageshri@cse.iitb.ac.in (Bageshri Sathe) (2005-03-24)
Re: Number of Phi-functions in SSA graph dnovillo@redhat.com (Diego Novillo) (2005-03-25)
Re: Number of Phi-functions in SSA graph nathan.moore@sdc.cox.net (Nathan Moore) (2005-03-25)
Re: Number of Phi-functions in SSA graph liekweg@ipd.info.uni-karlsruhe.de (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 jsinger@cs.man.ac.uk (Jeremy Singer) (2005-04-11)
| List of all articles for this month |

From: Martin Ward <Martin.Ward@durham.ac.uk>
Newsgroups: comp.compilers
Date: 31 Mar 2005 23:34:33 -0500
Organization: Compilers Central
References: 04-07-030 04-07-041 05-03-086
Keywords: analysis

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



Post a followup to this message

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