Update Examples in dataflowAPI (#700)
[dyninst.git] / parseAPI / h / CFG.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30 #ifndef _PARSER_CFG_H_
31 #define _PARSER_CFG_H_
32
33 #include <vector>
34 #include <set>
35 #include <map>
36 #include <string>
37 #include <functional>
38 #include <boost/iterator/transform_iterator.hpp>
39 #include <boost/range.hpp>
40 #include <boost/thread/lock_guard.hpp>
41 #include "dyntypes.h"
42 #include "IBSTree.h"
43
44 #include "InstructionSource.h"
45 #include "ParseContainers.h"
46 #include "Annotatable.h"
47 #include "DynAST.h"
48
49 #include <iostream>
50 #include <boost/thread/lockable_adapter.hpp>
51 #include <boost/thread/recursive_mutex.hpp>
52 #include <boost/atomic.hpp>
53 #include <list>
54
55 namespace Dyninst {
56
57    namespace InstructionAPI {
58       class Instruction;
59       typedef boost::shared_ptr<Instruction> InstructionPtr;
60    }
61
62 namespace ParseAPI {
63
64 class LoopAnalyzer;
65 class dominatorCFG;
66 class CodeObject;
67 class CFGModifier;
68 class ParseData;
69 class region_data;
70 enum EdgeTypeEnum {
71     CALL = 0,
72     COND_TAKEN,
73     COND_NOT_TAKEN,
74     INDIRECT,
75     DIRECT,
76     FALLTHROUGH,
77     CATCH,
78     CALL_FT,        // fallthrough after call instruction
79     RET,
80     NOEDGE,
81     _edgetype_end_
82 };
83
84 PARSER_EXPORT std::string format(EdgeTypeEnum e);
85
86 #define FLIST_BADNEXT ((void*)0x111)
87 #define FLIST_BADPREV ((void*)0x222)
88
89 /*
90  * All CFG objects extend allocatable, which
91  * allows them to be added and removed from
92  * accounting structures in constant time
93  */
94 class PARSER_EXPORT allocatable {
95  public:
96     allocatable() :
97        anext_((allocatable*)FLIST_BADNEXT),
98        aprev_((allocatable*)FLIST_BADPREV)
99     { }
100     allocatable * anext_;
101     allocatable * aprev_;
102
103     inline allocatable * alloc_next() const { return anext_; }
104     inline allocatable * alloc_prev() const { return aprev_; }
105     inline void alloc_set_next(allocatable *t) { anext_ = t; }
106     inline void alloc_set_prev(allocatable *t) { aprev_ = t; }
107
108     void remove() {
109         if(anext_ != (allocatable*)FLIST_BADNEXT)
110             anext_->aprev_ = aprev_;
111         if(aprev_ != (allocatable*)FLIST_BADPREV)
112             aprev_->anext_ = anext_;
113
114         anext_ = (allocatable*)FLIST_BADNEXT;
115         aprev_ = (allocatable*)FLIST_BADPREV;
116     }
117
118     void append(allocatable & new_elem) {
119         if(anext_ == (allocatable*)FLIST_BADNEXT ||
120            aprev_ == (allocatable*)FLIST_BADPREV)
121         {
122             fprintf(stderr,
123                 "allocatable::append called on element not on list: %p\n",this);
124             return;
125         }
126         anext_->aprev_ = &new_elem;
127         new_elem.anext_ = anext_;
128         new_elem.aprev_ = this;
129         anext_ = &new_elem;
130     }
131
132     void prepend(allocatable & new_elem) {
133         if(anext_ == (allocatable*)FLIST_BADNEXT ||
134            aprev_ == (allocatable*)FLIST_BADPREV)
135         {
136             fprintf(stderr,
137                "allocatable::prepend called on element not on list: %p\n",this);
138             return;
139         }
140         aprev_->anext_ = &new_elem;
141         new_elem.aprev_ = aprev_;
142         new_elem.anext_ = this;
143         aprev_ = &new_elem;
144     }
145 };
146
147 class Block;
148
149
150 class PARSER_EXPORT Edge : public allocatable {
151    friend class CFGModifier;
152     friend class Block;
153  protected:
154     boost::atomic<Block *> _source;
155     Block * _target;
156     ParseData* index;
157     Offset _target_off;
158     bool _from_index;
159
160  private:
161
162 #if defined(_MSC_VER)
163         typedef unsigned __int16 uint16_t;
164         typedef unsigned __int8 uint8_t;
165 #else
166         typedef unsigned short uint16_t;
167         typedef unsigned char uint8_t;
168 #endif
169
170     struct EdgeType {
171         EdgeType(EdgeTypeEnum t, bool s) :
172             _type_enum(t), _sink(s), _interproc(false)
173         { }
174         uint16_t _type_enum;
175         uint8_t _sink;
176         uint8_t  _interproc;    // modifier for interprocedural branches
177                                 // (tail calls)
178     };
179     EdgeType _type;
180
181  public:
182     Edge(Block * source,
183          Block * target,
184          EdgeTypeEnum type);
185      virtual ~Edge();
186
187     void ignore_index() { _from_index = false; }
188     void from_index() { _from_index = true; }
189     Block * src() const { return _source.load(); }
190     Block * trg() const;
191     Address trg_addr() const { return _target_off; }
192     EdgeTypeEnum type() const { 
193         return static_cast<EdgeTypeEnum>(_type._type_enum); 
194     }
195     bool sinkEdge() const { return _type._sink != 0; }
196     bool interproc() const { 
197        return (_type._interproc != 0 ||
198                type() == CALL ||
199                type() == RET);
200     }
201
202     bool intraproc() const {
203        return !interproc();
204     }
205
206     void install();
207
208     /* removes from blocks (and if of type CALL, from finalized source functions ) */
209     void uninstall();
210
211     static void destroy(Edge *, CodeObject *);
212
213  friend class CFGFactory;
214  friend class Parser;
215 };
216
217 /* 
218  * Iteration over edges can be controlled by an EdgePredicate.
219  * Edges are returned only if pred(edge) evaluates true.
220  * 
221  * EdgePredicates are composable by AND.
222  */
223 class PARSER_EXPORT EdgePredicate 
224 {
225  public:
226   EdgePredicate() { }
227     virtual ~EdgePredicate() { }
228     virtual bool pred_impl(Edge *) const;
229     bool operator()(Edge* e) const 
230     {
231       return pred_impl(e);
232     }
233  };
234
235 /* may follow branches into the function if there is shared code */
236 class PARSER_EXPORT Intraproc : public EdgePredicate {
237  public:
238     Intraproc() { }
239     ~Intraproc() { }
240     bool pred_impl(Edge *) const;
241
242 };
243
244 /* follow interprocedural edges */
245  class PARSER_EXPORT Interproc : public EdgePredicate {
246     public:
247         Interproc() {}
248         ~Interproc() { }
249         bool pred_impl(Edge *) const;
250 };
251
252 /*
253  * For proper ostritch-like denial of 
254  * unresolved control flow edges
255  */
256  class PARSER_EXPORT NoSinkPredicate : public ParseAPI::EdgePredicate {
257  public:
258     NoSinkPredicate() { }
259
260     bool pred_impl(ParseAPI::Edge * e) const {
261         return !e->sinkEdge() && EdgePredicate::pred_impl(e);
262     }
263 };
264
265 /* doesn't follow branches into the function if there is shared code */
266 class Function;
267  class PARSER_EXPORT SingleContext : public EdgePredicate {
268  private:
269     const Function * _context;
270     bool _forward;
271     bool _backward;
272  public:
273     SingleContext(const Function * f, bool forward, bool backward) :
274         _context(f),
275         _forward(forward),
276         _backward(backward) { }
277     ~SingleContext() { }
278     bool pred_impl(Edge *) const;
279 };
280
281 /* Doesn't follow branches into the function if there is shared code. 
282  * Will follow interprocedural call/return edges */
283  class PARSER_EXPORT SingleContextOrInterproc : public EdgePredicate {
284     private:
285         const Function * _context;
286         bool _forward;
287         bool _backward;
288     public:
289         SingleContextOrInterproc(const Function * f, bool forward, bool backward) :
290             _context(f),
291             _forward(forward),
292             _backward(backward) { }
293         ~SingleContextOrInterproc() { }
294         bool pred_impl(Edge *) const;
295         bool operator()(Edge* e) const 
296         {
297           return pred_impl(e);
298         }
299 };
300
301 class CodeRegion;
302
303 class PARSER_EXPORT Block :
304         public Dyninst::SimpleInterval<Address, int>,
305         public allocatable,
306         public boost::lockable_adapter<boost::recursive_mutex> {
307     friend class CFGModifier;
308     friend class Parser;
309  public:
310     typedef std::map<Offset, InstructionAPI::Instruction> Insns;
311     typedef std::list<Edge*> edgelist;
312 public:
313     static Block * sink_block;
314
315     Block(CodeObject * o, CodeRegion * r, Address start, Function* f = NULL);
316     virtual ~Block();
317     boost::recursive_mutex& lockable() { return boost::lockable_adapter<boost::recursive_mutex>::lockable(); }
318
319     inline Address start() const { return _start; }
320     inline Address end() const { return _end; }
321     inline Address lastInsnAddr() const {  return _lastInsn; }
322     virtual Address last() const {  return lastInsnAddr(); }
323     inline Address size() const {  return _end - _start; }
324     bool containsAddr(Address addr) const {   return addr >= _start && addr < _end; }
325
326     bool parsed() const {  return _parsed; }
327
328     CodeObject * obj() const {  return _obj; }
329     CodeRegion * region() const {  return _region; }
330
331     /* Edge access */
332     const edgelist & sources() const { return _srclist; }
333     const edgelist & targets() const { return _trglist; }
334     void copy_sources(edgelist & src) {
335         boost::lock_guard<Block> g(*this);
336         src = _srclist;
337     }
338     void copy_targets(edgelist & trg) {
339         boost::lock_guard<Block> g(*this);
340         trg = _trglist;
341     }
342
343     bool consistent(Address addr, Address & prev_insn);
344
345     int  containingFuncs() const;
346     void getFuncs(std::vector<Function *> & funcs);
347     template<class OutputIterator> void getFuncs(OutputIterator result); 
348
349     virtual void getInsns(Insns &insns) const;
350     InstructionAPI::Instruction getInsn(Offset o) const;
351
352     bool wasUserAdded() const;
353
354     /* interval implementation */
355     Address low() const override {  return start(); }
356     Address high() const override {   return end(); }
357
358     struct compare {
359         bool operator()(Block * const & b1, Block * const & b2) const {
360             if(b1->start() < b2->start()) return true;
361             if(b1->start() > b2->start()) return false;
362             
363             // XXX debugging
364             if(b1 != b2)
365                 fprintf(stderr,"FATAL: blocks %p [%lx,%lx) and %p [%lx,%lx) "
366                             "conflict",b1,b1->start(),b1->end(),
367                             b2,b2->start(),b2->end());
368
369             assert(b1 == b2);
370             return false;
371         }
372     };
373
374     static void destroy(Block *b);
375
376     bool operator==(const Block &rhs) const;
377
378     bool operator!=(const Block &rhs) const;
379     Function * createdByFunc() { return _createdByFunc; }
380
381 private:
382     std::map<int, std::set<Address> > targetMap;
383     std::map<int, std::set<Address> > sourceMap;
384     void addSource(Edge * e);
385     void addTarget(Edge * e);
386     void removeTarget(Edge * e);
387     void removeSource(Edge * e);
388     void removeFunc(Function *);
389     friend class region_data;
390     void updateEnd(Address addr);
391
392  private:
393     CodeObject * _obj;
394     CodeRegion * _region;
395
396     Address _start;
397     Address _end;
398     Address _lastInsn;
399
400
401     edgelist _srclist;
402     edgelist _trglist;
403     boost::atomic<int> _func_cnt;
404     bool _parsed;
405
406     Function * _createdByFunc;
407
408
409  friend class Edge;
410  friend class Function;
411  friend class CFGFactory;
412 };
413
414 enum FuncReturnStatus {
415     UNSET,
416     NORETURN,
417     UNKNOWN,
418     RETURN
419 };
420
421 /* Discovery method of functions */
422 enum FuncSource {
423     RT = 0,     // recursive traversal (default)
424     HINT,       // specified in code object hints
425     GAP,        // gap heuristics
426     GAPRT,      // RT from gap-discovered function
427     ONDEMAND,   // dynamically discovered
428     MODIFICATION, // Added via user modification
429     _funcsource_end_
430 };
431
432 enum StackTamper {
433     TAMPER_UNSET,
434     TAMPER_NONE,
435     TAMPER_REL,
436     TAMPER_ABS,
437     TAMPER_NONZERO
438 };
439
440 class CodeObject;
441 class CodeRegion;
442 class FuncExtent;
443 class Loop;
444 class LoopTreeNode;
445
446 class PARSER_EXPORT Function : public allocatable, public AnnotatableSparse, public boost::lockable_adapter<boost::recursive_mutex> {
447    friend class CFGModifier;
448    friend class LoopAnalyzer;
449  protected:
450     Address _start;
451     CodeObject * _obj;
452     CodeRegion * _region;
453     InstructionSource * _isrc;
454     bool _cache_valid;
455     
456     FuncSource _src;
457     boost::atomic<FuncReturnStatus> _rs;
458
459     std::string _name;
460     Block * _entry;
461  protected:
462     Function(); 
463  public:
464     
465     struct JumpTableInstance {
466         AST::Ptr jumpTargetExpr;
467         Address tableStart;
468         Address tableEnd;
469         int indexStride;
470         int memoryReadSize;
471         bool isZeroExtend;
472         std::map<Address, Address> tableEntryMap;
473         Block* block;
474     };
475     std::map<Address, JumpTableInstance> & getJumpTables() { return jumptables; }
476
477     bool _is_leaf_function;
478     Address _ret_addr; // return address of a function stored in stack at function entry
479     typedef std::map<Address, Block*> blockmap;
480     template <typename P>
481     struct select2nd
482     {
483       typedef typename P::second_type result_type;
484       
485       result_type operator()(const P& p) const
486       {
487         return p.second;
488       }
489     };
490     typedef select2nd<blockmap::value_type> selector;
491
492     
493     typedef boost::transform_iterator<selector, blockmap::iterator> bmap_iterator;
494     typedef boost::transform_iterator<selector, blockmap::const_iterator> bmap_const_iterator;
495     typedef boost::iterator_range<bmap_iterator> blocklist;
496     typedef boost::iterator_range<bmap_const_iterator> const_blocklist;
497     typedef std::set<Edge*> edgelist;
498     
499     Function(Address addr, std::string name, CodeObject * obj, 
500         CodeRegion * region, InstructionSource * isource);
501
502     virtual ~Function();
503     boost::recursive_mutex& lockable() { return boost::lockable_adapter<boost::recursive_mutex>::lockable(); }
504
505     virtual const std::string & name() const;
506     void rename(std::string n) { _name = n; }
507
508     Address addr() const { return _start; }
509     CodeRegion * region() const { return _region; }
510     InstructionSource * isrc() const { return _isrc; }
511     CodeObject * obj() const { return _obj; }
512     FuncSource src() const { return _src; }
513     FuncReturnStatus retstatus() const { 
514       FuncReturnStatus ret = _rs.load();
515       return ret; 
516     }
517     Block * entry() const { return _entry; }
518     bool parsed() const { return _parsed; }
519
520     /* Basic block and CFG access */
521     blocklist blocks();
522     const_blocklist blocks() const;
523     size_t num_blocks()
524     {
525       boost::lock_guard<Function> g(*this);
526       if(!_cache_valid) finalize();
527       return _bmap.size();
528     }
529     size_t num_blocks() const
530     { 
531       return _bmap.size();
532     }
533
534     
535     bool contains(Block *b);
536     bool contains(Block *b) const;
537     const edgelist & callEdges();
538     const_blocklist returnBlocks() ;
539     const_blocklist exitBlocks();
540     const_blocklist exitBlocks() const;
541
542     /* Function details */
543     bool hasNoStackFrame() const { return _no_stack_frame; }
544     bool savesFramePointer() const { return _saves_fp; }
545     bool cleansOwnStack() const { return _cleans_stack; }
546
547     /* Loops */    
548     LoopTreeNode* getLoopTree() const;
549     Loop* findLoop(const char *name) const;
550     bool getLoops(std::vector<Loop*> &loops) const;
551     bool getOuterLoops(std::vector<Loop*> &loops) const;
552
553     /* Dominator info */
554
555     /* Return true if A dominates B in this function */
556     bool dominates(Block* A, Block *B) const;
557     Block* getImmediateDominator(Block *A) const;
558     void getImmediateDominates(Block *A, std::set<Block*> &) const;
559     void getAllDominates(Block *A, std::set<Block*> &) const;
560
561     /* Post-dominator info */
562
563     /* Return true if A post-dominates B in this function */
564     bool postDominates(Block* A, Block *B) const;
565     Block* getImmediatePostDominator(Block *A) const;
566     void getImmediatePostDominates(Block *A, std::set<Block*> &) const;
567     void getAllPostDominates(Block *A, std::set<Block*> &) const;
568
569
570     /* Parse updates and obfuscation */
571     void setEntryBlock(Block *new_entry);
572     void set_retstatus(FuncReturnStatus rs);
573     void removeBlock( Block* );
574
575     StackTamper tampersStack(bool recalculate=false);
576
577     struct less
578     {
579         bool operator()(const Function * f1, const Function * f2) const
580         {
581             return f1->addr() < f2->addr();
582         }
583     };
584
585     /* Contiguous code segments of function */
586     std::vector<FuncExtent *> const& extents();
587
588     /* This should not remain here - this is an experimental fix for
589        defensive mode CFG inconsistency */
590     void invalidateCache() { _cache_valid = false; }
591     inline std::pair<Address, Block*> get_next_block(
592             Address addr,
593             CodeRegion *codereg) const;
594
595     static void destroy(Function *f);
596
597     /*** Internal parsing methods and state ***/
598     void add_block(Block *b);
599
600  private:
601     void delayed_link_return(CodeObject * co, Block * retblk);
602     void finalize();
603
604     bool _parsed;
605     //    blocklist _bl;
606     std::vector<FuncExtent *> _extents;
607
608     /* rapid lookup for edge predicate tests */
609     blocklist blocks_int();
610     
611     blockmap _bmap;
612     bmap_iterator blocks_begin() {
613       return bmap_iterator(_bmap.begin());
614     }
615     bmap_iterator blocks_end() {
616       return bmap_iterator(_bmap.end());
617     }
618     bmap_const_iterator blocks_begin() const 
619     {
620       return bmap_const_iterator(_bmap.begin());
621     }
622     
623     bmap_const_iterator blocks_end() const 
624     {
625       return bmap_const_iterator(_bmap.end());
626     }
627     
628     
629
630     /* rapid lookup for interprocedural queries */
631     edgelist _call_edge_list;
632     blockmap _retBL;
633     bmap_const_iterator ret_begin() const 
634     {
635       return bmap_const_iterator(_retBL.begin());
636     }
637     bmap_const_iterator ret_end() const 
638     {
639       return bmap_const_iterator(_retBL.end());
640     }
641     // Superset of return blocks; this includes all blocks where
642     // execution leaves the function without coming back, including
643     // returns, calls to non-returning calls, tail calls, etc.
644     // Might want to include exceptions...
645     blockmap _exitBL;
646     bmap_const_iterator exit_begin() const 
647     {
648       return bmap_const_iterator(_exitBL.begin());
649     }
650     bmap_const_iterator exit_end() const 
651     {
652       return bmap_const_iterator(_exitBL.end());
653     }
654
655     /* function details */
656     bool _no_stack_frame;
657     bool _saves_fp;
658     bool _cleans_stack;
659     StackTamper _tamper;
660     Address _tamper_addr;
661
662     /* Loop details*/
663     mutable bool _loop_analyzed; // true if loops in the function have been found and stored in _loops
664     mutable std::set<Loop*> _loops;
665     mutable LoopTreeNode *_loop_root; // NULL if the tree structure has not be calculated
666     void getLoopsByNestingLevel(std::vector<Loop*>& lbb, bool outerMostOnly) const;
667     std::map<Address, JumpTableInstance> jumptables;
668
669     /* Dominator and post-dominator info details */
670     mutable bool isDominatorInfoReady;
671     mutable bool isPostDominatorInfoReady;
672     void fillDominatorInfo() const;
673     void fillPostDominatorInfo() const;
674     /** set of basic blocks that this basicblock dominates immediately*/
675     mutable std::map<Block*, std::set<Block*>*> immediateDominates;
676     /** basic block which is the immediate dominator of the basic block */
677     mutable std::map<Block*, Block*> immediateDominator;
678     /** same as previous two fields, but for postdominator tree */
679     mutable std::map<Block*, std::set<Block*>*> immediatePostDominates;
680     mutable std::map<Block*, Block*> immediatePostDominator;
681
682     friend void Edge::uninstall();
683     friend class Parser;
684     friend class CFGFactory;
685     friend class CodeObject;
686     friend class dominatorCFG;
687 };
688 inline std::pair<Address, Block*> Function::get_next_block(
689         Address addr,
690         CodeRegion *) const
691 {
692     Block * nextBlock = NULL;
693     Address nextBlockAddr;
694     nextBlockAddr = std::numeric_limits<Address>::max();
695     for(auto i = _bmap.begin();
696         i != _bmap.end();
697         ++i)
698     {
699         if(i->first > addr && i->first < nextBlockAddr) {
700             nextBlockAddr = i->first;
701             nextBlock = i->second;
702         }
703     }
704
705     return std::pair<Address,Block*>(nextBlockAddr,nextBlock);
706 }
707
708 /* Describes a contiguous extent of a Function object */
709 class PARSER_EXPORT FuncExtent : public Dyninst::SimpleInterval<Address, Function* > {
710  private:
711     Function * _func;
712     Address _start;
713     Address _end;
714
715  public:
716     FuncExtent(Function * f, Address start, Address end) :
717         _func(f),
718         _start(start),
719         _end(end) { }
720
721     virtual ~FuncExtent() {
722         _func = NULL;
723     }
724
725     Function * func() { return _func; }
726
727     Address start() const { return _start; }
728     Address end() const { return _end; }
729
730     /* interval implementation */
731     Address low() const { return _start; }
732     Address high() const { return _end; }
733     Function* id() const { return _func; }
734
735     bool operator==(const FuncExtent &rhs) const {
736         return _func == rhs._func &&
737                _start == rhs._start &&
738                _end == rhs._end;
739     }
740
741     bool operator!=(const FuncExtent &rhs) const {
742         return !(rhs == *this);
743     }
744 };
745
746 /** Natural loops
747   */
748
749 class PARSER_EXPORT Loop  
750 {
751         friend class LoopAnalyzer;
752         friend std::ostream& operator<<(std::ostream&,Loop&);
753
754 private:
755         std::set<Edge*> backEdges;
756         std::set<Block*> entries;
757
758         // the function this loop is part of
759         const Function * func;
760
761         /** set of loops that are contained (nested) in this loop. */
762         std::set<Loop*> containedLoops;
763
764         /** the basic blocks in the loop */
765
766         std::set<Block*> childBlocks;
767         std::set<Block*> exclusiveBlocks;
768     Loop* parent;
769 public:
770         /** If loop which directly encloses this loop. NULL if no such loop */
771     void insertBlock(Block* b);
772     void insertChildBlock(Block* b);
773
774     Loop* parentLoop() { return parent; }
775         /** Return true if the given address is within the range of
776             this loop's basicBlocks */
777
778         bool containsAddress(Address addr);
779           
780         /** Return true if the given address is within the range of
781             this loop's basicBlocks or its children */
782                    
783         bool containsAddressInclusive(Address addr);
784
785
786         /** Loop::getBackEdges */
787         /** Sets edges to the set of back edges that define this loop,
788             returns the number of back edges that define this loop */
789         int getBackEdges(std::vector<Edge*> &edges);
790
791         /* returns the entry blocks of the loop.
792          * A natural loop has a single entry block
793          * and an irreducible loop has mulbile entry blocks
794          * */
795         int getLoopEntries(std::vector<Block*>&);
796
797         /** Loop::getContainedLoops    */
798         /** returns vector of contained loops */
799
800         bool getContainedLoops(std::vector<Loop*> &loops);
801
802         /** Loop::getOuterLoops    */
803         /** returns vector of outer contained loops */
804
805         bool getOuterLoops(std::vector<Loop*> &loops);
806
807         /** Loop::getLoopBasicBlocks    */
808         /** returns all basic blocks in the loop */
809
810         bool getLoopBasicBlocks(std::vector<Block*> &blocks);
811
812         /** Loop::getLoopBasicBlocksExclusive    */
813         /** returns all basic blocks in this loop, exluding the blocks
814             of its sub loops. */
815
816         bool getLoopBasicBlocksExclusive(std::vector<Block*> &blocks);
817
818         /** does this loop or its subloops contain the given block? */
819
820         bool hasBlock(Block *b);
821
822         /** does this loop contain the given block? */
823
824         bool hasBlockExclusive(Block *b);
825
826         /** Loop::hasAncestor    */
827         /** returns true if this loop is a descendant of the given loop */
828
829         bool hasAncestor(Loop *loop);
830
831         /** returns the function this loop is in */
832
833         const Function * getFunction();
834
835         /** Loop::~Loop    */
836         /** destructor for the class */
837
838         ~Loop() { }
839
840         std::string format() const;
841     void insertLoop(Loop *childLoop);
842
843 private:
844 // internal use only
845         /** constructor of class */
846         Loop(const Function *);
847
848         /** constructor of the class */
849         Loop(Edge *, const Function *);
850
851         /** get either contained or outer loops, determined by outerMostOnly */
852         bool getLoops(std::vector<Loop*>&, 
853                       bool outerMostOnly) const;
854
855         }; // class Loop
856
857 /** A class to represent the tree of nested loops and 
858  *  callees (functions) in the control flow graph.
859  *  @see BPatch_basicBlockLoop
860  *  @see BPatch_flowGraph
861  */
862
863 class PARSER_EXPORT LoopTreeNode {
864     friend class LoopAnalyzer;
865
866  public:
867     // A loop node contains a single Loop instance
868     Loop *loop;
869
870     // The LoopTreeNode instances nested within this loop.
871     std::vector<LoopTreeNode *> children;
872
873     //  LoopTreeNode::LoopTreeNode
874     //  Create a loop tree node for Loop with name n 
875     LoopTreeNode(Loop *l, const char *n);
876
877     //  Destructor
878     ~LoopTreeNode();
879
880     //  LoopTreeNode::name
881     //  Return the name of this loop. 
882     const char * name(); 
883
884     //  LoopTreeNode::getCalleeName
885     //  Return the function name of the ith callee. 
886     const char * getCalleeName(unsigned int i);
887
888     //  LoopTreeNode::numCallees
889     //  Return the number of callees contained in this loop's body. 
890     unsigned int numCallees();
891
892     //Returns a vector of the functions called by this loop.
893     bool getCallees(std::vector<Function *> &v);
894     
895
896     //  BPatch_loopTreeNode::findLoop
897     //  find loop by hierarchical name
898     Loop * findLoop(const char *name);
899
900  private:
901
902     /** name which indicates this loop's relative nesting */
903     char *hierarchicalName;
904
905     // A vector of functions called within the body of this loop (and
906     // not the body of sub loops). 
907     std::vector<Function *> callees;
908
909 }; // class LoopTreeNode 
910
911 } //namespace ParseAPI
912 } //namespace Dyninst
913
914 #endif