11 Apr 2005 00:19:45 -0400

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: | Jeremy Singer <jsinger@cs.man.ac.uk> |

Newsgroups: | comp.compilers |

Date: | 11 Apr 2005 00:19:45 -0400 |

Organization: | Compilers Central |

References: | 04-07-030 04-07-041 05-03-086 05-03-095 |

Keywords: | analysis |

Cc: | jsinger@cs.man.ac.uk |

Posted-Date: | 11 Apr 2005 00:19:45 EDT |

*>>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?*

This is a really interesting question. The number of phi-functions is

bounded above by the number of def-use edges that share a common use.

The number of phi-functions is bounded below by the number of

def-use-use-def webs (Muchnick, 1997) that contain more than one def.

The number of phi-functions depends on both control flow and data flow

behaviour of the subject program. So, both variable definitions and CFG

join points can affect it.

Here is a simple upper bound on the number of phi-functions in a minimal

SSA program:

-Assume program p has N nodes.

-So, assume p has O(N) original variables.

-In the worst case, there may be an edge from every node to every node in p.

-In the worst case, there may be a definition of every original variable

at every node in p.

-This worst case situation requires a phi-function for every original

variable at every node, which gives O(N^2) phi-functions.

The worst case assumptions are unlikely. Often CFGs have a reducible

structure, so it is not possible for every node to be joined to every

other node. Also, most variables are defined at O(1) program points. So

the worst case quadratic behaviour is rarely seen.

*>>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.*

Cytron et al (1991) discuss this worst case bound in section 9.1. I

have recently been investigating this issue for SSA and related

intermediate representations. My draft PhD dissertation is available

at http://www.cl.cam.ac.uk/~jds31/thesis/ if you are interested. The

title is "Static Program Analysis based on Virtual Register Renaming"

Best regards,

Jeremy

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.