Change to use unordered_map for indexing slice nodes and slice edges
[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 <unordered_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 DATAFLOW_EXPORT SliceNode : public Node {
76  public:
77   typedef boost::shared_ptr<SliceNode> Ptr;
78       
79   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   ParseAPI::Block *block() const { return b_; };
86   ParseAPI::Function *func() const { return f_; };
87   Address addr() const;
88   AssignmentPtr assign() const { return a_; }
89       
90   Node::Ptr copy() { return Node::Ptr(); }
91   bool isVirtual() const { return false; }
92       
93   std::string format() const;
94       
95   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   // 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      int 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         bool operator == (EdgeTuple const &o) const {
408             if (s != o.s) return false;
409             if (d != o.d) return false;
410             return r == o.r;
411         }
412         SliceNode::Ptr s;
413         SliceNode::Ptr d;
414         AbsRegion r;
415     };
416
417   // Shift an abs region by a given stack offset
418   void shiftAbsRegion(AbsRegion const&callerReg,
419                       AbsRegion &calleeReg,
420                       long stack_depth,
421                       ParseAPI::Function *callee);
422
423     // Shift all of the abstract regions active in the current frame
424     void shiftAllAbsRegions(
425         SliceFrame & cur,
426         long stack_depth,
427         ParseAPI::Function *callee);
428
429   /*
430    * Internal slicing support routines follow. See the
431    * implementation file for descriptions of what these
432    * routines actually do to implement slicing.
433    */
434     GraphPtr sliceInternal(Direction dir,
435             Predicates &predicates);
436     void sliceInternalAux(
437             GraphPtr g,
438             Direction dir,
439             Predicates &p,
440             SliceFrame &cand,
441             bool skip,
442             std::map<CacheEdge, std::set<AbsRegion> > & visited,
443             std::map<Address,DefCache> & cache);
444
445     bool updateAndLink(
446             GraphPtr g,
447             Direction dir,
448             SliceFrame & cand,
449             DefCache & cache,
450             Predicates &p);
451
452     void updateAndLinkFromCache(
453             GraphPtr g,
454             Direction dir,
455             SliceFrame & f,
456             DefCache & cache);
457
458     void removeBlocked(
459             SliceFrame & f,
460             std::set<AbsRegion> const& block);
461
462     void markVisited(
463             std::map<CacheEdge, std::set<AbsRegion> > & visited,
464             CacheEdge const& e,
465             SliceFrame::ActiveMap const& active);
466
467     void cachePotential(
468             Direction dir,
469             Assignment::Ptr assn,
470             DefCache & cache);
471
472     void findMatch(
473             GraphPtr g,
474             Direction dir,
475             SliceFrame const& cand,
476             AbsRegion const& cur,
477             Assignment::Ptr assn,
478             std::vector<Element> & matches,
479             DefCache & cache);
480
481     bool getNextCandidates(
482             Direction dir,
483             Predicates & p,
484             SliceFrame const& cand,
485             std::vector<SliceFrame> & newCands);
486
487     /* forward slicing */
488
489     bool getSuccessors(
490             Predicates &p,
491             SliceFrame const& cand,
492             std::vector<SliceFrame> & newCands);
493
494
495     bool handleCall(
496             Predicates & p,
497             SliceFrame & cur,
498             bool & err);
499
500     bool followCall(
501             Predicates & p,
502             ParseAPI::Block * target,
503             SliceFrame & cur);
504
505     bool handleCallDetails(
506             SliceFrame & cur,
507             ParseAPI::Block * caller_block);
508
509     bool handleReturn(
510             Predicates & p,
511             SliceFrame & cur,
512             bool & err);
513
514     void handleReturnDetails(
515             SliceFrame & cur);
516
517     bool handleDefault(
518             Direction dir,
519             Predicates & p,
520             ParseAPI::Edge * e,
521             SliceFrame & cur,
522             bool & err);
523
524     /* backwards slicing */
525
526     bool getPredecessors(
527             Predicates &p,
528             SliceFrame const& cand,
529             std::vector<SliceFrame> & newCands);
530
531     bool handleCallBackward(
532             Predicates & p,
533             SliceFrame const& cand,
534             std::vector<SliceFrame> & newCands,
535             ParseAPI::Edge * e,
536             bool & err);
537
538     std::vector<ParseAPI::Function *> followCallBackward(
539             Predicates & p,
540             SliceFrame const& cand,
541             AbsRegion const& reg,
542             ParseAPI::Block * caller_block);
543
544     bool handleCallDetailsBackward(
545             SliceFrame & cur);
546
547     bool handleReturnBackward(
548             Predicates & p,
549             SliceFrame const& cand,
550             SliceFrame & newCand,
551             ParseAPI::Edge * e,
552             bool & err);
553
554     bool handleReturnDetailsBackward(
555             SliceFrame & cur,
556             ParseAPI::Block * caller_block);
557
558     bool followReturn(
559             Predicates & p,
560             SliceFrame const& cand,
561             ParseAPI::Block * source);
562     void handlePredecessorEdge(ParseAPI::Edge* e,
563                                Predicates& p,
564                                SliceFrame const& cand,
565                                std::vector<SliceFrame> & newCands,
566                                bool& err,
567                                SliceFrame& nf);
568   
569
570     /* general slicing support */
571   
572     void constructInitialFrame(
573             Direction dir, 
574             SliceFrame & initFrame);
575     
576     void widenAll(GraphPtr graph, Direction dir, SliceFrame const& frame);
577   
578   bool kills(AbsRegion const& reg, Assignment::Ptr &assign);
579
580   void widen(GraphPtr graph, Direction dir, Element const&source);
581
582   void insertPair(GraphPtr graph,
583                   Direction dir,
584                   Element const&source,
585                   Element const&target,
586           AbsRegion const& data);
587
588   void convertInstruction(InstructionPtr,
589                           Address,
590                           ParseAPI::Function *,
591                           ParseAPI::Block *,
592                           std::vector<AssignmentPtr> &);
593
594   void fastForward(Location &loc, Address addr);
595
596   void fastBackward(Location &loc, Address addr);
597
598   SliceNode::Ptr widenNode();
599
600   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
601   
602   void markAsExitNode(GraphPtr ret, Element &current);
603
604   void markAsEntryNode(GraphPtr ret, Element &current);
605
606   void getInsns(Location &loc);
607
608   void getInsnsBackward(Location &loc);
609
610   void setAliases(Assignment::Ptr, Element &);
611
612   SliceNode::Ptr createNode(Element const&);
613
614   void cleanGraph(GraphPtr g);
615
616   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
617                             Direction dir);
618   
619
620   void insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP);
621
622   InsnCache insnCache_;
623
624   AssignmentPtr a_;
625   ParseAPI::Block *b_;
626   ParseAPI::Function *f_;
627
628
629   // Assignments map to unique slice nodes
630   struct AssignmentHasher {
631     size_t operator() (const AssignmentPtr &ap) const {
632       return (size_t)ap.get();
633     }
634   };
635   std::unordered_map<AssignmentPtr, SliceNode::Ptr, AssignmentHasher> created_;
636
637   // cache to prevent edge duplication
638   struct EdgeTupleHasher {
639     size_t operator() (const EdgeTuple& et) const {
640         size_t seed = (size_t)et.d.get();
641         return (size_t)(et.s.get()) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
642     }
643   };
644   std::unordered_map<EdgeTuple, int, EdgeTupleHasher> unique_edges_;
645
646   AssignmentConverter converter;
647
648   SliceNode::Ptr widen_;
649 };
650
651 }
652
653 #endif