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