<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 3/4/13 8:05 AM, Kevin Streit wrote:<br>
</div>
<blockquote
cite="mid:A664E69B-A98A-4E27-8E49-5FE5373B9005@googlemail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
Hi,
<div><br>
</div>
<div>during the hunt for a bug causing strange behavior of our
automatic parallelization framework, </div>
<div>I found some, at least for me, unexpected behavior of the
DataStructureAnalysis in Poolalloc.</div>
<div><br>
</div>
<div>Consider the following simplified program:</div>
<div><br>
</div>
<div>====================</div>
<div>
<div>int ARR[4] = {1, 2, 3, 4};</div>
<div><br>
</div>
<div>int a(int pos) {</div>
<div> return ARR[pos];</div>
<div>}</div>
<div><br>
</div>
<div>int sum(int op_a, int op_b) {</div>
<div> return a(op_a) + a(op_b);</div>
<div>}</div>
<div><br>
</div>
<div>int main(int argc, const char *argv[]) {</div>
<div> return sum(1, 3);</div>
<div>}</div>
</div>
<div>====================</div>
<div><br>
</div>
<div>The unexpected behavior is that the bottum-up-graphs (and
consequently the top-down-graphs)</div>
<div>of methods sum and main do not contain any hint on the read
of the global variable ARR. These </div>
<div>graphs thus do not reflect the full effects of the methods,
which I expected them to do. (Screenshots attached)</div>
</blockquote>
<br>
You are correct that the graphs themselves do not reflect all the
behaviors of callees, but that is not what the Bottom-Up (BU) pass
in DSA is supposed to do. If it did that, then the main() function
would be an unwieldy DSGraph that described every memory object in
the program.<br>
<br>
In BU, each function has a DSGraph that summarizes what the function
and its callees do to the memory objects that are reachable from
within that function. In your example, main() and sum() do not have
any SSA register values that point to any memory objects, nor do
they use any global SSA registers that could point to a memory
object. As a result, their DSGraph contains no memory objects.<br>
<br>
If you modified the program to be something like:<br>
<br>
<div>
<div>int ARR[4] = {1, 2, 3, 4};</div>
<div><br>
</div>
<div>int a(int * arr, int pos) {</div>
<div> return arr[pos];</div>
<div>}</div>
<div><br>
</div>
<div>int sum(int * arr, int op_a, int op_b) {</div>
<div> return a(arr, op_a) + a(arr, op_b);</div>
<div>}</div>
<div><br>
</div>
<div>int main(int argc, const char *argv[]) {</div>
<div> return sum(ARR, 1, 3);</div>
<div>}</div>
</div>
<br>
... then the DSGraphs for main() and sum() should show an SSA
register that points to a global memory object, and the flags on
that memory object should reflect what the callees do on that memory
object.<br>
<br>
If you want to find all the abstract memory objects which a function
and its callees could modify, even if the memory object isn't
reachable from the given function, you're going to have to traverse
the call graph and collect all the DSNodes within each one. You may
also have to match up the caller/callee DSNodes for each function
call.<br>
<br>
-- John T.<br>
<br>
</body>
</html>