llvm dev - Dec 2015 - Interpreting DSCallGraph results

Any suggestions for how to interpret DSCallGraph's output for the following?

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

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?

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?

Thanks,
Christian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151228/0fa94950/attachment.html>

Typo correction ...

Must I assume that the entire Module could be a single SCC
whenever
> "called_from_incomplete_site" returns true **OR**
"callee_is_complete"
> returns false?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151228/a17eed9c/attachment.html>

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>

>
> 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 believe I was using TDDataStructures in that run.

> 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).
>
Thanks, that's extremely useful.  Much appreciated.

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