1. Add a callback interface to slicing code. It triggers when a new node is added...
[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     // Callback function when adding a new node to the slice.
176     // Return true if we want to continue slicing
177     DATAFLOW_EXPORT virtual bool addNodeCallback(AssignmentPtr) { return true;}
178
179   };
180
181   DATAFLOW_EXPORT GraphPtr forwardSlice(Predicates &predicates);
182   
183   DATAFLOW_EXPORT GraphPtr backwardSlice(Predicates &predicates);
184
185  private:
186
187   typedef enum {
188     forward,
189     backward } Direction;
190
191   typedef std::map<ParseAPI::Block *, InsnVec> InsnCache;
192
193   // Our slicing is context-sensitive; that is, if we enter
194   // a function foo from a caller bar, all return edges
195   // from foo must enter bar. This makes an assumption that
196   // the return address is not modified, but hey. 
197   // We represent this as a list of call sites. This is redundant
198   // with the image_instPoint data structure, but hopefully that
199   // one will be going away. 
200
201   struct ContextElement {
202     // We can implicitly find the callsite given a block,
203     // since calls end blocks. It's easier to look up 
204     // the successor this way than with an address.
205
206     ParseAPI::Function *func;
207
208     // If non-NULL this must be an internal context
209     // element, since we have an active call site.
210     ParseAPI::Block *block;
211
212     // To enter or leave a function we must be able to
213     // map corresponding abstract regions. 
214     // In particular, we need to know the depth of the 
215     // stack in the caller.
216      int stackDepth;
217
218   ContextElement(ParseAPI::Function *f) : 
219     func(f), block(NULL), stackDepth(-1) {};
220   ContextElement(ParseAPI::Function *f, long depth) :
221     func(f), block(NULL), stackDepth(depth) {};
222   };
223
224   // This should be sufficient...
225   typedef std::deque<ContextElement> Context;
226
227   bool getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height);
228
229   // Add the newly called function to the given Context.
230   void pushContext(Context &context,
231                    ParseAPI::Function *callee,
232                    ParseAPI::Block *callBlock,
233                    long stackDepth);
234
235   // And remove it as appropriate
236   void popContext(Context &context);
237
238   // Where we are in a particular search...
239   struct Location {
240     // The block we're looking through
241     ParseAPI::Function *func;
242     ParseAPI::Block *block; // current block
243
244     // Where we are in the block
245     InsnVec::iterator current;
246     InsnVec::iterator end;
247
248     bool fwd;
249
250     InsnVec::reverse_iterator rcurrent;
251     InsnVec::reverse_iterator rend;
252
253     Address addr() const { if(fwd) return (*current).second; else return (*rcurrent).second;}
254
255   Location(ParseAPI::Function *f,
256            ParseAPI::Block *b) : func(f), block(b), fwd(true){};
257   Location() : func(NULL), block(NULL), fwd(true) {};
258   };
259     
260   typedef std::queue<Location> LocList;
261  
262   // Describes an abstract region, a minimal context
263   // (block and function), and the assignment that
264   // relates to that region (uses or defines it, 
265   // depending on slice direction)
266   //
267   // A slice is composed of Elements; SliceFrames 
268   // keep a list of the currently active elements
269   // that are at the `leading edge' of the 
270   // under-construction slice
271   struct Element {
272     Element(ParseAPI::Block * b,
273         ParseAPI::Function * f,
274         AbsRegion const& r,
275         Assignment::Ptr p)
276       : block(b),
277         func(f),
278         reg(r),
279         ptr(p)
280     { }
281
282     // basic comparator for ordering
283     bool operator<(const Element& el) const { 
284         if (ptr->addr() < el.ptr->addr()) { return true; }
285         if (el.ptr->addr() < ptr->addr()) { return false; }
286         if (ptr->out() < el.ptr->out()) { return true; }
287         return false;
288     }
289
290     ParseAPI::Block * block;
291     ParseAPI::Function * func;
292
293     AbsRegion reg;
294     Assignment::Ptr ptr;
295   };
296   bool ReachableFromBothBranches(ParseAPI::Edge *e, std::vector<Element> &newE);
297
298   // State for recursive slicing is a context, location pair
299   // and a list of AbsRegions that are being searched for.
300   struct SliceFrame {
301     SliceFrame(
302         Location const& l,
303         Context const& c,
304         bool f)
305       : loc(l),
306         con(c),
307         valid(true),
308         firstCond(f)
309     { }
310     SliceFrame() : valid(true), firstCond(true) { }
311     SliceFrame(bool v) : valid(v), firstCond(true) { }
312
313     // Active slice nodes -- describe regions
314     // that are currently under scrutiny
315     std::map<AbsRegion, std::vector<Element> > active;
316     typedef std::map<AbsRegion, std::vector<Element> > ActiveMap;
317
318     Location loc;
319     Context con;
320     bool valid;
321     bool firstCond;
322
323     Address addr() const { return loc.addr(); }
324   };
325
326   // Used for keeping track of visited edges in the
327   // slicing search
328   struct CacheEdge {
329     CacheEdge(Address src, Address trg) : s(src), t(trg) { }
330     Address s;
331     Address t;
332
333     bool operator<(CacheEdge const& o) const {
334         if(s < o.s)
335             return true;
336         else if(o.s < s)
337             return false;
338         else if(t < o.t)
339             return true;
340         else
341             return false;
342     }
343   };
344
345     /* 
346      * An element that is a slicing `def' (where
347      * def means `definition' in the backward case
348      * and `use' in the forward case, along with
349      * the associated AbsRegion that labels the slicing
350      * edge.
351      *
352      * These two pieces of information, along with an 
353      * element describing the other end of the dependency,
354      * are what you need to create a slice edge.
355      */
356     struct Def {
357       Def(Element const& e, AbsRegion const& r) : ele(e), data(r) { } 
358       Element ele;
359       AbsRegion data;
360  
361       struct DefHasher {
362           size_t operator() (const Def &o) const {
363               return Assignment::AssignmentPtrHasher()(o.ele.ptr);
364           }
365       };
366       // only the Assignment::Ptr of an Element matters
367       // for comparison
368       bool operator<(Def const& o) const {
369           if(ele.ptr < o.ele.ptr)
370               return true;
371           else if(o.ele.ptr < ele.ptr)
372               return false;
373           else if(data < o.data)
374               return true;
375           else 
376               return false;
377       }
378
379       bool operator==(Def const &o) const {
380           if (ele.ptr != o.ele.ptr) return false;
381           return data == o.data;
382       }
383     };
384
385     /*
386      * A cache from AbsRegions -> Defs.
387      *
388      * Each node that has been visited in the search
389      * has a DefCache that reflects the resolution of
390      * any AbsRegions down-slice. If the node is visited
391      * again through a different search path (if the graph
392      * has fork-join structure), this caching prevents
393      * expensive recursion
394      */
395     class DefCache {
396       public:
397         DefCache() { }
398         ~DefCache() { }
399
400         // add the values from another defcache
401         void merge(DefCache const& o);
402    
403         // replace mappings in this cache with those
404         // from another 
405         void replace(DefCache const& o);
406
407         std::set<Def> & get(AbsRegion const& r) { 
408             return defmap[r];
409         }
410         bool defines(AbsRegion const& r) const {
411             return defmap.find(r) != defmap.end();
412         }
413
414         void print() const;
415
416       private:
417         std::map< AbsRegion, std::set<Def> > defmap;
418     
419     };
420
421     // For preventing insertion of duplicate edges
422     // into the slice graph
423     struct EdgeTuple {
424         EdgeTuple(SliceNode::Ptr src, SliceNode::Ptr dst, AbsRegion const& reg)
425           : s(src), d(dst), r(reg) { }
426         bool operator<(EdgeTuple const& o) const {
427             if(s < o.s)
428                 return true;
429             else if(o.s < s)
430                 return false;
431             else if(d < o.d)
432                 return true;
433             else if(o.d < d)
434                 return false;
435             else if(r < o.r)
436                 return true;
437             else
438                 return false;
439         }
440         bool operator == (EdgeTuple const &o) const {
441             if (s != o.s) return false;
442             if (d != o.d) return false;
443             return r == o.r;
444         }
445         SliceNode::Ptr s;
446         SliceNode::Ptr d;
447         AbsRegion r;
448     };
449
450   // Shift an abs region by a given stack offset
451   void shiftAbsRegion(AbsRegion const&callerReg,
452                       AbsRegion &calleeReg,
453                       long stack_depth,
454                       ParseAPI::Function *callee);
455
456     // Shift all of the abstract regions active in the current frame
457     void shiftAllAbsRegions(
458         SliceFrame & cur,
459         long stack_depth,
460         ParseAPI::Function *callee);
461
462   /*
463    * Internal slicing support routines follow. See the
464    * implementation file for descriptions of what these
465    * routines actually do to implement slicing.
466    */
467     GraphPtr sliceInternal(Direction dir,
468             Predicates &predicates);
469     void sliceInternalAux(
470             GraphPtr g,
471             Direction dir,
472             Predicates &p,
473             SliceFrame &cand,
474             bool skip,
475             std::map<CacheEdge, std::set<AbsRegion> > & visited,
476             std::map<Address,DefCache> & single,
477             std::map<Address, DefCache>& cache);
478
479     bool updateAndLink(
480             GraphPtr g,
481             Direction dir,
482             SliceFrame & cand,
483             DefCache & cache,
484             Predicates &p);
485
486     void updateAndLinkFromCache(
487             GraphPtr g,
488             Direction dir,
489             SliceFrame & f,
490             DefCache & cache);
491
492     void removeBlocked(
493             SliceFrame & f,
494             std::set<AbsRegion> const& block);
495
496     bool stopSlicing(SliceFrame::ActiveMap& active, 
497                      GraphPtr g,
498                      Address addr,
499                      Direction dir);
500
501
502     void markVisited(
503             std::map<CacheEdge, std::set<AbsRegion> > & visited,
504             CacheEdge const& e,
505             SliceFrame::ActiveMap const& active);
506
507     void cachePotential(
508             Direction dir,
509             Assignment::Ptr assn,
510             DefCache & cache);
511
512     bool findMatch(
513             GraphPtr g,
514             Direction dir,
515             SliceFrame const& cand,
516             AbsRegion const& cur,
517             Assignment::Ptr assn,
518             std::vector<Element> & matches,
519             DefCache & cache);
520
521     bool getNextCandidates(
522             Direction dir,
523             Predicates & p,
524             SliceFrame const& cand,
525             std::vector<SliceFrame> & newCands);
526
527     /* forward slicing */
528
529     bool getSuccessors(
530             Predicates &p,
531             SliceFrame const& cand,
532             std::vector<SliceFrame> & newCands);
533
534
535     bool handleCall(
536             Predicates & p,
537             SliceFrame & cur,
538             bool & err);
539
540     bool followCall(
541             Predicates & p,
542             ParseAPI::Block * target,
543             SliceFrame & cur);
544
545     bool handleCallDetails(
546             SliceFrame & cur,
547             ParseAPI::Block * caller_block);
548
549     bool handleReturn(
550             Predicates & p,
551             SliceFrame & cur,
552             bool & err);
553
554     void handleReturnDetails(
555             SliceFrame & cur);
556
557     bool handleDefault(
558             Direction dir,
559             Predicates & p,
560             ParseAPI::Edge * e,
561             SliceFrame & cur,
562             bool & err);
563
564     /* backwards slicing */
565
566     bool getPredecessors(
567             Predicates &p,
568             SliceFrame const& cand,
569             std::vector<SliceFrame> & newCands);
570
571     bool handleCallBackward(
572             Predicates & p,
573             SliceFrame const& cand,
574             std::vector<SliceFrame> & newCands,
575             ParseAPI::Edge * e,
576             bool & err);
577
578     std::vector<ParseAPI::Function *> followCallBackward(
579             Predicates & p,
580             SliceFrame const& cand,
581             AbsRegion const& reg,
582             ParseAPI::Block * caller_block);
583
584     bool handleCallDetailsBackward(
585             SliceFrame & cur);
586
587     bool handleReturnBackward(
588             Predicates & p,
589             SliceFrame const& cand,
590             SliceFrame & newCand,
591             ParseAPI::Edge * e,
592             bool & err);
593
594     bool handleReturnDetailsBackward(
595             SliceFrame & cur,
596             ParseAPI::Block * caller_block);
597
598     bool followReturn(
599             Predicates & p,
600             SliceFrame const& cand,
601             ParseAPI::Block * source);
602     void handlePredecessorEdge(ParseAPI::Edge* e,
603                                Predicates& p,
604                                SliceFrame const& cand,
605                                std::vector<SliceFrame> & newCands,
606                                bool& err,
607                                SliceFrame& nf);
608   
609
610     /* general slicing support */
611   
612     void constructInitialFrame(
613             Direction dir, 
614             SliceFrame & initFrame);
615     
616     void widenAll(GraphPtr graph, Direction dir, SliceFrame const& frame);
617   
618   bool kills(AbsRegion const& reg, Assignment::Ptr &assign);
619
620   void widen(GraphPtr graph, Direction dir, Element const&source);
621
622   void insertPair(GraphPtr graph,
623                   Direction dir,
624                   Element const&source,
625                   Element const&target,
626           AbsRegion const& data);
627
628   void insertPair(GraphPtr graph,
629                   Direction dir,
630                   SliceNode::Ptr& source,
631                   SliceNode::Ptr& target,
632           AbsRegion const& data);
633
634   void convertInstruction(InstructionPtr,
635                           Address,
636                           ParseAPI::Function *,
637                           ParseAPI::Block *,
638                           std::vector<AssignmentPtr> &);
639
640   void fastForward(Location &loc, Address addr);
641
642   void fastBackward(Location &loc, Address addr);
643
644   SliceNode::Ptr widenNode();
645
646   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
647   
648   void markAsExitNode(GraphPtr ret, Element &current);
649
650   void markAsEntryNode(GraphPtr ret, Element &current);
651
652   void getInsns(Location &loc);
653
654   void getInsnsBackward(Location &loc);
655
656   void setAliases(Assignment::Ptr, Element &);
657
658   SliceNode::Ptr createNode(Element const&);
659
660   void cleanGraph(GraphPtr g);
661
662   void promotePlausibleNodes(GraphPtr g, Direction d);
663
664   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
665                             Direction dir);
666   
667
668   void insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP);
669
670   void mergeRecursiveCaches(std::map<Address, DefCache>& sc, std::map<Address, DefCache>& c, Address a);
671
672   InsnCache insnCache_;
673
674   AssignmentPtr a_;
675   ParseAPI::Block *b_;
676   ParseAPI::Function *f_;
677
678
679   // Assignments map to unique slice nodes
680   std::unordered_map<AssignmentPtr, SliceNode::Ptr, Assignment::AssignmentPtrHasher> created_;
681
682   // cache to prevent edge duplication
683   struct EdgeTupleHasher {
684     size_t operator() (const EdgeTuple& et) const {
685         size_t seed = (size_t)(et.s.get());
686         boost::hash_combine( seed , (size_t)(et.d.get()));
687         return seed;
688     }
689   };
690   std::unordered_map<EdgeTuple, int, EdgeTupleHasher> unique_edges_;
691
692   // map of previous active maps. these are used to end recursion.
693   typedef std::map<AbsRegion, std::set<Element> > PrevMap;
694   std::map<Address, PrevMap> prev_maps;
695
696   // set of plausible entry/exit nodes.
697   std::set<SliceNode::Ptr> plausibleNodes;
698
699   // a stack and set of addresses that mirror our recursion.
700   // these are used to detect loops and properly merge cache.
701   std::deque<Address> addrStack;
702   std::set<Address> addrSet;
703
704   AssignmentConverter converter;
705
706   SliceNode::Ptr widen_;
707 };
708
709 }
710
711 #endif