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