Support for using GNU g++ demangler, rationalize use of libiberty
[dyninst.git] / depGraphAPI / doc / depGraphAPI.tex
1 \documentclass[12pt,titlepage]{article}
2 \usepackage{fullpage}
3 \usepackage{epsfig}
4 \usepackage{subfigure}
5 \begin{document}
6 \title{Dependence Graph API (DepGraphAPI) Programmer's Guide \\ Release 0.9b}
7 \author{Paradyn Parallel Performance Tools}
8 \maketitle
9 \tableofcontents
10 \section{Introduction}
11
12 The DepGraphAPI is a multi-platform library for creating and analyzing
13 dependence graph representations of binary code. A dependence graph is
14 a representation of must-happen-before and must-happen-after
15 relationships between program elements such as instructions and basic
16 blocks. A program may consist of several logically separate streams
17 of execution that are interleaved by the compiler; dependence graph
18 representations undo this interleaving. We represent
19 relationships in terms of a \emph{graph}, a data structure that
20 consists of nodes connected by directed edges. Nodes in the graph
21 represent program elements and edges represent \emph{dependences}
22 (must-happen-before or must-happen-after) between
23 elements.
24
25 The DepGraphAPI currently provides four graph representations:
26 \begin{description}
27 \item[Data Dependence Graph (DDG)] This graph represents the relations
28 between instructions that define and instructions that use registers
29 and memory. Nodes in this graph represent instructions, and edges
30 connect definitions of a particular location to its uses.
31 \item[Control Dependence Graph (CDG)] This graph represents
32 conditional execution of basic blocks in the program.
33 \item[Program Dependence Graph (PDG)] This graph is the union of the
34 DDG and CDG, used to compute a \emph{program slice} (defined below).
35 \item[Extended Program Dependence Graph (xPDG)] This graph is the PDG
36 augmented with additional nodes and edges necessary for forming an
37 \emph{executable slice} (defined in Section \ref{ExecutableSlice}.
38 \end{description}
39
40 The main goal of this API is to provide the user with abstractions
41 representing the logical dependencies between code elements in a
42 program. An abstract interface provides two benefits: it simplifies
43 the development of tools by hiding the complexity of a particular
44 architecture, and it allows tools to easily be ported
45 between platforms. Using a dependence graph representation of a
46 program allows the user to focus on a particular aspect of program
47 behavior and ignore program elements that do not affect that aspect of
48 behavior.
49
50 \textbf{Program Slice}: An excellent example of the use of the program
51 dependence graph is the \emph{program slice}, or more commonly just
52 ``slice''. Intuitively, a slice of a program from a particular point
53 is the sub-program that affects that point (a backward slice) or is
54 affected by that point (a forward slice). Formally, we define slices
55 as follows. Let $i$ represent an instruction in the program and $a$
56 some location that $i$ defines (writes a value into).  The backward
57 slice from $(i,a)$ are all instructions (and defined locations) that
58 may affect the value written into $a$ by $i$.  A forward slice from
59 $(i,a)$ are all instructions (and defined locations) that may be
60 affected by the definition of $a$ by $i$.
61
62 A future goal of this library is to allow users to improve the
63 precision of these graph representations through the use of additional
64 analyses. The included analyses used to generate these graph
65 representations are conservative, and may overapproximate the actual
66 dependences between instructions. A future release will provide API
67 extensions for updating these graph structures, either with
68 information known to the user directly, with the results of more
69 sophisticated static analysis, or with dynamic analysis results.
70
71 The current beta of the DepGraphAPI depends on the InstructionAPI
72 library and the DyninstAPI; future versions will depend only on the
73 InstructionAPI and ParsingAPI libraries released as part of the
74 DyninstAPI. Currently we support the IA-32 and AMD-64 architectures as
75 these are the only architectures supported by the
76 InstructionAPI. Future architecture support will include PowerPC, IA-64,
77 and SPARC. The DepGraphAPI has no file format or operating system
78 constraints.
79
80 \section{Definitions}
81
82 \begin{description}
83 \item[Instruction] An instruction represents a single machine
84 instruction with a unique starting offset. Instruction instances are
85 identified by this offset.
86 \item[Basic Block] A basic block is a contiguous sequence of
87   instructions with the property that if the first instruction in the
88   block is executed all other instructions will be executed before the
89   block is exited.
90 \item[Function] A function is a collection of basic blocks with a
91   single entry block. Functions are frequently reached by call
92   instructions, although this may not be the case due to compiler
93   optimizations. Similarly, functions are frequently exited via return
94   instructions, but other exit methods may be used by the compiler.
95 \item[Abstract Location] An abstract location represents a machine
96 register, memory location, or set of memory locations. Registers are
97 referred to by their InstructionAPI representation. Memory locations
98 consist of a region and an optional offset within that region. Regions
99 include the stack, the heap, and global memory. Stack locations are
100 assumed to be relative from the top of the stack at the beginning of
101 the function. Our current implementation assumes a single heap
102 location; this may change in future releases. Finally, offsets into
103 global memory are absolute addresses from a base of zero.
104 \item[Operation] An operation is a pair of an instruction and an
105 abstract location defined by that instruction. An instruction may
106 define more than one abstract location, particularly on CISC
107 architectures. If we represent data dependence at the instruction
108 level we may overapproximate dependences between instructions; we
109 describe an example of this occurrence in Section
110 \ref{OperationJustification}. Instead we represent dependences at the
111 operation level.
112 \item[Parameters] The parameters to a function consist of all abstract
113   locations that may be used by an instruction in the function without
114   having been defined by an instruction in the function.
115 \item[Results] The results of a function consist of all abstract
116   locations that are defined by that function.
117 \item[Data Dependence] In general, instruction $j$ is data dependent
118   on an instruction $i$ if $i$ defines some abstract location $a$, $j$
119   uses $a$, and there is an execution path from $i$ to $j$ along which
120   $a$ is not redefined. We use a more precise definition that uses
121   operations instead of instructions. Let $m = (i,a)$ be an operation
122   representing the definition of $a$ by $i$, and similarly for $n =
123   (j, b)$. Then $n$ is data dependent on $m$ if $i$ defines $a$, $j$
124   uses $a$ to define $b$, and there exists a path as above. Note that
125   $j$ may define other abstract locations, but no data dependence will
126   exist if $a$ is not used in these other definitions.
127 \item[Control Dependence] An instruction $j$ is control dependent on
128   an instruction $i$ if $i$ has multiple successors and $j$ is
129   executed along at least one, but not all, possible execution paths
130   from $i$.
131
132 \end{description}
133
134 \begin{figure}
135 \begin{center}
136   \subfigure[Instruction nodes]{\label{ddg-a}\includegraphics[scale=0.75]{figs/DDG-a.pdf}}
137   \subfigure[Operation
138   nodes]{\label{ddg-b}\includegraphics[scale=0.75]{figs/DDG-b.pdf}}
139 \end{center}
140 \caption{Example of instruction vs. operation-based DDG. Figure a)
141 provides an example of the problems of representing instructions as
142 single nodes. In this graph it is possible for paths to ``cross''
143 definitions; for example, there is a path from the definition of $r_0$
144 by $i_0$ to the definition of $sp$ (the stack pointer) by $i_3$, when
145 in the actual program there is no such dependence. The DDG shown in
146 figure b) makes the intra-instruction data dependencies explicit and
147 thus removes the possibility of erroneous paths.}
148 \label{OperationsGraph}
149 \end{figure}
150
151
152 \subsection{Operation-Level Data Dependence}\label{OperationJustification}
153
154 The conventional definition of the DDG (in which nodes represent
155 instructions) may over-approximate the data dependencies within a
156 binary. This occurs when an instruction defines multiple abstract
157 locations and uses different sets of abstract locations for each
158 definition. For example, consider the IA-32 instruction xchng which
159 exchanges the contents of two registers. From an instruction
160 perspective, this instruction uses and defines two registers. However,
161 there is no dependence between the use and definition of the same
162 registers. To avoid this over-approximation, each node in the
163 DepGraphAPI DDG consists of an operation; an (instruction, abstract
164 location) pair. We show an example of the use of instructions and
165 operations in Figure \ref{OperationsGraph}.
166
167
168 \section{Abstractions}
169
170 DepGraphAPI provides a simple set of abstractions over complicated
171 data structures to make the API easy to use. We first define these
172 abstractions in terms of concepts; the classes that implement these
173 concepts are defined below. The fundamental representation used by
174 this library is the directed graph (or digraph). A digraph is a set of
175 nodes connected by directed edges; each edge has a single source and
176 target. Nodes represent logical elements of the program. We define two
177 types of nodes: \emph{physical} and \emph{virtual}.  We provide a set
178 of methods for operating on Graphs, Nodes, and Edges; these methods
179 provide a common interface to all four dependence graph types provided
180 by the DepGraphAPI.
181
182 \subsection{Graph Abstractions}
183 \begin{description}
184 \item[Graph] A graph is a collection of nodes connected by directed
185   edges; each edge has a unique source and target node. Graphs have a
186   set of entry nodes, from which all nodes are reachable by following
187   edges forward, and exit nodes, from which all nodes are reachable by
188   following edges backward.
189 \item[Node] We define two types of nodes: physical and
190   virtual. Physical nodes represent a particular instruction, basic
191   block, or function. Virtual nodes represent the behavior of code
192   that is not directly represented by a physical node. Virtual nodes
193   represent a summary of the behavior of code that is not contained
194   within the graph, such as the behavior of a called function, the
195   assignment of values to the parameters of a function, or the use of
196   values returned from a function. For example, let \texttt{foo} be a
197   function that calls \texttt{bar}. A DDG for function \texttt{foo}
198   would include physical nodes for the code within \texttt{foo}, but
199   not for the code in \texttt{bar}. Instead, the behavior of
200   \texttt{bar} would be represented by one or more virtual nodes.
201 \item[Edge] Edges connect nodes and represent a dependence between the
202   two connected nodes.
203 \end{description}
204
205 Figure \ref{inheritance} shows the inheritance hierarchy for the
206 DepGraphAPI classes. All references to DepGraphAPI classes are
207 internally reference counted; we do not require the user to perform
208 any manual memory allocation or deletion.
209
210 \begin{figure}
211 \begin{center}
212 \includegraphics[scale=0.75]{figs/Inheritance.pdf}
213 \caption{Inheritance diagram for the DepGraphAPI. The Graph, Node, and
214   Edge classes provide a common interface specification. The DDG, CDG,
215   PDG, and xPDG graphs customize these three classes as necessary.}
216 \end{center}
217 \label{inheritance}
218 \end{figure}
219
220 \subsection{Shared Class}
221
222 \begin{description}
223 \item[Graph] The Graph represents a dependence graph for a particular
224 function.
225 \item[Node] The Node represents an element within the graph. Nodes are
226 connected by edges and are labelled with information.
227 \item[PhysicalNode] These Nodes represent an element (instruction,
228 basic block, or function) of the program. They are labelled with the
229 starting address of that object.
230 \item[VirtualNode] These Nodes represent summaries of program behavior
231 not contained within the graph. Virtual nodes do not have an address
232 associated with them.
233 \item[Edge] Edges connect Nodes. Edges are directed and have a source
234 and target.
235 \end{description}
236
237 \subsection{Data Dependence Graph}
238
239 The data dependence graph adds five specialized node types. 
240
241 \begin{description}
242 \item[OperationNode] Each physical DDG node represents an operation (a
243 definition of an abstract location by an instruction). We describe
244 operations and our justification of this abstraction in Section
245 \ref{OperationJustification}.
246 \item[FormalParameterNode] A formal parameter node represents the
247   input parameters to a function. One of these nodes will exist in the
248   graph for each abstract location that is used without having first
249   been defined by the function. These are virtual nodes, and form a
250   subset of the entry nodes of the DDG.
251 \item[FormalReturnNode] A formal return node represents the values
252   returned by the function; this includes any explicit return result
253   register as well as all other definitions that may persist after the
254   function returns. These are virtual nodes, and form a subset of the
255   exit nodes of the DDG.
256 \item[ActualParameterNode] These virtual nodes represent abstract
257   locations used by a callee function.
258 \item[ActualReturnNode] These virtual nodes represent abstract
259   locations defined by a callee function.
260 \end{description}
261
262 \subsection{Control Dependence Graph}
263
264 The control dependence graph adds one new specialized node type:
265
266 \begin{description}
267 \item[BlockNode] We represent
268 control dependence at the basic block level for efficiency. Therefore, each
269 node in the CDG represents a block. 
270 \end{description}
271
272 \subsection{Program Dependence Graph}
273 The Program Dependence Graph is the union of the DDG and CDG and is
274 constructed from the same abstractions used by the DDG. The basic
275 block-level information in the CDG is automatically converted to
276 OperationNodes.
277
278 \subsection{Extended Program Dependence Graph}
279 Although users can use PDGs to slice programs, the slices obtained
280 through PDGs are not always executable slices due to the presence of
281 unconditional branches. An executable slice is a slice of a program
282 that can be executed without any change in program behavior with
283 respect to the given slicing criteria. Program slices obtained through
284 the PDG will not include branch instructions that do not depend on the
285 slicing target; however, these branch instructions are necessary to
286 ensure proper control flow. Therefore, we augment the PDG to create
287 the Extended Program Dependence Graph (xPDG). The xPDG adds
288 dependence edges between branches and and all other instructions in
289 the basic block that ends at the branch. 
290
291 \section{Examples} 
292
293 To illustrate the ideas in the API, we present two short examples that
294 demonstrate how the API can be used.
295
296 \begin{figure}
297 \include{include/example1}
298 \caption{Slicing example. This code fragment identifies the nodes
299   reachable by following edges forward from the node with address
300   \texttt{insnAddr}.}
301 \label{example1}
302 \end{figure}
303
304 Our first example demonstrates how to access the PDG for a particular
305 function and take a slice from a known instruction (identified by its
306 address) and register that the instruction defines. The code for this
307 example is shown in Figure \ref{example1}. Lines of interest are:
308 \begin{itemize}
309 \item Line 16 identifies all nodes with a particular address
310   \texttt{insnAddr}. The set of these nodes is represented by the pair
311   of iterators \texttt{nodeBegin} and \texttt{nodeEnd}.
312 \item Line 19 determines whether there were nodes at the given
313   address. If the iterators are equal the range is empty.
314 \item Line 25 determines the set of nodes reachable from the given
315   node (the \emph{forward closure} from the node). The statement
316   \texttt{*nodeBegin} returns the first node from the set identified
317   in line 16. As before, the closure is represented by an iterator
318   pair \texttt{sliceBegin, sliceEnd}. 
319 \item Line 28 shows how to iterate over the forward closure. The
320   iterator \texttt{sliceBegin} will represent each node in the
321   closure; the sequence in which the nodes are returned is
322   undefined. Each node can be accessed by dereferencing the iterator:
323   \texttt{*sliceBegin}.
324 \end{itemize}
325
326 \begin{figure}
327 \include{include/example2}
328 \caption{DDG traversal example. This code fragment identifies nodes
329   within a basic block that have a data dependence to themselves.}
330 \label{example2}
331 \end{figure}
332
333 The second example shows how to determine which instructions in a
334 basic block that have a data dependence to themselves; that is, they
335 define and use the same abstract location. This is one method to
336 identify a loop iteration variable. The code for this example is shown
337 in Figure \ref{example2}. Lines of interest are:
338 \begin{itemize}
339 \item Line 15 shows how to access the instructions in a basic
340   block. The \texttt{InsnInstance} typedef consists of an
341   InstructionAPI instruction object and the address of the
342   instruction. We use these addresses to identify nodes within the
343   graph.
344 \item Line 18 shows how to iterate over each instruction in the block.
345 \item Line 23 shows how to find the set of nodes representing each
346   instruction. Since the DDG may represent a single instruction as
347   multiple operation nodes this set may have multiple elements. 
348 \item Line 26 shows how to get the targets of a node. These targets
349   can be represented either as a set of edges or a set of nodes,
350   whichever is convenient. 
351 \item Line 28 identifies nodes that have edges to themselves; that is,
352   nodes that define themselves. 
353 \end{itemize}
354
355
356 \section{Definitions and Basic Types}
357
358 The DepGraphAPI supplies four types of dependence graphs. We define
359 these forms of dependence here, along with definitions of the
360 underlying concepts. The following definitions and basic types are
361 referenced throughout the rest of the document.
362
363 \subsection{Basic Types}
364
365 {\ttfamily \raggedright \small
366 typedef\ \textbf{unsigned}\ \textbf{long}\ Address\\
367  }
368 \normalfont\normalsize
369 \indent An integer value that represents a unique location in memory.\\[\baselineskip]
370 \noindent \textbf{Smart/shared pointers}
371
372 All objects returned to users are transparently wrapped with a
373 reference counted pointer implementation. This smart pointer
374 automatically handles deallocation and garbage collection. These
375 pointers are referred to by the \texttt{::Ptr} suffix (e.g., \texttt{Graph::Ptr},
376 \texttt{Node::Ptr}, etc.). Our implementation is derived from the Boost
377 \texttt{shared\_ptr} implementation; for more information, please visit
378 www.boost.org. Shared pointers have some limitations when compared
379 with standard pointers. In particular, \texttt{dynamic\_cast} (as well as other
380 casting operators) are not defined on shared pointers. Performing such
381 a cast must be done with the \texttt{dynamic\_pointer\_cast}
382 method. For example: \indent {\ttfamily \raggedright \small
383 VirtualNode::Ptr\ virt\ =\ dynamic\underline\ pointer\underline\ cast<{}VirtualNode>{}(nodePtr);} \\[\baselineskip]
384 \normalfont\normalsize 
385 \noindent \textbf{Iterators}
386
387 The DepGraphAPI uses an iterator-based interface in favor of a
388 collection-based interface. This is done to reduce copying and improve
389 efficiency. Any method that returns a range of objects (e.g.,
390 \texttt{Graph::allNodes}) takes as arguments two iterators that are updated to
391 point to the beginning and end of the range. The user can then use
392 standard iterator methods (e.g., a for loop) to examine each element
393 in the range. We define two types of iterators: \texttt{NodeIterator} and
394 \texttt{EdgeIterator}.
395
396 \section{API Reference}
397
398 This section describes the interface of the DepGraphAPI. Each of the
399 subsections represents a different interface.
400
401 The classes described in this section are defined in the \texttt{Dyninst::} and
402 \texttt{Dyninst::DepGraphAPI::} namespaces.  To access them a user
403 should refer to them using the appropriate prefix (e.g.,
404 \texttt{Dyninst::Graph} or
405 \texttt{Dyninst::DepGraphAPI::DDG}). Alternatively, a user can add the
406 C++ \texttt{using} keyword above any reference to such objects (e.g.,
407 "\texttt{using namespace Dyninst;}").  The Graph, Node, and Edge
408 classes are contained in the \texttt{Dyninst::} namespace.  All other
409 classes are defined under the \texttt{Dyninst::DepGraphAPI} namespace.
410
411         
412 \subsection{Shared Classes}
413
414 The \texttt{Graph}, \texttt{Node}, and \texttt{Edge} classes are written to be generic and
415 shareable between DyninstAPI components. We include the API for these
416 classes here.
417
418 \subsubsection{Graph}
419
420 \begin{description}
421
422 \item[void entryNodes(NodeIterator \&begin, NodeIterator \&end)] This
423 method returns a range of nodes (defined by \texttt{begin} and
424 \texttt{end}) such that 1) all nodes in the graph are reachable from
425 the nodes in this range by traversing out-edges and 2) the range is
426 minimal. The nodes included in this range may be virtual.
427 \item[void exitNodes(NodeIterator \&begin, NodeIterator \&end)] This
428 method returns a range of nodes (defined by \texttt{begin} and
429 \texttt{end}) such that 1) all nodes in the graph are reachable from
430 the nodes in this range by traversing in-edges and 2) the range is
431 minimal. The nodes included in this range may be virtual.
432 \item[void allNodes (NodeIterator \&begin, NodeIterator \&end)]
433 This method returns the range of all nodes in the graph.
434 \item[void printDOT(std::string fileName)]
435 This method generates a representation of the graph in DOT format.
436 \item[bool find(Address addr, NodeIterator \&begin, NodeIterator \&end)]
437 This method sets \texttt{begin} and \texttt{end} to point to a range
438 representing the nodes with a particular address. It returns true if
439 the range is non-empty. 
440 \item[void removeAnnotation()] This method removes the graph from
441 internal storage. Once all user handles to the graph are discarded the
442 graph will be destroyed.
443 \end{description}
444
445 \subsubsection{Node}
446
447 \begin{description}
448 \item[bool hasInEdges()] This method returns true if the node has at
449   least one in edge. 
450 \item[void ins(EdgeIterator \&begin, EdgeIterator \&end)]
451 This method returns the range of in edges to the node (edges that have the node as a target). 
452 \item[void ins(NodeIterator \&begin, NodeIterator \&end)]
453 This method is similar to the previous, but automatically traverses the edges and returns a range of source nodes. 
454 \item[bool hasOutEdges()] This method returns true if the node has at
455   least one out edge. 
456 \item[void outs(EdgeIterator \&begin, EdgeIterator \&end)]
457 This method returns the range of out edges from the node (edges that have the node as a source). 
458 \item[void outs(NodeIterator \&begin, NodeIterator \&end)]
459 This method is similar to the previous, but automatically traverses the edges and returns a range of target nodes.
460 \item[void forwardClosure(NodeIterator \&begin, NodeIterator \&end)]
461 This method returns all nodes reachable from this node in the forward direction (by traversing out-edges).
462 \item[void backwardsClosure(NodeIterator \&begin, NodeIterator \&end)]
463 This method returns all nodes reachable from this node by traversing in-edges.
464 \item[Graph::Ptr forwardSubgraph()]
465 This method constructs and returns the subgraph that includes all
466 nodes reachable from the current node along forward edges.
467 \item[Graph::Ptr backwardSubgraph()]
468 This method constructs and returns the subgraph that includes all
469 nodes reachable from the current node along forward edges.
470 \item[std::string format()]
471 This method returns a textual representation of the node.
472 \item[bool isVirtual() ]
473 This method returns true if a node is virtual.
474 \end{description}
475
476 \subsubsection{PhysicalNode : Node}
477 \begin{description}
478 \item[Address addr()] This method returns the starting
479 offset of the code object (basic block, instruction, or operation) the
480 node represents.
481 \item[bool isVirtual()] This method returns false for physical nodes.
482 \end{description}
483
484 \subsubsection{VirtualNode : Node}
485 \begin{description}
486 \item[bool isVirtual()]
487 This method always returns true for virtual nodes.
488 \end{description}
489
490 \subsubsection{Edge}
491 \begin{description}
492 \item[Node::Ptr source()]
493 This method returns the source node of an edge.
494 \item[Node::Ptr target() ]
495 This method returns the target node of an edge.
496 \end{description}
497
498 \subsection{Data Dependence Graph}
499 \subsubsection{DDG}
500 \begin{description}
501 \item[DDG::Ptr analyze(BPatch\_function *func)]
502 This method creates and returns a DDG for the provided function.
503 \item[void formalParamNodes(NodeIterator \&begin, NodeIterator \&end) ]
504 This method returns the range of all formal parameters to the function.
505 \item[void formalReturnNodes(NodeIterator \&begin, NodeIterator \&end)]
506 This method returns the range of all formal returns from the function.
507 \item[void actualParamNodes(Address callAddr, NodeIterator \&begin, NodeIterator \&end) ]
508 This method returns the range of all actual parameters for the call instruction
509 at the given address.
510 \item[void actualReturnNodes(Address callAddr, NodeIterator \&begin, NodeIterator \&end)]
511 This method returns the range of all actual returns for the call instruction at
512 the given address.
513 \item[bool find(Address addr, Absloc::Ptr absloc, NodeIterator \&begin, NodeIterator \&end) ]
514 This method returns the range of nodes that fit the specific address
515 and absloc requirements. This range will contain at most one
516 element. It returns true if the range is non-empty, and false
517 otherwise. 
518 \item[DDG::Ptr removeDeadNodes()] This method constructs a derived DDG
519   that contains no dead nodes. All nodes that cannot reach a
520   formal return node are removed. This includes definitions to
521   abstract locations that are redefined before being used. 
522 \item[void immediateDefinitions(NodeIterator \&begin, NodeIterator
523   \&end)] This method returns the range of non-formal-parameter nodes
524   that have no in-edges. This occurs when an instruction defines an
525   abstract location without using any other abstract location; for
526   example, \texttt{mov \$42, eax}. Using this in combination with
527   \texttt{formalParamNodes} will give the set of entry nodes to the DDG.
528 \item[void deadDefinitions(NodeIterator \&begin, NodeIterator \&end)]
529   This method gives the range of non-formal-return nodes that have no
530   out-edges. This occurs when a node defines an abstract location that
531   is redefined before being used. These dead definitions are commonly
532   instruction side-effects (e.g., ignored writes to the flags). 
533 \end{description}
534
535 \subsubsection{Absloc}
536 \begin{description}
537 \item[std:string format()]
538 This method returns a textual representation of the abstract location. This representation is guaranteed to be unique for unique abstract locations.
539 \item[void getAliases(AbslocIterator \&begin, AbslocIterator \&end)]
540 If more than one Absloc may refer to the same abstract location (e.g., a particular stack slot and the representation of the entire stack) return any such aliases.
541 \item[bool isPrecise()]
542 This method returns true if the absloc does not contain any others; that is, if any aliases are more general than this one.
543 \end{description}
544
545 \subsubsection{OperationNode : PhysicalNode}
546 \begin{description}
547 \item[Absloc::Ptr absloc()]
548 This method returns the abstract location represented by this node.
549 \end{description}
550
551 \subsubsection{FormalParameterNode : VirtualNode}
552 \begin{description}
553 \item[Absloc::Ptr absloc()]
554 This method returns the abstract location represented by this node. 
555 \end{description}
556
557 \subsubsection{FormalReturnNode : VirtualNode}
558 \begin{description}
559 \item[Absloc::Ptr absloc()]
560 This method returns the abstract location represented by this node.
561 \end{description}
562
563 \subsubsection{ActualParameterNode : VirtualNode}
564 \begin{description}
565 \item[Absloc::Ptr absloc()]
566 This method returns the abstract location represented by this node.
567 \item[BPatch\_function *callee() ]
568 This method returns the callee function whose argument is represented by this node.
569 \end{description}
570
571 \subsubsection{ActualReturnNode : VirtualNode}
572 \begin{description}
573 \item[Absloc::Ptr absloc()]
574 This method returns the abstract location represented by this node.
575 \item[BPatch\_function *callee() ]
576 This method returns the callee function whose return is represented by this node.
577 \end{description}
578
579 \subsection{Control Dependence Graph}
580 \subsubsection{CDG}
581 \begin{description}
582 \item[CDG::Ptr analyze(BPatch\_function *func)]
583 This method creates and returns a CDG for the provided function.
584 \item[bool find(BPatch\_basicBlock *block, NodeIterator \&begin, NodeIterator \&end)]
585 This method returns the range of nodes representing the provided
586 block. This range will have at most one element. It returns true if
587 the range is non-empty and false otherwise. 
588 \item[bool find(Address addr, NodeIterator \&begin, NodeIterator
589 \&end)] This method returns the range of nodes containing the provided
590 address. It returns true if the range is non-empty and false
591 otherwise.
592 \end{description}
593
594 \subsubsection{BlockNode : Node}
595 \begin{description}
596 \item[BPatch\_basicBlock *block() ]
597 This method returns the basic block represented by this node. 
598 \end{description}
599
600 \subsection{Program Dependence Graph}
601 \subsubsection{PDG}
602 \begin{description}
603 \item[PDG::Ptr analyze(BPatch\_function *func)]
604 Creates and returns a PDG for the provided function.
605 \item[find(Address addr, Absloc::Ptr absloc, NodeIterator \&begin, NodeIterator \&end) ]
606 This method returns the set of nodes that fit the specific address and absloc requirements. This node will be singular.
607 \end{description}
608
609 \subsection{Extended Program Dependence Graph}
610 \subsubsection{xPDG}
611 \begin{description}
612 \item[xPDG::Ptr analyze(BPatch\_function *func)]
613 Creates and returns an xPDG for the provided function.
614 \item[find(Address addr, Absloc::Ptr absloc, NodeIterator \&begin, NodeIterator \&end) ]
615 This method returns the set of nodes that fit the specific address and absloc requirements. This node will be singular.
616 \end{description}
617
618 \section{Implementation Status}
619
620 This release of the DepGraphAPI is a public beta and has limited
621 platform support and implementation features. These limitations are as
622 follows:
623 \begin{itemize}
624 \item Platforms: the DepGraphAPI is implemented for IA-32 and
625   x86-64. This is primarily due to a dependence on the InstructionAPI.
626 \end{itemize}
627
628
629 \section{Building DepGraphAPI}
630 This appendix describes how to build DepGraphAPI from source code,
631 which can be downloaded from http://www.paradyn.org or
632 http://www.dyninst.org.
633
634 \subsection{Building on Unix}
635 The beta of the DepGraphAPI depends on the DyninstAPI. It is currently
636 packaged with the DyninstAPI source tree. It can be built using the
637 DepGraphAPI make target once the DyninstAPI has been built and
638 installed.
639
640 \end{document}