Re: Number of Phi-functions in SSA graph

Truly, Bageshri Sathe wrote on 03/25/05 03:15:
> 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.


Hello,


You need a Phi node whenever two different definitions for a variable
are joined, hence the upper bound on Phi nodes in an SSA graph is
  n_var \times n_join, where n_var is the number of local variables
(including function parameters) and where n_join is the number of
basic blocks that have more than one predecessor.


My estimate is, however, that You'll have to go a long way to find an
actual piece of source code which only comes near this pessimistic
bound.


cheers,
Florian
--
=======================================================================
Florian Liekweg | Dot is a very forgiving language; it should
Universität Karlsruhe | be considered some form of religion.
================================= graphviz-interest@research.att.com ==

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