Revert "Fixes bugs related to our narrower bounds on shadowed memory"
[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
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