Finding the set of recursive calls

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

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