<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 12/28/15 1:02 PM, Christian Convey
wrote:<br>
</div>
<blockquote
cite="mid:CAPfS4Zz_FeZX_Z--e86VVq8g2x1QAtbv3brK1OGO3Kd92-NSrQ@mail.gmail.com"
type="cite">
<meta http-equiv="Context-Type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div>Any suggestions for how to interpret DSCallGraph's output
for the following?</div>
</div>
</blockquote>
<br>
Which DSA pass are you using to generate the call graph? You'll get
different results from different DSA passes.<br>
<br>
<blockquote
cite="mid:CAPfS4Zz_FeZX_Z--e86VVq8g2x1QAtbv3brK1OGO3Kd92-NSrQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>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:</div>
<div><br>
</div>
<div> main --> DoSorting</div>
<div> DoSorting --> qsort(..., QsortCallback)</div>
<div> qsort --> QsortCallback (via callback)</div>
<div> QsortCallback --> DoSorting</div>
<div><br>
</div>
<div><br>
</div>
<div>There were two things in DSCallGraph's results which
surprised me:</div>
<div>
<ul>
<li>"qsort" was placed into its own SCC (according to
DSCallGraph::scc_begin/end).</li>
<li>"qsort" 's SCC did not have any callees (according to
DSCallGraph::flat_callee_begin/end).</li>
</ul>
</div>
</div>
</blockquote>
<br>
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.<br>
<br>
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.<br>
<br>
<blockquote
cite="mid:CAPfS4Zz_FeZX_Z--e86VVq8g2x1QAtbv3brK1OGO3Kd92-NSrQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div>I'm not sure that DSCallGraph's output is <i>wrong</i>,
because it does report these caveats:</div>
</div>
<div>
<ul>
<li>DSCallGraph::called_from_incomplete_site( @QsortCallback
) returns true.</li>
<li>For all three callsites in the Module,
DSCallGraph::callee_is_complete(...) returns false.</li>
</ul>
<div>Must I assume that the entire Module could be a single
SCC whenever "called_from_incomplete_site" returns true
"callee_is_complete" returns false?<br>
</div>
</div>
</div>
</blockquote>
<br>
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).<br>
<br>
<blockquote
cite="mid:CAPfS4Zz_FeZX_Z--e86VVq8g2x1QAtbv3brK1OGO3Kd92-NSrQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>And if I <i>do</i> 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?</div>
</div>
</blockquote>
<br>
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.<br>
<br>
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.<br>
<br>
Regards,<br>
<br>
John Criswell<br>
<br>
<br>
<blockquote
cite="mid:CAPfS4Zz_FeZX_Z--e86VVq8g2x1QAtbv3brK1OGO3Kd92-NSrQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div><br>
</div>
<div>Thanks,</div>
<div>Christian</div>
</div>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
<a class="moz-txt-link-freetext" href="http://www.cs.rochester.edu/u/criswell">http://www.cs.rochester.edu/u/criswell</a></pre>
</body>
</html>