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