Re: Number of Phi-functions in SSA graph

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

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.