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