Merge branch 'master' into Kevin-Drew
[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" // SliceNode
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,
101          std::map<Node::Ptr, int> &state,
102          std::set<Edge::Ptr> &skipEdges) {
103
104    // DFS from the node given by source
105    // If we meet a node twice without having to backtrack first,
106    // insert that incoming edge into skipEdges.
107    //
108    // A node n has state[n] > 0 if it is on the path currently
109    // being explored. Incrementing and decrementing a counter
110    // for visited nodes (as opposed to setting a "PROGRESS" or "DONE"
111    // flag) avoids a corner case with the first node in the search.
112
113    EdgeIterator b, e;
114    source->outs(b, e);
115
116    // Because this is a non-simple graph---in particular because it has
117    // multiple edges between nodes---one must be careful not to repeatedly
118    // visit nodes to avoid exponential blowup.
119    std::set<Node::Ptr> done;
120
121    for (; b != e; ++b) {
122       Edge::Ptr edge = *b;
123       Node::Ptr cur = edge->target();
124       if (state[cur] > 0) { 
125          skipEdges.insert(edge);
126       }
127       else {
128          if(done.find(cur) != done.end()) {
129             done.insert(cur);
130
131             state[cur]++;
132             dfs(cur, state, skipEdges);
133             state[cur]--;
134         }
135       }
136    }
137 }
138
139 // Do the previous, but use a Graph as a guide for
140 // performing forward substitution on the AST results
141 void SymEval::expand(Graph::Ptr slice, Result_t &res) {
142     //cout << "Calling expand" << endl;
143     // Other than the substitution this is pretty similar to the first example.
144     NodeIterator gbegin, gend;
145     slice->entryNodes(gbegin, gend);
146
147     std::queue<Node::Ptr> worklist;
148     std::queue<Node::Ptr> dfs_worklist;
149     for (; gbegin != gend; ++gbegin) {
150       expand_cerr << "adding " << (*gbegin)->format() << " to worklist" << endl;
151       worklist.push(*gbegin);
152       dfs_worklist.push(*gbegin);
153     }
154
155     /* First, we'll do DFS to check for circularities in the graph;
156      * if so, mark them so we don't do infinite substitution */
157     std::set<Edge::Ptr> skipEdges;
158
159     while (!dfs_worklist.empty()) {
160        Node::Ptr ptr = dfs_worklist.front(); dfs_worklist.pop();
161        std::map<Node::Ptr, int> state;
162        state[ptr] = 1;
163        dfs(ptr, state, skipEdges);
164     }
165     
166     /* have a list
167      * for each node, process
168      * if processessing succeeded, remove the element
169      * if the size of the list has changed, continue */
170
171     while (!worklist.empty()) {
172       Node::Ptr ptr = worklist.front(); worklist.pop();
173       SliceNode::Ptr aNode = dyn_detail::boost::static_pointer_cast<SliceNode>(ptr);
174       if (!aNode) continue; // They need to be SliceNodes
175       
176       if (!aNode->assign()) continue; // Could be a widen point
177       
178       expand_cerr << "Visiting node " << aNode->assign()->format() << endl;
179
180       AST::Ptr prev = res[aNode->assign()];
181       
182       process(aNode, res, skipEdges); 
183     
184       AST::Ptr post = res[aNode->assign()];
185
186       if (post && !(post->equals(prev))) {
187         // Oy
188         expand_cerr << "Adding successors to list, as new expansion " << endl
189                     << "\t" << post->format() << endl 
190                     << " != " << endl
191                     << "\t" << (prev ? prev->format() : "<NULL>") << endl;
192         NodeIterator oB, oE;
193         aNode->outs(oB, oE);
194         for (; oB != oE; ++oB) {
195           worklist.push(*oB);
196         }
197       }
198     }
199 }
200
201 void SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
202                          const uint64_t addr,
203                          Result_t &res) {
204
205   SymEvalPolicy policy(res, addr, insn->getArch());
206
207   SgAsmInstruction *roseInsn;
208   switch(insn->getArch()) {
209   case Arch_x86:  {
210     RoseInsnX86Factory fac;
211     roseInsn = fac.convert(insn, addr);
212     
213     SymbolicExpansion exp;
214     exp.expandX86(roseInsn, policy);
215     break;
216   }
217   case Arch_ppc32: {
218     RoseInsnPPCFactory fac;
219     roseInsn = fac.convert(insn, addr);
220
221     SymbolicExpansion exp;
222     exp.expandPPC(roseInsn, policy);
223     break;
224   }
225   default:
226     assert(0 && "Unimplemented symbolic expansion architecture");
227     break;
228   }
229   return;
230 }
231
232
233 bool SymEval::process(SliceNode::Ptr ptr,
234                       Result_t &dbase,
235                       std::set<Edge::Ptr> &skipEdges) {
236     bool ret = false;
237     
238     std::map<const AbsRegion*, std::set<Assignment::Ptr> > inputMap;
239
240     expand_cerr << "Calling process on " << ptr->format() << endl;
241
242     // Don't try an expansion of a widen node...
243     if (!ptr->assign()) return ret;
244
245     EdgeIterator begin, end;
246     ptr->ins(begin, end);
247
248     for (; begin != end; ++begin) {
249        SliceEdge::Ptr edge = dyn_detail::boost::static_pointer_cast<SliceEdge>(*begin);
250        SliceNode::Ptr source = dyn_detail::boost::static_pointer_cast<SliceNode>(edge->source());
251
252        // Skip this one to break a cycle.
253        if (skipEdges.find(edge) != skipEdges.end()) {
254          expand_cerr << "In process, skipping edge from " 
255                      << source->format() << endl;
256          continue;
257        }
258        
259        Assignment::Ptr assign = source->assign();
260        if (!assign) continue; // widen node
261        
262        expand_cerr << "Assigning input " << edge->data().format() 
263                    << " from assignment " << assign->format() << endl;
264        inputMap[&edge->data()].insert(assign);
265     }
266     
267     expand_cerr << "\t Input map has size " << inputMap.size() << endl;
268     
269     // All of the expanded inputs are in the parameter dbase
270     // If not (like this one), add it
271
272     AST::Ptr ast = SymEval::expand(ptr->assign());
273     //expand_cerr << "\t ... resulting in " << dbase.format() << endl;
274
275     // We have an AST. Now substitute in all of its predecessors.
276     for (std::map<const AbsRegion*, std::set<Assignment::Ptr> >::iterator iter = inputMap.begin();
277          iter != inputMap.end(); ++iter) {
278       // If we have multiple secondary definitions, we:
279       //   if all definitions are equal, use the first
280       //   otherwise, use nothing
281       AST::Ptr definition;
282
283       for (std::set<Assignment::Ptr>::iterator iter2 = iter->second.begin(); 
284            iter2 != iter->second.end(); ++iter2) {
285         AST::Ptr newDef = dbase[*iter2];
286         if (!definition) {
287           definition = newDef;
288           continue;
289         }
290         else if (definition->equals(newDef)) {
291           continue;
292         }
293         else {
294           // Not equal
295           definition = AST::Ptr(); 
296           break;
297         }
298       }
299
300       
301       // The region used by the current assignment...
302       const AbsRegion &reg = *iter->first;
303       
304       // Create an AST around this one
305       VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
306       
307       if (!definition) {
308         // Can happen if we're expanding out of order, and is generally harmless.
309         continue;
310       }
311       
312       expand_cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
313       
314       if (!ast) {
315         expand_cerr << "Skipping substitution because of null AST" << endl;
316       } else {
317         ast = AST::substitute(ast, use, definition);
318         ret = true;
319       } 
320       //expand_cerr << "\t result is " << res->format() << endl;
321     }
322     expand_cerr << "Result of substitution: " << ptr->assign()->format() << " == " << (ast ? ast->format() : "<NULL AST>") << endl;
323     
324     // And attempt simplification again
325     ast = simplifyStack(ast, ptr->addr(), ptr->func());
326     expand_cerr << "Result of post-substitution simplification: " << ptr->assign()->format() << " == " 
327                 << (ast ? ast->format() : "<NULL AST>") << endl;
328     
329     dbase[ptr->assign()] = ast;
330     return ret;
331 }
332
333 AST::Ptr SymEval::simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func) {
334   if (!ast) return ast;
335   // Let's experiment with simplification
336   StackAnalysis sA(func);
337   StackAnalysis::Height sp = sA.findSP(addr);
338   StackAnalysis::Height fp = sA.findFP(addr);
339   
340   StackVisitor sv(addr, func, sp, fp);
341
342   AST::Ptr simplified = ast->accept(&sv);
343
344   return simplified;
345 }