Re: Finding the set of recursive calls

"VBDis" <vbdis@aol.com>
24 Jul 2002 02:25:06 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.