Re: Number of Phi-functions in SSA graph

Jeremy Singer <jsinger@cs.man.ac.uk>
11 Apr 2005 00:19:45 -0400

          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)
Interprocedural Constant Propagation bageshri@cse.iitb.ac.in (Bageshri Sathe) (2005-04-30)
| List of all articles for this month |

From: Jeremy Singer <jsinger@cs.man.ac.uk>
Newsgroups: comp.compilers
Date: 11 Apr 2005 00:19:45 -0400
Organization: Compilers Central
References: 04-07-030 04-07-041 05-03-086 05-03-095
Keywords: analysis
Cc: jsinger@cs.man.ac.uk

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


Post a followup to this message

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