Re: Finding the set of recursive calls

<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

Return to the comp.compilers page.
Search the comp.compilers archives again.