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