Re: Number of Phi-functions in SSA graph

>>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
SSA program:


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


Best regards,
Jeremy

Return to the comp.compilers page.
Search the comp.compilers archives again.