Build DataflowAPI as part of ParseAPI to remove circular dependency
[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 bool widenAtAssignment(const AbsRegion & /*in*/,
113                                                   const AbsRegion & /*out*/) { 
114        return false; 
115     }
116     DATAFLOW_EXPORT virtual ~Predicates() {};
117   };
118
119   DATAFLOW_EXPORT GraphPtr forwardSlice(Predicates &predicates);
120   
121   DATAFLOW_EXPORT GraphPtr backwardSlice(Predicates &predicates);
122
123  private:
124
125   typedef enum {
126     forward,
127     backward } Direction;
128
129   typedef std::map<ParseAPI::Block *, InsnVec> InsnCache;
130
131
132   // Our slicing is context-sensitive; that is, if we enter
133   // a function foo from a caller bar, all return edges
134   // from foo must enter bar. This makes an assumption that
135   // the return address is not modified, but hey. 
136   // We represent this as a list of call sites. This is redundant
137   // with the image_instPoint data structure, but hopefully that
138   // one will be going away. 
139
140   struct ContextElement {
141     // We can implicitly find the callsite given a block,
142     // since calls end blocks. It's easier to look up 
143     // the successor this way than with an address.
144
145     ParseAPI::Function *func;
146
147     // If non-NULL this must be an internal context
148     // element, since we have an active call site.
149     ParseAPI::Block *block;
150
151     // To enter or leave a function we must be able to
152     // map corresponding abstract regions. 
153     // In particular, we need to know the depth of the 
154     // stack in the caller.
155     long stackDepth;
156
157   ContextElement(ParseAPI::Function *f) : 
158     func(f), block(NULL), stackDepth(-1) {};
159   ContextElement(ParseAPI::Function *f, long depth) :
160     func(f), block(NULL), stackDepth(depth) {};
161   };
162
163   // This should be sufficient...
164   typedef std::deque<ContextElement> Context;
165
166   bool getStackDepth(ParseAPI::Function *func, Address callAddr, long &height);
167
168   // Add the newly called function to the given Context.
169   void pushContext(Context &context,
170                    ParseAPI::Function *callee,
171                    ParseAPI::Block *callBlock,
172                    long stackDepth);
173
174   // And remove it as appropriate
175   void popContext(Context &context);
176
177   // Shift an abs region by a given stack offset
178   void shiftAbsRegion(AbsRegion &callerReg,
179                       AbsRegion &calleeReg,
180                       long stack_depth,
181                       ParseAPI::Function *callee);
182
183   // Handling a call does two things:
184   // 1) Translates the given AbsRegion into the callee-side
185   //    view; this just means adjusting stack locations. 
186   // 2) Increases the given context
187   // Returns false if we didn't translate the absregion correctly
188   bool handleCallDetails(AbsRegion &reg,
189                          Context &context,
190                          ParseAPI::Block *callerBlock,
191                          ParseAPI::Function *callee);
192
193   void handleCallDetailsBackward(AbsRegion &reg,
194                                 Context &context);
195
196   // Where we are in a particular search...
197   struct Location {
198     // The block we're looking through
199     ParseAPI::Function *func;
200     ParseAPI::Block *block; // current block
201
202     // Where we are in the block
203     InsnVec::iterator current;
204     InsnVec::iterator end;
205
206     bool fwd;
207
208     InsnVec::reverse_iterator rcurrent;
209     InsnVec::reverse_iterator rend;
210
211     Address addr() const { if(fwd) return current->second; else return rcurrent->second;}
212
213   Location(ParseAPI::Function *f,
214            ParseAPI::Block *b) : func(f), block(b), fwd(true){};
215   Location() : func(NULL), block(NULL), fwd(true) {};
216   };
217     
218   typedef std::queue<Location> LocList;
219   
220   // And the tuple of (context, AbsRegion, Location)
221   // that specifies both context and what to search for
222   // in that context
223   struct Element {
224     Location loc;
225     Context con;
226     AbsRegion reg;
227     // This is for returns, and not for the intermediate
228     // steps. OTOH, I'm being a bit lazy...
229     Assignment::Ptr ptr;
230     unsigned usedIndex;
231     Address addr() const { return loc.addr(); }
232   };
233
234   typedef std::queue<Element> Elements;
235
236   GraphPtr sliceInternal(Direction dir,
237                          Predicates &predicates);
238   
239   bool getMatchingElements(Element &initial, Elements &worklist,
240                            Predicates &p, Direction dir);
241   
242   bool getNextCandidates(Element &initial, Elements &worklist,
243                          Predicates &p, Direction dir);
244
245   void findMatches(Element &current, Assignment::Ptr &assign, 
246                    Direction dir, int index, Elements &succ); 
247
248   bool kills(Element &current, Assignment::Ptr &assign);
249
250   bool followCall(ParseAPI::Block *b,
251                   Direction d,
252                   Element &current,
253                   Predicates &p);
254
255   bool followReturn(ParseAPI::Block *b,
256                     Direction d,
257                     Element &current,
258                     Predicates &p);
259
260   bool handleDefault(ParseAPI::Edge *e,
261                      Direction dir,
262                      Element &current,
263                      Element &newElement,
264                      Predicates &p,
265                      bool &err);
266                 
267   bool handleCall(ParseAPI::Block *block,
268                   Element &current,
269                   Element &newElement,
270                   Predicates &p,
271                   bool &err);
272
273   bool handleCallBackward(ParseAPI::Edge *e,
274                           Element &current,
275                           Elements &newElements,
276                           Predicates &p,
277                           bool &err);
278
279   bool handleReturn(ParseAPI::Block *b,
280                     Element &current,
281                     Element &newElement,
282                     Predicates &p,
283                     bool &err);
284
285   bool handleReturnBackward(ParseAPI::Edge *e,
286                             Element &current,
287                             Element &newElement,
288                             Predicates &p,
289                             bool &err);
290
291   void handleReturnDetails(AbsRegion &reg,
292                            Context &context);
293
294   bool handleReturnDetailsBackward(AbsRegion &reg,
295                                     Context &context,
296                                     ParseAPI::Block *callBlock,
297                                     ParseAPI::Function *callee);
298
299   bool getSuccessors(Element &current,
300                      Elements &worklist,
301                      Predicates &p);
302
303   bool getPredecessors(Element &current,
304                        Elements &worklist,
305                        Predicates &p);
306
307   bool search(Element &current,
308               Elements &foundList,
309               Predicates &p,
310               int index,
311               Direction dir);
312
313   void widen(GraphPtr graph, Direction dir, Element &source);
314
315   void insertPair(GraphPtr graph,
316                   Direction dir,
317                   Element &source,
318                   Element &target);
319
320   void convertInstruction(InstructionPtr,
321                           Address,
322                           ParseAPI::Function *,
323                           std::vector<AssignmentPtr> &);
324
325   void fastForward(Location &loc, Address addr);
326
327   void fastBackward(Location &loc, Address addr);
328
329   AssignNode::Ptr widenNode();
330
331   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
332   
333   void markAsExitNode(GraphPtr ret, Element &current);
334
335   void markAsEntryNode(GraphPtr ret, Element &current);
336
337   void getInsns(Location &loc);
338
339   void getInsnsBackward(Location &loc);
340
341   void setAliases(Assignment::Ptr, Element &);
342
343   AssignNode::Ptr createNode(Element &);
344
345   void cleanGraph(GraphPtr g);
346
347   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
348                             Direction dir);
349   
350   void constructInitialElement(Element &initial, Direction dir);
351
352   void insertInitialNode(GraphPtr ret, Direction dir, AssignNode::Ptr aP);
353
354   InsnCache insnCache_;
355
356   AssignmentPtr a_;
357   ParseAPI::Block *b_;
358   ParseAPI::Function *f_;
359
360   std::set<AssignNode::Ptr> visited_;
361   std::map<AssignmentPtr, AssignNode::Ptr> created_;
362
363   AssignmentConverter converter;
364
365   AssignNode::Ptr widen_;
366 };
367 };
368
369 #endif