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 allowImprecision() { return false; }
115     DATAFLOW_EXPORT virtual bool widenAtPoint(AssignmentPtr) { return false; }
116     DATAFLOW_EXPORT virtual bool endAtPoint(AssignmentPtr) { return false; }
117     DATAFLOW_EXPORT virtual bool followCall(ParseAPI::Function * /*callee*/,
118                                            CallStack_t & /*cs*/,
119                                            AbsRegion /*argument*/) { 
120        return false; 
121     }
122     DATAFLOW_EXPORT virtual std::vector<ParseAPI::Function *> 
123         followCallBackward(ParseAPI::Block * /*callerB*/,
124             CallStack_t & /*cs*/,
125             AbsRegion /*argument*/) {
126             std::vector<ParseAPI::Function *> vec;
127             return vec;
128         }
129     DATAFLOW_EXPORT virtual bool addPredecessor(AbsRegion /*reg*/) {
130         return true;
131     }
132     DATAFLOW_EXPORT virtual bool widenAtAssignment(const AbsRegion & /*in*/,
133                                                   const AbsRegion & /*out*/) { 
134        return false; 
135     }
136     DATAFLOW_EXPORT virtual ~Predicates() {};
137   };
138
139   DATAFLOW_EXPORT GraphPtr forwardSlice(Predicates &predicates);
140   
141   DATAFLOW_EXPORT GraphPtr backwardSlice(Predicates &predicates);
142
143  private:
144
145   typedef enum {
146     forward,
147     backward } Direction;
148
149   typedef std::map<ParseAPI::Block *, InsnVec> InsnCache;
150
151
152   // Our slicing is context-sensitive; that is, if we enter
153   // a function foo from a caller bar, all return edges
154   // from foo must enter bar. This makes an assumption that
155   // the return address is not modified, but hey. 
156   // We represent this as a list of call sites. This is redundant
157   // with the image_instPoint data structure, but hopefully that
158   // one will be going away. 
159
160   struct ContextElement {
161     // We can implicitly find the callsite given a block,
162     // since calls end blocks. It's easier to look up 
163     // the successor this way than with an address.
164
165     ParseAPI::Function *func;
166
167     // If non-NULL this must be an internal context
168     // element, since we have an active call site.
169     ParseAPI::Block *block;
170
171     // To enter or leave a function we must be able to
172     // map corresponding abstract regions. 
173     // In particular, we need to know the depth of the 
174     // stack in the caller.
175     long stackDepth;
176
177   ContextElement(ParseAPI::Function *f) : 
178     func(f), block(NULL), stackDepth(-1) {};
179   ContextElement(ParseAPI::Function *f, long depth) :
180     func(f), block(NULL), stackDepth(depth) {};
181   };
182
183   // This should be sufficient...
184   typedef std::deque<ContextElement> Context;
185
186   bool getStackDepth(ParseAPI::Function *func, Address callAddr, long &height);
187
188   // Add the newly called function to the given Context.
189   void pushContext(Context &context,
190                    ParseAPI::Function *callee,
191                    ParseAPI::Block *callBlock,
192                    long stackDepth);
193
194   // And remove it as appropriate
195   void popContext(Context &context);
196
197   // Where we are in a particular search...
198   struct Location {
199     // The block we're looking through
200     ParseAPI::Function *func;
201     ParseAPI::Block *block; // current block
202
203     // Where we are in the block
204     InsnVec::iterator current;
205     InsnVec::iterator end;
206
207     bool fwd;
208
209     InsnVec::reverse_iterator rcurrent;
210     InsnVec::reverse_iterator rend;
211
212     Address addr() const { if(fwd) return current->second; else return rcurrent->second;}
213
214   Location(ParseAPI::Function *f,
215            ParseAPI::Block *b) : func(f), block(b), fwd(true){};
216   Location() : func(NULL), block(NULL), fwd(true) {};
217   };
218     
219   typedef std::queue<Location> LocList;
220  
221   // Describes an abstract region, a minimal context
222   // (block and function), and the assignment that
223   // relates to that region (uses or defines it, 
224   // depending on slice direction)
225   //
226   // A slice is composed of Elements; SliceFrames 
227   // keep a list of the currently active elements
228   // that are at the `leading edge' of the 
229   // under-construction slice
230   struct Element {
231     Element(ParseAPI::Block * b,
232         ParseAPI::Function * f,
233         AbsRegion const& r,
234         Assignment::Ptr p)
235       : block(b),
236         func(f),
237         reg(r),
238         ptr(p)
239     { }
240
241     ParseAPI::Block * block;
242     ParseAPI::Function * func;
243
244     AbsRegion reg;
245     Assignment::Ptr ptr;
246   };
247
248   // State for recursive slicing is a context, location pair
249   // and a list of AbsRegions that are being searched for.
250   struct SliceFrame {
251     SliceFrame(
252         Location const& l,
253         Context const& c)
254       : loc(l),
255         con(c),
256         valid(true)
257     { }
258     SliceFrame() : valid(true) { }
259     SliceFrame(bool v) : valid(v) { }
260
261     // Active slice nodes -- describe regions
262     // that are currently under scrutiny
263     std::map<AbsRegion, std::vector<Element> > active;
264     typedef std::map<AbsRegion, std::vector<Element> > ActiveMap;
265
266     Location loc;
267     Context con;
268     bool valid;
269
270     Address addr() const { return loc.addr(); }
271   };
272
273   // Used for keeping track of visited edges in the
274   // slicing search
275   struct CacheEdge {
276     CacheEdge(Address src, Address trg) : s(src), t(trg) { }
277     Address s;
278     Address t;
279
280     bool operator<(CacheEdge const& o) const {
281         if(s < o.s)
282             return true;
283         else if(o.s < s)
284             return false;
285         else if(t < o.t)
286             return true;
287         else
288             return false;
289     }
290   };
291
292     /* 
293      * An element that is a slicing `def' (where
294      * def means `definition' in the backward case
295      * and `use' in the forward case, along with
296      * the associated AbsRegion that labels the slicing
297      * edge.
298      *
299      * These two pieces of information, along with an 
300      * element describing the other end of the dependency,
301      * are what you need to create a slice edge.
302      */
303     struct Def {
304       Def(Element const& e, AbsRegion const& r) : ele(e), data(r) { } 
305       Element ele;
306       AbsRegion data;
307   
308       // only the Assignment::Ptr of an Element matters
309       // for comparison
310       bool operator<(Def const& o) const {
311           if(ele.ptr < o.ele.ptr)
312               return true;
313           else if(o.ele.ptr < ele.ptr)
314               return false;
315           else if(data < o.data)
316               return true;
317           else 
318               return false;
319       }
320     };
321  
322     /*
323      * A cache from AbsRegions -> Defs.
324      *
325      * Each node that has been visited in the search
326      * has a DefCache that reflects the resolution of
327      * any AbsRegions down-slice. If the node is visited
328      * again through a different search path (if the graph
329      * has fork-join structure), this caching prevents
330      * expensive recursion
331      */
332     class DefCache {
333       public:
334         DefCache() { }
335         ~DefCache() { }
336
337         // add the values from another defcache
338         void merge(DefCache const& o);
339    
340         // replace mappings in this cache with those
341         // from another 
342         void replace(DefCache const& o);
343
344         std::set<Def> & get(AbsRegion const& r) { 
345             return defmap[r];
346         }
347         bool defines(AbsRegion const& r) const {
348             return defmap.find(r) != defmap.end();
349         }
350
351         void print() const;
352
353       private:
354         std::map< AbsRegion, std::set<Def> > defmap;
355     
356     };
357
358     // For preventing insertion of duplicate edges
359     // into the slice graph
360     struct EdgeTuple {
361         EdgeTuple(SliceNode::Ptr src, SliceNode::Ptr dst, AbsRegion const& reg)
362           : s(src), d(dst), r(reg) { }
363         bool operator<(EdgeTuple const& o) const {
364             if(s < o.s)
365                 return true;
366             else if(o.s < s)
367                 return false;
368             else if(d < o.d)
369                 return true;
370             else if(o.d < d)
371                 return false;
372             else if(r < o.r)
373                 return true;
374             else
375                 return false;
376         }
377         SliceNode::Ptr s;
378         SliceNode::Ptr d;
379         AbsRegion r;
380     };
381
382   // Shift an abs region by a given stack offset
383   void shiftAbsRegion(AbsRegion const&callerReg,
384                       AbsRegion &calleeReg,
385                       long stack_depth,
386                       ParseAPI::Function *callee);
387
388     // Shift all of the abstract regions active in the current frame
389     void shiftAllAbsRegions(
390         SliceFrame & cur,
391         long stack_depth,
392         ParseAPI::Function *callee);
393
394   /*
395    * Internal slicing support routines follow. See the
396    * implementation file for descriptions of what these
397    * routines actually do to implement slicing.
398    */
399     GraphPtr sliceInternal(Direction dir,
400             Predicates &predicates);
401     void sliceInternalAux(
402             GraphPtr g,
403             Direction dir,
404             Predicates &p,
405             SliceFrame &cand,
406             bool skip,
407             std::map<CacheEdge, std::set<AbsRegion> > & visited,
408             std::map<Address,DefCache> & cache);
409
410     bool updateAndLink(
411             GraphPtr g,
412             Direction dir,
413             SliceFrame & cand,
414             DefCache & cache,
415             Predicates &p);
416
417     void updateAndLinkFromCache(
418             GraphPtr g,
419             Direction dir,
420             SliceFrame & f,
421             DefCache & cache);
422
423     void removeBlocked(
424             SliceFrame & f,
425             std::set<AbsRegion> const& block);
426
427     void markVisited(
428             std::map<CacheEdge, std::set<AbsRegion> > & visited,
429             CacheEdge const& e,
430             SliceFrame::ActiveMap const& active);
431
432     void cachePotential(
433             Direction dir,
434             Assignment::Ptr assn,
435             DefCache & cache);
436
437     void findMatch(
438             GraphPtr g,
439             Direction dir,
440             SliceFrame const& cand,
441             AbsRegion const& cur,
442             Assignment::Ptr assn,
443             std::vector<Element> & matches,
444             DefCache & cache);
445
446     bool getNextCandidates(
447             Direction dir,
448             Predicates & p,
449             SliceFrame const& cand,
450             std::vector<SliceFrame> & newCands);
451
452     /* forward slicing */
453
454     bool getSuccessors(
455             Predicates &p,
456             SliceFrame const& cand,
457             std::vector<SliceFrame> & newCands);
458
459
460     bool handleCall(
461             Predicates & p,
462             SliceFrame & cur,
463             bool & err);
464
465     bool followCall(
466             Predicates & p,
467             ParseAPI::Block * target,
468             SliceFrame & cur);
469
470     bool handleCallDetails(
471             SliceFrame & cur,
472             ParseAPI::Block * caller_block);
473
474     bool handleReturn(
475             Predicates & p,
476             SliceFrame & cur,
477             bool & err);
478
479     void handleReturnDetails(
480             SliceFrame & cur);
481
482     bool handleDefault(
483             Direction dir,
484             Predicates & p,
485             ParseAPI::Edge * e,
486             SliceFrame & cur,
487             bool & err);
488
489     /* backwards slicing */
490
491     bool getPredecessors(
492             Predicates &p,
493             SliceFrame const& cand,
494             std::vector<SliceFrame> & newCands);
495
496     bool handleCallBackward(
497             Predicates & p,
498             SliceFrame const& cand,
499             std::vector<SliceFrame> & newCands,
500             ParseAPI::Edge * e,
501             bool & err);
502
503     std::vector<ParseAPI::Function *> followCallBackward(
504             Predicates & p,
505             SliceFrame const& cand,
506             AbsRegion const& reg,
507             ParseAPI::Block * caller_block);
508
509     bool handleCallDetailsBackward(
510             SliceFrame & cur);
511
512     bool handleReturnBackward(
513             Predicates & p,
514             SliceFrame const& cand,
515             SliceFrame & newCand,
516             ParseAPI::Edge * e,
517             bool & err);
518
519     bool handleReturnDetailsBackward(
520             SliceFrame & cur,
521             ParseAPI::Block * caller_block);
522
523     bool followReturn(
524             Predicates & p,
525             SliceFrame const& cand,
526             ParseAPI::Block * source);
527
528     /* general slicing support */
529   
530     void constructInitialFrame(
531             Direction dir, 
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