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