Check widen/end predicates in slicing; don't assert fail if a widen node is encounter...
[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             Predicates &p);
415
416     void updateAndLinkFromCache(
417             GraphPtr g,
418             Direction dir,
419             SliceFrame & f,
420             DefCache & cache);
421
422     void removeBlocked(
423             SliceFrame & f,
424             std::set<AbsRegion> const& block);
425
426     void markVisited(
427             std::map<CacheEdge, std::set<AbsRegion> > & visited,
428             CacheEdge const& e,
429             SliceFrame::ActiveMap const& active);
430
431     void cachePotential(
432             Direction dir,
433             Assignment::Ptr assn,
434             DefCache & cache);
435
436     void findMatch(
437             GraphPtr g,
438             Direction dir,
439             SliceFrame const& cand,
440             AbsRegion const& cur,
441             Assignment::Ptr assn,
442             std::vector<Element> & matches,
443             DefCache & cache);
444
445     bool getNextCandidates(
446             Direction dir,
447             Predicates & p,
448             SliceFrame const& cand,
449             std::vector<SliceFrame> & newCands);
450
451     /* forward slicing */
452
453     bool getSuccessors(
454             Predicates &p,
455             SliceFrame const& cand,
456             std::vector<SliceFrame> & newCands);
457
458
459     bool handleCall(
460             Predicates & p,
461             SliceFrame & cur,
462             bool & err);
463
464     bool followCall(
465             Predicates & p,
466             ParseAPI::Block * target,
467             SliceFrame & cur);
468
469     bool handleCallDetails(
470             SliceFrame & cur,
471             ParseAPI::Block * caller_block);
472
473     bool handleReturn(
474             Predicates & p,
475             SliceFrame & cur,
476             bool & err);
477
478     void handleReturnDetails(
479             SliceFrame & cur);
480
481     bool handleDefault(
482             Direction dir,
483             Predicates & p,
484             ParseAPI::Edge * e,
485             SliceFrame & cur,
486             bool & err);
487
488     /* backwards slicing */
489
490     bool getPredecessors(
491             Predicates &p,
492             SliceFrame const& cand,
493             std::vector<SliceFrame> & newCands);
494
495     bool handleCallBackward(
496             Predicates & p,
497             SliceFrame const& cand,
498             std::vector<SliceFrame> & newCands,
499             ParseAPI::Edge * e,
500             bool & err);
501
502     std::vector<ParseAPI::Function *> followCallBackward(
503             Predicates & p,
504             SliceFrame const& cand,
505             AbsRegion const& reg,
506             ParseAPI::Block * caller_block);
507
508     bool handleCallDetailsBackward(
509             SliceFrame & cur);
510
511     bool handleReturnBackward(
512             Predicates & p,
513             SliceFrame const& cand,
514             SliceFrame & newCand,
515             ParseAPI::Edge * e,
516             bool & err);
517
518     bool handleReturnDetailsBackward(
519             SliceFrame & cur,
520             ParseAPI::Block * caller_block);
521
522     bool followReturn(
523             Predicates & p,
524             SliceFrame const& cand,
525             ParseAPI::Block * source);
526
527     /* general slicing support */
528   
529     void constructInitialFrame(
530             Direction dir, 
531             SliceFrame & initFrame);
532     
533     void widenAll(GraphPtr graph, Direction dir, SliceFrame const& frame);
534   
535   bool kills(AbsRegion const& reg, Assignment::Ptr &assign);
536
537   void widen(GraphPtr graph, Direction dir, Element const&source);
538
539   void insertPair(GraphPtr graph,
540                   Direction dir,
541                   Element const&source,
542                   Element const&target,
543           AbsRegion const& data);
544
545   void convertInstruction(InstructionPtr,
546                           Address,
547                           ParseAPI::Function *,
548                           std::vector<AssignmentPtr> &);
549
550   void fastForward(Location &loc, Address addr);
551
552   void fastBackward(Location &loc, Address addr);
553
554   SliceNode::Ptr widenNode();
555
556   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
557   
558   void markAsExitNode(GraphPtr ret, Element &current);
559
560   void markAsEntryNode(GraphPtr ret, Element &current);
561
562   void getInsns(Location &loc);
563
564   void getInsnsBackward(Location &loc);
565
566   void setAliases(Assignment::Ptr, Element &);
567
568   SliceNode::Ptr createNode(Element const&);
569
570   void cleanGraph(GraphPtr g);
571
572   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
573                             Direction dir);
574   
575
576   void insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP);
577
578   InsnCache insnCache_;
579
580   AssignmentPtr a_;
581   ParseAPI::Block *b_;
582   ParseAPI::Function *f_;
583
584   // Assignments map to unique slice nodes
585   std::map<AssignmentPtr, SliceNode::Ptr> created_;
586
587   // cache to prevent edge duplication
588   std::map<EdgeTuple, int> unique_edges_;
589
590   AssignmentConverter converter;
591
592   SliceNode::Ptr widen_;
593 };
594
595 }
596
597 #endif