Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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) |
| From: | Diego Novillo <dnovillo@redhat.com> |
| Newsgroups: | comp.compilers |
| Date: | 25 Mar 2005 21:54:19 -0500 |
| Organization: | Red Hat Canada |
| References: | 04-07-030 04-07-041 05-03-086 |
| Keywords: | SSA, analysis |
| Posted-Date: | 25 Mar 2005 21:54:19 EST |
On Thu, Mar 24, 2005 at 09:15:05PM -0500, 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?
I assume that you mean minimal in the original sense (i.e., PHI nodes
are always added to the iterated dominance frontier of definition
sites). The pruned and semi-pruned forms will actually yield a
smaller number of PHI nodes, as the IDFs are pruned with live-in
information.
The main factor is the size of the iterated dominance frontier of each
definition site, and, of course, the number of definition sites.
For instance, if you have a very convoluted graph but all the
definitions are in the entry block, there will be exactly 0 PHI nodes
(the example is extreme and is only meant as an illustration). At the
other extreme, you may have just 1 definition site that is very "deep"
inside the CFG and has a huge IDF. Each block in that IDF will need a
PHI node.
> 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.
Diego.
Return to the
comp.compilers page.
Search the
comp.compilers archives again.