|Text of Jim Welsh and Atholl Hay: A Model Implementation of Standard P firstname.lastname@example.org (Hans Otten) (2004-07-13)|
|Re: Text of Jim Welsh and Atholl Hay: A Model Implementation of Standa email@example.com (Franck Pissotte) (2004-07-15)|
|Number of Phi-functions in SSA graph firstname.lastname@example.org (Bageshri Sathe) (2005-03-24)|
|Re: Number of Phi-functions in SSA graph email@example.com (Diego Novillo) (2005-03-25)|
|Re: Number of Phi-functions in SSA graph firstname.lastname@example.org (Nathan Moore) (2005-03-25)|
|Re: Number of Phi-functions in SSA graph email@example.com (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 firstname.lastname@example.org (Jeremy Singer) (2005-04-11)|
|From:||Nathan Moore <email@example.com>|
|Date:||25 Mar 2005 21:55:44 -0500|
|References:||04-07-030 04-07-041 05-03-086|
|Posted-Date:||25 Mar 2005 21:55:44 EST|
Bageshri Sathe wrote:
> 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)))
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.
Return to the
Search the comp.compilers archives again.