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