25 Mar 2005 21:57:00 -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: | "F. Liekweg" <liekweg@ipd.info.uni-karlsruhe.de> |

Newsgroups: | comp.compilers |

Date: | 25 Mar 2005 21:57:00 -0500 |

Organization: | University of Karlsruhe, Germany |

References: | 04-07-030 04-07-041 05-03-086 |

Keywords: | SSA, analysis |

Truly, Bageshri Sathe wrote on 03/25/05 03:15:

*> 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.*

Hello,

You need a Phi node whenever two different definitions for a variable

are joined, hence the upper bound on Phi nodes in an SSA graph is

n_var \times n_join, where n_var is the number of local variables

(including function parameters) and where n_join is the number of

basic blocks that have more than one predecessor.

My estimate is, however, that You'll have to go a long way to find an

actual piece of source code which only comes near this pessimistic

bound.

cheers,

Florian

--

=======================================================================

Florian Liekweg | Dot is a very forgiving language; it should

Universität Karlsruhe | be considered some form of religion.

================================= graphviz-interest@research.att.com ==

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.