Fix vpadd decoding. Clean up control flow target logic and shared pointer constructio...
[dyninst.git] / instructionAPI / doc / 2-Abstractions.tex
1 \section{InstructionAPI Modules and Abstractions}
2
3 The Instruction API contains three major components: the top-\/level instruction
4 representation, the abstract syntax trees representing the operands of an
5 instruction, and the decoder that creates the entire representation. We will
6 present an overview of the features and uses of each of these three components,
7 followed by an example of how the Instruction API can be applied to binary
8 analysis. 
9
10 \subsection{Instruction Interface}
11
12 The Instruction API represents a machine language instruction as an Instruction
13 object, which contains an Operation and a collection of Operands. The Operation
14 contains the following items:
15
16 \begin{itemize}
17 \item The mnemonic for the machine language instruction represented by its associated Instruction
18 \item The number of operands accepted by the Operation
19 \item Which Operands are read and/or written by the associated machine operation
20 \item What other registers (if any) are affected by the underlying machine operation
21 \end{itemize}
22
23 Each Operand contains flags to indicate whether it is read, written, or both by
24 the machine instruction represented by its parent Instruction, and contains a
25 Expression abstract syntax tree representing the operations required to compute
26 the value of the operand. Figure~\ref{fig:ownership-graph} depicts these
27 ownership relationships within an Instruction. 
28
29 \begin{figure}
30 \centering
31     \includegraphics{fig/ownership_graph}
32 \caption{An Instruction and the objects it owns}
33 \label{fig:ownership-graph}
34 \end{figure}
35
36 Instruction objects provide two types of interfaces: direct read access to their
37 components, and common summary operations on those components. The first
38 interface allows access to the Operation and Operand data members, and each
39 Operand object in turn allows traversal of its abstract syntax tree. More
40 details about how to work with this abstract syntax tree can be found in
41 Section~\ref{subsec:hierarchy}.
42 This interface would be used, for example, in a data flow analysis where a user wants
43 to evaluate the results of an effective address computation given a known
44 register state.
45
46 The second interface allows a user to get the sets of registers read and written
47 by the instruction, information about how the instruction accesses memory, and
48 information about how the instruction affects control flow, without having to
49 manipulate the Operands directly. For instance, a user could implement a
50 register liveness analysis algorithm using just this second interface (namely
51 the \code{getReadSet} and \code{getWriteSet} functions).
52
53 \subsection{Instruction Decoding}
54
55 An InstructionDecoder interprets a sequence of bytes according to a given
56 machine language and transforms them into an instruction representation. It
57 determines the opcode of the machine instruction, translates that opcode to an
58 Operation object, uses that Operation to determine how to decode the
59 instruction's Operands, and produces a decoded Instruction.
60
61 \begin{figure}
62     \centering
63     \includegraphics[scale=.8]{fig/decoder_use}
64 \caption{The InstructionDecoder's inputs and outputs}
65 \label{fig:decoder-use}
66 \end{figure}
67  
68 Instruction decoders are built from the following elements:
69
70 \begin{itemize}
71 \item A function to find and extract an opcode given a pointer into a buffer that points to the beginning of a machine instruction
72 \item A table that, for a particular architecture, maps opcodes to Operations and functions that decode Operands
73 \end{itemize}
74
75 From these elements, it is possible to generalize the construction of
76 Instructions from Operations and Operands to an entirely platform-\/independent
77 algorithm. Likewise, much of the construction of the ASTs representing each
78 operand can be performed in a platform-\/independent manner. 
79
80 \subsection{InstructionAST Hierarchy}
81 \label{subsec:hierarchy}
82
83 The AST representation of an operand encapsulates the operations performed on
84 registers and immediates to produce an operand for the machine language
85 instruction.
86
87 The inheritance hierarchy of the AST classes is shown in
88 Figure~\ref{fig:inheritance}. 
89 \begin{figure}
90     \centering
91 \includegraphics{fig/full_inheritance_graph}
92 \caption{The InstructionAST inheritance hierarchy}
93 \label{fig:inheritance}
94 \end{figure}
95
96 The grammar for these AST representations is simple: all leaves must be
97 RegisterAST or Immediate nodes. These nodes may be combined using a
98 BinaryFunction node, which may be constructed as either an addition or a
99 multiplication. Also, a single node may descend from a Dereference node, which
100 treats its child as a memory address. Figure~\ref{fig:ownership} shows the allowable parent/child
101 relationships within a given tree, and Figure~\ref{fig:representation} shows how an example IA32
102 instruction is represented using these objects. 
103
104 \begin{figure}
105     \centering
106 \includegraphics{fig/ast_ownership}
107 \caption{InstructionAST intermediate node types and the objects they own}
108 \label{fig:ownership}
109 \end{figure}
110  
111 \begin{figure}
112     \centering
113 \includegraphics{fig/instruction_representation}
114 \caption{The decomposition of \code{mov} \code{\%eax}, (\code{\%esi})}
115 \label{fig:representation}
116 \end{figure}
117
118 These ASTs may be searched for leaf elements or subtrees (via 
119 \code{getUses} and \code{isUsed}) and traversed breadth-\/first or depth-\/first
120 (via \code{getChildren}).
121
122 Any node in these ASTs may be evaluated. Evaluation attempts to determine the
123 value represented by a node. If successful, it will return that value and cache
124 it in the node. The tree structure, combined with the evaluation mechanism,
125 allows the substitution of known register and memory values into an operand,
126 regardless of whether those values are known at the time an instruction is
127 decoded. More details on this mechanism may be found in
128 Section~\ref{sec:expression}.