[LLVMdev] Questions bout the Steensguard AA Pass in rDSA

[John Criswell]

On 6/15/14, 10:20 PM, Daniel Guo wrote:
> 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.

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

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

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.

> 2. Which api or data structures in DSA can be used to get the useful 
> information?

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

>
> Thanks very much John and have a good night~!
>
> Dan.
>
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140616/36bd3e3e/attachment.html>