[llvm-dev] Interpreting DSCallGraph results

[John Criswell via llvm-dev]

On 12/28/15 1:02 PM, Christian Convey wrote:
> Any suggestions for how to interpret DSCallGraph's output for the 
> following?

Which DSA pass are you using to generate the call graph?  You'll get 
different results from different DSA passes.

>
> I'm trying to use DSCallGraph to get a conservative estimate of a 
> whole-program SCC call graph.  I wanted to see how it handles real 
> call-graph cycles involving functions both internal and external to 
> the module.  So I made a test program with the following actual call 
> graph, using the standard library's "qsort" function:
>
>    main          --> DoSorting
>    DoSorting     --> qsort(..., QsortCallback)
>    qsort         --> QsortCallback (via callback)
>    QsortCallback --> DoSorting
>
>
> There were two things in DSCallGraph's results which surprised me:
>
>   * "qsort" was placed into its own SCC (according to
>     DSCallGraph::scc_begin/end).
>   * "qsort" 's SCC did not have any callees (according to
>     DSCallGraph::flat_callee_begin/end).
>

A quick grep on the DSA code doesn't reveal any special handling of 
qsort() by the StdLib DSA pass.  The qsort() function is an external 
function; DSA cannot see its body, so it doesn't know what it does with 
its function pointer argument.  Since the StdLib DSA pass does not 
appear to be generating a specialized DSGraph for qsort()'s documented 
behavior, DSA should be treating it as a function that can call external 
code which can call any function pointer that is visible to external code.

A small enhancement to the StdLib pass could probably teach DSA to 
handle qsort accurately.  The StdLib pass is a DSA pass that understands 
the semantics of various C library functions and adjusts the DSGraphs 
with this information.  It is a separate pass so that we can (in theory) 
use DSA on LLVM IR generated from other programming languages.

> I'm not sure that DSCallGraph's output is /wrong/, because it does 
> report these caveats:
>
>   * DSCallGraph::called_from_incomplete_site( @QsortCallback ) returns
>     true.
>   * For all three callsites in the Module,
>     DSCallGraph::callee_is_complete(...) returns false.
>
> Must I assume that the entire Module could be a single SCC whenever 
> "called_from_incomplete_site" returns true "callee_is_complete" 
> returns false?

You need to assume that any incomplete call site calls external code 
which can call any function that a) whose linkage makes it visible to 
(and therefore callable from) external code and b) any function whose 
address is in a DSNode that has the Incomplete or External flag set 
(i.e., the function pointer could be read by external code).

>
> And if I /do/ need to be that pessimistic, anyone know why DSCallGraph 
> doesn't apply that pessimism itself and return a single-SCC call graph 
> in such cases?

I don't recall why DSCallGraph doesn't handle this itself.  It may be an 
arbitrary choice, or it could be that different clients want to handle 
incomplete or external DSNodes differently.

Kevin, do you remember what code we used in the AutoPriv project for 
using the DSA-generated call graph?  I don't think we used DSCallGraph, 
but my memory is fuzzy.

Regards,

John Criswell


>
> Thanks,
> Christian


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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151228/e941402f/attachment.html>