[llvm-dev] Interpreting DSCallGraph results
John Criswell via llvm-dev
llvm-dev at lists.llvm.org
Mon Dec 28 11:51:01 PST 2015
On 12/28/15 1:02 PM, Christian Convey wrote:
> Any suggestions for how to interpret DSCallGraph's output for the
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
> * "qsort" 's SCC did not have any callees (according to
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
> * 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.
Department of Computer Science, University of Rochester
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev