31 Mar 2005 23:34:33 -0500

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) |

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.