|Text of Jim Welsh and Atholl Hay: A Model Implementation of Standard P email@example.com (Hans Otten) (2004-07-13)|
|Re: Text of Jim Welsh and Atholl Hay: A Model Implementation of Standa firstname.lastname@example.org (Franck Pissotte) (2004-07-15)|
|Number of Phi-functions in SSA graph email@example.com (Bageshri Sathe) (2005-03-24)|
|Re: Number of Phi-functions in SSA graph firstname.lastname@example.org (Diego Novillo) (2005-03-25)|
|Re: Number of Phi-functions in SSA graph email@example.com (Nathan Moore) (2005-03-25)|
|Re: Number of Phi-functions in SSA graph firstname.lastname@example.org (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 email@example.com (Jeremy Singer) (2005-04-11)|
|From:||"F. Liekweg" <firstname.lastname@example.org>|
|Date:||25 Mar 2005 21:57:00 -0500|
|Organization:||University of Karlsruhe, Germany|
|References:||04-07-030 04-07-041 05-03-086|
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.
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
Florian Liekweg | Dot is a very forgiving language; it should
Universitšt Karlsruhe | be considered some form of religion.
================================= email@example.com ==
Return to the
Search the comp.compilers archives again.