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