24 Jul 2002 01:48:58 -0400

Related articles |
---|

Finding the set of recursive calls jeremy.wright@microfocus.com (Jeremy Wright) (2002-07-21) |

Re: Finding the set of recursive calls haberg@matematik.su.se (Hans Aberg) (2002-07-24) |

Re: Finding the set of recursive calls dietz@dls.net (Paul F. Dietz) (2002-07-24) |

Re: Finding the set of recursive calls Martin.Ward@durham.ac.uk (Martin Ward) (2002-07-24) |

Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-07-24) |

Re: Finding the set of recursive calls jeremy.wright@microfocus.com (Jeremy Wright) (2002-07-25) |

Re: Finding the set of recursive calls vbdis@aol.com (VBDis) (2002-07-31) |

Re: Finding the set of recursive calls haberg@matematik.su.se (Hans Aberg) (2002-08-04) |

[3 later articles] |

From: | "Hans Aberg" <haberg@matematik.su.se> |

Newsgroups: | comp.compilers |

Date: | 24 Jul 2002 01:48:58 -0400 |

Organization: | Mathematics |

References: | 02-07-084 |

Keywords: | analysis |

Posted-Date: | 24 Jul 2002 01:48:58 EDT |

<jeremy.wright@microfocus.com> wrote:

*>Given complete call information, is there an algorithm to determine*

*>which functions can be called recursively ?*

...

*>Calculating the set of functions that are recursive is not so simple.*

*>This is not the same problem as finding loops, because loops require*

*>the head of the edge to dominate the tail. This is not a requirement*

*>for call recursion.*

For a directed graph, one can compute the strongly connected components

(SCC's) using Tarjan's algorithm, see for example

http://www1.ics.uci.edu/~eppstein/161/960220.html#sca

This is the most efficient possible, visiting each vertex and edge exactly once.

Possibly, you need a version for a undirected graph. But to every

undirected graph, one can associate a directed graph with two arrows the

opposite direction for every undirected edge. Then the SCC's of the

directed graph are the same as the connectivity components of the

undirected one. So it is perhaps not so difficult.

Hans Aberg * Anti-spam: remove "remove." from email address.

* Email: Hans Aberg <remove.haberg@member.ams.org>

* Home Page: <http://www.matematik.su.se/~haberg/>

* AMS member listing: <http://www.ams.org/cml/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.