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