Merge branch 'master' of git.dyninst.org:/pub/dyninst
[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 #include "external/rose/powerpcInstructionEnum.h"
50 #include "Graph.h"
51
52 class SgAsmx86Instruction;
53 class SgAsmExpression;
54 class SgAsmPowerpcInstruction;
55 class SgAsmOperandList;
56 class SgAsmx86RegisterReferenceExpression;
57 class SgAsmPowerpcRegisterReferenceExpression;
58
59 namespace Dyninst {
60 namespace SymbolicEvaluation {
61
62 // The ROSE symbolic evaluation engine wants a data type that
63 // is template parametrized on the number of bits in the data
64 // type. However, our ASTs don't have this, and a shared_ptr
65 // to an AST _definitely_ doesn't have it. Instead, we use
66 // a wrapper class (Handle) that is parametrized appropriately
67 // and contains a shared pointer. 
68
69 // This uses a pointer to a shared pointer. This is ordinarily a really
70 // bad idea, but stripping the pointer part makes the compiler allocate
71 // all available memory and crash. No idea why. 
72
73 // Define the operations used by ROSE
74
75 struct Variable {
76   Variable() : reg(), addr(0) {};
77   Variable(AbsRegion r) : reg(r), addr(0) {};
78   Variable(AbsRegion r, Address a) : reg(r), addr(a) {};
79
80   bool operator==(const Variable &rhs) const { 
81     return ((rhs.addr == addr) && (rhs.reg == reg));
82   }
83
84   bool operator<(const Variable &rhs) const { 
85     if (addr < rhs.addr) return true;
86     if (reg < rhs.reg) return true;
87     return false;
88   }
89
90   const std::string format() const {
91     std::stringstream ret;
92     ret << reg;
93     if (addr) ret << ":" << std::hex << addr << std::dec;
94     return ret.str();
95   }
96
97   AbsRegion reg;
98   Address addr;
99 };
100
101 struct Constant {
102   Constant() : val(0), size(0) {};
103   Constant(uint64_t v) : val(v), size(0) {};
104   Constant(uint64_t v, size_t s) : val(v), size(s) {};
105
106 bool operator==(const Constant &rhs) const {
107     return ((rhs.val == val) && (rhs.size == size));
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 SymbolicEvaluation {
291
292 typedef std::map<Assignment::Ptr, AST::Ptr> Result_t;
293     
294 DEF_AST_LEAF_TYPE(BottomAST, bool);
295 DEF_AST_LEAF_TYPE(ConstantAST, Constant);
296 DEF_AST_LEAF_TYPE(VariableAST, Variable);
297 DEF_AST_INTERNAL_TYPE(RoseAST, ROSEOperation);
298
299 class SymEvalPolicy;
300
301 template <Architecture a>
302 struct SymEvalArchTraits
303 {
304     typedef unsigned int InstructionKind_t;
305     static SgAsmExpression* convertOperand(InstructionKind_t opcode,
306                                            unsigned int which,
307                                            SgAsmExpression* expr);
308     static unsigned int convert(entryID) { return 0; }
309 };
310
311
312 struct ConversionArchTraitsBase
313 {
314     virtual SgAsmExpression* archSpecificRegisterProc(InstructionAPI::RegisterAST* regast) = 0;
315     virtual SgAsmExpression* makeSegRegExpr() = 0;
316     virtual ~ConversionArchTraitsBase() {}
317 };
318
319 template <Architecture a>
320         struct ConversionArchTraits : public ConversionArchTraitsBase
321 {
322     virtual SgAsmExpression* archSpecificRegisterProc(InstructionAPI::RegisterAST* regast)
323     {
324         return NULL;
325     }
326     virtual SgAsmExpression* makeSegRegExpr()
327     {
328         return NULL;
329     }
330     virtual ~ConversionArchTraits() {}
331     typedef SgAsmPowerpcRegisterReferenceExpression regRef;
332     typedef PowerpcRegisterClass regClass;
333     typedef PowerpcConditionRegisterAccessGranularity regField;
334 };
335             
336 template <>
337         struct ConversionArchTraits<Arch_x86> : public ConversionArchTraitsBase
338 {
339     virtual SgAsmExpression* archSpecificRegisterProc(InstructionAPI::RegisterAST* regast);
340     virtual SgAsmExpression* makeSegRegExpr();
341     typedef SgAsmx86RegisterReferenceExpression regRef;
342     typedef X86RegisterClass regClass;
343     typedef X86PositionInRegister regField;
344     virtual ~ConversionArchTraits<Arch_x86>() {}
345 };
346             
347 template <>
348         struct ConversionArchTraits<Arch_ppc32> : public ConversionArchTraitsBase
349 {
350     virtual SgAsmExpression* archSpecificRegisterProc(InstructionAPI::RegisterAST* regast);
351     virtual SgAsmExpression* makeSegRegExpr()
352     {
353         return NULL;
354     }
355     virtual ~ConversionArchTraits<Arch_ppc32>() {}
356     typedef SgAsmPowerpcRegisterReferenceExpression regRef;
357     typedef PowerpcRegisterClass regClass;
358     typedef PowerpcConditionRegisterAccessGranularity regField;
359
360 };
361
362 template <Architecture a = Arch_x86>
363         class ExpressionConversionVisitor : public InstructionAPI::Visitor, public ConversionArchTraits<a>
364 {
365     public:
366         typedef typename ConversionArchTraits<a>::regRef regRef;
367         typedef typename ConversionArchTraits<a>::regClass regClass;
368         typedef typename ConversionArchTraits<a>::regClass regField;
369         ExpressionConversionVisitor() { roseExpression = NULL; }
370
371         SgAsmExpression *getRoseExpression() { return roseExpression; }
372
373         virtual void visit(InstructionAPI::BinaryFunction *binfunc);
374         virtual void visit(InstructionAPI::Immediate *immed);
375         virtual void visit(InstructionAPI::RegisterAST *regast);
376         virtual void visit(InstructionAPI::Dereference *deref);
377
378     private:
379         SgAsmExpression *roseExpression;
380         std::list<SgAsmExpression*> m_stack;
381 };
382
383
384
385 template <>
386 struct SymEvalArchTraits<Arch_x86>
387 {
388     typedef SgAsmx86Instruction SageInstruction_t;
389     typedef X86InstructionKind InstructionKind_t;
390     typedef X86GeneralPurposeRegister GPR_t;
391     typedef ExpressionConversionVisitor<Arch_x86> Visitor_t;
392     static SgAsmExpression* convertOperand(InstructionKind_t opcode,
393                                            unsigned int which,
394                                            SgAsmExpression* expr);
395     static bool handleSpecialCases(entryID , SageInstruction_t& ,
396                                    SgAsmOperandList* ) {
397                                        return false;
398                                    }
399     static void handleSpecialCases(InstructionAPI::Instruction::Ptr,
400                                     std::vector<InstructionAPI::Operand>&) {
401         return;
402     }
403
404     static InstructionKind_t convert(entryID e, std::string);
405     static void processInstruction(SageInstruction_t* insn, SymEvalPolicy& policy);
406 };
407 template <>
408 struct SymEvalArchTraits<Arch_ppc32>
409 {
410     typedef SgAsmPowerpcInstruction SageInstruction_t;
411     typedef PowerpcInstructionKind InstructionKind_t;
412     typedef unsigned int GPR_t;
413     typedef ExpressionConversionVisitor<Arch_ppc32> Visitor_t;
414     static SgAsmExpression* convertOperand(InstructionKind_t opcode,
415                                            unsigned int which,
416                                            SgAsmExpression* expr);
417     static bool handleSpecialCases(entryID iapi_opcode, SageInstruction_t& rose_insn,
418                                    SgAsmOperandList* rose_operands);
419     static void handleSpecialCases(InstructionAPI::Instruction::Ptr insn, std::vector<InstructionAPI::Operand>& operands);
420     static InstructionKind_t convert(entryID e, std::string mnem);
421     static void processInstruction(SageInstruction_t* insn, SymEvalPolicy& policy);
422 };
423
424
425 template <Architecture a = Arch_x86>
426 class SymEval : public SymEvalArchTraits<a> {
427 public:
428     typedef typename SymEvalArchTraits<a>::SageInstruction_t SageInstruction_t;
429     typedef typename SymEvalArchTraits<a>::InstructionKind_t InstructionKind_t;
430     typedef typename SymEvalArchTraits<a>::Visitor_t Visitor_t;
431     typedef typename SymEvalArchTraits<a>::GPR_t GPR_t;
432     typedef std::map<Assignment::Ptr, AST::Ptr> Result_t;
433 public:
434   // Return type: mapping AbsRegions to ASTs
435   // We then can map Assignment::AbsRegions to 
436   // SymEval::AbsRegions and come up with the answer
437   static const AST::Ptr Placeholder;
438   
439   // Single version: hand in an Assignment, get an AST
440   static AST::Ptr expand(const Assignment::Ptr &assignment);
441
442   // Hand in a set of Assignments
443   // get back a map of Assignments->ASTs
444   // We assume the assignments are prepped in the input; whatever
445   // they point to is discarded.
446   static void expand(Result_t &res);
447
448   // Hand in a Graph (of AssignNodes, natch) and get back a Result;
449   // prior results from the Graph
450   // are substituted into anything that uses them.
451   static void expand(Graph::Ptr slice, Result_t &res);
452   
453  private:
454   static void process(AssignNode::Ptr, SymEval::Result_t &res);
455
456   static SageInstruction_t convert(const InstructionAPI::Instruction::Ptr &insn, uint64_t addr);
457   static InstructionKind_t convert(entryID opcode, std::string mnem)
458   {
459       return SymEvalArchTraits<a>::convert(opcode,mnem);
460   }
461   static SgAsmExpression *convert(const InstructionAPI::Operand &operand);
462   static SgAsmExpression *convert(const InstructionAPI::Expression::Ptr expression);
463
464   // Symbolically evaluate an instruction and assign 
465   // an AST representation to every written absloc
466   static void expandInsn(const InstructionAPI::Instruction::Ptr insn,
467                          const uint64_t addr,
468                          Result_t& res);
469   
470   friend class ExpressionConversionVisitor<a>;
471 };
472
473 };
474 };
475
476 #endif