24 Jul 2002 02:25:06 -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) |

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

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

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

From: | "VBDis" <vbdis@aol.com> |

Newsgroups: | comp.compilers |

Date: | 24 Jul 2002 02:25:06 -0400 |

Organization: | AOL Bertelsmann Online GmbH & Co. KG http://www.germany.aol.com |

References: | 02-07-084 |

Keywords: | analysis, optimize |

Posted-Date: | 24 Jul 2002 02:25:06 EDT |

<jeremy.wright@microfocus.com> schreibt:

*>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'd check whether a node has itself as successor (or predecessor),

with the full set of successors/predecessors, not only for the

immediate ones.

The search can be restricted to nodes in loops, where all nodes

represent recursive functions which have an path to the latching node

of the loop.

In general for a recursive function 2 (forward) pathes must exist, one

from the loop header to the node, and one from the node to the

latching node of the loop. (which are identical for self-recursion,

where the node is both the header and latching node of the

loop). Every back edge l->h identifies h as the header node of the

loop, and l as the latching node, if also a path h->l exists. All

nodes on the pathes h->l then represent recursive functions.

When you construct the full set of predecessors Preds(n) for every

node n (from forward edges is sufficient), then recursive nodes are

all predecessors of an latching node l, which have the corresponding

header node h as an predecessor. [n in Preds(l) and h in Preds(n),

for all back edges l->h]

Or, with predecessors and successors:

[intersection of Preds(l) and Succs(h), for all back edges l->h]

You may search for "Roman Chariots [Problem]", for methods to

construct all pathes to an specific node.

DoDi

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.