Various slicing fixes.
[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     // For preventing insertion of duplicate edges
364     // into the slice graph
365     struct EdgeTuple {
366         EdgeTuple(SliceNode::Ptr src, SliceNode::Ptr dst, AbsRegion const& reg)
367           : s(src), d(dst), r(reg) { }
368         bool operator<(EdgeTuple const& o) const {
369             if(s < o.s)
370                 return true;
371             else if(o.s < s)
372                 return false;
373             else if(d < o.d)
374                 return true;
375             else if(o.d < d)
376                 return false;
377             else if(r < o.r)
378                 return true;
379             else
380                 return false;
381         }
382         SliceNode::Ptr s;
383         SliceNode::Ptr d;
384         AbsRegion r;
385     };
386
387   // Shift an abs region by a given stack offset
388   void shiftAbsRegion(AbsRegion const&callerReg,
389                       AbsRegion &calleeReg,
390                       long stack_depth,
391                       ParseAPI::Function *callee);
392
393     // Shift all of the abstract regions active in the current frame
394     void shiftAllAbsRegions(
395         SliceFrame & cur,
396         long stack_depth,
397         ParseAPI::Function *callee);
398
399   /*
400    * Internal slicing support routines follow. See the
401    * implementation file for descriptions of what these
402    * routines actually do to implement slicing.
403    */
404     GraphPtr sliceInternal(Direction dir,
405             Predicates &predicates);
406     void sliceInternalAux(
407             GraphPtr g,
408             Direction dir,
409             Predicates &p,
410             SliceFrame &cand,
411             bool skip,
412             std::map<CacheEdge, std::set<AbsRegion> > & visited);
413
414     bool updateAndLink(
415             GraphPtr g,
416             Direction dir,
417             SliceFrame & cand,
418             Predicates &p);
419
420     bool stopSlicing(SliceFrame::ActiveMap& active, 
421                      GraphPtr g,
422                      Address addr,
423                      Direction dir);
424
425
426     void markVisited(
427             std::map<CacheEdge, std::set<AbsRegion> > & visited,
428             CacheEdge const& e,
429             SliceFrame::ActiveMap const& active);
430
431     void findMatch(
432             GraphPtr g,
433             Direction dir,
434             SliceFrame const& cand,
435             AbsRegion const& cur,
436             Assignment::Ptr assn,
437             std::vector<Element> & matches);
438
439     bool getNextCandidates(
440             Direction dir,
441             Predicates & p,
442             SliceFrame const& cand,
443             std::vector<SliceFrame> & newCands);
444
445     /* forward slicing */
446
447     bool getSuccessors(
448             Predicates &p,
449             SliceFrame const& cand,
450             std::vector<SliceFrame> & newCands);
451
452
453     bool handleCall(
454             Predicates & p,
455             SliceFrame & cur,
456             bool & err);
457
458     bool followCall(
459             Predicates & p,
460             ParseAPI::Block * target,
461             SliceFrame & cur);
462
463     bool handleCallDetails(
464             SliceFrame & cur,
465             ParseAPI::Block * caller_block);
466
467     bool handleReturn(
468             Predicates & p,
469             SliceFrame & cur,
470             bool & err);
471
472     void handleReturnDetails(
473             SliceFrame & cur);
474
475     bool handleDefault(
476             Direction dir,
477             Predicates & p,
478             ParseAPI::Edge * e,
479             SliceFrame & cur,
480             bool & err);
481
482     /* backwards slicing */
483
484     bool getPredecessors(
485             Predicates &p,
486             SliceFrame const& cand,
487             std::vector<SliceFrame> & newCands);
488
489     bool handleCallBackward(
490             Predicates & p,
491             SliceFrame const& cand,
492             std::vector<SliceFrame> & newCands,
493             ParseAPI::Edge * e,
494             bool & err);
495
496     std::vector<ParseAPI::Function *> followCallBackward(
497             Predicates & p,
498             SliceFrame const& cand,
499             AbsRegion const& reg,
500             ParseAPI::Block * caller_block);
501
502     bool handleCallDetailsBackward(
503             SliceFrame & cur);
504
505     bool handleReturnBackward(
506             Predicates & p,
507             SliceFrame const& cand,
508             SliceFrame & newCand,
509             ParseAPI::Edge * e,
510             bool & err);
511
512     bool handleReturnDetailsBackward(
513             SliceFrame & cur,
514             ParseAPI::Block * caller_block);
515
516     bool followReturn(
517             Predicates & p,
518             SliceFrame const& cand,
519             ParseAPI::Block * source);
520     void handlePredecessorEdge(ParseAPI::Edge* e,
521                                Predicates& p,
522                                SliceFrame const& cand,
523                                std::vector<SliceFrame> & newCands,
524                                bool& err,
525                                SliceFrame& nf);
526   
527
528     /* general slicing support */
529   
530     void constructInitialFrame(
531             Direction dir, 
532             SliceFrame & initFrame);
533     
534     void widenAll(GraphPtr graph, Direction dir, SliceFrame const& frame);
535   
536   bool kills(AbsRegion const& reg, Assignment::Ptr &assign);
537
538   void widen(GraphPtr graph, Direction dir, Element const&source);
539
540   void insertPair(GraphPtr graph,
541                   Direction dir,
542                   Element const&source,
543                   Element const&target,
544           AbsRegion const& data);
545
546   void insertPair(GraphPtr graph,
547                   Direction dir,
548                   SliceNode::Ptr& source,
549                   SliceNode::Ptr& target,
550           AbsRegion const& data);
551
552   void convertInstruction(InstructionPtr,
553                           Address,
554                           ParseAPI::Function *,
555                           ParseAPI::Block *,
556                           std::vector<AssignmentPtr> &);
557
558   void fastForward(Location &loc, Address addr);
559
560   void fastBackward(Location &loc, Address addr);
561
562   SliceNode::Ptr widenNode();
563
564   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
565   
566   void markAsExitNode(GraphPtr ret, Element &current);
567
568   void markAsEntryNode(GraphPtr ret, Element &current);
569
570   void getInsns(Location &loc);
571
572   void getInsnsBackward(Location &loc);
573
574   void setAliases(Assignment::Ptr, Element &);
575
576   SliceNode::Ptr createNode(Element const&);
577
578   void cleanGraph(GraphPtr g);
579
580   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
581                             Direction dir);
582   
583
584   void insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP);
585
586   InsnCache insnCache_;
587
588   AssignmentPtr a_;
589   ParseAPI::Block *b_;
590   ParseAPI::Function *f_;
591
592   // Assignments map to unique slice nodes
593   std::map<AssignmentPtr, SliceNode::Ptr> created_;
594
595   // cache to prevent edge duplication
596   std::map<EdgeTuple, int> unique_edges_;
597
598   // map of previous active maps. these are used to end recursion.
599   typedef std::map<AbsRegion, std::set<Element> > PrevMap;
600   std::map<Address, PrevMap> prev_maps;
601
602   AssignmentConverter converter;
603
604   SliceNode::Ptr widen_;
605 };
606
607 }
608
609 #endif