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