Fix memory leak in memory emulation; add a predicate to widen slices before we chase...
[dyninst.git] / dataflowAPI / h / slicing.h
1 // A simple forward slice using a search of the control flow graph.
2 // Templated on a function that says when to stop slicing.
3
4 #if !defined(_SLICING_H_)
5 #define _SLICING_H_
6
7 #include "dyn_detail/boost/shared_ptr.hpp"
8 #include <vector>
9 #include "dyntypes.h"
10 #include <queue>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <stack>
15
16 #include "util.h"
17 #include "Node.h"
18 #include "Edge.h"
19
20 #include "AbslocInterface.h"
21
22
23 namespace Dyninst {
24
25 namespace ParseAPI {
26   class Block;
27   class Edge;
28   class Function;
29 };
30
31 class Assignment;
32 class AbsRegion;
33 typedef dyn_detail::boost::shared_ptr<Assignment> AssignmentPtr;
34
35 class Graph;
36 typedef dyn_detail::boost::shared_ptr<Graph> GraphPtr;
37
38 class InstructionAPI::Instruction;
39 typedef dyn_detail::boost::shared_ptr<InstructionAPI::Instruction> InstructionPtr;
40
41 // Used in temp slicer; should probably
42 // replace OperationNodes when we fix up
43 // the DDG code.
44 class SliceNode : public Node {
45  public:
46   typedef dyn_detail::boost::shared_ptr<SliceNode> Ptr;
47       
48   DATAFLOW_EXPORT static SliceNode::Ptr create(AssignmentPtr ptr,
49                                 ParseAPI::Block *block,
50                                 ParseAPI::Function *func) {
51     return Ptr(new SliceNode(ptr, block, func));
52   }
53       
54   DATAFLOW_EXPORT ParseAPI::Block *block() const { return b_; };
55   DATAFLOW_EXPORT ParseAPI::Function *func() const { return f_; };
56   DATAFLOW_EXPORT Address addr() const;
57   DATAFLOW_EXPORT AssignmentPtr assign() const { return a_; }
58       
59   DATAFLOW_EXPORT Node::Ptr copy() { return Node::Ptr(); }
60   DATAFLOW_EXPORT bool isVirtual() const { return false; }
61       
62   DATAFLOW_EXPORT std::string format() const;
63       
64   DATAFLOW_EXPORT virtual ~SliceNode() {};
65       
66  private:
67       
68  SliceNode(AssignmentPtr ptr,
69             ParseAPI::Block *block,
70             ParseAPI::Function *func) : 
71   a_(ptr), b_(block), f_(func) {};
72       
73   AssignmentPtr a_;
74   ParseAPI::Block *b_;
75   ParseAPI::Function *f_;
76       
77   // This is ugly and should be cleaned up once we've figured
78   // out how to move forward on edge classes
79   std::map<SliceNode::Ptr, unsigned> assignMap_;
80 };
81
82 class SliceEdge : public Edge {
83   public:
84    typedef dyn_detail::boost::shared_ptr<SliceEdge> Ptr;
85
86    DATAFLOW_EXPORT static SliceEdge::Ptr create(SliceNode::Ptr source,
87                                                 SliceNode::Ptr target,
88                                                 AbsRegion &data) {
89       return Ptr(new SliceEdge(source, target, data)); 
90    }
91
92    const AbsRegion &data() const { return data_; };
93
94   private:
95    SliceEdge(const SliceNode::Ptr source, 
96              const SliceNode::Ptr target,
97              AbsRegion data) 
98       : Edge(source, target), data_(data) {};
99    AbsRegion data_;
100 };
101
102 class Slicer {
103  public:
104   typedef std::pair<InstructionPtr, Address> InsnInstance;
105   typedef std::vector<InsnInstance> InsnVec;
106
107   DATAFLOW_EXPORT Slicer(AssignmentPtr a,
108          ParseAPI::Block *block,
109          ParseAPI::Function *func);
110     
111   DATAFLOW_EXPORT static bool isWidenNode(Node::Ptr n);
112
113   class Predicates {
114   public:
115     typedef std::pair<ParseAPI::Function *, int> StackDepth_t;
116     typedef std::stack<StackDepth_t> CallStack_t;
117
118     DATAFLOW_EXPORT virtual bool allowImprecision() { return false; }
119     DATAFLOW_EXPORT virtual bool widenAtPoint(AssignmentPtr) { return false; }
120     DATAFLOW_EXPORT virtual bool endAtPoint(AssignmentPtr) { return false; }
121     DATAFLOW_EXPORT virtual bool followCall(ParseAPI::Function * /*callee*/,
122                                            CallStack_t & /*cs*/,
123                                            AbsRegion /*argument*/) { 
124        return false; 
125     }
126     DATAFLOW_EXPORT virtual std::vector<ParseAPI::Function *> 
127         followCallBackward(ParseAPI::Block * /*callerB*/,
128             CallStack_t & /*cs*/,
129             AbsRegion /*argument*/) {
130             std::vector<ParseAPI::Function *> vec;
131             return vec;
132         }
133     DATAFLOW_EXPORT virtual bool addPredecessor(AbsRegion reg) {
134         return true;
135     }
136     DATAFLOW_EXPORT virtual bool widenAtAssignment(const AbsRegion & /*in*/,
137                                                   const AbsRegion & /*out*/) { 
138        return false; 
139     }
140     DATAFLOW_EXPORT virtual ~Predicates() {};
141   };
142
143   DATAFLOW_EXPORT GraphPtr forwardSlice(Predicates &predicates);
144   
145   DATAFLOW_EXPORT GraphPtr backwardSlice(Predicates &predicates);
146
147  private:
148
149   typedef enum {
150     forward,
151     backward } Direction;
152
153   typedef std::map<ParseAPI::Block *, InsnVec> InsnCache;
154
155
156   // Our slicing is context-sensitive; that is, if we enter
157   // a function foo from a caller bar, all return edges
158   // from foo must enter bar. This makes an assumption that
159   // the return address is not modified, but hey. 
160   // We represent this as a list of call sites. This is redundant
161   // with the image_instPoint data structure, but hopefully that
162   // one will be going away. 
163
164   struct ContextElement {
165     // We can implicitly find the callsite given a block,
166     // since calls end blocks. It's easier to look up 
167     // the successor this way than with an address.
168
169     ParseAPI::Function *func;
170
171     // If non-NULL this must be an internal context
172     // element, since we have an active call site.
173     ParseAPI::Block *block;
174
175     // To enter or leave a function we must be able to
176     // map corresponding abstract regions. 
177     // In particular, we need to know the depth of the 
178     // stack in the caller.
179     long stackDepth;
180
181   ContextElement(ParseAPI::Function *f) : 
182     func(f), block(NULL), stackDepth(-1) {};
183   ContextElement(ParseAPI::Function *f, long depth) :
184     func(f), block(NULL), stackDepth(depth) {};
185   };
186
187   // This should be sufficient...
188   typedef std::deque<ContextElement> Context;
189
190   bool getStackDepth(ParseAPI::Function *func, Address callAddr, long &height);
191
192   // Add the newly called function to the given Context.
193   void pushContext(Context &context,
194                    ParseAPI::Function *callee,
195                    ParseAPI::Block *callBlock,
196                    long stackDepth);
197
198   // And remove it as appropriate
199   void popContext(Context &context);
200
201   // Shift an abs region by a given stack offset
202   void shiftAbsRegion(AbsRegion &callerReg,
203                       AbsRegion &calleeReg,
204                       long stack_depth,
205                       ParseAPI::Function *callee);
206
207   // Handling a call does two things:
208   // 1) Translates the given AbsRegion into the callee-side
209   //    view; this just means adjusting stack locations. 
210   // 2) Increases the given context
211   // Returns false if we didn't translate the absregion correctly
212   bool handleCallDetails(AbsRegion &reg,
213                          Context &context,
214                          ParseAPI::Block *callerBlock,
215                          ParseAPI::Function *callee);
216
217   bool handleCallDetailsBackward(AbsRegion &reg,
218                                 Context &context,
219                                 ParseAPI::Block * callBlock,
220                                 ParseAPI::Function * caller);
221
222   // Where we are in a particular search...
223   struct Location {
224     // The block we're looking through
225     ParseAPI::Function *func;
226     ParseAPI::Block *block; // current block
227
228     // Where we are in the block
229     InsnVec::iterator current;
230     InsnVec::iterator end;
231
232     bool fwd;
233
234     InsnVec::reverse_iterator rcurrent;
235     InsnVec::reverse_iterator rend;
236
237     Address addr() const { if(fwd) return current->second; else return rcurrent->second;}
238
239   Location(ParseAPI::Function *f,
240            ParseAPI::Block *b) : func(f), block(b), fwd(true){};
241   Location() : func(NULL), block(NULL), fwd(true) {};
242   };
243     
244   typedef std::queue<Location> LocList;
245   
246   // And the tuple of (context, AbsRegion, Location)
247   // that specifies both context and what to search for
248   // in that context
249   struct Element {
250   Element() : valid(true) {};
251     Location loc;
252     Context con;
253     AbsRegion reg;
254     // This is for returns, and not for the intermediate
255     // steps. OTOH, I'm being a bit lazy...
256     Assignment::Ptr ptr;
257      AbsRegion inputRegion;
258      bool valid;
259     Address addr() const { return loc.addr(); }
260   };
261
262   typedef std::queue<Element> Elements;
263
264   GraphPtr sliceInternal(Direction dir,
265                          Predicates &predicates);
266   
267   bool getMatchingElements(Element &initial, Elements &worklist,
268                            Predicates &p, Direction dir);
269   
270   bool getNextCandidates(Element &initial, Elements &worklist,
271                          Predicates &p, Direction dir);
272
273   bool findMatches(Element &current, Assignment::Ptr &assign, 
274                    Direction dir,  Predicates &p, Elements &succ); 
275
276   bool kills(Element &current, Assignment::Ptr &assign);
277
278   bool followCall(ParseAPI::Block *b,
279                   Direction d,
280                   Element &current,
281                   Predicates &p);
282   
283   std::vector<ParseAPI::Function *> 
284       followCallBackward(ParseAPI::Block * callerBlock,
285               Direction d,
286               Element &current,
287               Predicates &p);
288
289   bool followReturn(ParseAPI::Block *b,
290                     Direction d,
291                     Element &current,
292                     Predicates &p);
293
294   bool handleDefault(ParseAPI::Edge *e,
295                      Direction dir,
296                      Element &current,
297                      Element &newElement,
298                      Predicates &p,
299                      bool &err);
300                 
301   bool handleCall(ParseAPI::Block *block,
302                   Element &current,
303                   Element &newElement,
304                   Predicates &p,
305                   bool &err);
306
307   bool handleCallBackward(ParseAPI::Edge *e,
308                           Element &current,
309                           Elements &newElements,
310                           Predicates &p,
311                           bool &err);
312
313   bool handleReturn(ParseAPI::Block *b,
314                     Element &current,
315                     Element &newElement,
316                     Predicates &p,
317                     bool &err);
318
319   bool handleReturnBackward(ParseAPI::Edge *e,
320                             Element &current,
321                             Element &newElement,
322                             Predicates &p,
323                             bool &err);
324
325   void handleReturnDetails(AbsRegion &reg,
326                            Context &context);
327
328   bool handleReturnDetailsBackward(AbsRegion &reg,
329                                     Context &context,
330                                     ParseAPI::Block *callBlock,
331                                     ParseAPI::Function *callee);
332
333   bool getSuccessors(Element &current,
334                      Elements &worklist,
335                      Predicates &p);
336
337   bool getPredecessors(Element &current,
338                        Elements &worklist,
339                        Predicates &p);
340
341   bool search(Element &current,
342               Elements &foundList,
343               Predicates &p,
344               Direction dir);
345
346   void widen(GraphPtr graph, Direction dir, Element &source);
347
348   void insertPair(GraphPtr graph,
349                   Direction dir,
350                   Element &source,
351                   Element &target);
352
353   void convertInstruction(InstructionPtr,
354                           Address,
355                           ParseAPI::Function *,
356                           std::vector<AssignmentPtr> &);
357
358   void fastForward(Location &loc, Address addr);
359
360   void fastBackward(Location &loc, Address addr);
361
362   SliceNode::Ptr widenNode();
363
364   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
365   
366   void markAsExitNode(GraphPtr ret, Element &current);
367
368   void markAsEntryNode(GraphPtr ret, Element &current);
369
370   void getInsns(Location &loc);
371
372   void getInsnsBackward(Location &loc);
373
374   void setAliases(Assignment::Ptr, Element &);
375
376   SliceNode::Ptr createNode(Element &);
377
378   void cleanGraph(GraphPtr g);
379
380   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
381                             Direction dir);
382   
383   void constructInitialElement(Element &initial, Direction dir);
384
385   void insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP);
386
387   InsnCache insnCache_;
388
389   AssignmentPtr a_;
390   ParseAPI::Block *b_;
391   ParseAPI::Function *f_;
392
393   std::set<SliceNode::Ptr> visited_;
394   std::map<AssignmentPtr, SliceNode::Ptr> created_;
395
396   AssignmentConverter converter;
397
398   SliceNode::Ptr widen_;
399 };
400 };
401
402 #endif