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

Typo correction ...

Must I assume that the entire Module could be a single SCC whenever

Which DSA pass are you using to generate the call graph? You’ll get different results from different DSA passes. 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. 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). 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

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

Dear all,

I checked the old code and the DSA pass we used in the project was CallTargetFinder, and it required the data structure to use. And we used TDDataStructures.

The require statement in getAnalysisUsage method looks like this:

AU.addRequired<CallTargetFinder >();

Is this what you’re asking?

BTW, what’s the state of the DSA and poolalloc project at the moment? Which version of LLVM does it work with? And where can I find documentation?

Thanks.

Regards,

Kevin