<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 6/15/14, 10:20 PM, Daniel Guo wrote:<br>
</div>
<blockquote
cite="mid:CAC9jkXSWcrF_=0qv2tRv84zF6=D-WUOg-=CerzKK9qcpLzrFdw@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div dir="ltr">Hi John,
<div><br>
<div>Many thanks for the suggestion.</div>
<div>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.</div>
</div>
</div>
</blockquote>
<br>
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).<br>
<br>
<blockquote
cite="mid:CAC9jkXSWcrF_=0qv2tRv84zF6=D-WUOg-=CerzKK9qcpLzrFdw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div><br>
</div>
<div>And my requirements are:</div>
<div>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.</div>
<div>2. The "Inst" here is an Instruction* accessing a global
variable.</div>
<div>3. Right now the "Pointer" is from the iteration on the
Instructions of each function. </div>
<div><br>
</div>
<div>So my questions are:</div>
<div>1. How can i take use of the graphs as they contain the
"pointing-to" relationship among different objects? <br>
</div>
</div>
</div>
</blockquote>
<br>
Give two LLVM values, you can determine their local aliasing
behavior by:<br>
<br>
1) Get the DSGraph for the function.<br>
2) Get the DSNode for each value:<br>
a) If it's a GlobalVariable, the DSNode is in the global
GlobalsGraph.<br>
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).<br>
3) If the two values point to the same DSNode, then they may alias.<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
<blockquote
cite="mid:CAC9jkXSWcrF_=0qv2tRv84zF6=D-WUOg-=CerzKK9qcpLzrFdw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div>2. Which api or data structures in DSA can be used to get
the useful information?</div>
</div>
</div>
</blockquote>
<br>
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.<br>
<br>
The dsa-manual in the docs directory has more information, and
there's plenty of examples in the source code.<br>
<br>
Regards,<br>
<br>
John Criswell<br>
<br>
<blockquote
cite="mid:CAC9jkXSWcrF_=0qv2tRv84zF6=D-WUOg-=CerzKK9qcpLzrFdw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div><br>
</div>
<div>Thanks very much John and have a good night~!</div>
<div><br>
</div>
<div>Dan.</div>
<div><br>
</div>
</div>
</div>
<div class="gmail_extra"><br>
<br>
</div>
</blockquote>
<br>
</body>
</html>