Add a list of "exit" blocks to functions, which includes non-returning calls as well...
[dyninst.git] / parseAPI / h / CFG.h
1 /*
2  * Copyright (c) 1996-2011 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31 #ifndef _PARSER_CFG_H_
32 #define _PARSER_CFG_H_
33
34 #include <vector>
35 #include <set>
36 #include <map>
37 #include <string>
38
39 #include "dyntypes.h"
40 #include "IBSTree.h"
41
42 #include "InstructionSource.h"
43 #include "ParseContainers.h"
44 #include "Annotatable.h"
45 #include <iostream>
46 namespace Dyninst {
47 namespace ParseAPI {
48
49 class CFGModifier;
50 class CodeObject;
51
52 enum EdgeTypeEnum {
53     CALL = 0,
54     COND_TAKEN,
55     COND_NOT_TAKEN,
56     INDIRECT,
57     DIRECT,
58     FALLTHROUGH,
59     CATCH,
60     CALL_FT,        // fallthrough after call instruction
61     RET,
62     NOEDGE,
63     _edgetype_end_
64 };
65
66 PARSER_EXPORT std::string format(EdgeTypeEnum e);
67
68 #define FLIST_BADNEXT ((void*)0x111)
69 #define FLIST_BADPREV ((void*)0x222)
70
71 /*
72  * All CFG objects extend allocatable, which
73  * allows them to be added and removed from
74  * accounting structures in constant time
75  */
76 class allocatable {
77  public:
78     allocatable() :
79        anext_((allocatable*)FLIST_BADNEXT),
80        aprev_((allocatable*)FLIST_BADPREV)
81     { }
82     allocatable * anext_;
83     allocatable * aprev_;
84
85     inline allocatable * alloc_next() const { return anext_; }
86     inline allocatable * alloc_prev() const { return aprev_; }
87     inline void alloc_set_next(allocatable *t) { anext_ = t; }
88     inline void alloc_set_prev(allocatable *t) { aprev_ = t; }
89
90     void remove() {
91         if(anext_ != (allocatable*)FLIST_BADNEXT)
92             anext_->aprev_ = aprev_;
93         if(aprev_ != (allocatable*)FLIST_BADPREV)
94             aprev_->anext_ = anext_;
95
96         anext_ = (allocatable*)FLIST_BADNEXT;
97         aprev_ = (allocatable*)FLIST_BADPREV;
98     }
99
100     void append(allocatable & new_elem) {
101         if(anext_ == (allocatable*)FLIST_BADNEXT ||
102            aprev_ == (allocatable*)FLIST_BADPREV)
103         {
104             fprintf(stderr,
105                 "allocatable::append called on element not on list: %p\n",this);
106             return;
107         }
108         anext_->aprev_ = &new_elem;
109         new_elem.anext_ = anext_;
110         new_elem.aprev_ = this;
111         anext_ = &new_elem;
112     }
113
114     void prepend(allocatable & new_elem) {
115         if(anext_ == (allocatable*)FLIST_BADNEXT ||
116            aprev_ == (allocatable*)FLIST_BADPREV)
117         {
118             fprintf(stderr,
119                "allocatable::prepend called on element not on list: %p\n",this);
120             return;
121         }
122         aprev_->anext_ = &new_elem;
123         new_elem.aprev_ = aprev_;
124         new_elem.anext_ = this;
125         aprev_ = &new_elem;
126     }
127 };
128
129 class Block;
130 class Edge : public allocatable {
131    friend class CFGModifier;
132  protected:
133     Block * _source;
134     Block * _target;
135
136  private:
137
138 #if defined(_MSC_VER)
139         typedef unsigned __int16 uint16_t;
140         typedef unsigned __int8 uint8_t;
141 #else
142         typedef unsigned short uint16_t;
143         typedef unsigned char uint8_t;
144 #endif
145
146     struct EdgeType {
147         EdgeType(EdgeTypeEnum t, bool s) :
148             _type_enum(t), _sink(s), _interproc(false)
149         { }
150         uint16_t _type_enum;
151         uint8_t _sink;
152         uint8_t  _interproc;    // modifier for interprocedural branches
153                                 // (tail calls)
154     };
155     EdgeType _type;
156
157  public:
158     PARSER_EXPORT Edge(Block * source,
159          Block * target,
160          EdgeTypeEnum type);
161      PARSER_EXPORT virtual ~Edge();
162
163     PARSER_EXPORT virtual Block * src() const { return _source; }
164     PARSER_EXPORT virtual Block * trg() const { return _target; }
165     PARSER_EXPORT EdgeTypeEnum type() const { 
166         return static_cast<EdgeTypeEnum>(_type._type_enum); 
167     }
168     bool sinkEdge() const { return _type._sink != 0; }
169     bool interproc() const { 
170        return (_type._interproc != 0 ||
171                type() == CALL ||
172                type() == RET);
173     }
174
175     bool intraproc() const {
176        return !interproc();
177     }
178
179     PARSER_EXPORT void install();
180
181     /* removes from blocks (and if of type CALL, from finalized source functions ) */
182     PARSER_EXPORT void uninstall();
183
184     PARSER_EXPORT static void destroy(Edge *, CodeObject *);
185
186  friend class CFGFactory;
187  friend class Parser;
188 };
189
190 /* 
191  * Iteration over edges can be controlled by an EdgePredicate.
192  * Edges are returned only if pred(edge) evaluates true.
193  * 
194  * EdgePredicates are composable by AND.
195  */
196 class EdgePredicate 
197     : public iterator_predicate<
198         EdgePredicate,
199         Edge *,
200         Edge *
201       >
202 {
203  protected:
204     EdgePredicate * _next; 
205  public:
206     PARSER_EXPORT EdgePredicate() : _next(NULL) { }
207     PARSER_EXPORT EdgePredicate(EdgePredicate * next) : _next(next) { }
208     PARSER_EXPORT virtual ~EdgePredicate() { }
209     PARSER_EXPORT virtual bool pred_impl(Edge *) const;
210 };
211
212 /* may follow branches into the function if there is shared code */
213 class Intraproc : public EdgePredicate {
214  public:
215     PARSER_EXPORT Intraproc() { }
216     PARSER_EXPORT Intraproc(EdgePredicate * next) : EdgePredicate(next) { }
217     PARSER_EXPORT ~Intraproc() { }
218     PARSER_EXPORT bool pred_impl(Edge *) const;
219 };
220
221 /* follow interprocedural edges */
222 class Interproc : public EdgePredicate {
223     public:
224         PARSER_EXPORT Interproc() {}
225         PARSER_EXPORT Interproc(EdgePredicate * next) : EdgePredicate(next) { }
226         PARSER_EXPORT ~Interproc() { }
227         PARSER_EXPORT bool pred_impl(Edge *) const;
228 };
229
230 /*
231  * For proper ostritch-like denial of 
232  * unresolved control flow edges
233  */
234 class NoSinkPredicate : public ParseAPI::EdgePredicate {
235  public:
236     NoSinkPredicate() { }
237     NoSinkPredicate(EdgePredicate * next)
238         : EdgePredicate(next) 
239     { } 
240
241     bool pred_impl(ParseAPI::Edge * e) const {
242         return !e->sinkEdge() && EdgePredicate::pred_impl(e);
243     }
244 };
245
246 /* doesn't follow branches into the function if there is shared code */
247 class Function;
248 class SingleContext : public EdgePredicate {
249  private:
250     Function * _context;
251     bool _forward;
252     bool _backward;
253  public:
254     PARSER_EXPORT SingleContext(Function * f, bool forward, bool backward) : 
255         _context(f),
256         _forward(forward),
257         _backward(backward) { }
258     PARSER_EXPORT ~SingleContext() { }
259     PARSER_EXPORT bool pred_impl(Edge *) const;
260 };
261
262 /* Doesn't follow branches into the function if there is shared code. 
263  * Will follow interprocedural call/return edges */
264 class SingleContextOrInterproc : public EdgePredicate {
265     private:
266         Function * _context;
267         bool _forward;
268         bool _backward;
269     public:
270         PARSER_EXPORT SingleContextOrInterproc(Function * f, bool forward, bool backward) :
271             _context(f),
272             _forward(forward),
273             _backward(backward) { }
274         PARSER_EXPORT ~SingleContextOrInterproc() { }
275         PARSER_EXPORT bool pred_impl(Edge *) const;
276 };
277
278 class CodeObject;
279 class CodeRegion;
280 class Block : public Dyninst::interval<Address>, 
281               public allocatable {
282     friend class CFGModifier;
283  public:
284     typedef ContainerWrapper<
285         std::vector<Edge*>,
286         Edge*,
287         Edge*,
288         EdgePredicate
289     > edgelist;
290
291     PARSER_EXPORT Block(CodeObject * o, CodeRegion * r, Address start);
292     PARSER_EXPORT virtual ~Block();
293
294     PARSER_EXPORT Address start() const { return _start; }
295     PARSER_EXPORT Address end() const { return _end; }
296     PARSER_EXPORT Address lastInsnAddr() const { return _lastInsn; } 
297     PARSER_EXPORT Address last() const { return lastInsnAddr(); }
298     PARSER_EXPORT Address size() const { return _end - _start; }
299
300     PARSER_EXPORT bool parsed() const { return _parsed; }
301
302     PARSER_EXPORT CodeObject * obj() const { return _obj; }
303     PARSER_EXPORT CodeRegion * region() const { return _region; }
304
305     /* Edge access */
306     PARSER_EXPORT const edgelist & sources() const { return _srclist; }
307     PARSER_EXPORT const edgelist & targets() const { return _trglist; }
308
309     PARSER_EXPORT bool consistent(Address addr, Address & prev_insn);
310
311     PARSER_EXPORT int  containingFuncs() const;
312     PARSER_EXPORT void getFuncs(std::vector<Function *> & funcs);
313
314     /* interval implementation */
315     Address low() const { return start(); }
316     Address high() const { return end(); }
317
318     struct compare {
319         bool operator()(Block * const & b1, Block * const & b2) const {
320             if(b1->start() < b2->start()) return true;
321             if(b1->start() > b2->start()) return false;
322             
323             // XXX debugging
324             if(b1 != b2)
325                 fprintf(stderr,"FATAL: blocks %p [%lx,%lx) and %p [%lx,%lx) "
326                             "conflict",b1,b1->start(),b1->end(),
327                             b2,b2->start(),b2->end());
328
329             assert(b1 == b2);
330             return false;
331         }
332     };
333
334     static void destroy(Block *b);
335
336  private:
337     void addSource(Edge * e);
338     void addTarget(Edge * e);
339     void removeTarget(Edge * e);
340     void removeSource(Edge * e);
341     void removeFunc(Function *);
342
343  private:
344     CodeObject * _obj;
345     CodeRegion * _region;
346
347     Address _start;
348     Address _end;
349     Address _lastInsn;
350
351     std::vector<Edge *> _sources;
352     std::vector<Edge *> _targets;
353
354     edgelist _srclist;
355     edgelist _trglist;
356     int _func_cnt;
357     bool _parsed;
358
359  friend class Edge;
360  friend class Function;
361  friend class Parser;
362  friend class CFGFactory;
363 };
364
365 inline void Block::addSource(Edge * e) 
366 {
367     _sources.push_back(e);
368 }
369
370 inline void Block::addTarget(Edge * e)
371 {
372     _targets.push_back(e);
373 }
374
375 inline void Block::removeTarget(Edge * e)
376 {
377     for(unsigned i=0;i<_targets.size();++i) {
378         if(_targets[i] == e) {
379             _targets[i] = _targets.back();
380             _targets.pop_back();    
381             break;
382         }
383     }
384 }
385
386 inline void Block::removeSource(Edge * e) {
387     for(unsigned i=0;i<_sources.size();++i) {
388         if(_sources[i] == e) {
389             _sources[i] = _sources.back();
390             _sources.pop_back();    
391             break;
392         }
393     }
394 }
395
396 enum FuncReturnStatus {
397     UNSET,
398     NORETURN,
399     UNKNOWN,
400     RETURN
401 };
402
403 /* Discovery method of functions */
404 enum FuncSource {
405     RT = 0,     // recursive traversal (default)
406     HINT,       // specified in code object hints
407     GAP,        // gap heuristics
408     GAPRT,      // RT from gap-discovered function
409     ONDEMAND,   // dynamically discovered
410     _funcsource_end_
411 };
412
413 enum StackTamper {
414     TAMPER_UNSET,
415     TAMPER_NONE,
416     TAMPER_REL,
417     TAMPER_ABS,
418     TAMPER_NONZERO
419 };
420
421 class CodeObject;
422 class CodeRegion;
423 class FuncExtent;
424 class Function : public allocatable, public AnnotatableSparse {
425    friend class CFGModifier;
426  protected:
427     Address _start;
428     CodeObject * _obj;
429     CodeRegion * _region;
430     InstructionSource * _isrc;
431     
432     FuncSource _src;
433     FuncReturnStatus _rs;
434
435     std::string _name;
436     Block * _entry;
437  protected:
438     PARSER_EXPORT Function(); 
439  public:
440     bool _is_leaf_function;
441     Address _ret_addr; // return address of a function stored in stack at function entry
442     typedef ContainerWrapper<
443         std::vector<Block*>,
444         Block*,
445         Block*
446     > blocklist;
447     typedef ContainerWrapper<
448         std::set<Edge*>,
449         Edge*,
450         Edge*
451     > edgelist;
452
453     PARSER_EXPORT Function(Address addr, string name, CodeObject * obj, 
454         CodeRegion * region, InstructionSource * isource);
455
456     PARSER_EXPORT virtual ~Function();
457
458     PARSER_EXPORT virtual const string & name();
459
460     PARSER_EXPORT Address addr() const { return _start; }
461     PARSER_EXPORT CodeRegion * region() const { return _region; }
462     PARSER_EXPORT InstructionSource * isrc() const { return _isrc; }
463     PARSER_EXPORT CodeObject * obj() const { return _obj; }
464     PARSER_EXPORT FuncSource src() const { return _src; }
465     PARSER_EXPORT FuncReturnStatus retstatus() const { return _rs; }
466     PARSER_EXPORT Block * entry() const { return _entry; }
467     PARSER_EXPORT bool parsed() const { return _parsed; }
468
469     /* Basic block and CFG access */
470     PARSER_EXPORT blocklist & blocks();
471     PARSER_EXPORT bool contains(Block *b);
472     PARSER_EXPORT edgelist & callEdges();
473     PARSER_EXPORT blocklist & returnBlocks();
474     PARSER_EXPORT blocklist & exitBlocks();
475
476     /* Function details */
477     PARSER_EXPORT bool hasNoStackFrame() const { return _no_stack_frame; }
478     PARSER_EXPORT bool savesFramePointer() const { return _saves_fp; }
479     PARSER_EXPORT bool cleansOwnStack() const { return _cleans_stack; }
480
481     /* Parse updates and obfuscation */
482     PARSER_EXPORT void setEntryBlock(Block *new_entry);
483     PARSER_EXPORT void set_retstatus(FuncReturnStatus rs) { _rs = rs; }
484     PARSER_EXPORT void removeBlock( Block* );
485
486     PARSER_EXPORT StackTamper tampersStack(bool recalculate=false);
487
488     struct less
489     {
490         bool operator()(const Function * f1, const Function * f2) const
491         {
492             return f1->addr() < f2->addr();
493         }
494     };
495
496     /* Contiguous code segments of function */
497     PARSER_EXPORT std::vector<FuncExtent *> const& extents();
498
499     /* This should not remain here - this is an experimental fix for
500        defensive mode CFG inconsistency */
501     void invalidateCache() { _cache_valid = false; }
502
503     static void destroy(Function *f);
504
505  private:
506     std::vector<Block *> const& blocks_int();
507     void delayed_link_return(CodeObject * co, Block * retblk);
508     void finalize();
509
510     bool _parsed;
511     bool _cache_valid;
512     blocklist _bl;
513     std::vector<Block *> _blocks;
514     std::vector<FuncExtent *> _extents;
515
516     /* rapid lookup for edge predicate tests */
517     //typedef dyn_hash_map<Address, Block*> blockmap;
518     typedef std::map<Address, Block*> blockmap;
519     blockmap _bmap;
520
521     /* rapid lookup for interprocedural queries */
522     std::set<Edge *> _call_edges;
523     edgelist _call_edge_list;
524     std::vector<Block *> _return_blocks;
525     blocklist _retBL;
526     // Superset of return blocks; this includes all blocks where
527     // execution leaves the function without coming back, including
528     // returns, calls to non-returning calls, tail calls, etc.
529     // Might want to include exceptions...
530     std::vector<Block *> _exit_blocks;
531     blocklist _exitBL;
532
533     /* function details */
534     bool _no_stack_frame;
535     bool _saves_fp;
536     bool _cleans_stack;
537     StackTamper _tamper;
538     Address _tamper_addr;
539
540     /*** Internal parsing methods and state ***/
541     void add_block(Block *b);
542
543     friend void Edge::uninstall();
544     friend class Parser;
545     friend class CFGFactory;
546     friend class CodeObject;
547 };
548
549 /* Describes a contiguous extent of a Function object */
550 class FuncExtent : public Dyninst::interval<Address> {
551  private:
552     Function * _func;
553     Address _start;
554     Address _end;
555
556  public:
557     FuncExtent(Function * f, Address start, Address end) :
558         _func(f),
559         _start(start),
560         _end(end) { }
561
562     ~FuncExtent() {
563         _func = NULL;
564     }
565
566     PARSER_EXPORT Function * func() { return _func; }
567
568     PARSER_EXPORT Address start() const { return _start; }
569     PARSER_EXPORT Address end() const { return _end; }
570
571     /* interval implementation */
572     PARSER_EXPORT Address low() const { return _start; }
573     PARSER_EXPORT Address high() const { return _end; } 
574 };
575
576
577 } //namespace ParseAPI
578 } //namespace Dyninst
579
580 #endif