Merge branch 'master' into devel
[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 "Absloc.h"
40 #include "AST.h"
41
42 #include "external/rose/rose-compat.h"
43 #include "external/rose/powerpcInstructionEnum.h"
44 #include "Graph.h"
45
46 class SgAsmx86Instruction;
47 class SgAsmExpression;
48 class SgAsmPowerpcInstruction;
49 class SgAsmOperandList;
50 class SgAsmx86RegisterReferenceExpression;
51 class SgAsmPowerpcRegisterReferenceExpression;
52
53 namespace Dyninst {
54 namespace SymbolicEvaluation {
55
56 // The ROSE symbolic evaluation engine wants a data type that
57 // is template parametrized on the number of bits in the data
58 // type. However, our ASTs don't have this, and a shared_ptr
59 // to an AST _definitely_ doesn't have it. Instead, we use
60 // a wrapper class (Handle) that is parametrized appropriately
61 // and contains a shared pointer. 
62
63 // This uses a pointer to a shared pointer. This is ordinarily a really
64 // bad idea, but stripping the pointer part makes the compiler allocate
65 // all available memory and crash. No idea why. 
66
67 // Define the operations used by ROSE
68
69 struct SYMEVAL_EXPORT Variable {
70   Variable() : reg(), addr(0) {};
71   Variable(AbsRegion r) : reg(r), addr(0) {};
72   Variable(AbsRegion r, Address a) : reg(r), addr(a) {};
73
74   bool operator==(const Variable &rhs) const { 
75     return ((rhs.addr == addr) && (rhs.reg == reg));
76   }
77
78   bool operator<(const Variable &rhs) const { 
79     if (addr < rhs.addr) return true;
80     if (reg < rhs.reg) return true;
81     return false;
82   }
83
84   const std::string format() const {
85     std::stringstream ret;
86     ret << reg;
87     if (addr) ret << ":" << std::hex << addr << std::dec;
88     return ret.str();
89   }
90
91   AbsRegion reg;
92   Address addr;
93 };
94
95 struct SYMEVAL_EXPORT Constant {
96   Constant() : val(0), size(0) {};
97   Constant(uint64_t v) : val(v), size(0) {};
98   Constant(uint64_t v, size_t s) : val(v), size(s) {};
99
100   bool operator==(const Constant &rhs) const {
101     return ((rhs.val == val) && (rhs.size == size));
102   }
103
104   bool operator<(const Constant &rhs) const {
105     if (val < rhs.val) return true;
106     if (size < rhs.size) return true;
107     return false;
108   }
109
110   const std::string format() const {
111     std::stringstream ret;
112     ret << val;
113     if (size) {
114     ret << ":" << size;
115     }
116     return ret.str();
117   }
118   
119   uint64_t val;
120   size_t size;
121 };
122
123 // Define the operations used by ROSE
124
125 struct ROSEOperation {
126 typedef enum {
127     nullOp,
128     extractOp,
129     invertOp,
130     negateOp,
131     signExtendOp,
132     equalToZeroOp,
133     generateMaskOp,
134     LSBSetOp,
135     MSBSetOp,
136     concatOp,
137     andOp,
138     orOp,
139     xorOp,
140     addOp,
141     rotateLOp,
142     rotateROp,
143     shiftLOp,
144     shiftROp,
145     shiftRArithOp,
146     derefOp,
147     writeRepOp,
148     writeOp,
149     ifOp,
150     sMultOp,
151     uMultOp,
152     sDivOp,
153     sModOp,
154     uDivOp,
155     uModOp,
156     extendOp,
157     extendMSBOp
158 } Op;
159
160 ROSEOperation(Op o) : op(o), size(0) {};
161 ROSEOperation(Op o, size_t s) : op(o), size(s) {};
162
163 bool operator==(const ROSEOperation &rhs) const {
164     return ((rhs.op == op) && (rhs.size == size));
165 }
166
167 const std::string format() const {
168     std::stringstream ret;
169     ret << "<";
170     switch(op) {
171     case nullOp:
172     ret << "null";
173     break;
174     case extractOp:
175     ret << "extract";
176     break;
177     case invertOp:
178     ret << "invert";
179     break;
180     case negateOp:
181     ret << "negate";
182     break;
183     case signExtendOp:
184     ret << "signExtend";
185     break;
186     case equalToZeroOp:
187     ret << "eqZero?";
188     break;
189     case generateMaskOp:
190     ret << "genMask";
191     break;
192     case LSBSetOp:
193     ret << "LSB?";
194     break;
195     case MSBSetOp:
196     ret << "MSB?";
197     break;
198     case concatOp:
199     ret << "concat";
200     break;
201     case andOp:
202     ret << "and";
203     break;
204     case orOp:
205     ret << "or";
206     break;
207     case xorOp:
208     ret << "xor";
209     break;
210     case addOp:
211     ret << "add";
212     break;
213     case rotateLOp:
214     ret << "rotL";
215     break;
216     case rotateROp:
217     ret << "rotR";
218     break;
219     case shiftLOp:
220     ret << "shl";
221     break;
222     case shiftROp:
223     ret << "shr";
224     break;
225     case shiftRArithOp:
226     ret << "shrA";
227     break;
228     case derefOp:
229     ret << "deref";
230     break;
231     case writeRepOp:
232     ret << "writeRep";
233     break;
234     case writeOp:
235     ret << "write";
236     break;
237     case ifOp:
238     ret << "if";
239     break;
240     case sMultOp:
241     ret << "sMult";
242     break;
243     case uMultOp:
244     ret << "uMult";
245     break;
246     case sDivOp:
247     ret << "sDiv";
248     break;
249     case sModOp:
250     ret << "sMod";
251     break;
252     case uDivOp:
253     ret << "uDiv";
254     break;
255     case uModOp:
256     ret << "uMod";
257     break;
258     case extendOp:
259     ret << "ext";
260     break;
261     case extendMSBOp:
262     ret << "extMSB";
263     break;
264     default:
265     ret << " ??? ";
266     break;
267     };
268     if (size) {
269     ret << ":" << size;
270     }
271     ret << ">";
272     return ret.str();
273 };
274
275 Op op;
276 size_t size;
277 };
278
279 };
280
281 };
282
283 // Get this out of the Dyninst namespace...
284 std::ostream &operator<<(std::ostream &os, const Dyninst::SymbolicEvaluation::ROSEOperation &o);
285 std::ostream &operator<<(std::ostream &os, const Dyninst::SymbolicEvaluation::Constant &o);
286 std::ostream &operator<<(std::ostream &os, const Dyninst::SymbolicEvaluation::Variable &o);
287
288 namespace Dyninst {
289
290 namespace InstructionAPI {
291   class Instruction;
292 }
293
294 class AssignNode;
295
296 namespace SymbolicEvaluation {
297
298 typedef std::map<Assignment::Ptr, AST::Ptr> Result_t;
299     
300 DEF_AST_LEAF_TYPE(BottomAST, bool);
301 DEF_AST_LEAF_TYPE(ConstantAST, Constant);
302 DEF_AST_LEAF_TYPE(VariableAST, Variable);
303 DEF_AST_INTERNAL_TYPE(RoseAST, ROSEOperation);
304
305 class SymEvalPolicy;
306
307 class SYMEVAL_EXPORT SymEval {
308
309 public:
310     typedef std::map<Assignment::Ptr, AST::Ptr> Result_t;
311     typedef dyn_detail::boost::shared_ptr<AssignNode> AssignNodePtr;
312 public:
313   // Return type: mapping AbsRegions to ASTs
314   // We then can map Assignment::AbsRegions to 
315   // SymEval::AbsRegions and come up with the answer
316   // static const AST::Ptr Placeholder;
317   //
318   // Single version: hand in an Assignment, get an AST
319   static AST::Ptr expand(const Assignment::Ptr &assignment);
320
321   // Hand in a set of Assignments
322   // get back a map of Assignments->ASTs
323   // We assume the assignments are prepped in the input; whatever
324   // they point to is discarded.
325   static void expand(Result_t &res, bool applyVisitors = true);
326
327   // Hand in a Graph (of AssignNodes, natch) and get back a Result;
328   // prior results from the Graph
329   // are substituted into anything that uses them.
330   static void expand(Graph::Ptr slice, Result_t &res);
331   
332  private:
333
334  typedef dyn_detail::boost::shared_ptr<InstructionAPI::Instruction> InstructionPtr;
335
336   // Symbolically evaluate an instruction and assign 
337   // an AST representation to every written absloc
338   static void expandInsn(const InstructionPtr insn,
339                          const uint64_t addr,
340                          Result_t& res);
341
342   static void process(AssignNodePtr ptr, Result_t &dbase);
343   
344 };
345
346 };
347 };
348
349 #endif