[LLVMdev] Unexpected DSAnalysis behavior

Kevin Streit kevin.streit at googlemail.com
Tue Mar 5 00:57:36 PST 2013

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,

More information about the llvm-dev mailing list