Re: Number of Phi-functions in SSA graph

Nathan Moore <nathan.moore@sdc.cox.net>
25 Mar 2005 21:55:44 -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: Nathan Moore <nathan.moore@sdc.cox.net>
Newsgroups: comp.compilers
Date: 25 Mar 2005 21:55:44 -0500
Organization: Cox Communications
References: 04-07-030 04-07-041 05-03-086
Keywords: SSA, analysis
Posted-Date: 25 Mar 2005 21:55:44 EST

Bageshri Sathe wrote:
> Hi,
>
> 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.


Why does it matter (please answer)?




Depends on what values you know. The simple answer would be that
there is no upper-bound (in the theoretical/mathematical world).
(variable means original variable in non-ssa form) If you know the
number of nodes with multiple immediate dominator and the number of
variables, you can get an upper limit by multiplying those together,
b/c in any block where control can flow from more than one place, all
variables could be phi-functioned, even if they are not live. The
cartesiam product of (set of blocks with multiple paths in) X (the set
of variables in the function).


This will most likely be a BIG number, but it should be an upper
limit. If I knew more about what you were doing and why it mattered.
Just a stab in the dark, but for someone who asks this, it may matter
how many paths there are into a block if you are using something like


x4 = phi(x0,phi(x1,phi(x2,x3)))
rather than
x4 = phi(x0,x1,x2,x3)


There are probably other ways to increase the number of phi()s with
out altering the semantics of the program that may be easier to work
with or create for different types of actions and/or transformations,
so the limit is really hard to nail down, but I can't think of a
reason you would want to.


Nathan Moore


Post a followup to this message

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