|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)|
|Interprocedural Constant Propagation firstname.lastname@example.org (Bageshri Sathe) (2005-04-30)|
|From:||Jeremy Singer <email@example.com>|
|Date:||11 Apr 2005 00:19:45 -0400|
|References:||04-07-030 04-07-041 05-03-086 05-03-095|
|Posted-Date:||11 Apr 2005 00:19:45 EDT|
>>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?
This is a really interesting question. The number of phi-functions is
bounded above by the number of def-use edges that share a common use.
The number of phi-functions is bounded below by the number of
def-use-use-def webs (Muchnick, 1997) that contain more than one def.
The number of phi-functions depends on both control flow and data flow
behaviour of the subject program. So, both variable definitions and CFG
join points can affect it.
Here is a simple upper bound on the number of phi-functions in a minimal
-Assume program p has N nodes.
-So, assume p has O(N) original variables.
-In the worst case, there may be an edge from every node to every node in p.
-In the worst case, there may be a definition of every original variable
at every node in p.
-This worst case situation requires a phi-function for every original
variable at every node, which gives O(N^2) phi-functions.
The worst case assumptions are unlikely. Often CFGs have a reducible
structure, so it is not possible for every node to be joined to every
other node. Also, most variables are defined at O(1) program points. So
the worst case quadratic behaviour is rarely seen.
>>Any literature that discusses this?
> The various papers that describe techniques for PHI placement should
> help, but I'm not aware of anything that discusses this particular
> topic in detail.
Cytron et al (1991) discuss this worst case bound in section 9.1. I
have recently been investigating this issue for SSA and related
intermediate representations. My draft PhD dissertation is available
at http://www.cl.cam.ac.uk/~jds31/thesis/ if you are interested. The
title is "Static Program Analysis based on Virtual Register Renaming"
Return to the
Search the comp.compilers archives again.