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