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