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