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