Merge branch 'master' into devel
[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 #include <iostream>
34
35 #include "../h/SymEval.h"
36 #include "SymEvalPolicy.h"
37
38 #include "AST.h"
39
40 #include "parseAPI/h/CFG.h"
41
42 #include "../rose/x86InstructionSemantics.h"
43 #include "../rose/powerpcInstructionSemantics.h"
44 #include "../rose/SgAsmInstruction.h"
45 #include "../h/stackanalysis.h"
46 #include "SymEvalVisitors.h"
47
48 #include "RoseInsnFactory.h"
49 #include "SymbolicExpansion.h"
50
51 #include "../h/Absloc.h"
52
53 #include "../h/slicing.h" // AssignNode
54
55 using namespace Dyninst;
56 using namespace InstructionAPI;
57 using namespace SymbolicEvaluation;
58
59
60 AST::Ptr SymEval::expand(const Assignment::Ptr &assignment) {
61   // This is a shortcut version for when we only want a
62   // single assignment
63   
64   Result_t res;
65   // Fill it in to mark it as existing
66   res[assignment] = AST::Ptr();
67   expand(res);
68   return res[assignment];
69 }
70
71 void SymEval::expand(Result_t &res, bool applyVisitors) {
72   // Symbolic evaluation works off an Instruction
73   // so we have something to hand to ROSE. 
74   for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
75     if (i->second != AST::Ptr()) {
76       // Must've already filled it in from a previous instruction crack
77       continue;
78     }
79     Assignment::Ptr ptr = i->first;
80     
81     //cerr << "Expand called for insn " << ptr->insn()->format() << endl;
82     
83     expandInsn(ptr->insn(),
84                ptr->addr(),
85                res);
86     
87   }
88
89   if (applyVisitors) {
90     // Must apply the visitor to each filled in element
91     for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
92       if (i->second == AST::Ptr()) {
93         // Must not have been filled in above
94         continue;
95       }
96       Assignment::Ptr ptr = i->first;
97
98       // Let's experiment with simplification
99       StackAnalysis sA(ptr->func());
100       StackAnalysis::Height sp = sA.findSP(ptr->addr());
101       StackAnalysis::Height fp = sA.findFP(ptr->addr());
102
103       StackVisitor sv(ptr->addr(), ptr->func()->name(), sp, fp);
104       if (i->second)
105         i->second = i->second->accept(&sv);
106     }
107   }
108 }
109
110 // Do the previous, but use a Graph as a guide for
111 // performing forward substitution on the AST results
112 void SymEval::expand(Graph::Ptr slice, Result_t &res) {
113     //cout << "Calling expand" << endl;
114   // Other than the substitution this is pretty similar to the first example.
115   NodeIterator gbegin, gend;
116   slice->entryNodes(gbegin, gend);
117
118   std::queue<Node::Ptr> worklist;
119   for (; gbegin != gend; ++gbegin) {
120       //cout << "adding " << (*gbegin)->format() << " to worklist" << endl;
121     worklist.push(*gbegin);
122   }
123   std::set<Node::Ptr> visited;
124
125   while (!worklist.empty()) {
126     Node::Ptr ptr = worklist.front(); worklist.pop();
127     AssignNode::Ptr aNode = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(ptr);
128     if (!aNode) continue; // They need to be AssignNodes
129
130     if (!aNode->assign()) continue; // Could be a widen point
131
132     //cerr << "Visiting node " << aNode->assign()->format() << endl;
133     if (visited.find(ptr) != visited.end()) continue;
134     visited.insert(ptr);
135
136     process(aNode, res);
137
138     NodeIterator nbegin, nend;
139     aNode->outs(nbegin, nend);
140     for (; nbegin != nend; ++nbegin) {
141       AssignNode::Ptr target = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(*nbegin);
142       if (!target) continue;
143       if (!target->assign()) continue;
144       //cerr << "\t Pushing successors " << aNode->assign()->format() << endl;
145       worklist.push(*nbegin);
146     }
147   }
148 }
149
150 void SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
151                          const uint64_t addr,
152                          Result_t &res) {
153
154   SymEvalPolicy policy(res, addr, insn->getArch());
155
156   SgAsmInstruction *roseInsn;
157   switch(insn->getArch()) {
158   case Arch_x86:  {
159     RoseInsnX86Factory fac;
160     roseInsn = fac.convert(insn, addr);
161     
162     SymbolicExpansion exp;
163     exp.expandX86(roseInsn, policy);
164     break;
165   }
166   case Arch_ppc32: {
167     RoseInsnPPCFactory fac;
168     roseInsn = fac.convert(insn, addr);
169
170     SymbolicExpansion exp;
171     exp.expandPPC(roseInsn, policy);
172     break;
173   }
174   default:
175     assert(0 && "Unimplemented symbolic expansion architecture");
176     break;
177   }
178   return;
179 }
180
181
182 void SymEval::process(AssignNode::Ptr ptr,
183                          Result_t &dbase) {
184   std::map<unsigned, Assignment::Ptr> inputMap;
185
186   //cerr << "Calling process on " << ptr->format() << endl;
187
188   // Don't try an expansion of a widen node...
189   if (!ptr->assign()) return;
190
191   NodeIterator begin, end;
192   ptr->ins(begin, end);
193   
194   for (; begin != end; ++begin) {
195     AssignNode::Ptr in = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(*begin);
196     if (!in) continue;
197
198     Assignment::Ptr assign = in->assign();
199
200     if (!assign) continue;
201
202     // Find which input this assignNode maps to
203     unsigned index = ptr->getAssignmentIndex(in);
204     //cerr << "Assigning input " << index << " from assignment " << assign->format() << endl;
205     if (inputMap.find(index) == inputMap.end()) {
206       inputMap[index] = assign;
207     }
208     else {
209       // Need join operator!
210       //cerr << "\t Overlap in inputs, setting to null assignment pointer" << endl;
211       inputMap[index] = Assignment::Ptr(); // Null equivalent
212     }
213   }
214
215   //cerr << "\t Input map has size " << inputMap.size() << endl;
216
217   // All of the expanded inputs are in the parameter dbase
218   // If not (like this one), add it
219
220   AST::Ptr ast = SymEval::expand(ptr->assign());
221   //cerr << "\t ... resulting in " << dbase.format() << endl;
222   
223   // We have an AST. Now substitute in all of its predecessors.
224   for (std::map<unsigned, Assignment::Ptr>::iterator iter = inputMap.begin();
225        iter != inputMap.end(); ++iter) {
226     if (!iter->second) {
227       // Colliding definitions; skip.
228       //cerr << "Skipping subsitution for input " << iter->first << endl;
229       continue;
230     }
231     //cerr << "Substituting input " << iter->first << endl;
232     // The region used by the current assignment...
233     const AbsRegion &reg = ptr->assign()->inputs()[iter->first];
234
235     // Create an AST around this one
236     VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
237
238     // And substitute whatever we have in the database for that AST
239     AST::Ptr definition = dbase[iter->second];
240
241     if (!definition) {
242       //cerr << "Odd; no expansion for " << iter->second->format() << endl;
243       // Can happen if we're expanding out of order, and is generally harmless.
244       continue;
245     }
246
247     //cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
248
249     ast = AST::substitute(ast, use, definition);
250     //cerr << "\t result is " << res->format() << endl;
251     }
252   //cerr << "Result of subsitution: " << ptr->assign()->format() << " == " << (ast ? ast->format() : "<NULL AST>") << endl;
253   dbase[ptr->assign()] = ast;
254 }
255