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