Make SymEval an exported header
[dyninst.git] / symEval / h / SymEval.h
1 /*
2  * Copyright (c) 1996-2007 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 // Stubs for now
33
34 #if !defined(SymEval_h)
35 #define SymEval_h
36
37 #include <map>
38
39 #include "Instruction.h"
40 #include "BinaryFunction.h"
41 #include "Dereference.h"
42 #include "Immediate.h"
43 #include "Absloc.h"
44 #include "AST.h"
45
46 #include "slicing.h"
47
48 #include "external/rose/rose-compat.h"
49
50 #include "Graph.h"
51
52 class SgAsmx86Instruction;
53 class SgAsmExpression;
54
55 namespace Dyninst {
56 namespace SymbolicEvaluation {
57
58 // The ROSE symbolic evaluation engine wants a data type that
59 // is template parametrized on the number of bits in the data
60 // type. However, our ASTs don't have this, and a shared_ptr
61 // to an AST _definitely_ doesn't have it. Instead, we use
62 // a wrapper class (Handle) that is parametrized appropriately
63 // and contains a shared pointer. 
64
65 // This uses a pointer to a shared pointer. This is ordinarily a really
66 // bad idea, but stripping the pointer part makes the compiler allocate
67 // all available memory and crash. No idea why. 
68
69 // Define the operations used by ROSE
70
71 struct ROSEOperation {
72   typedef enum {
73     nullOp,
74     extractOp,
75     invertOp,
76     negateOp,
77     signExtendOp,
78     equalToZeroOp,
79     generateMaskOp,
80     LSBSetOp,
81     MSBSetOp,
82     concatOp,
83     andOp,
84     orOp,
85     xorOp,
86     addOp,
87     rotateLOp,
88     rotateROp,
89     shiftLOp,
90     shiftROp,
91     shiftRArithOp,
92     derefOp,
93     writeRepOp,
94     writeOp,
95     ifOp,
96     sMultOp,
97     uMultOp,
98     sDivOp,
99     sModOp,
100     uDivOp,
101     uModOp,
102     extendOp,
103     extendMSBOp
104   } Op;
105
106   ROSEOperation(Op o) : op(o) {};
107
108   bool operator==(const ROSEOperation &rhs) const {
109     return (rhs.op == op);
110   }
111
112   const std::string format() const {
113     switch(op) {
114     case nullOp:
115       return "<null>";
116     case extractOp:
117       return "<extract>";
118     case invertOp:
119       return "<invert>";
120     case negateOp:
121       return "<negate>";
122     case signExtendOp:
123       return "<signExtend>";
124     case equalToZeroOp:
125       return "<eqZero?>";
126     case generateMaskOp:
127       return "<genMask>";
128     case LSBSetOp:
129       return "<LSB?>";
130     case MSBSetOp:
131       return "<MSB?>";
132     case concatOp:
133       return "<concat>";
134     case andOp:
135       return "<and>";
136     case orOp:
137       return "<or>";
138     case xorOp:
139       return "<xor>";
140     case addOp:
141       return "<add>";
142     case rotateLOp:
143       return "<rotL>";
144     case rotateROp:
145       return "<rotR>";
146     case shiftLOp:
147       return "<shl>";
148     case shiftROp:
149       return "<shr>";
150     case shiftRArithOp:
151       return "<shrA>";
152     case derefOp:
153       return "<deref>";
154     case writeRepOp:
155       return "<writeRep>";
156     case writeOp:
157       return "<write>";
158     case ifOp:
159       return "<if>";
160     case sMultOp:
161       return "<sMult>";
162     case uMultOp:
163       return "<uMult>";
164     case sDivOp:
165       return "<sDiv>";
166     case sModOp:
167       return "<sMod>";
168     case uDivOp:
169       return "<uDiv>";
170     case uModOp:
171       return "<uMod>";
172     case extendOp:
173       return "<ext>";
174     case extendMSBOp:
175       return "<extMSB>";
176     default:
177       return "< ??? >";
178     };
179   };
180
181   Op op;
182 };
183
184 };
185
186 };
187
188 // Get this out of the Dyninst namespace...
189 std::ostream &operator<<(std::ostream &os, const Dyninst::SymbolicEvaluation::ROSEOperation &o);
190
191 namespace Dyninst {
192
193 namespace SymbolicEvaluation {
194
195 DEF_AST_LEAF_TYPE(BottomAST, bool);
196 DEF_AST_LEAF_TYPE(ConstantAST, uint64_t);
197 DEF_AST_LEAF_TYPE(AbsRegionAST, AbsRegion);
198 DEF_AST_INTERNAL_TYPE(RoseAST, ROSEOperation);
199
200 class SymEval {
201  public:
202   // Return type: mapping AbsRegions to ASTs
203   // We then can map Assignment::AbsRegions to 
204   // SymEval::AbsRegions and come up with the answer
205
206   typedef std::map<Assignment::Ptr, AST::Ptr> Result;
207   static const AST::Ptr Placeholder;
208   
209   // Single version: hand in an Assignment, get an AST
210   static AST::Ptr expand(const Assignment::Ptr &assignment);
211
212   // Hand in a set of Assignments
213   // get back a map of Assignments->ASTs
214   // We assume the assignments are prepped in the input; whatever
215   // they point to is discarded.
216   static void expand(Result &res);
217
218   // Hand in a Graph (of AssignNodes, natch) and get back a Result;
219   // prior results from the Graph
220   // are substituted into anything that uses them.
221   static void expand(Graph::Ptr slice, Result &res);
222   
223  private:
224   static void process(AssignNode::Ptr, SymEval::Result &res);
225
226   static SgAsmx86Instruction convert(const InstructionAPI::Instruction::Ptr &insn, uint64_t addr);
227   static X86InstructionKind convert(entryID opcode);
228   static SgAsmExpression *convert(const InstructionAPI::Operand &operand);
229   static SgAsmExpression *convert(const InstructionAPI::Expression::Ptr expression);
230
231   // Symbolically evaluate an instruction and assign 
232   // an AST representation to every written absloc
233   static void expandInsn(const InstructionAPI::Instruction::Ptr insn,
234                          const uint64_t addr,
235                          Result &res);
236   
237   friend class ExpressionConversionVisitor;
238 };
239
240 class ExpressionConversionVisitor : public InstructionAPI::Visitor {
241  public:
242     ExpressionConversionVisitor() { roseExpression = NULL; }
243
244     SgAsmExpression *getRoseExpression() { return roseExpression; }
245
246     virtual void visit(InstructionAPI::BinaryFunction *binfunc);
247     virtual void visit(InstructionAPI::Immediate *immed);
248     virtual void visit(InstructionAPI::RegisterAST *regast);
249     virtual void visit(InstructionAPI::Dereference *deref);
250
251  private:
252     SgAsmExpression *roseExpression;
253 };
254
255 };
256 };
257
258 #endif