Update copyright to LGPL on all files
[dyninst.git] / instructionAPI / src / groups.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 // groups.C: Doxygen file to collect group definitions and documentation, and ensure that they are found in the correct order.
33
34 /*! 
35  * \defgroup moduleAbstractionIntro REMOVE
36  * The Instruction API contains three major components: the top-level instruction representation,
37  * the abstract syntax trees representing the operands of an instruction, and the decoder that creates
38  * the entire representation.  We will present an overview of the features and uses of each of these three components,
39  * followed by an example of how the Instruction API can be applied to binary analysis.
40  */
41 /** \defgroup instruction Instruction Interface
42  * The Instruction API represents a machine language instruction as an Instruction object,
43  * which contains an Operation
44  * and a collection of Operands.  The %Operation contains the following items:
45  *   - The mnemonic for the machine language instruction represented by its associated %Instruction
46  *   - The number of operands accepted by the %Operation
47  *   - Which Operands are read and/or written by the associated machine operation
48  *   - What other registers (if any) are affected by the underlying machine operation
49  *
50  * Each Operand contains
51  * flags to indicate whether it is read, written, or both by the machine instruction
52  * represented by its parent %Instruction, and contains a Expression abstract
53  * syntax tree representing the operations required to compute the value of the operand.  Figure 1 depicts
54  * these ownership relationships within an %Instruction.
55  * \dotfile ownership_graph.dot "An Instruction and the objects it owns"
56  *
57  * Instruction objects provide two types of interfaces: direct read access to their components,
58  * and common summary operations on those
59  * components.  The first interface allows access to the %Operation and %Operand data members, and each
60  * %Operand object in turn allows traversal of its abstract syntax tree.
61  * More details about how to work with this abstract syntax tree can be found in \ref instruction_ast_module.
62  * This interface would be used, for example, in a data flow analysis where a user wants to evaluate
63  * the results of an effective address computation given a known register state.
64  * 
65  * The second interface allows
66  * a user to get the sets of registers read and written by the instruction, information
67  * about how the instruction accesses memory, and information about how the instruction affects
68  * control flow, without having to manipulate the Operands directly.
69  * For instance, a user could implement a register liveness analysis algorithm using just this second interface
70  * (namely the \c getReadSet and \c getWriteSet functions).
71  */
72 /** \defgroup instructiondecoder Instruction Decoding
73  * An InstructionDecoder interprets a sequence of bytes according to a
74  * given machine language and transforms them into an instruction
75  * representation. It determines the opcode of the machine instruction,
76  * translates that opcode to an Operation object, uses that %Operation to determine 
77  * how to decode the instruction's Operands, and produces a decoded Instruction.
78  *
79  * \dotfile decoder_use.dot "The InstructionDecoder's inputs and outputs"
80  * Instruction decoders are built from the following elements:
81  *  - A function to find and extract an opcode given a pointer into a buffer that points to the beginning of a machine instruction
82  *  - A table that, for a particular architecture,
83  * maps opcodes to Operations and functions that decode Operands
84  *
85  * From these elements, it is possible to generalize the construction of Instructions
86  * from Operations and Operands to an entirely platform-independent algorithm.  Likewise, much of
87  * the construction of the ASTs representing each operand can be performed in a platform-independent manner.
88  * 
89  */
90 /** \defgroup instruction_ast_module InstructionAST Hierarchy
91  * The AST representation of an operand encapsulates the operations performed
92  * on registers and immediates to produce an operand for the machine
93  * language instruction.
94  *
95  * The inheritance hierarchy of the AST classes is shown in Figure 3.
96  * \dotfile full_inheritance_graph.dot "The InstructionAST inheritance hierarchy"
97  * The grammar for these AST representations is simple: all leaves must be RegisterAST or Immediate nodes.
98  * These nodes may be combined using a BinaryFunction node, which may be constructed as either
99  * an addition or a multiplication.  Also, a single node may descend from a Dereference node, which
100  * treats its child as a memory address.  Figure 4 shows the allowable parent/child relationships
101  * within a given tree, and Figure 5 shows how an example IA32 instruction is represented using these objects.
102  * \dotfile ast_ownership.dot "InstructionAST intermediate node types and the objects they own"
103  * \dotfile instruction_representation.dot "The decomposition of \c mov \c %eax, (\c %esi)"
104  * These ASTs may be searched for leaf elements or subtrees (via \c getUses and \c isUsed) and traversed
105  * breadth-first or depth-first (via \c getChildren).
106  *
107  * Any node in these ASTs may be evaluated.  Evaluation attempts
108  * to determine the value represented by a node.  If successful, it will return that value and cache it in the node.
109  * The tree structure, combined with the evaluation mechanism, allows the substitution of known register and memory
110  * values into an operand, regardless of whether those values are known at the time an instruction is decoded.
111  * More details on this mechanism may be found in \ref Dyninst::InstructionAPI::Expression.
112  *
113  */
114
115 /** \defgroup liveness_example Example of Use: Register Liveness Analysis
116 /// Now that we've discussed the components of the API, we present an example that shows
117 /// how the API helps make analysis algorithms easy to implement.
118 ///
119 /// Our first example will be a register liveness analysis algorithm over a basic block of code.
120 /// We'll elide the decoding of instructions and the parsing necessary to build a basic block,
121 /// and start from a representation of a basic block as a decoded sequence of Instruction objects.
122 ///
123 /// \code
124 /// std::set<RegisterAST::Ptr> getLiveRegisters(const std::map<Address, Instruction>& basicBlock)
125 /// {
126 ///   typedef std::map<Address, std::set<RegisterAST::Ptr> > LivenessSet;
127 ///   LivenessSet liveRegsPost;
128 ///   LivenessSet liveRegsPre;
129 ///   for(std::map<Address, Instruction>::reverse_iterator ri = basicBlock.rbegin();
130 ///       ri != basicBlock.rend();
131 ///       ++ri)
132 ///   {
133 ///     Address curAddr = ri->first;
134 ///     Instruction curInsn = ri->second;
135 ///     std::set_difference(liveRegsPost[curAddr].begin(), liveRegsPost[curAddr].end(), 
136 ///       curInsn->getRegsWritten().begin(), curInsn.getRegsWritten().end(), std::inserter(liveRegsPre[curAddr].begin());
137 ///     std::set_union(liveRegsPre[curAddr].begin(), liveRegsPre[curAddr].end(), curInsn->getRegsRead().begin(), curInsn->getRegsRead().end(),
138 ///       std::inserter(liveRegsPre[curAddr].begin()));
139 ///     
140 ///   }
141 */