25 Mar 2005 21:54:19 -0500

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 |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.