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