[llvm-dev] Functions accessible from a function

[John Criswell via llvm-dev]

On 3/21/17 1:21 AM, Alex Denisov via llvm-dev wrote:
> Hello everybody,
>
> I am trying to do some static analysis, e.g. find which other functions accessible from a function.

In other words, you're trying to compute the call graph (a graph that 
shows which functions call other functions), correct?


> Current naive implementation goes over each instruction and whether it is a call site or not.
> It works great so far, but there are some cases where it doesn’t work. For example:
>
>    declare no_source(function: f) // uses f internally
>    define foo() { ... }
>    define bar() { ... }
>
>    define buzz() {
>      call foo()
>      call no_source(&bar)
>      ret
>    }
>
> In this case, my implementation catches 'foo' but not 'bar.'
> There are must be less trivial but also detectable cases.
>
> Can anybody give a hint or advice on how to do such kind of analysis?

LLVM already has a call graph analysis pass 
(http://llvm.org/doxygen/classllvm_1_1CallGraphAnalysis.html) which can 
compute a call graph for you.

In your example above, a function escapes to external code.  The call 
graph has an externalCalledNode and an externalCallNode which represents 
functions called by external code and functions calling external code, 
respectively.  You should examine these nodes to understand how external 
code affects the call graph.

The call graph analysis within LLVM does not really handle function 
pointers (the results are correct but a very conservative).  If you need 
to analyze function pointers, you might try DSA.

Regards,

John Criswell

>
> Cheers,
> Alex.


-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell