Missed line from patch in last commit.
[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     expandInsn(ptr->insn(),
84                ptr->addr(),
85                res);
86   }
87
88   if (applyVisitors) {
89     // Must apply the visitor to each filled in element
90     for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
91       if (!i->second) continue;
92       AST::Ptr tmp = simplifyStack(i->second, i->first->addr(), i->first->func());
93       i->second = tmp;
94     }
95   }
96 }
97
98 void dfs(Node::Ptr source, Node::Ptr node,
99         set<Node::Ptr> & dfs_nodes,
100         map<Node::Ptr, unsigned> & cycles) {
101     // If we've already encountered this node, we've found a loop!
102     // Mark as a circularity and break
103     if (dfs_nodes.find(node) != dfs_nodes.end()) {
104         expand_cerr << "Found cycle at " << node->format()
105             << ", marking node as not for substitution" << endl;
106
107         AssignNode::Ptr in = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(source);
108         Assignment::Ptr assign = in->assign();
109         AssignNode::Ptr cur_node = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(node);
110         
111         unsigned index = cur_node->getAssignmentIndex(in);
112         cycles.insert(make_pair(node, index));
113         return;
114     } else {
115         dfs_nodes.insert(node);
116     }   
117
118     // Continue DFS by following out-edges
119     NodeIterator gbegin, gend;
120     node->outs(gbegin, gend);
121     for (; gbegin != gend; ++gbegin) {
122         dfs(node, *gbegin, dfs_nodes, cycles);
123     }
124 }
125
126 // Do the previous, but use a Graph as a guide for
127 // performing forward substitution on the AST results
128 void SymEval::expand(Graph::Ptr slice, Result_t &res) {
129     //cout << "Calling expand" << endl;
130     // Other than the substitution this is pretty similar to the first example.
131     NodeIterator gbegin, gend;
132     slice->entryNodes(gbegin, gend);
133
134     std::queue<Node::Ptr> worklist;
135     std::queue<Node::Ptr> dfs_worklist;
136     for (; gbegin != gend; ++gbegin) {
137       expand_cerr << "adding " << (*gbegin)->format() << " to worklist" << endl;
138       worklist.push(*gbegin);
139       dfs_worklist.push(*gbegin);
140     }
141
142     /* First, we'll do DFS to check for circularities in the graph;
143      * if so, mark them so we don't do infinite substitution */
144     set<Node::Ptr> dfs_nodes;
145     map<Node::Ptr, unsigned> cycles;
146     while (!dfs_worklist.empty()) {
147         Node::Ptr ptr = dfs_worklist.front(); dfs_worklist.pop();
148
149         NodeIterator nbegin, nend;
150         ptr->outs(nbegin, nend);
151
152         for (; nbegin != nend; ++nbegin) {
153             dfs(ptr, *nbegin, dfs_nodes, cycles);
154         }
155     }
156
157     /* have a list
158      * for each node, process
159      * if processessing succeeded, remove the element
160      * if the size of the list has changed, continue */
161
162     while (!worklist.empty()) {
163       Node::Ptr ptr = worklist.front(); worklist.pop();
164       AssignNode::Ptr aNode = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(ptr);
165       if (!aNode) continue; // They need to be AssignNodes
166       
167       if (!aNode->assign()) continue; // Could be a widen point
168       
169       expand_cerr << "Visiting node " << aNode->assign()->format() << endl;
170
171       AST::Ptr prev = res[aNode->assign()];
172       
173       process(aNode, res, cycles); 
174     
175       AST::Ptr post = res[aNode->assign()];
176
177       if (post && !(post->equals(prev))) {
178         // Oy
179         expand_cerr << "Adding successors to list, as new expansion " << endl
180                     << "\t" << post->format() << endl 
181                     << " != " << endl
182                     << "\t" << (prev ? prev->format() : "<NULL>") << endl;
183         NodeIterator oB, oE;
184         aNode->outs(oB, oE);
185         for (; oB != oE; ++oB) {
186           worklist.push(*oB);
187         }
188       }
189     }
190 }
191
192 void SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
193                          const uint64_t addr,
194                          Result_t &res) {
195
196   SymEvalPolicy policy(res, addr, insn->getArch());
197
198   SgAsmInstruction *roseInsn;
199   switch(insn->getArch()) {
200   case Arch_x86:  {
201     RoseInsnX86Factory fac;
202     roseInsn = fac.convert(insn, addr);
203     
204     SymbolicExpansion exp;
205     exp.expandX86(roseInsn, policy);
206     break;
207   }
208   case Arch_ppc32: {
209     RoseInsnPPCFactory fac;
210     roseInsn = fac.convert(insn, addr);
211
212     SymbolicExpansion exp;
213     exp.expandPPC(roseInsn, policy);
214     break;
215   }
216   default:
217     assert(0 && "Unimplemented symbolic expansion architecture");
218     break;
219   }
220   return;
221 }
222
223
224 bool SymEval::process(AssignNode::Ptr ptr,
225                       Result_t &dbase,
226                       map<Node::Ptr, unsigned> & cycles) {
227     bool ret = false;
228     
229     std::map<unsigned, Assignment::Ptr> inputMap;
230
231     expand_cerr << "Calling process on " << ptr->format() << endl;
232
233     // Don't try an expansion of a widen node...
234     if (!ptr->assign()) return ret;
235
236     NodeIterator begin, end;
237     ptr->ins(begin, end);
238
239     for (; begin != end; ++begin) {
240         AssignNode::Ptr in = dyn_detail::boost::dynamic_pointer_cast<AssignNode>(*begin);
241         if (!in) continue;
242
243         Assignment::Ptr assign = in->assign();
244
245         if (!assign) continue;
246
247         // Find which input this assignNode maps to
248         unsigned index = ptr->getAssignmentIndex(in);
249         expand_cerr << "Assigning input " << index << " from assignment " << assign->format() << endl;
250         if (inputMap.find(index) == inputMap.end()) {
251             inputMap[index] = assign;
252         }
253         else {
254             // Need join operator!
255             expand_cerr << "\t Overlap in inputs, setting to null assignment pointer" << endl;
256             inputMap[index] = Assignment::Ptr(); // Null equivalent
257         }
258     }
259
260     expand_cerr << "\t Input map has size " << inputMap.size() << endl;
261
262     // All of the expanded inputs are in the parameter dbase
263     // If not (like this one), add it
264
265     AST::Ptr ast = SymEval::expand(ptr->assign());
266     //expand_cerr << "\t ... resulting in " << dbase.format() << endl;
267
268     // We have an AST. Now substitute in all of its predecessors.
269     for (std::map<unsigned, Assignment::Ptr>::iterator iter = inputMap.begin();
270             iter != inputMap.end(); ++iter) {
271         if (!iter->second) {
272             // Colliding definitions; skip.
273             //cerr << "Skipping subsitution for input " << iter->first << endl;
274             continue;
275         }
276         expand_cerr << "Substituting input " << iter->first << " with assignment " << iter->second->format() << endl;
277         // The region used by the current assignment...
278         const AbsRegion &reg = ptr->assign()->inputs()[iter->first];
279
280         // Create an AST around this one
281         VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
282
283         // And substitute whatever we have in the database for that AST
284         AST::Ptr definition = dbase[iter->second];
285
286         if (!definition) {
287             // Can happen if we're expanding out of order, and is generally harmless.
288             continue;
289         }
290
291         expand_cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
292
293         if (!ast) {
294             expand_cerr << "Skipping substitution because of null AST" << endl;
295         } else {
296             // Check if we have a circular dependency here; if yes, don't substitute
297             map<Node::Ptr, unsigned>::iterator cit;
298             cit = cycles.find(ptr);
299             if (cit != cycles.end()) {
300                 if (cit->second == iter->first) {
301                     expand_cerr << "Found in-edge that's a cycle, skipping substitution" << endl;
302                     break;
303                 }
304             }
305
306             ast = AST::substitute(ast, use, definition);
307             ret = true;
308         }       
309         //expand_cerr << "\t result is " << res->format() << endl;
310     }
311     expand_cerr << "Result of substitution: " << ptr->assign()->format() << " == " << (ast ? ast->format() : "<NULL AST>") << endl;
312
313     // And attempt simplification again
314     ast = simplifyStack(ast, ptr->addr(), ptr->func());
315     expand_cerr << "Result of post-substitution simplification: " << ptr->assign()->format() << " == " 
316                 << (ast ? ast->format() : "<NULL AST>") << endl;
317     
318     dbase[ptr->assign()] = ast;
319     return ret;
320 }
321
322 AST::Ptr SymEval::simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func) {
323   if (!ast) return ast;
324   // Let's experiment with simplification
325   StackAnalysis sA(func);
326   StackAnalysis::Height sp = sA.findSP(addr);
327   StackAnalysis::Height fp = sA.findFP(addr);
328   
329   StackVisitor sv(addr, func, sp, fp);
330
331   AST::Ptr simplified = ast->accept(&sv);
332
333   return simplified;
334 }