Three bug fixes and a lot of warning removals.
[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
45 #include "Annotatable.h"
46 #include <iostream>
47 namespace Dyninst {
48 namespace ParseAPI {
49
50 class CFGModifier;
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     PARSER_EXPORT void install();
176
177     /* removes from blocks & finalized source functions if of type CALL */
178     PARSER_EXPORT void uninstall();
179
180     PARSER_EXPORT static void destroy(Edge *);
181
182  friend class CFGFactory;
183  friend class Parser;
184 };
185
186 /* 
187  * Iteration over edges can be controlled by an EdgePredicate.
188  * Edges are returned only if pred(edge) evaluates true.
189  * 
190  * EdgePredicates are composable by AND.
191  */
192 class EdgePredicate 
193     : public iterator_predicate<
194         EdgePredicate,
195         Edge *,
196         Edge *
197       >
198 {
199  protected:
200     EdgePredicate * _next; 
201  public:
202     PARSER_EXPORT EdgePredicate() : _next(NULL) { }
203     PARSER_EXPORT EdgePredicate(EdgePredicate * next) : _next(next) { }
204     PARSER_EXPORT virtual ~EdgePredicate() { }
205     PARSER_EXPORT virtual bool pred_impl(Edge *) const;
206 };
207
208 /* may follow branches into the function if there is shared code */
209 class Intraproc : public EdgePredicate {
210  public:
211     PARSER_EXPORT Intraproc() { }
212     PARSER_EXPORT Intraproc(EdgePredicate * next) : EdgePredicate(next) { }
213     PARSER_EXPORT ~Intraproc() { }
214     PARSER_EXPORT bool pred_impl(Edge *) const;
215 };
216
217 /* follow interprocedural edges */
218 class Interproc : public EdgePredicate {
219     public:
220         PARSER_EXPORT Interproc() {}
221         PARSER_EXPORT Interproc(EdgePredicate * next) : EdgePredicate(next) { }
222         PARSER_EXPORT ~Interproc() { }
223         PARSER_EXPORT bool pred_impl(Edge *) const;
224 };
225
226 /*
227  * For proper ostritch-like denial of 
228  * unresolved control flow edges
229  */
230 class NoSinkPredicate : public ParseAPI::EdgePredicate {
231  public:
232     NoSinkPredicate() { }
233     NoSinkPredicate(EdgePredicate * next)
234         : EdgePredicate(next) 
235     { } 
236
237     bool pred_impl(ParseAPI::Edge * e) const {
238         return !e->sinkEdge() && EdgePredicate::pred_impl(e);
239     }
240 };
241
242 /* doesn't follow branches into the function if there is shared code */
243 class Function;
244 class SingleContext : public EdgePredicate {
245  private:
246     Function * _context;
247     bool _forward;
248     bool _backward;
249  public:
250     PARSER_EXPORT SingleContext(Function * f, bool forward, bool backward) : 
251         _context(f),
252         _forward(forward),
253         _backward(backward) { }
254     PARSER_EXPORT ~SingleContext() { }
255     PARSER_EXPORT bool pred_impl(Edge *) const;
256 };
257
258 /* Doesn't follow branches into the function if there is shared code. 
259  * Will follow interprocedural call/return edges */
260 class SingleContextOrInterproc : public EdgePredicate {
261     private:
262         Function * _context;
263         bool _forward;
264         bool _backward;
265     public:
266         PARSER_EXPORT SingleContextOrInterproc(Function * f, bool forward, bool backward) :
267             _context(f),
268             _forward(forward),
269             _backward(backward) { }
270         PARSER_EXPORT ~SingleContextOrInterproc() { }
271         PARSER_EXPORT bool pred_impl(Edge *) const;
272 };
273
274 class CodeObject;
275 class CodeRegion;
276 class Block : public Dyninst::interval<Address>, 
277               public allocatable {
278     friend class CFGModifier;
279  public:
280     typedef ContainerWrapper<
281         std::vector<Edge*>,
282         Edge*,
283         Edge*,
284         EdgePredicate
285     > edgelist;
286
287     PARSER_EXPORT Block(CodeObject * o, CodeRegion * r, Address start);
288     PARSER_EXPORT virtual ~Block();
289
290     PARSER_EXPORT Address start() const { return _start; }
291     PARSER_EXPORT Address end() const { return _end; }
292     PARSER_EXPORT Address lastInsnAddr() const { return _lastInsn; } 
293     PARSER_EXPORT Address size() const { return _end - _start; }
294
295     PARSER_EXPORT bool parsed() const { return _parsed; }
296
297     PARSER_EXPORT CodeObject * obj() const { return _obj; }
298     PARSER_EXPORT CodeRegion * region() const { return _region; }
299
300     /* Edge access */
301     PARSER_EXPORT edgelist & sources() { return _srclist; }
302     PARSER_EXPORT edgelist & targets() { return _trglist; }
303
304     PARSER_EXPORT bool consistent(Address addr, Address & prev_insn);
305
306     PARSER_EXPORT int  containingFuncs() const;
307     PARSER_EXPORT void getFuncs(std::vector<Function *> & funcs);
308
309     PARSER_EXPORT bool wasUserAdded() const;
310
311     /* interval implementation */
312     Address low() const { return start(); }
313     Address high() const { return end(); }
314
315     struct compare {
316         bool operator()(Block * const & b1, Block * const & b2) const {
317             if(b1->start() < b2->start()) return true;
318             if(b1->start() > b2->start()) return false;
319             
320             // XXX debugging
321             if(b1 != b2)
322                 fprintf(stderr,"FATAL: blocks %p [%lx,%lx) and %p [%lx,%lx) "
323                             "conflict",b1,b1->start(),b1->end(),
324                             b2,b2->start(),b2->end());
325
326             assert(b1 == b2);
327             return false;
328         }
329     };
330
331     static void destroy(Block *b);
332
333  private:
334     void addSource(Edge * e);
335     void addTarget(Edge * e);
336     void removeTarget(Edge * e);
337     void removeSource(Edge * e);
338     void removeFunc(Function *);
339
340  private:
341     CodeObject * _obj;
342     CodeRegion * _region;
343
344     Address _start;
345     Address _end;
346     Address _lastInsn;
347
348     std::vector<Edge *> _sources;
349     std::vector<Edge *> _targets;
350
351     edgelist _srclist;
352     edgelist _trglist;
353     int _func_cnt;
354     bool _parsed;
355
356  friend class Edge;
357  friend class Function;
358  friend class Parser;
359  friend class CFGFactory;
360 };
361
362 inline void Block::addSource(Edge * e) 
363 {
364     _sources.push_back(e);
365 }
366
367 inline void Block::addTarget(Edge * e)
368 {
369     _targets.push_back(e);
370 }
371
372 inline void Block::removeTarget(Edge * e)
373 {
374     for(unsigned i=0;i<_targets.size();++i) {
375         if(_targets[i] == e) {
376             _targets[i] = _targets.back();
377             _targets.pop_back();    
378             break;
379         }
380     }
381 }
382
383 inline void Block::removeSource(Edge * e) {
384     for(unsigned i=0;i<_sources.size();++i) {
385         if(_sources[i] == e) {
386             _sources[i] = _sources.back();
387             _sources.pop_back();    
388             break;
389         }
390     }
391 }
392
393 enum FuncReturnStatus {
394     UNSET,
395     NORETURN,
396     UNKNOWN,
397     RETURN
398 };
399
400 /* Discovery method of functions */
401 enum FuncSource {
402     RT = 0,     // recursive traversal (default)
403     HINT,       // specified in code object hints
404     GAP,        // gap heuristics
405     GAPRT,      // RT from gap-discovered function
406     ONDEMAND,   // dynamically discovered
407     _funcsource_end_
408 };
409
410 enum StackTamper {
411     TAMPER_UNSET,
412     TAMPER_NONE,
413     TAMPER_REL,
414     TAMPER_ABS,
415     TAMPER_NONZERO
416 };
417
418 class CodeObject;
419 class CodeRegion;
420 class FuncExtent;
421 class Function : public allocatable, public AnnotatableSparse {
422    friend class CFGModifier;
423  protected:
424     Address _start;
425     CodeObject * _obj;
426     CodeRegion * _region;
427     InstructionSource * _isrc;
428     
429     FuncSource _src;
430     FuncReturnStatus _rs;
431
432     std::string _name;
433     Block * _entry;
434  protected:
435     PARSER_EXPORT Function(); 
436  public:
437     bool _is_leaf_function;
438     Address _ret_addr; // return address of a function stored in stack at function entry
439     typedef ContainerWrapper<
440         std::vector<Block*>,
441         Block*,
442         Block*
443     > blocklist;
444     typedef ContainerWrapper<
445         std::set<Edge*>,
446         Edge*,
447         Edge*
448     > edgelist;
449
450     PARSER_EXPORT Function(Address addr, string name, CodeObject * obj, 
451         CodeRegion * region, InstructionSource * isource);
452
453     PARSER_EXPORT virtual ~Function();
454
455     PARSER_EXPORT virtual const string & name();
456
457     PARSER_EXPORT Address addr() const { return _start; }
458     PARSER_EXPORT CodeRegion * region() const { return _region; }
459     PARSER_EXPORT InstructionSource * isrc() const { return _isrc; }
460     PARSER_EXPORT CodeObject * obj() const { return _obj; }
461     PARSER_EXPORT FuncSource src() const { return _src; }
462     PARSER_EXPORT FuncReturnStatus retstatus() const { return _rs; }
463     PARSER_EXPORT Block * entry() const { return _entry; }
464     PARSER_EXPORT bool parsed() const { return _parsed; }
465
466     /* Basic block and CFG access */
467     PARSER_EXPORT blocklist & blocks();
468     PARSER_EXPORT bool contains(Block *b);
469     PARSER_EXPORT edgelist & callEdges();
470     PARSER_EXPORT blocklist & returnBlocks();
471
472     /* Function details */
473     PARSER_EXPORT bool hasNoStackFrame() const { return _no_stack_frame; }
474     PARSER_EXPORT bool savesFramePointer() const { return _saves_fp; }
475     PARSER_EXPORT bool cleansOwnStack() const { return _cleans_stack; }
476
477     /* Parse updates and obfuscation */
478     PARSER_EXPORT void setEntryBlock(Block *new_entry);
479     PARSER_EXPORT void set_retstatus(FuncReturnStatus rs) { _rs = rs; }
480     PARSER_EXPORT void removeBlock( Block* );
481
482     PARSER_EXPORT StackTamper tampersStack(bool recalculate=false);
483
484     struct less
485     {
486         bool operator()(const Function * f1, const Function * f2) const
487         {
488             return f1->addr() < f2->addr();
489         }
490     };
491
492     /* Contiguous code segments of function */
493     PARSER_EXPORT std::vector<FuncExtent *> const& extents();
494
495     /* This should not remain here - this is an experimental fix for
496        defensive mode CFG inconsistency */
497     void invalidateCache() { _cache_valid = false; }
498
499     static void destroy(Function *f);
500
501  private:
502     std::vector<Block *> const& blocks_int();
503     void delayed_link_return(CodeObject * co, Block * retblk);
504     void finalize();
505
506     bool _parsed;
507     bool _cache_valid;
508     blocklist _bl;
509     std::vector<Block *> _blocks;
510     std::vector<FuncExtent *> _extents;
511
512     /* rapid lookup for edge predicate tests */
513     //typedef dyn_hash_map<Address, Block*> blockmap;
514     typedef std::map<Address, Block*> blockmap;
515     blockmap _bmap;
516
517     /* rapid lookup for interprocedural queries */
518     std::set<Edge *> _call_edges;
519     edgelist _call_edge_list;
520     std::vector<Block *> _return_blocks;
521     blocklist _retBL;
522
523
524     /* function details */
525     bool _no_stack_frame;
526     bool _saves_fp;
527     bool _cleans_stack;
528     StackTamper _tamper;
529     Address _tamper_addr;
530
531     /*** Internal parsing methods and state ***/
532     void add_block(Block *b);
533
534     friend void Edge::uninstall();
535     friend class Parser;
536     friend class CFGFactory;
537     friend class CodeObject;
538 };
539
540 /* Describes a contiguous extent of a Function object */
541 class FuncExtent : public Dyninst::interval<Address> {
542  private:
543     Function * _func;
544     Address _start;
545     Address _end;
546
547  public:
548     FuncExtent(Function * f, Address start, Address end) :
549         _func(f),
550         _start(start),
551         _end(end) { }
552
553     ~FuncExtent() {
554         _func = NULL;
555     }
556
557     PARSER_EXPORT Function * func() { return _func; }
558
559     PARSER_EXPORT Address start() const { return _start; }
560     PARSER_EXPORT Address end() const { return _end; }
561
562     /* interval implementation */
563     PARSER_EXPORT Address low() const { return _start; }
564     PARSER_EXPORT Address high() const { return _end; } 
565 };
566
567
568 } //namespace ParseAPI
569 } //namespace Dyninst
570
571 #endif