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