ppc fixes
[dyninst.git] / dataflowAPI / h / SymEval.h
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 // Stubs for now
32
33 #if !defined(SymEval_h)
34 #define SymEval_h
35
36 #include <map>
37
38 #include "Absloc.h"
39 #include "DynAST.h"
40
41 #include "Graph.h"
42 #include "util.h"
43 #include "Node.h"
44 #include "Edge.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
55    namespace ParseAPI {
56       class Function;
57       class Block;
58    };
59
60 namespace DataflowAPI {
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   DATAFLOW_EXPORT Variable() : reg(), addr(0) {};
77   DATAFLOW_EXPORT Variable(AbsRegion r) : reg(r), addr(0) {};
78   DATAFLOW_EXPORT Variable(AbsRegion r, Address a) : reg(r), addr(a) {};
79
80   DATAFLOW_EXPORT bool operator==(const Variable &rhs) const { 
81     return ((rhs.addr == addr) && (rhs.reg == reg));
82   }
83
84   DATAFLOW_EXPORT 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   DATAFLOW_EXPORT const std::string format() const {
91     std::stringstream ret;
92     ret << "V(" << reg;
93     if (addr) ret << ":" << std::hex << addr << std::dec;
94     ret << ")";
95     return ret.str();
96   }
97
98    AbsRegion reg;
99    Address addr;
100 };
101
102 struct Constant {
103   DATAFLOW_EXPORT Constant() : val(0), size(0) {};
104   DATAFLOW_EXPORT Constant(uint64_t v) : val(v), size(0) {};
105   DATAFLOW_EXPORT Constant(uint64_t v, size_t s) : val(v), size(s) {};
106
107  DATAFLOW_EXPORT  bool operator==(const Constant &rhs) const {
108     return ((rhs.val == val) && (rhs.size == size));
109   }
110
111   DATAFLOW_EXPORT bool operator<(const Constant &rhs) const {
112     if (val < rhs.val) return true;
113     if (size < rhs.size) return true;
114     return false;
115   }
116
117   DATAFLOW_EXPORT const std::string format() const {
118     std::stringstream ret;
119     ret << val;
120     if (size) {
121     ret << ":" << size;
122     }
123     return ret.str();
124   }
125   
126    uint64_t val;
127    size_t size;
128 };
129
130 // Define the operations used by ROSE
131
132 struct ROSEOperation {
133 typedef enum {
134     nullOp,
135     extractOp,
136     invertOp,
137     negateOp,
138     signExtendOp,
139     equalToZeroOp,
140     generateMaskOp,
141     LSBSetOp,
142     MSBSetOp,
143     concatOp,
144     andOp,
145     orOp,
146     xorOp,
147     addOp,
148     rotateLOp,
149     rotateROp,
150     shiftLOp,
151     shiftROp,
152     shiftRArithOp,
153     derefOp,
154     writeRepOp,
155     writeOp,
156     ifOp,
157     sMultOp,
158     uMultOp,
159     sDivOp,
160     sModOp,
161     uDivOp,
162     uModOp,
163     extendOp,
164     extendMSBOp
165 } Op;
166
167 DATAFLOW_EXPORT ROSEOperation(Op o) : op(o), size(0) {};
168 DATAFLOW_EXPORT ROSEOperation(Op o, size_t s) : op(o), size(s) {};
169
170 DATAFLOW_EXPORT bool operator==(const ROSEOperation &rhs) const {
171     return ((rhs.op == op) && (rhs.size == size));
172 }
173
174 DATAFLOW_EXPORT const std::string format() const {
175     std::stringstream ret;
176     ret << "<";
177     switch(op) {
178     case nullOp:
179     ret << "null";
180     break;
181     case extractOp:
182     ret << "extract";
183     break;
184     case invertOp:
185     ret << "invert";
186     break;
187     case negateOp:
188     ret << "negate";
189     break;
190     case signExtendOp:
191     ret << "signExtend";
192     break;
193     case equalToZeroOp:
194     ret << "eqZero?";
195     break;
196     case generateMaskOp:
197     ret << "genMask";
198     break;
199     case LSBSetOp:
200     ret << "LSB?";
201     break;
202     case MSBSetOp:
203     ret << "MSB?";
204     break;
205     case concatOp:
206     ret << "concat";
207     break;
208     case andOp:
209     ret << "and";
210     break;
211     case orOp:
212     ret << "or";
213     break;
214     case xorOp:
215     ret << "xor";
216     break;
217     case addOp:
218     ret << "add";
219     break;
220     case rotateLOp:
221     ret << "rotL";
222     break;
223     case rotateROp:
224     ret << "rotR";
225     break;
226     case shiftLOp:
227     ret << "shl";
228     break;
229     case shiftROp:
230     ret << "shr";
231     break;
232     case shiftRArithOp:
233     ret << "shrA";
234     break;
235     case derefOp:
236     ret << "deref";
237     break;
238     case writeRepOp:
239     ret << "writeRep";
240     break;
241     case writeOp:
242     ret << "write";
243     break;
244     case ifOp:
245     ret << "if";
246     break;
247     case sMultOp:
248     ret << "sMult";
249     break;
250     case uMultOp:
251     ret << "uMult";
252     break;
253     case sDivOp:
254     ret << "sDiv";
255     break;
256     case sModOp:
257     ret << "sMod";
258     break;
259     case uDivOp:
260     ret << "uDiv";
261     break;
262     case uModOp:
263     ret << "uMod";
264     break;
265     case extendOp:
266     ret << "ext";
267     break;
268     case extendMSBOp:
269     ret << "extMSB";
270     break;
271     default:
272     ret << " ??? ";
273     break;
274     };
275     if (size) {
276     ret << ":" << size;
277     }
278     ret << ">";
279     return ret.str();
280 };
281
282 Op op;
283 size_t size;
284 };
285
286 };
287
288 };
289
290 // Get this out of the Dyninst namespace...
291 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os, const Dyninst::DataflowAPI::ROSEOperation &o);
292 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os, const Dyninst::DataflowAPI::Constant &o);
293 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os, const Dyninst::DataflowAPI::Variable &o);
294
295 namespace Dyninst {
296
297 namespace InstructionAPI {
298   class Instruction;
299 }
300
301 class SliceNode;
302
303 namespace DataflowAPI {
304
305 typedef std::map<Assignment::Ptr, AST::Ptr> Result_t;
306     
307 DEF_AST_LEAF_TYPE(BottomAST, bool);
308 DEF_AST_LEAF_TYPE(ConstantAST, Constant);
309 DEF_AST_LEAF_TYPE(VariableAST, Variable);
310 DEF_AST_INTERNAL_TYPE(RoseAST, ROSEOperation);
311
312 class SymEvalPolicy;
313
314 class  SymEval {
315 public:
316     typedef boost::shared_ptr<SliceNode> SliceNodePtr;
317     typedef boost::shared_ptr<InstructionAPI::Instruction> InstructionPtr;
318 public:
319   typedef enum {
320      FAILED,
321      WIDEN_NODE,
322      FAILED_TRANSLATION,
323      SKIPPED_INPUT,
324      SUCCESS } Retval_t;
325
326   // Return type: mapping AbsRegions to ASTs
327   // We then can map Assignment::AbsRegions to 
328   // SymEval::AbsRegions and come up with the answer
329   // static const AST::Ptr Placeholder;
330   //
331   // Single version: hand in an Assignment, get an AST
332     DATAFLOW_EXPORT static std::pair<AST::Ptr, bool> expand(const Assignment::Ptr &assignment);
333
334   // Hand in a set of Assignments
335   // get back a map of Assignments->ASTs
336   // We assume the assignments are prepped in the input; whatever
337   // they point to is discarded.
338   DATAFLOW_EXPORT static bool expand(Result_t &res, 
339                                      std::set<InstructionPtr> &failedInsns,
340                                      bool applyVisitors = true);
341
342   // Hand in a Graph (of SliceNodes, natch) and get back a Result;
343   // prior results from the Graph
344   // are substituted into anything that uses them.
345   DATAFLOW_EXPORT static Retval_t expand(Dyninst::Graph::Ptr slice, DataflowAPI::Result_t &res);
346   
347  private:
348
349   // Symbolically evaluate an instruction and assign 
350   // an AST representation to every written absloc
351  static bool expandInsn(const InstructionPtr insn,
352                          const uint64_t addr,
353                          Result_t& res);
354
355  static Retval_t process(SliceNodePtr ptr, Result_t &dbase, std::set<Edge::Ptr> &skipEdges);
356   
357  static AST::Ptr simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func, ParseAPI::Block *block);
358 };
359
360 };
361 };
362
363 #endif