[LLVMdev] Unexpected DSAnalysis behavior

[John Criswell]

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>