Merge branch 'master' of git.dyninst.org:/pub/dyninst
[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<std::pair<image_func *, int> > &cs, bool plt, AbsRegion a)>
97                     CallStackFunc;
98
99             GraphPtr forwardSlice(PredicateFunc &e, PredicateFunc &w, CallStackFunc &c);
100   
101             GraphPtr backwardSlice(PredicateFunc &e, PredicateFunc &w);
102   
103             static bool isWidenNode(Node::Ptr n);
104
105         private:
106             typedef std::pair<InstructionPtr, Address> InsnInstance;
107             typedef std::vector<InsnInstance> InsnVec;
108
109             typedef enum {
110                 forward,
111                 backward } Direction;
112
113                 typedef std::map<image_basicBlock *, InsnVec> InsnCache;
114
115                 struct Predicates {
116     // It's safe for these to be references because they will only exist
117     // under a forward/backwardSlice call.
118                     PredicateFunc &end;
119                     PredicateFunc &widen;
120                     CallStackFunc &followCall;
121     
122                     Predicates(PredicateFunc &e, PredicateFunc &w, CallStackFunc &c) : end(e), widen(w), followCall(c) {};
123
124                 };
125
126   // Our slicing is context-sensitive; that is, if we enter
127   // a function foo from a caller bar, all return edges
128   // from foo must enter bar. This makes an assumption that
129   // the return address is not modified, but hey. 
130   // We represent this as a list of call sites. This is redundant
131   // with the image_instPoint data structure, but hopefully that
132   // one will be going away. 
133
134                 struct ContextElement {
135     // We can implicitly find the callsite given a block,
136     // since calls end blocks. It's easier to look up 
137     // the successor this way than with an address.
138
139                     image_func *func;
140
141     // If non-NULL this must be an internal context
142     // element, since we have an active call site.
143                     image_basicBlock *block;
144
145     // To enter or leave a function we must be able to
146     // map corresponding abstract regions. 
147     // In particular, we need to know the depth of the 
148     // stack in the caller.
149                     long stackDepth;
150
151   ContextElement(image_func *f) : 
152           func(f), block(NULL), stackDepth(-1) {};
153   ContextElement(image_func *f, long depth) :
154           func(f), block(NULL), stackDepth(depth) {};
155                 };
156
157   // This should be sufficient...
158                 typedef std::deque<ContextElement> Context;
159
160                 bool getStackDepth(image_func *func, Address callAddr, long &height);
161
162   // Add the newly called function to the given Context.
163                 void pushContext(Context &context,
164                                  image_func *callee,
165                                  image_basicBlock *callBlock,
166                                  long stackDepth);
167
168   // And remove it as appropriate
169                 void popContext(Context &context);
170
171   // Shift an abs region by a given stack offset
172                 void shiftAbsRegion(AbsRegion &callerReg,
173                                     AbsRegion &calleeReg,
174                                     long stack_depth,
175                                     image_func *callee);
176
177   // Handling a call does two things:
178   // 1) Translates the given AbsRegion into the callee-side
179   //    view; this just means adjusting stack locations. 
180   // 2) Increases the given context
181   // Returns false if we didn't translate the absregion correctly
182                 bool handleCallDetails(AbsRegion &reg,
183                                        Context &context,
184                                        image_basicBlock *callerBlock,
185                                        image_func *callee);
186
187   // Where we are in a particular search...
188                 struct Location {
189     // The block we're looking through
190                     image_func *func;
191                     image_basicBlock *block; // current block
192
193     // Where we are in the block
194                     InsnVec::iterator current;
195                     InsnVec::iterator end;
196
197                     Address addr() const { return current->second; }
198
199                     Location(image_func *f,
200                              image_basicBlock *b) : func(f), block(b) {};
201                     Location() : func(NULL), block(NULL) {};
202                 };
203     
204                 typedef std::queue<Location> LocList;
205   
206   // And the tuple of (context, AbsRegion, Location)
207   // that specifies both context and what to search for
208   // in that context
209                 struct Element {
210                     Location loc;
211                     Context con;
212                     AbsRegion reg;
213     // This is for returns, and not for the intermediate
214     // steps. OTOH, I'm being a bit lazy...
215                     Assignment::Ptr ptr;
216                     unsigned usedIndex;
217
218                     Address addr() const { return loc.addr(); }
219                 };
220                 typedef std::queue<Element> Elements;
221
222                 bool followCall(image_basicBlock *b,
223                                 Direction d,
224                                 Element &current,
225                                 Predicates &p);
226
227                 bool handleDefault(image_edge *e,
228                                    Element &current,
229                                    Element &newElement,
230                                    Predicates &p,
231                                    bool &err);
232
233                 bool handleCall(image_basicBlock *block,
234                                 Element &current,
235                                 Element &newElement,
236                                 Predicates &p,
237                                 bool &err);
238
239                 bool handleReturn(image_basicBlock *b,
240                                   Element &current,
241                                   Element &newElement,
242                                   Predicates &p,
243                                   bool &err);
244
245                 void handleReturnDetails(AbsRegion &reg,
246                                          Context &context);
247
248                 bool getSuccessors(Element &current,
249                                    Elements &worklist,
250                                    Predicates &p);
251
252
253                 bool forwardSearch(Element &current,
254                                    Elements &foundList,
255                                    Predicates &p);
256
257                 void widen(GraphPtr graph, Element &source);
258
259                 void insertPair(GraphPtr graph,
260                                 Element &source,
261                                 Element &target);
262
263                 void convertInstruction(InstructionPtr,
264                                         Address,
265                                         image_func *,
266                                         std::vector<AssignmentPtr> &);
267
268                 void fastForward(Location &loc, Address addr);
269
270                 AssignNode::Ptr widenNode();
271
272                 void markAsExitNode(GraphPtr ret, Element &current);
273   
274
275                 void getInsns(Location &loc);
276
277                 void setAliases(Assignment::Ptr, Element &);
278
279                 AssignNode::Ptr createNode(Element &);
280
281                 void cleanGraph(GraphPtr g);
282
283                 image_basicBlock *getBlock(image_edge *e,
284                                            Direction dir);
285   
286                 void constructInitialElement(Element &initial);
287
288                 InsnCache insnCache_;
289
290                 AssignmentPtr a_;
291                 image_basicBlock *b_;
292                 image_func *f_;
293
294                 std::set<AssignNode::Ptr> visited_;
295                 std::map<AssignmentPtr, AssignNode::Ptr> created_;
296
297                 AssignmentConverter converter;
298
299                 AssignNode::Ptr widen_;
300     };
301 };
302
303 #endif