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