21 Jul 2002 02:12:17 -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) |

[4 later articles] |

From: | "Jeremy Wright" <jeremy.wright@microfocus.com> |

Newsgroups: | comp.compilers |

Date: | 21 Jul 2002 02:12:17 -0400 |

Organization: | Micro Focus |

Keywords: | analysis, question |

Posted-Date: | 21 Jul 2002 02:12:16 EDT |

Given complete call information, is there an algorithm to determine

which functions can be called recursively ? I have tried Google, but

it returns so many hits that it is unusable.

Detecting that recursion exists is easy. You simply construct a rooted

directed graph that represent the call graph. You then do a

depth-first numbering. The presence of a back edge indicates

recursion.

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.

I started with the observation that a function cannot be recursive if

either

a) it is a leaf

b) it only calls functions known to be non recursive

This suggested the following

Visit each node (function) in reverse depth first order

Removing a leaf nodes from the graph

If a node n has successor s such that Dfn(n) > Dfn(s) carry on

Otherwise node n and all it descendants are recursive. Mark and

delete

However - this does not work in the case where a calls b, b calls c,

and c calls a and b.

I am sure this must be a well known problem, which has a solution. Can

anyone point me to a reference.

Thanks

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.