Fixes problems resulting from merge with master branch
[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 #include "boost/tuple/tuple.hpp"
58
59 using namespace Dyninst;
60 using namespace InstructionAPI;
61 using namespace DataflowAPI;
62
63
64 AST::Ptr SymEval::expand(const Assignment::Ptr &assignment) {
65   // This is a shortcut version for when we only want a
66   // single assignment
67   
68   Result_t res;
69   // Fill it in to mark it as existing
70   res[assignment] = AST::Ptr();
71   expand(res);
72   return res[assignment];
73 }
74
75 void SymEval::expand(Result_t &res, bool applyVisitors) {
76   // Symbolic evaluation works off an Instruction
77   // so we have something to hand to ROSE. 
78   for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
79     if (i->second != AST::Ptr()) {
80       // Must've already filled it in from a previous instruction crack
81       continue;
82     }
83     Assignment::Ptr ptr = i->first;
84     
85     expandInsn(ptr->insn(),
86                ptr->addr(),
87                res);
88   }
89
90   if (applyVisitors) {
91     // Must apply the visitor to each filled in element
92     for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
93       if (!i->second) continue;
94       AST::Ptr tmp = simplifyStack(i->second, i->first->addr(), i->first->func());
95       BooleanVisitor b;
96       AST::Ptr tmp2 = tmp->accept(&b);
97       i->second = tmp2;
98     }
99   }
100 }
101
102 void dfs(Node::Ptr source,
103          std::map<Node::Ptr, int> &state,
104          std::set<Edge::Ptr> &skipEdges) {
105
106    // DFS from the node given by source
107    // If we meet a node twice without having to backtrack first,
108    // insert that incoming edge into skipEdges.
109    //
110    // A node n has state[n] > 0 if it is on the path currently
111    // being explored.
112
113    EdgeIterator b, e;
114    source->outs(b, e);
115
116    //state[source]++;
117    std::map<Node::Ptr, int>::iterator ssit = state.find(source);
118    if(ssit == state.end())
119     boost::tuples::tie(ssit,boost::tuples::ignore) = 
120         state.insert(make_pair(source,1));
121    else
122     (*ssit).second++;
123
124    for (; b != e; ++b) {
125       Edge::Ptr edge = *b;
126       Node::Ptr cur = edge->target();
127
128       std::map<Node::Ptr, int>::iterator sit = state.find(cur);
129       bool done = (sit != state.end());
130
131       if(done && (*sit).second > 0)
132         skipEdges.insert(edge);
133
134       if(!done)
135         dfs(cur, state, skipEdges);
136    }
137
138    //state[source]--;
139    (*ssit).second--;
140 }
141
142 /*
143  * Optimal ordering for visiting the slicing
144  * nodes during expansion; this is possible to do
145  * because we have removed loops
146  */
147 class ExpandOrder {
148  public:
149     ExpandOrder() { }
150     ~ExpandOrder() { }
151
152     // remove an element from the next-lowest queue
153     // and return it and its order
154     pair<SliceNode::Ptr,int> pop_next()
155     {
156         SliceNode::Ptr rn = SliceNode::Ptr();
157         int ro = -1;
158
159         map<int,order_queue>::iterator qit = queues.begin();
160         for( ; qit != queues.end(); ++qit) {
161             order_queue & q = (*qit).second;
162             if(!q.nodes.empty()) {
163                 rn = *q.nodes.begin();
164                 ro = q.order; 
165                 remove(rn);
166                 break;
167             }
168         }
169         return make_pair(rn,ro);
170     }
171
172     // removes a node from the structure
173     // returns true if the node was there
174     bool remove(SliceNode::Ptr n) {
175         map<SliceNode::Ptr, int>::iterator it = order_map.find(n);
176         if(it != order_map.end()) {
177             queues[ (*it).second ].nodes.erase(n);
178             order_map.erase(it);
179             return true;
180         } 
181         return false;
182     }
183
184     // places a node in the structure -- its
185     // order is computed
186     void insert(SliceNode::Ptr n, bool force_done = false) {
187         // compute the order of this node --- the number of its parents
188         // not on the skipedges list and not done
189         EdgeIterator begin, end;
190         n->ins(begin,end);
191         int pcnt = 0;
192         for( ; begin != end; ++begin) {
193             Edge::Ptr edge = *begin;
194             if(skip_edges.find(edge) == skip_edges.end()) {
195                 SliceNode::Ptr parent =
196                     dyn_detail::boost::static_pointer_cast<SliceNode>(
197                         edge->source());
198                 if(done.find(parent) == done.end())
199                     ++pcnt;
200             }
201         }
202
203         queues[pcnt].nodes.insert(n);
204         queues[pcnt].order = pcnt;
205         order_map[n] = pcnt;
206
207         if(force_done)
208             done.insert(n);
209     }
210
211     // Mark a node complete, updating its children.
212     // Removes the node from the data structure
213     void mark_done(SliceNode::Ptr n) {
214         // First pull all of the children of this node
215         // that are not on the skip list
216
217         set<SliceNode::Ptr> children;
218
219         EdgeIterator begin, end;
220         n->outs(begin, end);
221         for (; begin != end; ++begin) {
222             Edge::Ptr edge = *begin;
223             if(skip_edges.find(edge) == skip_edges.end()) {
224                 SliceNode::Ptr child = 
225                     dyn_detail::boost::static_pointer_cast<SliceNode>(
226                         edge->target());
227                 if(remove(child))
228                     children.insert(child);
229             }
230         }
231
232         // remove n and set done
233         remove(n);
234         done.insert(n);
235
236         // put the children back
237         set<SliceNode::Ptr>::iterator cit = children.begin();
238         for( ; cit != children.end(); ++cit) {
239             insert(*cit); 
240         }
241     }
242     
243     bool is_done(SliceNode::Ptr n) const {
244         return done.find(n) == done.end();
245     }
246
247     set<Edge::Ptr> & skipEdges() { return skip_edges; }
248
249  private:
250     struct order_queue {
251         int order;
252         set<SliceNode::Ptr> nodes; 
253     };
254
255     set<Edge::Ptr> skip_edges; 
256     map<int,order_queue> queues;
257     map<SliceNode::Ptr, int> order_map;
258     set<SliceNode::Ptr> done;
259 };
260
261
262 // Do the previous, but use a Graph as a guide for
263 // performing forward substitution on the AST results
264 void SymEval::expand(Graph::Ptr slice, Result_t &res) {
265     //cout << "Calling expand" << endl;
266     // Other than the substitution this is pretty similar to the first example.
267     NodeIterator gbegin, gend;
268     slice->allNodes(gbegin, gend);
269
270     // Optimal ordering of search
271     ExpandOrder worklist;
272
273     std::queue<Node::Ptr> dfs_worklist;
274     for (; gbegin != gend; ++gbegin) {
275       Node::Ptr ptr = *gbegin;
276       dfs_worklist.push(ptr);
277     }
278
279     /* First, we'll do DFS to check for circularities in the graph;
280      * if so, mark them so we don't do infinite substitution */
281     std::map<Node::Ptr, int> state;
282     while (!dfs_worklist.empty()) {
283        Node::Ptr ptr = dfs_worklist.front(); dfs_worklist.pop();
284        dfs(ptr, state, worklist.skipEdges());
285     }
286
287     slice->allNodes(gbegin, gend);
288     for (; gbegin != gend; ++gbegin) {
289         expand_cerr << "adding " << (*gbegin)->format() << " to worklist" << endl;
290         Node::Ptr ptr = *gbegin;
291         SliceNode::Ptr sptr = 
292             dyn_detail::boost::static_pointer_cast<SliceNode>(ptr);
293         worklist.insert(sptr,false);
294     }
295
296     /* have a list
297      * for each node, process
298      * if processessing succeeded, remove the element
299      * if the size of the list has changed, continue */
300
301     while (1) {
302       SliceNode::Ptr aNode;
303       int order;
304
305       boost::tie(aNode,order) = worklist.pop_next();
306       if(order == -1) // empty
307         break;
308
309       if (!aNode->assign()) continue; // Could be a widen point
310
311       expand_cerr << "Visiting node " << aNode->assign()->format() 
312         << " order " << order << endl;
313
314       assert(order == 0); // there are no loops
315
316       AST::Ptr prev = res[aNode->assign()];
317       process(aNode, res, worklist.skipEdges()); 
318       AST::Ptr post = res[aNode->assign()];
319
320       // We've visited this node, freeing its children
321       // to be visited in turn
322       worklist.mark_done(aNode);
323
324       if (post && !(post->equals(prev))) {
325         expand_cerr << "Adding successors to list, as new expansion " << endl
326             << "\t" << post->format() << endl 
327             << " != " << endl
328             << "\t" << (prev ? prev->format() : "<NULL>") << endl;
329         EdgeIterator oB, oE;
330         aNode->outs(oB, oE);
331         for (; oB != oE; ++oB) {
332             if(worklist.skipEdges().find(*oB) == worklist.skipEdges().end()) {
333                 SliceNode::Ptr out =
334                     dyn_detail::boost::static_pointer_cast<SliceNode>(
335                         (*oB)->target());
336                 worklist.insert(out);
337             }
338         }
339       }
340     }
341 }
342
343 void SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
344                          const uint64_t addr,
345                          Result_t &res) {
346
347   SymEvalPolicy policy(res, (Address)addr, insn->getArch());
348
349   SgAsmInstruction *roseInsn;
350   switch(insn->getArch()) {
351   case Arch_x86:  {
352     RoseInsnX86Factory fac;
353     roseInsn = fac.convert(insn, addr);
354     
355     SymbolicExpansion exp;
356     exp.expandX86(roseInsn, policy);
357     break;
358   }
359   case Arch_ppc32: {
360     RoseInsnPPCFactory fac;
361     roseInsn = fac.convert(insn, addr);
362
363     SymbolicExpansion exp;
364     exp.expandPPC(roseInsn, policy);
365     break;
366   }
367   default:
368     assert(0 && "Unimplemented symbolic expansion architecture");
369     break;
370   }
371   return;
372 }
373
374
375 bool SymEval::process(SliceNode::Ptr ptr,
376                       Result_t &dbase,
377                       std::set<Edge::Ptr> &skipEdges) {
378     bool ret = false;
379     
380     std::map<const AbsRegion*, std::set<Assignment::Ptr> > inputMap;
381
382     expand_cerr << "Calling process on " << ptr->format() << endl;
383
384     // Don't try an expansion of a widen node...
385     if (!ptr->assign()) return ret;
386
387     EdgeIterator begin, end;
388     ptr->ins(begin, end);
389
390     for (; begin != end; ++begin) {
391        SliceEdge::Ptr edge = dyn_detail::boost::static_pointer_cast<SliceEdge>(*begin);
392        SliceNode::Ptr source = dyn_detail::boost::static_pointer_cast<SliceNode>(edge->source());
393
394        // Skip this one to break a cycle.
395        if (skipEdges.find(edge) != skipEdges.end()) {
396          expand_cerr << "In process, skipping edge from " 
397                      << source->format() << endl;
398          continue;
399        }
400        
401        Assignment::Ptr assign = source->assign();
402        if (!assign) continue; // widen node
403        
404        expand_cerr << "Assigning input " << edge->data().format() 
405                    << " from assignment " << assign->format() << endl;
406        inputMap[&edge->data()].insert(assign);
407     }
408     
409     expand_cerr << "\t Input map has size " << inputMap.size() << endl;
410     
411     // All of the expanded inputs are in the parameter dbase
412     // If not (like this one), add it
413
414     AST::Ptr ast = SymEval::expand(ptr->assign());
415     //expand_cerr << "\t ... resulting in " << dbase.format() << endl;
416
417     // We have an AST. Now substitute in all of its predecessors.
418     for (std::map<const AbsRegion*, std::set<Assignment::Ptr> >::iterator iter = inputMap.begin();
419          iter != inputMap.end(); ++iter) {
420       // If we have multiple secondary definitions, we:
421       //   if all definitions are equal, use the first
422       //   otherwise, use nothing
423       AST::Ptr definition;
424
425       for (std::set<Assignment::Ptr>::iterator iter2 = iter->second.begin(); 
426            iter2 != iter->second.end(); ++iter2) {
427         AST::Ptr newDef = dbase[*iter2];
428         if (!definition) {
429           definition = newDef;
430           continue;
431         }
432         else if (definition->equals(newDef)) {
433           continue;
434         }
435         else {
436           // Not equal
437           definition = AST::Ptr(); 
438           break;
439         }
440       }
441
442       
443       // The region used by the current assignment...
444       const AbsRegion &reg = *iter->first;
445       
446       // Create an AST around this one
447       VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
448       
449       if (!definition) {
450         // Can happen if we're expanding out of order, and is generally harmless.
451         continue;
452       }
453       
454       expand_cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
455       
456       if (!ast) {
457         expand_cerr << "Skipping substitution because of null AST" << endl;
458       } else {
459         ast = AST::substitute(ast, use, definition);
460         ret = true;
461       } 
462       //expand_cerr << "\t result is " << res->format() << endl;
463     }
464     expand_cerr << "Result of substitution: " << ptr->assign()->format() << " == " << (ast ? ast->format() : "<NULL AST>") << endl;
465     
466     // And attempt simplification again
467     ast = simplifyStack(ast, ptr->addr(), ptr->func());
468     expand_cerr << "Result of post-substitution simplification: " << ptr->assign()->format() << " == " 
469                 << (ast ? ast->format() : "<NULL AST>") << endl;
470     
471     dbase[ptr->assign()] = ast;
472     return ret;
473 }
474
475 AST::Ptr SymEval::simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func) {
476   if (!ast) return ast;
477   // Let's experiment with simplification
478   StackAnalysis sA(func);
479   StackAnalysis::Height sp = sA.findSP(addr);
480   StackAnalysis::Height fp = sA.findFP(addr);
481   
482   StackVisitor sv(addr, func, sp, fp);
483
484   AST::Ptr simplified = ast->accept(&sv);
485
486   return simplified;
487 }