llvm dev - Mar 2013 - [LLVMdev] Unexpected DSAnalysis behavior

Hi,

during the hunt for a bug causing strange behavior of our automatic
parallelization framework,
I found some, at least for me, unexpected behavior of the DataStructureAnalysis
in Poolalloc.

Consider the following simplified program:

===================int ARR[4] = {1, 2, 3, 4};

int a(int pos) {
    return ARR[pos];
}

int sum(int op_a, int op_b) {
    return a(op_a) + a(op_b);
}

int main(int argc, const char *argv[]) {
    return sum(1, 3);
}
===================
The unexpected behavior is that the bottum-up-graphs (and consequently the
top-down-graphs)
of methods sum and main do not contain any hint on the read of the global
variable ARR. These
graphs thus do not reflect the full effects of the methods, which I expected
them to do. (Screenshots attached)

This seems to be deliberate as the code states that "[...] we don't
care about merging globals [...] here"
(BottomUpClosure.cpp:641 in the release_32 version from the poolalloc SVN).

The "here" in the comment suggests that this should happen at some
later point, which it doesn't.

This behavior is also not in line with the PLDI Paper.
Is it intended? And if so, why?

Thanks for your efforts,
Kevin




-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130304/3997400c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dsa-test.png
Type: image/png
Size: 22919 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130304/3997400c/attachment.png>

On 3/4/13 8:05 AM, Kevin Streit wrote:
> Hi,
>
> during the hunt for a bug causing strange behavior of our automatic 
> parallelization framework,
> I found some, at least for me, unexpected behavior of the 
> DataStructureAnalysis in Poolalloc.
>
> Consider the following simplified program:
>
> ===================> int ARR[4] = {1, 2, 3, 4};
>
> int a(int pos) {
>     return ARR[pos];
> }
>
> int sum(int op_a, int op_b) {
>     return a(op_a) + a(op_b);
> }
>
> int main(int argc, const char *argv[]) {
>     return sum(1, 3);
> }
> ===================>
> The unexpected behavior is that the bottum-up-graphs (and consequently 
> the top-down-graphs)
> of methods sum and main do not contain any hint on the read of the 
> global variable ARR. These
> graphs thus do not reflect the full effects of the methods, which I 
> expected them to do. (Screenshots attached)
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.

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.

If you modified the program to be something like:

int ARR[4] = {1, 2, 3, 4};

int a(int * arr, int pos) {
     return arr[pos];
}

int sum(int * arr, int op_a, int op_b) {
     return a(arr, op_a) + a(arr, op_b);
}

int main(int argc, const char *argv[]) {
     return sum(ARR, 1, 3);
}

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

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.

-- John T.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130304/5efdfd37/attachment.html>

Thanks for the fast reply.

On 04.03.2013, at 22:44, John Criswell <criswell at illinois.edu> wrote:
> 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.
Sorry, my fault. Of course I was talking about the effects on memory objects
reachable from within that function. But I was assuming the globals are assumed
to be reachable.
The DSGraph of the main function would then indeed contain a copy of the globals
graph, but all the (possibly merged) nodes of its callees.
Figure 7 in the PLDI Paper suggested that this was the case, but I see that
section 4 explains the current behavior.
> 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.
As I said, I'm interested only in the locally reachable objects plus
globals. In the course of deciding if two calls are executable in parallel I
already compute the callee caller mapping between the callee's BU graph and
the caller's TD graph to determine the effects on locally reachable memory
objects. I think the only thing I would need to do in addition to what is done
now is to also merge global nodes over during BOTTOM UP inlining (And make the
removeDeadNodes function not to remove them again if the KeepUnreachableGlobals
flag is set), but not during top down merging.
I basically did that and it works as I expect it to, but keeping my own copy of
the DSA should be the last resort.

Thanks again,
Kevin