25 Mar 2005 21:55:44 -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) |

From: | Nathan Moore <nathan.moore@sdc.cox.net> |

Newsgroups: | comp.compilers |

Date: | 25 Mar 2005 21:55:44 -0500 |

Organization: | Cox Communications |

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

Keywords: | SSA, analysis |

Posted-Date: | 25 Mar 2005 21:55:44 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.