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