[llvm-dev] Functions accessible from a function

Alex Denisov via llvm-dev llvm-dev at lists.llvm.org
Wed Mar 22 05:52:53 PDT 2017


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

I called it Call Tree in my head, but yes, this is exactly what I need.

> 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.

Thanks a lot, I will look into. If the algorithm doesn’t cover all cases then it is still better than my naive approach.
Could you also tell what’s the DSA is? The most relevant finding I see is the “data structure analysis”.

> On 21 Mar 2017, at 22:05, John Criswell <jtcriswel at gmail.com> wrote:
> 
> 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



More information about the llvm-dev mailing list