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