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