More conversion overrides for IAPI->ROSE conversions
[dyninst.git] / symEval / src / SymEval.C
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 #include <string>
33
34 #include "../h/SymEval.h"
35 #include "SymEvalPolicy.h"
36
37 #include "AST.h"
38
39 #include "../rose/x86InstructionSemantics.h"
40
41 #include "dyninstAPI/src/stackanalysis.h"
42 #include "SymEvalVisitors.h"
43
44 using namespace Dyninst;
45 using namespace Dyninst::InstructionAPI;
46 using namespace Dyninst::SymbolicEvaluation;
47
48 const AST::Ptr SymEval::Placeholder;
49
50 AST::Ptr SymEval::expand(const Assignment::Ptr &assignment) {
51   // This is a shortcut version for when we only want a 
52   // single assignment
53
54   SymEval::Result res;
55   // Fill it in to mark it as existing
56   res[assignment] = Placeholder;
57   expand(res);
58   return res[assignment];
59 }
60
61 void SymEval::expand(Result &res) {
62   // Symbolic evaluation works off an Instruction
63   // so we have something to hand to ROSE. 
64   for (Result::iterator i = res.begin(); i != res.end(); ++i) {
65     if (i->second != Placeholder) {
66       // Must've already filled it in from a previous instruction crack
67       continue;
68     }
69     Assignment::Ptr ptr = i->first;
70
71     expandInsn(ptr->insn(),
72                ptr->addr(),
73                res);
74
75   }
76
77   // Must apply the visitor to each filled in element
78   for (Result::iterator i = res.begin(); i != res.end(); ++i) {
79     if (i->second == Placeholder) {
80       // Must not have been filled in above
81       continue;
82     }
83     Assignment::Ptr ptr = i->first;
84
85     // Let's experiment with simplification
86     image_func *func = ptr->func();
87     StackAnalysis sA(func);
88     StackAnalysis::Height sp = sA.findSP(ptr->addr());
89     StackAnalysis::Height fp = sA.findFP(ptr->addr());
90     
91     StackVisitor sv(ptr->addr(), func->symTabName(), sp, fp);
92     if (i->second)
93       i->second = i->second->accept(&sv);
94   }
95 }
96
97 // Do the previous, but use a Graph as a guide for
98 // performing forward substitution on the AST results
99 void SymEval::expand(Graph::Ptr slice, Result &res) {
100   // Other than the substitution this is pretty similar to the first example.
101   NodeIterator gbegin, gend;
102   slice->entryNodes(gbegin, gend);
103   
104   std::queue<Node::Ptr> worklist;
105   for (; gbegin != gend; ++gbegin) {
106     worklist.push(*gbegin);
107   }
108   std::set<Node::Ptr> visited;
109   
110   while (!worklist.empty()) {
111     Node::Ptr ptr = worklist.front(); worklist.pop();
112     AssignNode::Ptr aNode = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(ptr);
113     if (!aNode) continue; // They need to be AssignNodes
114
115     if (!aNode->assign()) continue; // Could be a widen point
116
117     //cerr << "Visiting node " << ass->assign()->format() << endl;
118     if (visited.find(ptr) != visited.end()) continue;
119     visited.insert(ptr);
120
121     process(aNode, res);
122     
123     NodeIterator nbegin, nend;
124     aNode->outs(nbegin, nend);
125     for (; nbegin != nend; ++nbegin) {
126       AssignNode::Ptr target = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(*nbegin);
127       if (!target) continue;
128       if (!target->assign()) continue;
129       //cerr << "\t Pushing successors " << ass2->assign()->format() << endl;
130       worklist.push(*nbegin);
131     }
132   }
133 }
134
135
136 void SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
137                          const uint64_t addr,
138                          Result &res) {
139   SgAsmx86Instruction roseInsn = convert(insn, addr);
140   SymEvalPolicy policy(res, addr, insn->getArch());
141   X86InstructionSemantics<SymEvalPolicy, Handle> t(policy);
142   t.processInstruction(&roseInsn);
143   return;
144 }
145
146 void SymEval::process(AssignNode::Ptr ptr,
147                       SymEval::Result &dbase) {
148   std::map<unsigned, Assignment::Ptr> inputMap;
149
150   //cerr << "Calling process on " << ptr->format() << endl;
151
152   // Don't try an expansion of a widen node...
153   if (!ptr->assign()) return;
154
155   NodeIterator begin, end;
156   ptr->ins(begin, end);
157   
158   for (; begin != end; ++begin) {
159     AssignNode::Ptr in = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(*begin);
160     if (!in) continue;
161
162     Assignment::Ptr assign = in->assign();
163
164     if (!assign) continue;
165
166     // Find which input this assignNode maps to
167     unsigned index = ptr->getAssignmentIndex(in);
168     if (inputMap.find(index) == inputMap.end()) {
169       inputMap[index] = assign;
170     }
171     else {
172       // Need join operator!
173       inputMap[index] = Assignment::Ptr(); // Null equivalent
174     }
175   }
176
177   //cerr << "\t Input map has size " << inputMap.size() << endl;
178
179   // All of the expanded inputs are in the parameter dbase
180   // If not (like this one), add it
181
182   AST::Ptr ast = SymEval::expand(ptr->assign());
183   //cerr << "\t ... resulting in " << res->format() << endl;
184
185   // We have an AST. Now substitute in all of its predecessors.
186   for (std::map<unsigned, Assignment::Ptr>::iterator iter = inputMap.begin();
187        iter != inputMap.end(); ++iter) {
188     if (!iter->second) {
189       // Colliding definitions; skip.
190       continue;
191     }
192
193     // The region used by the current assignment...
194     const AbsRegion &reg = ptr->assign()->inputs()[iter->first];
195
196     // Create an AST around this one
197     VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
198
199     // And substitute whatever we have in the database for that AST
200     AST::Ptr definition = dbase[iter->second]; 
201
202     if (!definition) {
203       //cerr << "Odd; no expansion for " << iter->second->format() << endl;
204       // Can happen if we're expanding out of order, and is generally harmless.
205       continue;
206     }
207
208     ast = AST::substitute(ast, use, definition);
209     //cerr << "\t result is " << res->format() << endl;
210   }
211   dbase[ptr->assign()] = ast;
212 }
213
214
215 SgAsmx86Instruction SymEval::convert(const InstructionAPI::Instruction::Ptr &insn, uint64_t addr) {
216     SgAsmx86Instruction rinsn;
217
218     rinsn.set_address(addr);
219     rinsn.set_mnemonic(insn->format());
220     rinsn.set_kind(convert(insn->getOperation().getID()));
221     // semantics don't support 64-bit code
222     rinsn.set_operandSize(x86_insnsize_32);
223     rinsn.set_addressSize(x86_insnsize_32);
224
225     std::vector<unsigned char> rawBytes;
226     for (unsigned i = 0; i < insn->size(); ++i) rawBytes.push_back(insn->rawByte(i));
227     rinsn.set_raw_bytes(rawBytes);
228
229     // operand list
230     SgAsmOperandList *roperands = new SgAsmOperandList;
231     std::vector<InstructionAPI::Operand> operands;
232     insn->getOperands(operands);
233
234     switch (rinsn.get_kind()) {
235     case x86_lea: {
236       assert(operands.size() == 2);
237       roperands->append_operand(convert(operands[0]));
238       
239       SgAsmExpression *o1 = convert(operands[1]);
240       // We need to wrap o1 in a memory dereference...
241       SgAsmMemoryReferenceExpression *expr = new SgAsmMemoryReferenceExpression(o1);
242       roperands->append_operand(expr);
243       break;
244     }
245     case x86_push: {
246       assert(operands.size() == 2); 
247       roperands->append_operand(convert(operands[0]));
248       break;
249     }
250     case x86_pop: {
251       assert(operands.size() == 2);
252       roperands->append_operand(convert(operands[0]));
253       break;
254     }
255     case x86_cmpxchg: {
256       assert(operands.size() == 3);
257       roperands->append_operand(convert(operands[0]));
258       roperands->append_operand(convert(operands[1]));
259       break;
260     }
261     case x86_movsb:
262     case x86_movsw:
263     case x86_movsd: {
264       // No operands
265       break;
266     }
267     case x86_repne_cmpsb:
268     case x86_repne_cmpsw:
269     case x86_repne_cmpsd:
270     case x86_repe_cmpsb:
271     case x86_repe_cmpsw:
272     case x86_repe_cmpsd:
273     case x86_cmpsb:
274     case x86_cmpsw:
275     case x86_cmpsd: {
276       // No operands
277       break;
278     }
279     case x86_stosb:
280     case x86_stosw:
281     case x86_stosd: {
282       // Also, no operands
283       break;
284     }
285     case x86_jcxz:
286     case x86_jecxz: {
287       assert(operands.size() == 2); 
288       roperands->append_operand(convert(operands[0]));
289       break;
290     }
291     case x86_cbw:
292     case x86_cwde:
293     case x86_cwd:
294     case x86_cdq: {
295       // Nada
296       break;
297     }
298     default: {
299       for (std::vector<InstructionAPI::Operand>::iterator opi = operands.begin(),
300              ope = operands.end();
301            opi != ope;
302            ++opi) {
303         InstructionAPI::Operand &currOperand = *opi;
304         roperands->append_operand(convert(currOperand));
305       }
306     }
307     }
308     rinsn.set_operandList(roperands);
309
310     return rinsn;
311 }
312
313 SgAsmExpression *SymEval::convert(const InstructionAPI::Operand &operand) {
314     return convert(operand.getValue());
315 }
316
317 SgAsmExpression *SymEval::convert(const Expression::Ptr expression) {
318     ExpressionConversionVisitor visitor;
319     expression->apply(&visitor);
320     return visitor.getRoseExpression();
321 }
322
323 void ExpressionConversionVisitor::visit(BinaryFunction* binfunc) {
324     // get two children
325     vector<InstructionAST::Ptr> children;
326     binfunc->getChildren(children);
327     // convert each InstAST::Ptr to SgAsmExpression*
328     // these casts will not fail
329     SgAsmExpression *lhs = 
330       SymEval::convert(dyn_detail::boost::dynamic_pointer_cast<Expression>(children[0]));
331     SgAsmExpression *rhs =
332       SymEval::convert(dyn_detail::boost::dynamic_pointer_cast<Expression>(children[1]));
333
334     // ROSE doesn't expect us to include the implicit PC update
335     //   along with explicit updates to the PC
336     // If the current function involves the PC, ignore it 
337     //   so the parent makes it disappear
338     RegisterAST::Ptr lhsReg = dyn_detail::boost::dynamic_pointer_cast<RegisterAST>(children[0]);
339     if (lhsReg)
340     {
341       if (lhsReg->getID().isPC())
342       {
343         roseExpression = NULL;
344         return;
345       }
346     }
347     // If the RHS didn't convert, that means it should disappear
348     // And we are just left with the LHS
349     if (!rhs)
350     {
351       roseExpression = lhs;
352       return;
353     }
354
355     // now build either add or multiply
356     if (binfunc->isAdd())
357         roseExpression = new SgAsmBinaryAdd(lhs, rhs);
358     else if (binfunc->isMultiply())
359         roseExpression = new SgAsmBinaryMultiply(lhs, rhs);
360     else roseExpression = NULL; // error
361 }
362
363 void ExpressionConversionVisitor::visit(Immediate* immed) {
364     // no children
365
366     const Result &value = immed->eval();
367     
368     // TODO rose doesn't distinguish signed/unsigned within the value itself,
369     // only at operations?
370
371     // TODO rose doesn't handle large values (XMM?)
372
373     // build different kind of rose value object based on type
374     switch (value.type) {
375         case s8:
376         case u8:
377             roseExpression = new SgAsmByteValueExpression(value.val.u8val);
378             break;
379         case s16:
380         case u16:
381             roseExpression = new SgAsmWordValueExpression(value.val.u16val);
382             break;
383         case s32:
384         case u32:
385             roseExpression = new SgAsmDoubleWordValueExpression(value.val.u32val);
386             break;
387         case s64:
388         case u64:
389             roseExpression = new SgAsmQuadWordValueExpression(value.val.u64val);
390             break;
391         case sp_float:
392             roseExpression = new SgAsmSingleFloatValueExpression(value.val.floatval);
393             break;
394         case dp_float:
395             roseExpression = new SgAsmDoubleFloatValueExpression(value.val.dblval);
396             break;
397         default:
398             roseExpression = NULL;
399             // error!
400     }
401 }
402
403 void ExpressionConversionVisitor::visit(RegisterAST* regast) {
404     // has no children
405
406     int rreg_class;
407     int rreg_num;
408     int rreg_pos;
409
410     MachRegister machReg = regast->getID();
411     machReg.getROSERegister(rreg_class, rreg_num, rreg_pos);
412
413     roseExpression = new SgAsmx86RegisterReferenceExpression((X86RegisterClass)rreg_class, 
414                                                              rreg_num, 
415                                                              (X86PositionInRegister)rreg_pos);
416 }
417
418 void ExpressionConversionVisitor::visit(Dereference* deref) {
419     // get child
420     vector<InstructionAST::Ptr> children;
421     deref->getChildren(children);
422     SgAsmExpression *toderef = 
423       SymEval::convert(dyn_detail::boost::dynamic_pointer_cast<Expression>(children[0]));
424     
425     SgAsmType *type;
426
427     // TODO fix some mismatched types?
428     // pick correct type
429     switch (deref->eval().type)
430     {
431         case s8:
432         case u8:
433             type = new SgAsmTypeByte();
434             break;
435         case s16:
436         case u16:
437             type = new SgAsmTypeWord();
438             break;
439         case s32:
440         case u32:
441             type = new SgAsmTypeDoubleWord();
442             break;
443         case s64:
444         case u64:
445             type = new SgAsmTypeQuadWord();
446             break;
447         case sp_float:
448             type = new SgAsmTypeSingleFloat();
449             break;
450         case dp_float:
451             type = new SgAsmTypeDoubleFloat();
452             break;
453         default:
454             type = NULL;
455             // error
456     }
457
458     SgAsmx86RegisterReferenceExpression *segReg = new SgAsmx86RegisterReferenceExpression(x86_regclass_segment, x86_segreg_none, x86_regpos_all);
459
460     SgAsmMemoryReferenceExpression *result = new SgAsmMemoryReferenceExpression(toderef, segReg);
461     result->set_type(type);
462     roseExpression = result;
463 }
464