Re: Number of Phi-functions in SSA graph

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

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