Merge branch 'master' into IndirectControlFlow
[dyninst.git] / dataflowAPI / h / slicing.h
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 // A simple forward slice using a search of the control flow graph.
31 // Templated on a function that says when to stop slicing.
32
33 #if !defined(_SLICING_H_)
34 #define _SLICING_H_
35
36 #include <vector>
37 #include "dyntypes.h"
38 #include <queue>
39 #include <set>
40 #include <unordered_set>
41 #include <map>
42 #include <unordered_map>
43 #include <list>
44 #include <stack>
45
46 #include "util.h"
47 #include "Node.h"
48 #include "Edge.h"
49
50 #include "AbslocInterface.h"
51
52 #include <boost/functional/hash.hpp>
53
54 namespace Dyninst {
55
56 namespace ParseAPI {
57   class Block;
58   class Edge;
59   class Function;
60 };
61
62 class Assignment;
63 class AbsRegion;
64 typedef boost::shared_ptr<Assignment> AssignmentPtr;
65
66 class Graph;
67 typedef boost::shared_ptr<Graph> GraphPtr;
68
69  namespace InstructionAPI {
70    class Instruction;
71  }
72  typedef boost::shared_ptr<InstructionAPI::Instruction> InstructionPtr;
73
74  class Slicer;
75
76 // Used in temp slicer; should probably
77 // replace OperationNodes when we fix up
78 // the DDG code.
79 class DATAFLOW_EXPORT SliceNode : public Node {
80  public:
81   typedef boost::shared_ptr<SliceNode> Ptr;
82       
83   static SliceNode::Ptr create(AssignmentPtr ptr,
84                                 ParseAPI::Block *block,
85                                 ParseAPI::Function *func) {
86     return Ptr(new SliceNode(ptr, block, func));
87   }
88       
89   ParseAPI::Block *block() const { return b_; };
90   ParseAPI::Function *func() const { return f_; };
91   Address addr() const;
92   AssignmentPtr assign() const { return a_; }
93       
94   Node::Ptr copy() { return Node::Ptr(); }
95   bool isVirtual() const { return false; }
96       
97   std::string format() const;
98       
99   virtual ~SliceNode() {};
100       
101  private:
102       
103  SliceNode(AssignmentPtr ptr,
104             ParseAPI::Block *block,
105             ParseAPI::Function *func) : 
106   a_(ptr), b_(block), f_(func) {};
107       
108   AssignmentPtr a_;
109   ParseAPI::Block *b_;
110   ParseAPI::Function *f_;
111
112   friend class Slicer;
113 };
114
115 class SliceEdge : public Edge {
116   public:
117    typedef boost::shared_ptr<SliceEdge> Ptr;
118
119    DATAFLOW_EXPORT static SliceEdge::Ptr create(SliceNode::Ptr source,
120                                                 SliceNode::Ptr target,
121                                                 AbsRegion const&data) {
122       return Ptr(new SliceEdge(source, target, data)); 
123    }
124
125    const AbsRegion &data() const { return data_; };
126
127   private:
128    SliceEdge(const SliceNode::Ptr source, 
129              const SliceNode::Ptr target,
130              AbsRegion const& data) 
131       : Edge(source, target), data_(data) {};
132    AbsRegion data_;
133 };
134
135 class Slicer {
136  public:
137   typedef std::pair<InstructionPtr, Address> InsnInstance;
138   typedef std::vector<InsnInstance> InsnVec;
139
140   DATAFLOW_EXPORT Slicer(AssignmentPtr a,
141          ParseAPI::Block *block,
142          ParseAPI::Function *func);
143     
144   DATAFLOW_EXPORT static bool isWidenNode(Node::Ptr n);
145
146   class Predicates {
147   public:
148     typedef std::pair<ParseAPI::Function *, int> StackDepth_t;
149     typedef std::stack<StackDepth_t> CallStack_t;
150
151     DATAFLOW_EXPORT virtual bool allowImprecision() { return false; }
152     DATAFLOW_EXPORT virtual bool widenAtPoint(AssignmentPtr) { return false; }
153     DATAFLOW_EXPORT virtual bool endAtPoint(AssignmentPtr) { return false; }
154     DATAFLOW_EXPORT virtual bool followCall(ParseAPI::Function * /*callee*/,
155                                            CallStack_t & /*cs*/,
156                                            AbsRegion /*argument*/) { 
157        return false; 
158     }
159     DATAFLOW_EXPORT virtual std::vector<ParseAPI::Function *> 
160         followCallBackward(ParseAPI::Block * /*callerB*/,
161             CallStack_t & /*cs*/,
162             AbsRegion /*argument*/) {
163             std::vector<ParseAPI::Function *> vec;
164             return vec;
165         }
166     DATAFLOW_EXPORT virtual bool addPredecessor(AbsRegion /*reg*/) {
167         return true;
168     }
169     DATAFLOW_EXPORT virtual bool widenAtAssignment(const AbsRegion & /*in*/,
170                                                   const AbsRegion & /*out*/) { 
171        return false; 
172     }
173     DATAFLOW_EXPORT virtual ~Predicates() {};
174   };
175
176   DATAFLOW_EXPORT GraphPtr forwardSlice(Predicates &predicates);
177   
178   DATAFLOW_EXPORT GraphPtr backwardSlice(Predicates &predicates);
179
180  private:
181
182   typedef enum {
183     forward,
184     backward } Direction;
185
186   typedef std::map<ParseAPI::Block *, InsnVec> InsnCache;
187
188   // Our slicing is context-sensitive; that is, if we enter
189   // a function foo from a caller bar, all return edges
190   // from foo must enter bar. This makes an assumption that
191   // the return address is not modified, but hey. 
192   // We represent this as a list of call sites. This is redundant
193   // with the image_instPoint data structure, but hopefully that
194   // one will be going away. 
195
196   struct ContextElement {
197     // We can implicitly find the callsite given a block,
198     // since calls end blocks. It's easier to look up 
199     // the successor this way than with an address.
200
201     ParseAPI::Function *func;
202
203     // If non-NULL this must be an internal context
204     // element, since we have an active call site.
205     ParseAPI::Block *block;
206
207     // To enter or leave a function we must be able to
208     // map corresponding abstract regions. 
209     // In particular, we need to know the depth of the 
210     // stack in the caller.
211      int stackDepth;
212
213   ContextElement(ParseAPI::Function *f) : 
214     func(f), block(NULL), stackDepth(-1) {};
215   ContextElement(ParseAPI::Function *f, long depth) :
216     func(f), block(NULL), stackDepth(depth) {};
217   };
218
219   // This should be sufficient...
220   typedef std::deque<ContextElement> Context;
221
222   bool getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height);
223
224   // Add the newly called function to the given Context.
225   void pushContext(Context &context,
226                    ParseAPI::Function *callee,
227                    ParseAPI::Block *callBlock,
228                    long stackDepth);
229
230   // And remove it as appropriate
231   void popContext(Context &context);
232
233   // Where we are in a particular search...
234   struct Location {
235     // The block we're looking through
236     ParseAPI::Function *func;
237     ParseAPI::Block *block; // current block
238
239     // Where we are in the block
240     InsnVec::iterator current;
241     InsnVec::iterator end;
242
243     bool fwd;
244
245     InsnVec::reverse_iterator rcurrent;
246     InsnVec::reverse_iterator rend;
247
248     Address addr() const { if(fwd) return (*current).second; else return (*rcurrent).second;}
249
250   Location(ParseAPI::Function *f,
251            ParseAPI::Block *b) : func(f), block(b), fwd(true){};
252   Location() : func(NULL), block(NULL), fwd(true) {};
253   };
254     
255   typedef std::queue<Location> LocList;
256  
257   // Describes an abstract region, a minimal context
258   // (block and function), and the assignment that
259   // relates to that region (uses or defines it, 
260   // depending on slice direction)
261   //
262   // A slice is composed of Elements; SliceFrames 
263   // keep a list of the currently active elements
264   // that are at the `leading edge' of the 
265   // under-construction slice
266   struct Element {
267     Element(ParseAPI::Block * b,
268         ParseAPI::Function * f,
269         AbsRegion const& r,
270         Assignment::Ptr p)
271       : block(b),
272         func(f),
273         reg(r),
274         ptr(p)
275     { }
276
277     // basic comparator for ordering
278     bool operator<(const Element& el) const { 
279         if (ptr->addr() < el.ptr->addr()) { return true; }
280         if (el.ptr->addr() < ptr->addr()) { return false; }
281         if (ptr->out() < el.ptr->out()) { return true; }
282         return false;
283     }
284
285     ParseAPI::Block * block;
286     ParseAPI::Function * func;
287
288     AbsRegion reg;
289     Assignment::Ptr ptr;
290   };
291   bool ReachableFromBothBranches(ParseAPI::Edge *e, std::vector<Element> &newE);
292
293   // State for recursive slicing is a context, location pair
294   // and a list of AbsRegions that are being searched for.
295   struct SliceFrame {
296     SliceFrame(
297         Location const& l,
298         Context const& c,
299         bool f)
300       : loc(l),
301         con(c),
302         valid(true),
303         firstCond(f)
304     { }
305     SliceFrame() : valid(true), firstCond(true) { }
306     SliceFrame(bool v) : valid(v), firstCond(true) { }
307
308     // Active slice nodes -- describe regions
309     // that are currently under scrutiny
310     std::map<AbsRegion, std::vector<Element> > active;
311     typedef std::map<AbsRegion, std::vector<Element> > ActiveMap;
312
313     Location loc;
314     Context con;
315     bool valid;
316     bool firstCond;
317
318     Address addr() const { return loc.addr(); }
319   };
320
321   // Used for keeping track of visited edges in the
322   // slicing search
323   struct CacheEdge {
324     CacheEdge(Address src, Address trg) : s(src), t(trg) { }
325     Address s;
326     Address t;
327
328     bool operator<(CacheEdge const& o) const {
329         if(s < o.s)
330             return true;
331         else if(o.s < s)
332             return false;
333         else if(t < o.t)
334             return true;
335         else
336             return false;
337     }
338   };
339
340     /* 
341      * An element that is a slicing `def' (where
342      * def means `definition' in the backward case
343      * and `use' in the forward case, along with
344      * the associated AbsRegion that labels the slicing
345      * edge.
346      *
347      * These two pieces of information, along with an 
348      * element describing the other end of the dependency,
349      * are what you need to create a slice edge.
350      */
351     struct Def {
352       Def(Element const& e, AbsRegion const& r) : ele(e), data(r) { } 
353       Element ele;
354       AbsRegion data;
355  
356       struct DefHasher {
357           size_t operator() (const Def &o) const {
358               return Assignment::AssignmentPtrHasher()(o.ele.ptr);
359           }
360       };
361       // only the Assignment::Ptr of an Element matters
362       // for comparison
363       bool operator<(Def const& o) const {
364           if(ele.ptr < o.ele.ptr)
365               return true;
366           else if(o.ele.ptr < ele.ptr)
367               return false;
368           else if(data < o.data)
369               return true;
370           else 
371               return false;
372       }
373
374       bool operator==(Def const &o) const {
375           if (ele.ptr != o.ele.ptr) return false;
376           return data == o.data;
377       }
378     };
379
380     // For preventing insertion of duplicate edges
381     // into the slice graph
382     struct EdgeTuple {
383         EdgeTuple(SliceNode::Ptr src, SliceNode::Ptr dst, AbsRegion const& reg)
384           : s(src), d(dst), r(reg) { }
385         bool operator<(EdgeTuple const& o) const {
386             if(s < o.s)
387                 return true;
388             else if(o.s < s)
389                 return false;
390             else if(d < o.d)
391                 return true;
392             else if(o.d < d)
393                 return false;
394             else if(r < o.r)
395                 return true;
396             else
397                 return false;
398         }
399         bool operator == (EdgeTuple const &o) const {
400             if (s != o.s) return false;
401             if (d != o.d) return false;
402             return r == o.r;
403         }
404         SliceNode::Ptr s;
405         SliceNode::Ptr d;
406         AbsRegion r;
407     };
408
409   // Shift an abs region by a given stack offset
410   void shiftAbsRegion(AbsRegion const&callerReg,
411                       AbsRegion &calleeReg,
412                       long stack_depth,
413                       ParseAPI::Function *callee);
414
415     // Shift all of the abstract regions active in the current frame
416     void shiftAllAbsRegions(
417         SliceFrame & cur,
418         long stack_depth,
419         ParseAPI::Function *callee);
420
421   /*
422    * Internal slicing support routines follow. See the
423    * implementation file for descriptions of what these
424    * routines actually do to implement slicing.
425    */
426     GraphPtr sliceInternal(Direction dir,
427             Predicates &predicates);
428     void sliceInternalAux(
429             GraphPtr g,
430             Direction dir,
431             Predicates &p,
432             SliceFrame &cand,
433             bool skip,
434             std::map<CacheEdge, std::set<AbsRegion> > & visited);
435
436     bool updateAndLink(
437             GraphPtr g,
438             Direction dir,
439             SliceFrame & cand,
440             Predicates &p);
441
442     bool stopSlicing(SliceFrame::ActiveMap& active, 
443                      GraphPtr g,
444                      Address addr,
445                      Direction dir);
446
447
448     void markVisited(
449             std::map<CacheEdge, std::set<AbsRegion> > & visited,
450             CacheEdge const& e,
451             SliceFrame::ActiveMap const& active);
452
453     void findMatch(
454             GraphPtr g,
455             Direction dir,
456             SliceFrame const& cand,
457             AbsRegion const& cur,
458             Assignment::Ptr assn,
459             std::vector<Element> & matches);
460
461     bool getNextCandidates(
462             Direction dir,
463             Predicates & p,
464             SliceFrame const& cand,
465             std::vector<SliceFrame> & newCands);
466
467     /* forward slicing */
468
469     bool getSuccessors(
470             Predicates &p,
471             SliceFrame const& cand,
472             std::vector<SliceFrame> & newCands);
473
474
475     bool handleCall(
476             Predicates & p,
477             SliceFrame & cur,
478             bool & err);
479
480     bool followCall(
481             Predicates & p,
482             ParseAPI::Block * target,
483             SliceFrame & cur);
484
485     bool handleCallDetails(
486             SliceFrame & cur,
487             ParseAPI::Block * caller_block);
488
489     bool handleReturn(
490             Predicates & p,
491             SliceFrame & cur,
492             bool & err);
493
494     void handleReturnDetails(
495             SliceFrame & cur);
496
497     bool handleDefault(
498             Direction dir,
499             Predicates & p,
500             ParseAPI::Edge * e,
501             SliceFrame & cur,
502             bool & err);
503
504     /* backwards slicing */
505
506     bool getPredecessors(
507             Predicates &p,
508             SliceFrame const& cand,
509             std::vector<SliceFrame> & newCands);
510
511     bool handleCallBackward(
512             Predicates & p,
513             SliceFrame const& cand,
514             std::vector<SliceFrame> & newCands,
515             ParseAPI::Edge * e,
516             bool & err);
517
518     std::vector<ParseAPI::Function *> followCallBackward(
519             Predicates & p,
520             SliceFrame const& cand,
521             AbsRegion const& reg,
522             ParseAPI::Block * caller_block);
523
524     bool handleCallDetailsBackward(
525             SliceFrame & cur);
526
527     bool handleReturnBackward(
528             Predicates & p,
529             SliceFrame const& cand,
530             SliceFrame & newCand,
531             ParseAPI::Edge * e,
532             bool & err);
533
534     bool handleReturnDetailsBackward(
535             SliceFrame & cur,
536             ParseAPI::Block * caller_block);
537
538     bool followReturn(
539             Predicates & p,
540             SliceFrame const& cand,
541             ParseAPI::Block * source);
542     void handlePredecessorEdge(ParseAPI::Edge* e,
543                                Predicates& p,
544                                SliceFrame const& cand,
545                                std::vector<SliceFrame> & newCands,
546                                bool& err,
547                                SliceFrame& nf);
548   
549
550     /* general slicing support */
551   
552     void constructInitialFrame(
553             Direction dir, 
554             SliceFrame & initFrame);
555     
556     void widenAll(GraphPtr graph, Direction dir, SliceFrame const& frame);
557   
558   bool kills(AbsRegion const& reg, Assignment::Ptr &assign);
559
560   void widen(GraphPtr graph, Direction dir, Element const&source);
561
562   void insertPair(GraphPtr graph,
563                   Direction dir,
564                   Element const&source,
565                   Element const&target,
566           AbsRegion const& data);
567
568   void insertPair(GraphPtr graph,
569                   Direction dir,
570                   SliceNode::Ptr& source,
571                   SliceNode::Ptr& target,
572           AbsRegion const& data);
573
574   void convertInstruction(InstructionPtr,
575                           Address,
576                           ParseAPI::Function *,
577                           ParseAPI::Block *,
578                           std::vector<AssignmentPtr> &);
579
580   void fastForward(Location &loc, Address addr);
581
582   void fastBackward(Location &loc, Address addr);
583
584   SliceNode::Ptr widenNode();
585
586   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
587   
588   void markAsExitNode(GraphPtr ret, Element &current);
589
590   void markAsEntryNode(GraphPtr ret, Element &current);
591
592   void getInsns(Location &loc);
593
594   void getInsnsBackward(Location &loc);
595
596   void setAliases(Assignment::Ptr, Element &);
597
598   SliceNode::Ptr createNode(Element const&);
599
600   void cleanGraph(GraphPtr g);
601
602   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
603                             Direction dir);
604   
605
606   void insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP);
607
608   InsnCache insnCache_;
609
610   AssignmentPtr a_;
611   ParseAPI::Block *b_;
612   ParseAPI::Function *f_;
613
614
615   // Assignments map to unique slice nodes
616   std::unordered_map<AssignmentPtr, SliceNode::Ptr, Assignment::AssignmentPtrHasher> created_;
617
618   // cache to prevent edge duplication
619   struct EdgeTupleHasher {
620     size_t operator() (const EdgeTuple& et) const {
621         size_t seed = (size_t)(et.s.get());
622         boost::hash_combine( seed , (size_t)(et.d.get()));
623         return seed;
624     }
625   };
626   std::unordered_map<EdgeTuple, int, EdgeTupleHasher> unique_edges_;
627
628   // map of previous active maps. these are used to end recursion.
629   typedef std::map<AbsRegion, std::set<Element> > PrevMap;
630   std::map<Address, PrevMap> prev_maps;
631
632   AssignmentConverter converter;
633
634   SliceNode::Ptr widen_;
635 };
636
637 }
638
639 #endif