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