Re:Call Graph in C

>Help with Interprocedural analysis in C ....
>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.


>Ex :


>int foo (ft, f)
>int (* f)(); /* A pointer to function */
>int (* ft[])(); /* An array of pointers to functions that return int */
>{
>int i = 0;
>
> ........
> i = ....... ;
> f( ..., ... ,..);
> ft[i]( ..., ..., ...) ;
> ........
>}
>
>Someone who could give me some pointers ?


>Gilles




Yes, this is an interesting problem, which we faced while developing
the framework for interprocedural analysis for our McCAT compiler (McGill
Compiler Architecture Testbed).


The framework is implemented and is now operational. It effectively
handles the problems posed by function pointers of all types : single
level function pointers, arrays of function pointers and multiple level
function pointers ( int (**fp)()). Techniques described in the literature
typically concentrate on single level function pointers, termed as
procedure variables in other languages. Our framework also handles
recursion quite neatly.




Our approach is as follows : We perform an analysis called *points-to*
analysis (analogous to alias analysis), which collects the information as
to which pointer points-to which variables/functions in the program, at a
given program point. This analysis is interprocedural and uses the
call-graph of the program. Now, in the presence of function pointers, the
*complete call-graph* is not available before the points-to analysis. So,
the central idea is to keep updating the call-graph during points-to
analysis, as the points-to information about function pointers gets
collected. To handle *statically initialized* function pointer arrays, we
generate intermediate code for the initialization, but get rid of it at
code-generation time : so we don't sacrifice efficiency.


A complete description of our interprocedural analysis framework
can be found in:


  L. Hendren, M. Emami, R. Ghiya and C. Verbrugge.
  A Practical Context-Sensitive Interprocedural Analysis Framework for C
  Compilers. ACAPS Technical Memo72, McGill University, July 1993.


A detailed description of how do we handle function pointers can
be found in:


  Rakesh Ghiya. Interprocedural Analysis in the Presence of Function
  Pointers. ACAPS Technical Memo62, McGill University, December 1992.


A technical report on points-to analysis itself is under preparation.
It is presently described in the Master's Thesis of Maryam Emami.


You can get these tech reports via anonymous ftp from wally.cs.mcgill.ca
in the directory pub/doc/memos . The file names are memo72 and memo62
respectively.


Hope this helps.


Rakesh Ghiya.
School of Computer Science
McGill University
Montreal, Canada.


ghiya@acaps.cs.mcgill.ca
--

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