Fixes to stack tampering code and cleanup
[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       Element() {
225           usedIndex = -1;
226       };
227     Location loc;
228     Context con;
229     AbsRegion reg;
230     // This is for returns, and not for the intermediate
231     // steps. OTOH, I'm being a bit lazy...
232     Assignment::Ptr ptr;
233     unsigned usedIndex;
234     Address addr() const { return loc.addr(); }
235   };
236
237   typedef std::queue<Element> Elements;
238
239   GraphPtr sliceInternal(Direction dir,
240                          Predicates &predicates);
241   
242   bool getMatchingElements(Element &initial, Elements &worklist,
243                            Predicates &p, Direction dir);
244   
245   bool getNextCandidates(Element &initial, Elements &worklist,
246                          Predicates &p, Direction dir);
247
248   void findMatches(Element &current, Assignment::Ptr &assign, 
249                    Direction dir, int index, Elements &succ); 
250
251   bool kills(Element &current, Assignment::Ptr &assign);
252
253   bool followCall(ParseAPI::Block *b,
254                   Direction d,
255                   Element &current,
256                   Predicates &p);
257
258   bool followReturn(ParseAPI::Block *b,
259                     Direction d,
260                     Element &current,
261                     Predicates &p);
262
263   bool handleDefault(ParseAPI::Edge *e,
264                      Direction dir,
265                      Element &current,
266                      Element &newElement,
267                      Predicates &p,
268                      bool &err);
269                 
270   bool handleCall(ParseAPI::Block *block,
271                   Element &current,
272                   Element &newElement,
273                   Predicates &p,
274                   bool &err);
275
276   bool handleCallBackward(ParseAPI::Edge *e,
277                           Element &current,
278                           Elements &newElements,
279                           Predicates &p,
280                           bool &err);
281
282   bool handleReturn(ParseAPI::Block *b,
283                     Element &current,
284                     Element &newElement,
285                     Predicates &p,
286                     bool &err);
287
288   bool handleReturnBackward(ParseAPI::Edge *e,
289                             Element &current,
290                             Element &newElement,
291                             Predicates &p,
292                             bool &err);
293
294   void handleReturnDetails(AbsRegion &reg,
295                            Context &context);
296
297   bool handleReturnDetailsBackward(AbsRegion &reg,
298                                     Context &context,
299                                     ParseAPI::Block *callBlock,
300                                     ParseAPI::Function *callee);
301
302   bool getSuccessors(Element &current,
303                      Elements &worklist,
304                      Predicates &p);
305
306   bool getPredecessors(Element &current,
307                        Elements &worklist,
308                        Predicates &p);
309
310   bool search(Element &current,
311               Elements &foundList,
312               Predicates &p,
313               int index,
314               Direction dir);
315
316   void widen(GraphPtr graph, Direction dir, Element &source);
317
318   void insertPair(GraphPtr graph,
319                   Direction dir,
320                   Element &source,
321                   Element &target);
322
323   void convertInstruction(InstructionPtr,
324                           Address,
325                           ParseAPI::Function *,
326                           std::vector<AssignmentPtr> &);
327
328   void fastForward(Location &loc, Address addr);
329
330   void fastBackward(Location &loc, Address addr);
331
332   AssignNode::Ptr widenNode();
333
334   void markAsEndNode(GraphPtr ret, Direction dir, Element &current);
335   
336   void markAsExitNode(GraphPtr ret, Element &current);
337
338   void markAsEntryNode(GraphPtr ret, Element &current);
339
340   void getInsns(Location &loc);
341
342   void getInsnsBackward(Location &loc);
343
344   void setAliases(Assignment::Ptr, Element &);
345
346   AssignNode::Ptr createNode(Element &);
347
348   void cleanGraph(GraphPtr g);
349
350   ParseAPI::Block *getBlock(ParseAPI::Edge *e,
351                             Direction dir);
352   
353   void constructInitialElement(Element &initial, Direction dir);
354
355   void insertInitialNode(GraphPtr ret, Direction dir, AssignNode::Ptr aP);
356
357   InsnCache insnCache_;
358
359   AssignmentPtr a_;
360   ParseAPI::Block *b_;
361   ParseAPI::Function *f_;
362
363   std::set<AssignNode::Ptr> visited_;
364   std::map<AssignmentPtr, AssignNode::Ptr> created_;
365
366   AssignmentConverter converter;
367
368   AssignNode::Ptr widen_;
369 };
370 };
371
372 #endif