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