Merge branch 'master' of git.dyninst.org:/pub/dyninst
[dyninst.git] / depGraphAPI / DepGraphAPI.txt
1 Introduction
2
3 DepGraphAPI is a multi-platform library for creating and analyzing dependence graph representations of binary code. These graph representations include a data dependence graph (DDG), control dependence graph (CDG), flow dependence graph (FDG), and program dependence graph (PDG). The current beta of the DepGraphAPI depends on the InstructionAPI library and the DyninstAPI; future versions will depend only on the InstructionAPI and ParsingAPI libraries released as part of the DyninstAPI. Currently we support the IA-32 and AMD-64 architectures as these are the only architectures supported by the InstructionAPI. Future architecture support includes PPC, IA-64, and SPARC. 
4
5 The main goal of this API is to provide the user with abstractions representing the logical dependencies between instructions in a program. An abstract interface provides two benefits: it simplifies the development of a tool since the complexity of a particular architecture is hidden, and it allows tools to easily be ported between platforms. We use graphs to represent fundamental must-happen-before and must-happen-after relationships between instructions. These graphs represent:
6         * DDG: the set of instructions that define a value used by a particular target instruction, or the set of instructions that use the value defined by a particular source instruction.
7         * CDG: The instruction whose execution determines whether a particular target instruction is executed, or the set of instructions whose execution is determined by a particular source instruction.
8         * FDG: ???
9         * PDG: The union of the DDG, CDG, and FDG.
10
11 A future goal of this library is to allow users to improve these graph representations through the use of additional analyses. The included analyses used to generate these graph representations are conservative, and may over-represent the actual dependences between instructions. A future release will provide an API for updating these graph structures, either with information known to the user directly or with the results of more sophisticated analysis. 
12
13 This document describes DepGraphAPI, an Application Program Interface (API) for analyzing and representing dependence graphs from binary code. 
14
15 Abstractions
16
17 DepGraphAPI provides a simple set of abstractions over complicated data structures to make it easy to use. The DepGraphAPI consists of four graph variants: the data dependence graph (DDG), control dependence graph (CDG), flow dependence graph (FDG), and program dependence graph (PDG). 
18
19 The fundamental representation used by this library is the graph. A graph is a set of nodes connected by directed edges; each edge has a distinct (and unique) source and target. A node may be physical or virtual. Physical nodes represent objects within the code; either an instruction or a combination of an instruction and the register or memory location that instruction defines (referred to collectively as abstract locations). Virtual nodes are added to the graph to represent dependences between the graph and code external to the graph (e.g., parameters of a called function). 
20
21 Figure 1 shows the ownership hierarchy for the DepGraphAPI classes. Ownership here is a "contains" relationship; if one class owns another, then instances of the owner class contain an exclusive instance of the other. All references to DepGraphAPI classes are internally reference counted; we do not require the user to perform any manual memory allocation or deletion. 
22         * Graphs own nodes
23         * Nodes own edges
24         * Analyzers own graphs(?)
25
26 Shared Abstractions
27         * Graph: the Graph represents a dependence graph for a particular function.
28         * Node: the Node represents an element within the graph. Nodes are connected by edges. All physical nodes have both in and out edges; virtual nodes may lack one or both. 
29         * Edge: Edges connect Nodes. Edges are directed and have a source and target.
30         * Absloc: An Absloc represents a register, memory location, or set of memory locations.
31
32 Data Dependence Graph
33         The data dependence graph adds several specialized node types.
34         * OperNode: Each physical DDG node represents an operation (a definition of a particular abstract location by a particular instruction instance). We describe operations and our justification of this abstraction below.
35         * FormalParameterNode: These represent input parameters to a function. An input parameter is a definition of an abstract location before the function is executed.
36         * FormalReturnNode: These represent definitions that persist after the function returns.
37         * ActualParameterNode: These represent arguments to a called function. 
38         * ActualReturnNode: These represent definitions made by a called function.
39         * ImmediateNode: These represent uses of constant (immediate) values, and exist to ensure that all physical nodes have at least one in edge. 
40         
41 Control Dependence Graph
42         *???
43         
44 Flow Dependence Graph
45         *???
46         
47 Program Dependence Graph
48         The Program Dependence Graph is the union of these three graphs and is constructed from the same abstractions.
49
50 Analyzer
51         The analyzer class is responsible for deriving the desired dependence graph from the underlying code. The analyzer is a temporary object that contains intermediate analysis results, and can safely be discarded as soon as graph construction is complete. 
52         
53 Annotations
54         The DepGraphAPI makes use of the Annotation infrastructure in the DyninstAPI classes. First, all DepGraphAPI abstractions are annotatable. The internal implementation of the annotation infrastructure is optimized for sparse annotation; that is, when the majority of abstractions are not annotated. Second, the function abstractions are annotated with the completed graphs. Therefore, the user does not need to keep a reference to an analyzed graph. This annotation can be discarded by using the appropriate methods on the Graph class.
55         
56 Examples
57         TODO
58         
59 Definitions and Basic Types
60
61 The DepGraphAPI supplies four types of dependence graphs. We define these forms of dependence here, along with definitions of the underlying concepts. The following definitions and basic types are referenced throughout the rest of the document.
62
63 Definitions
64         Instruction Instance: an instruction instance represents a single machine instruction with a unique starting offset. Instruction instances are identified by this offset. For the remainder of this document an instruction represents an instruction instance.
65         Abstract Location: An abstract location represents a machine register, memory location, or set of memory locations. Registers are referred to by their InstructionAPI representation. Memory locations consist of a region and an optional offset within that region. Regions include the stack, the heap, and global memory. Stack locations are assumed to be relative from the top of the stack at the beginning of the function. Our current implementation assumes a single heap location; this may change in future releases. Finally, offsets into global memory represent absolute addresses. 
66         Operation: an operation is a pair of an instruction and an abstract location defined by that instruction. An instruction may define more than one abstract location, particularly on CISC architectures. In this case the operation allows us to specify which abstract location is defined.
67         Data Dependence: In general instruction j is data dependent on i if i defines an abstract that j uses and there is an execution path from i to j along which a is not redefined. We use a more precise definition that uses operations as nodes. Let m = (i,a) be an operation representing the definition of a by i, and similarly for n = (j, b). Then n is data dependent on m if i defines a, j uses a to define b, and there exists a path as above. We discuss this more precise formulation below.
68         Control Dependence: An instruction j is control dependent on i if i has multiple successors and j is executed along at least one, but not all, possible execution paths from i. 
69         Flow Dependence: not sure what this one means...
70         Transitive Dependence: An instruction j is transitively dependent on i if there is a path (i, ..., j) in the corresponding dependence graph.
71         
72 Basic Types
73         typedef unsigned long Offset
74                 An integer value that represents the offset from the base address of the file. 
75         typedef unsigned long Address
76                 An integer value that represents a unique location in memory used or defined by an instruction.
77         Smart/shared pointers
78                 All objects returned to users are transparently wrapped with a reference counted pointer implementation. This smart pointer automatically handles deallocation and garbage collection. These pointers are referred to by the ::Ptr suffix (e.g., Graph::Ptr, Node::Ptr, etc.). Our implementation is derived from the Boost shared_ptr implementation; for more information, please visit www.boost.org.
79         Collections
80                 We use STL structures to contain collections of objects. For ease of use each class contains typedefs for these types: ::Set, ::Vector, ... respectively. Each of these collections is defined over shared pointers (see above). 
81                 
82 Operation-Level Data Dependence
83         Include from paper with example figure. 
84                 
85 Namespace DepGraphAPI
86         The classes described in Section (API) are under the C++ namespace Dyninst::DepGraphAPI. To access them a user should refer to them using the Dyninst:: and SymtabAPI:: prefixes (e.g., Dyninst::DepGraphAPI::Graph). Alternatively, a user can add the C++ using keyword above any reference to DepGraphAPI objects (e.g., using namespace Dyninst and using namespace DepGraphAPI). Uses  of other DyninstAPI libraries by this library handle namespaces appropriately. 
87
88 API Reference
89         This section describes the interface of the DepGraphAPI. Each of the subsections represents a different interface.
90         
91         Shared Classes
92                 Each graph type shares certain functionality. To reduce redundancy we describe these shared types here. All derived types can be assumed to provide the same functions.
93                 
94         Graph
95                 entryNodes(..., bool includeVirtual) - returns a minimal set of nodes such that all nodes are reachable from this set. If useVirtual is false then only physical nodes will be returned. 
96                 allNodes - return the set of all nodes in the graph.
97                 printDOT - generates a representation of the graph in DOT format.
98                 getNodes (Offset off) - returns the set of physical nodes that have an offset off.
99                 removeAnnotation() - removes the graph from internal storage. Once this is called, if all user handles to the graph are removed the graph will be destroyed and must be re-analyzed.
100         Node
101                 Edge::Vector ins() - returns the set of in edges to the node (edges that have the node as a target). 
102                 Edge::Vector outs() - returns the set of out edges from the node (edges that have the node as a source). 
103                 std::string format() - returns a textual representation of the node. This representation is guaranteed to be unique. 
104                 bool isVirtual() - returns whether a node is virtual or physical.
105         PhysicalNode : Node
106                 Offset offset() - returns the offset of the instruction (or operation) the node represents.
107                 bool isVirtual() - returns false
108         VirtualNode : Node
109                 bool isVirtual() - returns true
110         Edge
111                 Node::Ptr source() - returns the source node of an edge
112                 Node::Ptr target() - returns the target node of an edge
113         Absloc
114                 std:string name() - returns a textual representation of the abstract location. This representation is guaranteed to be unique. 
115                 getAliases() - 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. 
116                 isPrecise() - Returns true if the Absloc does not contain any others.
117         
118         Analyzer
119                 Analyzer createAnalyzer(BPatch_function *func): creates an Analyzer for the specified function. This function will continue to exist in future versions of the DepGraphAPI; in addition, we will add additional Analyzer creation methods.
120                 Graph::Ptr createDDG()
121                 Graph::Ptr createCDG()
122                 Graph::Ptr createFDG()
123                 Graph::Ptr createPDG() : Creates and returns the specified graph. In addition, the provided function is annotated with the graph so the user does not have to keep a handle; to remove this annotation use Graph::removeAnnotation(). If an annotation is present the user is returned a handle to the previously analyzed graph.
124         
125         Data Dependence Graph
126         DDG
127                 Node::Vector formalParameterNodes() - returns the vector of all formal parameters to the function.
128                 Node::Vector formalReturnNodes() - returns the vector of all formal returns from the function.
129         OperationNode : PhysicalNode
130                 Absloc::Ptr absloc() - returns the abstract location defined by the operation represented by this node.
131         FormalParameterNode : VirtualNode
132         FormalReturnNode : VirtualNode
133         ActualParameterNode : VirtualNode
134         ActualReturnNode : VirtualNode
135         ImmediateNode : VirtualNode
136         
137         Control Dependence Graph
138         CDG
139         
140         InstructionNode : PhysicalNode
141         
142                 
143