Questions bout the Steensguard AA Pass in rDSA

Deal all,
Recently i am searching for a intra-procedure alias analysis pass and the -ds-aa pass seems to be the one i am looking for.
However, i find this post described that the rDSA code in PoorAlloc project was abandoned before …
https://groups.google.com/d/topic/llvm-dev/FMLmIh9Nz84/discussion

But some other guys were interested in it and John Criswell also made a request in bug database on this topic.
Now after 3 years, what’s the status of this issue? Are there still any problems in the pass if i compile and run it?

Thanks,

Daniel.

Intra-procedural or inter-procedural? I do not believe that the status has changed. I believe the -dsa-aa pass in DSA is still removed and has not been resurrected (at least not with a patch that applied cleanly to the release_32 branch). If someone wants to resurrect -dsa-aa with a patch that cleanly applies to the release_32 branch or the trunk branch, I’ll review it and apply it. Regards, John Criswell

Hi Criswell,
Thanks for the reply.
I am looking for a pass for the intra-procedural alias analyzing, as i am working on multithreaded debugging and looking for a way to pick up instructions from different threads accessing the same global variable, and is Steensguard workable for this scenario? or any other suggestions?

I also find that the “rDSA” folder is not included in the Makefile, and this means the -dsa-aa pass is still not reliable and probably i cannot use it, right?

Thanks,

Dan.

The local DSA pass provides a shape graph of each function, and it uses the Incomplete and External flags to mark for which nodes in the shape graph it does not have complete information. I think you could use the Local DSA pass directly to determine which instructions are accessing global variables. The rDSA directory contained an altered version of the DSA implementation. We eventually abandoned it and removed it. The code you found in rDSA either is or was at some point part of DSA. Regards, John Criswell

@John:

Since rDSA hasn't been used in ages, perhaps it's time we deleted it
from the repository?

It'll live on in SVN glory forever for interested parties, and will
avoid some of the confusion about its purpose.

Additionally, we probably shouldn't have entire directories of dead
code in mainline O:).

Given these reasons: mind if I remove it from trunk?

~Will

I thought it already had been. :slight_smile:

Yes, it would be fine to remove it from trunk.

Regards,

John Criswell

Honestly, I thought it had been as well :).

Anyway, removed in r210999, thanks!

~Will

Hi John,

Many thanks for the suggestion.
I read the user manual and the source code of the Local DSA pass, and it seems that the output of the Local pass is a set of graphs for some further analysis.

And my requirements are:

  1. I need a alias analysis pass that implements the universal AA->alias(Pointer, size, Inst, …), here the “Inst” is obtained from previous process and the alias function is detecting if “Pointer” and “Inst” are aliasing.
  2. The “Inst” here is an Instruction* accessing a global variable.
  3. Right now the “Pointer” is from the iteration on the Instructions of each function.

So my questions are:

  1. How can i take use of the graphs as they contain the “pointing-to” relationship among different objects?
  2. Which api or data structures in DSA can be used to get the useful information?

Thanks very much John and have a good night~!

Dan.

The result is best described as a shape graph. It maps LLVM scalar values to nodes in the shape graph; the shape graph describes the links between memory objects (i.e., heap objects, stack objects, and global variable objects). Give two LLVM values, you can determine their local aliasing behavior by: 1) Get the DSGraph for the function. 2) Get the DSNode for each value: a) If it’s a GlobalVariable, the DSNode is in the global GlobalsGraph. b) If it’s a local LLVM value (e.g., result of a load), the DSNode is in the local graph or in the local GlobalsGraph (or both). 3) If the two values point to the same DSNode, then they may alias. 4) If one or both values have the Incomplete or External flags set, then DSA does not know their aliasing behavior, so assume may alias. Just to be on the paranoid side, I’d try looking up each LLVM value in the global GlobalsGraph, the local GlobalsGraph, and the local DSGraph and comparing all three. Note that you’ve asked about doing intra-procedural points-to analysis, meaning that you’ll get lots of DSNodes with Incomplete flags because the analysis will know nothing about values coming from callers or manipulated by callees. If you need that information, then you need to use the Bottom-Up or Top-Down DSA passes. If you want to make life really easy, use the DSNodeEquivs pass. That pass uses the top-down DSA pass and places all potentially aliasing DSNodes into an equivalence class. To see if two values alias, you just ask DSNodeEquivs if their DSNodes are in the same equivalence class. The pass class itself has a getGlobalsGraph() method which will return the global GlobalsGraph. The pass class has a getDSGgraph() method for returning a function’s DSGraph. The DSGraph class has methods for returning a handle to a DSNode (getDSNodeHandle()) and the function’s globalGraph (getGlobalGraph()). The DSNodeHandle::getNode() method will return the DSNode pointed to by a DSNodeHandle. The dsa-manual in the docs directory has more information, and there’s plenty of examples in the source code. Regards, John Criswell