Update copyright disclaimer structure by outlining copyright notice. Add LLNL and...
[dyninst.git] / dataflowAPI / src / SymEval.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #include <string>
32 #include <iostream>
33
34 #include "../h/SymEval.h"
35 #include "SymEvalPolicy.h"
36
37 #include "DynAST.h"
38
39 #include "parseAPI/h/CFG.h"
40
41 #include "../rose/x86InstructionSemantics.h"
42 #include "../rose/powerpcInstructionSemantics.h"
43 #include "../rose/SgAsmInstruction.h"
44 #include "../h/stackanalysis.h"
45 #include "SymEvalVisitors.h"
46
47 #include "RoseInsnFactory.h"
48 #include "SymbolicExpansion.h"
49
50 #include "../h/Absloc.h"
51
52 #include "../h/slicing.h" // SliceNode
53
54 #include "debug_dataflow.h"
55
56 #include "boost/tuple/tuple.hpp"
57
58 using namespace Dyninst;
59 using namespace InstructionAPI;
60 using namespace DataflowAPI;
61
62
63 std::pair<AST::Ptr, bool> SymEval::expand(const Assignment::Ptr &assignment) {
64   // This is a shortcut version for when we only want a
65   // single assignment
66   
67   Result_t res;
68   // Fill it in to mark it as existing
69   res[assignment] = AST::Ptr();
70   std::set<Instruction::Ptr> ignored;
71   bool succ = expand(res, ignored);
72   return std::make_pair(res[assignment], succ);
73 }
74
75 bool SymEval::expand(Result_t &res, 
76                      std::set<InstructionPtr> &failedInsns,
77                      bool applyVisitors) {
78   // Symbolic evaluation works off an Instruction
79   // so we have something to hand to ROSE. 
80    failedInsns.clear();
81    for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
82       if (i->second != AST::Ptr()) {
83          // Must've already filled it in from a previous instruction crack
84          continue;
85       }
86     Assignment::Ptr ptr = i->first;
87     
88     bool success = expandInsn(ptr->insn(),
89                               ptr->addr(),
90                               res);
91     if (!success) failedInsns.insert(ptr->insn());
92    }
93
94    if (applyVisitors) {
95       // Must apply the visitor to each filled in element
96       for (Result_t::iterator i = res.begin(); i != res.end(); ++i) {
97          if (!i->second) continue;
98          AST::Ptr tmp = simplifyStack(i->second, i->first->addr(), i->first->func(), i->first->block());
99          BooleanVisitor b;
100          AST::Ptr tmp2 = tmp->accept(&b);
101          i->second = tmp2;
102       }
103    }
104    return (failedInsns.empty());
105 }
106
107 bool edgeSort(Edge::Ptr ptr1, Edge::Ptr ptr2) {
108     Address addr1 = ptr1->target()->addr();
109     Address addr2 = ptr2->target()->addr();
110
111     return (addr1 < addr2);
112 }
113
114 void dfs(Node::Ptr source,
115          std::map<Node::Ptr, int> &state,
116          std::set<Edge::Ptr> &skipEdges) {
117
118    // DFS from the node given by source
119    // If we meet a node twice without having to backtrack first,
120    // insert that incoming edge into skipEdges.
121    //
122    // A node n has state[n] > 0 if it is on the path currently
123    // being explored.
124
125    EdgeIterator b, e;
126    source->outs(b, e);
127
128     vector<Edge::Ptr> edges;
129     for ( ; b!=e; ++b) {
130         Edge::Ptr edge = *b;
131         edges.push_back(edge);
132     }
133     std::stable_sort(edges.begin(), edges.end(), edgeSort);
134
135    //state[source]++;
136    std::map<Node::Ptr, int>::iterator ssit = state.find(source);
137    if(ssit == state.end())
138     boost::tuples::tie(ssit,boost::tuples::ignore) = 
139         state.insert(make_pair(source,1));
140    else
141     (*ssit).second++;
142
143    vector<Edge::Ptr>::iterator eit = edges.begin();
144    for ( ; eit != edges.end(); ++eit) {
145       Edge::Ptr edge = *eit;
146       Node::Ptr cur = edge->target();
147
148       std::map<Node::Ptr, int>::iterator sit = state.find(cur);
149       bool done = (sit != state.end());
150
151       if(done && (*sit).second > 0)
152         skipEdges.insert(edge);
153
154       if(!done)
155         dfs(cur, state, skipEdges);
156    }
157
158    //state[source]--;
159    (*ssit).second--;
160 }
161
162 /*
163  * Optimal ordering for visiting the slicing
164  * nodes during expansion; this is possible to do
165  * because we have removed loops
166  */
167 class ExpandOrder {
168  public:
169     ExpandOrder() { }
170     ~ExpandOrder() { }
171
172     // remove an element from the next-lowest queue
173     // and return it and its order
174     pair<SliceNode::Ptr,int> pop_next()
175     {
176         SliceNode::Ptr rn = SliceNode::Ptr();
177         int ro = -1;
178
179         map<int,order_queue>::iterator qit = queues.begin();
180         for( ; qit != queues.end(); ++qit) {
181             order_queue & q = (*qit).second;
182             if(!q.nodes.empty()) {
183                 rn = *q.nodes.begin();
184                 ro = q.order; 
185                 remove(rn);
186                 break;
187             }
188         }
189         return make_pair(rn,ro);
190     }
191
192     // removes a node from the structure
193     // returns true if the node was there
194     bool remove(SliceNode::Ptr n) {
195         map<SliceNode::Ptr, int>::iterator it = order_map.find(n);
196         if(it != order_map.end()) {
197             queues[ (*it).second ].nodes.erase(n);
198             order_map.erase(it);
199             return true;
200         } 
201         return false;
202     }
203
204     // places a node in the structure -- its
205     // order is computed
206     void insert(SliceNode::Ptr n, bool force_done = false) {
207         // compute the order of this node --- the number of its parents
208         // not on the skipedges list and not done
209         EdgeIterator begin, end;
210         n->ins(begin,end);
211         int pcnt = 0;
212         for( ; begin != end; ++begin) {
213             Edge::Ptr edge = *begin;
214             if(skip_edges.find(edge) == skip_edges.end()) {
215                 SliceNode::Ptr parent =
216                     boost::static_pointer_cast<SliceNode>(
217                         edge->source());
218                 if(done.find(parent) == done.end())
219                     ++pcnt;
220             }
221         }
222
223         queues[pcnt].nodes.insert(n);
224         queues[pcnt].order = pcnt;
225         order_map[n] = pcnt;
226
227         if(force_done)
228             done.insert(n);
229     }
230
231     // Mark a node complete, updating its children.
232     // Removes the node from the data structure
233     void mark_done(SliceNode::Ptr n) {
234         // First pull all of the children of this node
235         // that are not on the skip list
236
237         set<SliceNode::Ptr> children;
238
239         EdgeIterator begin, end;
240         n->outs(begin, end);
241         for (; begin != end; ++begin) {
242             Edge::Ptr edge = *begin;
243             if(skip_edges.find(edge) == skip_edges.end()) {
244                 SliceNode::Ptr child = 
245                     boost::static_pointer_cast<SliceNode>(
246                         edge->target());
247                 if(remove(child))
248                     children.insert(child);
249             }
250         }
251
252         // remove n and set done
253         remove(n);
254         done.insert(n);
255
256         // put the children back
257         set<SliceNode::Ptr>::iterator cit = children.begin();
258         for( ; cit != children.end(); ++cit) {
259             insert(*cit); 
260         }
261     }
262     
263     bool is_done(SliceNode::Ptr n) const {
264         return done.find(n) == done.end();
265     }
266
267     set<Edge::Ptr> & skipEdges() { return skip_edges; }
268
269  private:
270     struct order_queue {
271         int order;
272         set<SliceNode::Ptr> nodes; 
273     };
274
275     set<Edge::Ptr> skip_edges; 
276     map<int,order_queue> queues;
277     map<SliceNode::Ptr, int> order_map;
278     set<SliceNode::Ptr> done;
279 };
280
281 // implements < , <= causes failures when used to sort Windows vectors
282 bool vectorSort(SliceNode::Ptr ptr1, SliceNode::Ptr ptr2) {
283
284     AssignmentPtr assign1 = ptr1->assign();
285     AssignmentPtr assign2 = ptr2->assign();
286
287     if (!assign2) return false;
288     else if (!assign1) return true;
289
290     Address addr1 = assign1->addr();
291     Address addr2 = assign2->addr();
292
293     if (addr1 == addr2) {
294         AbsRegion &out1 = assign1->out();
295         AbsRegion &out2 = assign2->out();
296         return out1 < out2;
297     } else {
298         return addr1 < addr2;
299     }
300 }
301
302 // Do the previous, but use a Graph as a guide for
303 // performing forward substitution on the AST results
304 SymEval::Retval_t SymEval::expand(Dyninst::Graph::Ptr slice, DataflowAPI::Result_t &res) {
305    bool failedTranslation = false;
306    bool skippedInput = false;
307
308     //cout << "Calling expand" << endl;
309     // Other than the substitution this is pretty similar to the first example.
310     NodeIterator gbegin, gend;
311     slice->allNodes(gbegin, gend);
312
313     // First, we'll sort the nodes in some deterministic order so that the loop removal
314     // is deterministic
315     std::vector<SliceNode::Ptr> sortVector;
316     for ( ; gbegin != gend; ++gbegin) {
317         Node::Ptr ptr = *gbegin;
318         SliceNode::Ptr cur = boost::static_pointer_cast<SliceNode>(ptr);
319         sortVector.push_back(cur);
320     }
321     std::stable_sort(sortVector.begin(), sortVector.end(), vectorSort);
322
323     // Optimal ordering of search
324     ExpandOrder worklist;
325
326     std::queue<Node::Ptr> dfs_worklist;
327     std::vector<SliceNode::Ptr>::iterator vit = sortVector.begin();
328     for ( ; vit != sortVector.end(); ++vit) {
329         SliceNode::Ptr ptr = *vit;
330         Node::Ptr cur = boost::static_pointer_cast<Node>(ptr);
331         dfs_worklist.push(cur);
332     }
333
334     /* First, we'll do DFS to check for circularities in the graph;
335      * if so, mark them so we don't do infinite substitution */
336     std::map<Node::Ptr, int> state;
337     while (!dfs_worklist.empty()) {
338        Node::Ptr ptr = dfs_worklist.front(); dfs_worklist.pop();
339        dfs(ptr, state, worklist.skipEdges());
340     }
341
342     slice->allNodes(gbegin, gend);
343     for (; gbegin != gend; ++gbegin) {
344         expand_cerr << "adding " << (*gbegin)->format() << " to worklist" << endl;
345         Node::Ptr ptr = *gbegin;
346         SliceNode::Ptr sptr = 
347             boost::static_pointer_cast<SliceNode>(ptr);
348         worklist.insert(sptr,false);
349     }
350
351     /* have a list
352      * for each node, process
353      * if processessing succeeded, remove the element
354      * if the size of the list has changed, continue */
355
356     while (1) {
357       SliceNode::Ptr aNode;
358       int order;
359
360       boost::tie(aNode,order) = worklist.pop_next();
361       if(order == -1) // empty
362         break;
363
364       if (!aNode->assign()) {
365           worklist.mark_done(aNode);
366           continue; // Could be a widen point
367       }
368
369       expand_cerr << "Visiting node " << aNode->assign()->format() 
370         << " order " << order << endl;
371
372       if (order != 0) {
373         cerr << "ERROR: order is non zero: " << order << endl;
374       }
375       assert(order == 0); // there are no loops
376
377       AST::Ptr prev = res[aNode->assign()];
378       Retval_t result = process(aNode, res, worklist.skipEdges()); 
379       AST::Ptr post = res[aNode->assign()];
380       switch (result) {
381          case FAILED:
382             return FAILED;
383             break;
384          case WIDEN_NODE:
385             // Okay...
386             break;
387          case FAILED_TRANSLATION:
388             failedTranslation = true;
389             break;
390          case SKIPPED_INPUT:
391             skippedInput = true;
392             break;
393          case SUCCESS:
394             break;
395       }
396
397       // We've visited this node, freeing its children
398       // to be visited in turn
399       worklist.mark_done(aNode);
400
401       if (post && !(post->equals(prev))) {
402         expand_cerr << "Adding successors to list, as new expansion " << endl
403             << "\t" << post->format() << endl 
404             << " != " << endl
405             << "\t" << (prev ? prev->format() : "<NULL>") << endl;
406         EdgeIterator oB, oE;
407         aNode->outs(oB, oE);
408         for (; oB != oE; ++oB) {
409             if(worklist.skipEdges().find(*oB) == worklist.skipEdges().end()) {
410                 SliceNode::Ptr out =
411                     boost::static_pointer_cast<SliceNode>(
412                         (*oB)->target());
413                 worklist.insert(out);
414             }
415         }
416       }
417     }
418     if (failedTranslation) return FAILED_TRANSLATION;
419     else if (skippedInput) return SKIPPED_INPUT;
420     else return SUCCESS;
421 }
422
423 bool SymEval::expandInsn(const InstructionAPI::Instruction::Ptr insn,
424                          const uint64_t addr,
425                          Result_t &res)
426 {
427
428    SymEvalPolicy policy(res, addr, insn->getArch(), insn);
429
430   SgAsmInstruction *roseInsn;
431   switch(insn->getArch()) {
432   case Arch_x86:  {
433     RoseInsnX86Factory fac;
434     roseInsn = fac.convert(insn, addr);
435     
436     SymbolicExpansion exp;
437     exp.expandX86(roseInsn, policy);
438     break;
439   }
440   case Arch_ppc32: {
441     RoseInsnPPCFactory fac;
442     roseInsn = fac.convert(insn, addr);
443
444     SymbolicExpansion exp;
445     exp.expandPPC(roseInsn, policy);
446     break;
447   }
448   default:
449     assert(0 && "Unimplemented symbolic expansion architecture");
450     break;
451   }
452
453   if (policy.failedTranslate()) {
454      cerr << "Warning: failed semantic translation of instruction " << insn->format() << endl;
455      return false;
456   }
457   return true;
458 }
459
460
461 SymEval::Retval_t SymEval::process(SliceNode::Ptr ptr,
462                                    Result_t &dbase,
463                                    std::set<Edge::Ptr> &skipEdges) {
464    bool failedTranslation;
465    bool skippedEdge = false;
466    bool skippedInput = false;
467    bool success = false;
468
469     std::map<const AbsRegion*, std::set<Assignment::Ptr> > inputMap;
470
471     expand_cerr << "Calling process on " << ptr->format() << endl;
472
473     // Don't try an expansion of a widen node...
474     if (!ptr->assign()) return WIDEN_NODE;
475
476     EdgeIterator begin, end;
477     ptr->ins(begin, end);
478
479     for (; begin != end; ++begin) {
480        SliceEdge::Ptr edge = boost::static_pointer_cast<SliceEdge>(*begin);
481        SliceNode::Ptr source = boost::static_pointer_cast<SliceNode>(edge->source());
482
483        // Skip this one to break a cycle.
484        if (skipEdges.find(edge) != skipEdges.end()) {
485          expand_cerr << "In process, skipping edge from " 
486                      << source->format() << endl;
487          skippedEdge = true;
488          continue;
489        }
490        
491        Assignment::Ptr assign = source->assign();
492        if (!assign) continue; // widen node
493        
494        expand_cerr << "Assigning input " << edge->data().format() 
495                    << " from assignment " << assign->format() << endl;
496        inputMap[&edge->data()].insert(assign);
497     }
498     
499     expand_cerr << "\t Input map has size " << inputMap.size() << endl;
500     
501     // All of the expanded inputs are in the parameter dbase
502     // If not (like this one), add it
503     
504     AST::Ptr ast;
505     boost::tie(ast, failedTranslation) = SymEval::expand(ptr->assign());
506     //expand_cerr << "\t ... resulting in " << dbase.format() << endl;
507
508     // We have an AST. Now substitute in all of its predecessors.
509     for (std::map<const AbsRegion*, std::set<Assignment::Ptr> >::iterator iter = inputMap.begin();
510          iter != inputMap.end(); ++iter) {
511       // If we have multiple secondary definitions, we:
512       //   if all definitions are equal, use the first
513       //   otherwise, use nothing
514       AST::Ptr definition;
515
516       for (std::set<Assignment::Ptr>::iterator iter2 = iter->second.begin(); 
517            iter2 != iter->second.end(); ++iter2) {
518         AST::Ptr newDef = dbase[*iter2];
519         if (!definition) {
520           definition = newDef;
521           continue;
522         }
523         else if (definition->equals(newDef)) {
524           continue;
525         }
526         else {
527           // Not equal
528           definition = AST::Ptr(); 
529           skippedInput = true;
530           break;
531         }
532       }
533
534       
535       // The region used by the current assignment...
536       const AbsRegion &reg = *iter->first;
537       
538       // Create an AST around this one
539       VariableAST::Ptr use = VariableAST::create(Variable(reg, ptr->addr()));
540       
541       if (!definition) {
542         // Can happen if we're expanding out of order, and is generally harmless.
543         continue;
544       }
545       
546       expand_cerr << "Before substitution: " << (ast ? ast->format() : "<NULL AST>") << endl;
547       
548       if (!ast) {
549         expand_cerr << "Skipping substitution because of null AST" << endl;
550       } else {
551         ast = AST::substitute(ast, use, definition);
552         success = true;
553       } 
554       //expand_cerr << "\t result is " << res->format() << endl;
555     }
556     expand_cerr << "Result of substitution: " << ptr->assign()->format() << " == " << (ast ? ast->format() : "<NULL AST>") << endl;
557     
558     // And attempt simplification again
559     ast = simplifyStack(ast, ptr->addr(), ptr->func(), ptr->block());
560     expand_cerr << "Result of post-substitution simplification: " << ptr->assign()->format() << " == " 
561                 << (ast ? ast->format() : "<NULL AST>") << endl;
562     
563     dbase[ptr->assign()] = ast;
564     if (failedTranslation) return FAILED_TRANSLATION;
565     else if (skippedEdge || skippedInput) return SKIPPED_INPUT;
566     else if (success) return SUCCESS;
567     else return FAILED;
568 }
569
570 AST::Ptr SymEval::simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func, ParseAPI::Block *block) {
571   if (!ast) return ast;
572   // Let's experiment with simplification
573   StackAnalysis sA(func);
574   StackAnalysis::Height sp = sA.findSP(block, addr);
575   StackAnalysis::Height fp = sA.find(block, addr, MachRegister::getFramePointer(func->isrc()->getArch()));
576   
577   StackVisitor sv(addr, func, sp, fp);
578
579   AST::Ptr simplified = ast->accept(&sv);
580
581   return simplified;
582 }