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