Re: Call Graph in C

Gilles MENEZ"<menez@mimosa.unice.fr> writes:


      I'm looking for an algorithm which would be able to decide if a C program
      contains recursion (static or dynamic) and to define the call graph.


      It seems to be a hard job because of the dynamic function parameter
      capabilities offered by C.


I haven't got any hard references, but there seems to be a simple and
possibly very imprecise method: keep track of what functions have had
their address taken and approximate the target of a 'jump through pointer'
with the set of these procedures. If C offers any further troublesome
constructs, you can always approximate with 'all visible procedures' (if I
remember correctly, "static" functions are invisible outside their source
file or module). Unknown procedures can jump anywhere, possibly by using
stashed-away pointers to static procedures. I am no expert on ANSI C, so
some dirty tricks could be prevented by the standard.


Olin Shivers studied the problem for Scheme, have a look
in his thesis, which can be found as:


1. ftp to cs.cmu.edu
2. cd /afs/cs.cmu.edu/users/shivers/lib/papers, where there
is a wealth of papers. (You must cd in one step.)


He explains various degrees of approximation of the control flow of a
program there. Your problem seems substantially harder, for the reasons
you mention. To get more precise results, I suppose you would have to
develop a good theory to handle C pointers and pointer arithmetic and so
on, to narrow down the possibilities a bit when stored function pointers
are considered. This in turn involves computing pointer aliasing, which
can be hard to do well. Check out Landi and Ryder, in various proceedings,
or recent PLDI's. I think the latest PLDI-proceedings have a couple of
papers on pointer aliasing. I seem to remember that GCC can do
optimization with stored labels, so have a look there as well.


Thomas


(From Rutgers: report LCSR-TR-168 and LCSR-TR-174 (Landi's thesis)
  might be interesting for aliasing.)
--
Thomas Lindgren, UPMAIL, thomasl@csd.uu.se, lindgren@sics.se
[Remember that signals can happen anytime, so any function that can be
called from a signal is potentially recursive. This is a hard problem,
though I expect that there are heuristics that could be useful in common
cases. -John]


--

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