LLVM API Documentation

Dominators.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the following classes:
00011 //  1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
00012 //     and their immediate dominator.
00013 //  2. DominatorSet: Calculates the [reverse] dominator set for a function
00014 //  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
00015 //     structure.
00016 //  4. ETForest: Efficient data structure for dominance comparisons and 
00017 //     nearest-common-ancestor queries.
00018 //  5. DominanceFrontier: Calculate and hold the dominance frontier for a
00019 //     function.
00020 //
00021 //  These data structures are listed in increasing order of complexity.  It
00022 //  takes longer to calculate the dominator frontier, for example, than the
00023 //  ImmediateDominator mapping.
00024 //
00025 //===----------------------------------------------------------------------===//
00026 
00027 #ifndef LLVM_ANALYSIS_DOMINATORS_H
00028 #define LLVM_ANALYSIS_DOMINATORS_H
00029 
00030 #include "llvm/Analysis/ET-Forest.h"
00031 #include "llvm/Pass.h"
00032 #include <set>
00033 
00034 namespace llvm {
00035 
00036 class Instruction;
00037 
00038 template <typename GraphType> struct GraphTraits;
00039 
00040 //===----------------------------------------------------------------------===//
00041 /// DominatorBase - Base class that other, more interesting dominator analyses
00042 /// inherit from.
00043 ///
00044 class DominatorBase : public FunctionPass {
00045 protected:
00046   std::vector<BasicBlock*> Roots;
00047   const bool IsPostDominators;
00048 
00049   inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
00050 public:
00051   /// getRoots -  Return the root blocks of the current CFG.  This may include
00052   /// multiple blocks if we are computing post dominators.  For forward
00053   /// dominators, this will always be a single block (the entry node).
00054   ///
00055   inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
00056 
00057   /// isPostDominator - Returns true if analysis based of postdoms
00058   ///
00059   bool isPostDominator() const { return IsPostDominators; }
00060 };
00061 
00062 
00063 //===----------------------------------------------------------------------===//
00064 /// ImmediateDominators - Calculate the immediate dominator for each node in a
00065 /// function.
00066 ///
00067 class ImmediateDominatorsBase : public DominatorBase {
00068 protected:
00069   struct InfoRec {
00070     unsigned Semi;
00071     unsigned Size;
00072     BasicBlock *Label, *Parent, *Child, *Ancestor;
00073     
00074     std::vector<BasicBlock*> Bucket;
00075     
00076     InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
00077   };
00078   
00079   std::map<BasicBlock*, BasicBlock*> IDoms;
00080 
00081   // Vertex - Map the DFS number to the BasicBlock*
00082   std::vector<BasicBlock*> Vertex;
00083   
00084   // Info - Collection of information used during the computation of idoms.
00085   std::map<BasicBlock*, InfoRec> Info;
00086 public:
00087   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
00088 
00089   virtual void releaseMemory() { IDoms.clear(); }
00090 
00091   // Accessor interface:
00092   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
00093   typedef IDomMapType::const_iterator const_iterator;
00094   inline const_iterator begin() const { return IDoms.begin(); }
00095   inline const_iterator end()   const { return IDoms.end(); }
00096   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
00097 
00098   /// operator[] - Return the idom for the specified basic block.  The start
00099   /// node returns null, because it does not have an immediate dominator.
00100   ///
00101   inline BasicBlock *operator[](BasicBlock *BB) const {
00102     return get(BB);
00103   }
00104 
00105   /// get() - Synonym for operator[].
00106   ///
00107   inline BasicBlock *get(BasicBlock *BB) const {
00108     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
00109     return I != IDoms.end() ? I->second : 0;
00110   }
00111 
00112   //===--------------------------------------------------------------------===//
00113   // API to update Immediate(Post)Dominators information based on modifications
00114   // to the CFG...
00115 
00116   /// addNewBlock - Add a new block to the CFG, with the specified immediate
00117   /// dominator.
00118   ///
00119   void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
00120     assert(get(BB) == 0 && "BasicBlock already in idom info!");
00121     IDoms[BB] = IDom;
00122   }
00123 
00124   /// setImmediateDominator - Update the immediate dominator information to
00125   /// change the current immediate dominator for the specified block to another
00126   /// block.  This method requires that BB already have an IDom, otherwise just
00127   /// use addNewBlock.
00128   ///
00129   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
00130     assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
00131     IDoms[BB] = NewIDom;
00132   }
00133 
00134   /// print - Convert to human readable form
00135   ///
00136   virtual void print(std::ostream &OS, const Module* = 0) const;
00137 };
00138 
00139 //===-------------------------------------
00140 /// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
00141 /// that is used to compute a normal immediate dominator set.
00142 ///
00143 struct ImmediateDominators : public ImmediateDominatorsBase {
00144   ImmediateDominators() : ImmediateDominatorsBase(false) {}
00145 
00146   BasicBlock *getRoot() const {
00147     assert(Roots.size() == 1 && "Should always have entry node!");
00148     return Roots[0];
00149   }
00150 
00151   virtual bool runOnFunction(Function &F);
00152 
00153   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00154     AU.setPreservesAll();
00155   }
00156 
00157 private:
00158   unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
00159   void Compress(BasicBlock *V, InfoRec &VInfo);
00160   BasicBlock *Eval(BasicBlock *v);
00161   void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
00162 };
00163 
00164 
00165 
00166 //===----------------------------------------------------------------------===//
00167 /// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
00168 /// function, that represents the blocks that dominate the block.  If the block
00169 /// is unreachable in this function, the set will be empty.  This cannot happen
00170 /// for reachable code, because every block dominates at least itself.
00171 ///
00172 struct DominatorSetBase : public DominatorBase {
00173   typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
00174   // Map of dom sets
00175   typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
00176 protected:
00177   DomSetMapType Doms;
00178 public:
00179   DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
00180 
00181   virtual void releaseMemory() { Doms.clear(); }
00182 
00183   // Accessor interface:
00184   typedef DomSetMapType::const_iterator const_iterator;
00185   typedef DomSetMapType::iterator iterator;
00186   inline const_iterator begin() const { return Doms.begin(); }
00187   inline       iterator begin()       { return Doms.begin(); }
00188   inline const_iterator end()   const { return Doms.end(); }
00189   inline       iterator end()         { return Doms.end(); }
00190   inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
00191   inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
00192 
00193 
00194   /// getDominators - Return the set of basic blocks that dominate the specified
00195   /// block.
00196   ///
00197   inline const DomSetType &getDominators(BasicBlock *BB) const {
00198     const_iterator I = find(BB);
00199     assert(I != end() && "BB not in function!");
00200     return I->second;
00201   }
00202 
00203   /// isReachable - Return true if the specified basicblock is reachable.  If
00204   /// the block is reachable, we have dominator set information for it.
00205   ///
00206   bool isReachable(BasicBlock *BB) const {
00207     return !getDominators(BB).empty();
00208   }
00209 
00210   /// dominates - Return true if A dominates B.
00211   ///
00212   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
00213     return getDominators(B).count(A) != 0;
00214   }
00215 
00216   /// properlyDominates - Return true if A dominates B and A != B.
00217   ///
00218   bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
00219     return dominates(A, B) && A != B;
00220   }
00221 
00222   /// print - Convert to human readable form
00223   ///
00224   virtual void print(std::ostream &OS, const Module* = 0) const;
00225 
00226   /// dominates - Return true if A dominates B.  This performs the special
00227   /// checks necessary if A and B are in the same basic block.
00228   ///
00229   bool dominates(Instruction *A, Instruction *B) const;
00230 
00231   //===--------------------------------------------------------------------===//
00232   // API to update (Post)DominatorSet information based on modifications to
00233   // the CFG...
00234 
00235   /// addBasicBlock - Call to update the dominator set with information about a
00236   /// new block that was inserted into the function.
00237   ///
00238   void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
00239     assert(find(BB) == end() && "Block already in DominatorSet!");
00240     Doms.insert(std::make_pair(BB, Dominators));
00241   }
00242 
00243   /// addDominator - If a new block is inserted into the CFG, then method may be
00244   /// called to notify the blocks it dominates that it is in their set.
00245   ///
00246   void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
00247     iterator I = find(BB);
00248     assert(I != end() && "BB is not in DominatorSet!");
00249     I->second.insert(NewDominator);
00250   }
00251 };
00252 
00253 
00254 //===-------------------------------------
00255 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
00256 /// compute a normal dominator set.
00257 ///
00258 struct DominatorSet : public DominatorSetBase {
00259   DominatorSet() : DominatorSetBase(false) {}
00260 
00261   virtual bool runOnFunction(Function &F);
00262 
00263   BasicBlock *getRoot() const {
00264     assert(Roots.size() == 1 && "Should always have entry node!");
00265     return Roots[0];
00266   }
00267 
00268   /// getAnalysisUsage - This simply provides a dominator set
00269   ///
00270   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00271     AU.addRequired<ImmediateDominators>();
00272     AU.setPreservesAll();
00273   }
00274 
00275   // stub - dummy function, just ignore it
00276   static void stub();
00277 };
00278 
00279 
00280 //===----------------------------------------------------------------------===//
00281 /// DominatorTree - Calculate the immediate dominator tree for a function.
00282 ///
00283 struct DominatorTreeBase : public DominatorBase {
00284   class Node;
00285 protected:
00286   std::map<BasicBlock*, Node*> Nodes;
00287   void reset();
00288   typedef std::map<BasicBlock*, Node*> NodeMapType;
00289 
00290   Node *RootNode;
00291 public:
00292   class Node {
00293     friend struct DominatorTree;
00294     friend struct PostDominatorTree;
00295     friend struct DominatorTreeBase;
00296     BasicBlock *TheBB;
00297     Node *IDom;
00298     std::vector<Node*> Children;
00299   public:
00300     typedef std::vector<Node*>::iterator iterator;
00301     typedef std::vector<Node*>::const_iterator const_iterator;
00302 
00303     iterator begin()             { return Children.begin(); }
00304     iterator end()               { return Children.end(); }
00305     const_iterator begin() const { return Children.begin(); }
00306     const_iterator end()   const { return Children.end(); }
00307 
00308     inline BasicBlock *getBlock() const { return TheBB; }
00309     inline Node *getIDom() const { return IDom; }
00310     inline const std::vector<Node*> &getChildren() const { return Children; }
00311 
00312     /// properlyDominates - Returns true iff this dominates N and this != N.
00313     /// Note that this is not a constant time operation!
00314     ///
00315     bool properlyDominates(const Node *N) const {
00316       const Node *IDom;
00317       if (this == 0 || N == 0) return false;
00318       while ((IDom = N->getIDom()) != 0 && IDom != this)
00319         N = IDom;   // Walk up the tree
00320       return IDom != 0;
00321     }
00322 
00323     /// dominates - Returns true iff this dominates N.  Note that this is not a
00324     /// constant time operation!
00325     ///
00326     inline bool dominates(const Node *N) const {
00327       if (N == this) return true;  // A node trivially dominates itself.
00328       return properlyDominates(N);
00329     }
00330     
00331   private:
00332     inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
00333     inline Node *addChild(Node *C) { Children.push_back(C); return C; }
00334 
00335     void setIDom(Node *NewIDom);
00336   };
00337 
00338 public:
00339   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
00340   ~DominatorTreeBase() { reset(); }
00341 
00342   virtual void releaseMemory() { reset(); }
00343 
00344   /// getNode - return the (Post)DominatorTree node for the specified basic
00345   /// block.  This is the same as using operator[] on this class.
00346   ///
00347   inline Node *getNode(BasicBlock *BB) const {
00348     NodeMapType::const_iterator i = Nodes.find(BB);
00349     return (i != Nodes.end()) ? i->second : 0;
00350   }
00351 
00352   inline Node *operator[](BasicBlock *BB) const {
00353     return getNode(BB);
00354   }
00355 
00356   /// getRootNode - This returns the entry node for the CFG of the function.  If
00357   /// this tree represents the post-dominance relations for a function, however,
00358   /// this root may be a node with the block == NULL.  This is the case when
00359   /// there are multiple exit nodes from a particular function.  Consumers of
00360   /// post-dominance information must be capable of dealing with this
00361   /// possibility.
00362   ///
00363   Node *getRootNode() { return RootNode; }
00364   const Node *getRootNode() const { return RootNode; }
00365 
00366   //===--------------------------------------------------------------------===//
00367   // API to update (Post)DominatorTree information based on modifications to
00368   // the CFG...
00369 
00370   /// createNewNode - Add a new node to the dominator tree information.  This
00371   /// creates a new node as a child of IDomNode, linking it into the children
00372   /// list of the immediate dominator.
00373   ///
00374   Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
00375     assert(getNode(BB) == 0 && "Block already in dominator tree!");
00376     assert(IDomNode && "Not immediate dominator specified for block!");
00377     return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
00378   }
00379 
00380   /// changeImmediateDominator - This method is used to update the dominator
00381   /// tree information when a node's immediate dominator changes.
00382   ///
00383   void changeImmediateDominator(Node *N, Node *NewIDom) {
00384     assert(N && NewIDom && "Cannot change null node pointers!");
00385     N->setIDom(NewIDom);
00386   }
00387 
00388   /// print - Convert to human readable form
00389   ///
00390   virtual void print(std::ostream &OS, const Module* = 0) const;
00391 };
00392 
00393 
00394 //===-------------------------------------
00395 /// ET-Forest Class - Class used to construct forwards and backwards 
00396 /// ET-Forests
00397 ///
00398 struct ETForestBase : public DominatorBase {
00399   ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(), 
00400                                  DFSInfoValid(false), SlowQueries(0) {}
00401   
00402   virtual void releaseMemory() { reset(); }
00403 
00404   typedef std::map<BasicBlock*, ETNode*> ETMapType;
00405 
00406   void updateDFSNumbers();
00407     
00408   /// dominates - Return true if A dominates B.
00409   ///
00410   inline bool dominates(BasicBlock *A, BasicBlock *B) {
00411     if (A == B)
00412       return true;
00413     
00414     ETNode *NodeA = getNode(A);
00415     ETNode *NodeB = getNode(B);
00416     
00417     if (DFSInfoValid)
00418       return NodeB->DominatedBy(NodeA);
00419     else {
00420       // If we end up with too many slow queries, just update the
00421       // DFS numbers on the theory that we are going to keep querying.
00422       SlowQueries++;
00423       if (SlowQueries > 32) {
00424         updateDFSNumbers();
00425         return NodeB->DominatedBy(NodeA);
00426       }
00427       return NodeB->DominatedBySlow(NodeA);
00428     }
00429   }
00430 
00431   /// properlyDominates - Return true if A dominates B and A != B.
00432   ///
00433   bool properlyDominates(BasicBlock *A, BasicBlock *B) {
00434     return dominates(A, B) && A != B;
00435   }
00436 
00437   /// Return the nearest common dominator of A and B.
00438   BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
00439     ETNode *NodeA = getNode(A);
00440     ETNode *NodeB = getNode(B);
00441     
00442     ETNode *Common = NodeA->NCA(NodeB);
00443     if (!Common)
00444       return NULL;
00445     return Common->getData<BasicBlock>();
00446   }
00447 
00448   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00449     AU.setPreservesAll();
00450     AU.addRequired<ImmediateDominators>();
00451   }
00452   //===--------------------------------------------------------------------===//
00453   // API to update Forest information based on modifications
00454   // to the CFG...
00455 
00456   /// addNewBlock - Add a new block to the CFG, with the specified immediate
00457   /// dominator.
00458   ///
00459   void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
00460 
00461   /// setImmediateDominator - Update the immediate dominator information to
00462   /// change the current immediate dominator for the specified block
00463   /// to another block.  This method requires that BB for NewIDom
00464   /// already have an ETNode, otherwise just use addNewBlock.
00465   ///
00466   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
00467   /// print - Convert to human readable form
00468   ///
00469   virtual void print(std::ostream &OS, const Module* = 0) const;
00470 protected:
00471   /// getNode - return the (Post)DominatorTree node for the specified basic
00472   /// block.  This is the same as using operator[] on this class.
00473   ///
00474   inline ETNode *getNode(BasicBlock *BB) const {
00475     ETMapType::const_iterator i = Nodes.find(BB);
00476     return (i != Nodes.end()) ? i->second : 0;
00477   }
00478 
00479   inline ETNode *operator[](BasicBlock *BB) const {
00480     return getNode(BB);
00481   }
00482 
00483   void reset();
00484   ETMapType Nodes;
00485   bool DFSInfoValid;
00486   unsigned int SlowQueries;
00487 
00488 };
00489 
00490 //==-------------------------------------
00491 /// ETForest Class - Concrete subclass of ETForestBase that is used to
00492 /// compute a forwards ET-Forest.
00493 
00494 struct ETForest : public ETForestBase {
00495   ETForest() : ETForestBase(false) {}
00496 
00497   BasicBlock *getRoot() const {
00498     assert(Roots.size() == 1 && "Should always have entry node!");
00499     return Roots[0];
00500   }
00501 
00502   virtual bool runOnFunction(Function &F) {
00503     reset();     // Reset from the last time we were run...
00504     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
00505     Roots = ID.getRoots();
00506     calculate(ID);
00507     return false;
00508   }
00509 
00510   void calculate(const ImmediateDominators &ID);
00511   ETNode *getNodeForBlock(BasicBlock *BB);
00512 };
00513 
00514 //===-------------------------------------
00515 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
00516 /// compute a normal dominator tree.
00517 ///
00518 struct DominatorTree : public DominatorTreeBase {
00519   DominatorTree() : DominatorTreeBase(false) {}
00520 
00521   BasicBlock *getRoot() const {
00522     assert(Roots.size() == 1 && "Should always have entry node!");
00523     return Roots[0];
00524   }
00525 
00526   virtual bool runOnFunction(Function &F) {
00527     reset();     // Reset from the last time we were run...
00528     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
00529     Roots = ID.getRoots();
00530     calculate(ID);
00531     return false;
00532   }
00533 
00534   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00535     AU.setPreservesAll();
00536     AU.addRequired<ImmediateDominators>();
00537   }
00538 private:
00539   void calculate(const ImmediateDominators &ID);
00540   Node *getNodeForBlock(BasicBlock *BB);
00541 };
00542 
00543 //===-------------------------------------
00544 /// DominatorTree GraphTraits specialization so the DominatorTree can be
00545 /// iterable by generic graph iterators.
00546 ///
00547 template <> struct GraphTraits<DominatorTree::Node*> {
00548   typedef DominatorTree::Node NodeType;
00549   typedef NodeType::iterator  ChildIteratorType;
00550 
00551   static NodeType *getEntryNode(NodeType *N) {
00552     return N;
00553   }
00554   static inline ChildIteratorType child_begin(NodeType* N) {
00555     return N->begin();
00556   }
00557   static inline ChildIteratorType child_end(NodeType* N) {
00558     return N->end();
00559   }
00560 };
00561 
00562 template <> struct GraphTraits<DominatorTree*>
00563   : public GraphTraits<DominatorTree::Node*> {
00564   static NodeType *getEntryNode(DominatorTree *DT) {
00565     return DT->getRootNode();
00566   }
00567 };
00568 
00569 //===----------------------------------------------------------------------===//
00570 /// DominanceFrontier - Calculate the dominance frontiers for a function.
00571 ///
00572 struct DominanceFrontierBase : public DominatorBase {
00573   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
00574   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
00575 protected:
00576   DomSetMapType Frontiers;
00577 public:
00578   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
00579 
00580   virtual void releaseMemory() { Frontiers.clear(); }
00581 
00582   // Accessor interface:
00583   typedef DomSetMapType::iterator iterator;
00584   typedef DomSetMapType::const_iterator const_iterator;
00585   iterator       begin()       { return Frontiers.begin(); }
00586   const_iterator begin() const { return Frontiers.begin(); }
00587   iterator       end()         { return Frontiers.end(); }
00588   const_iterator end()   const { return Frontiers.end(); }
00589   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
00590   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
00591 
00592   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
00593     assert(find(BB) == end() && "Block already in DominanceFrontier!");
00594     Frontiers.insert(std::make_pair(BB, frontier));
00595   }
00596 
00597   void addToFrontier(iterator I, BasicBlock *Node) {
00598     assert(I != end() && "BB is not in DominanceFrontier!");
00599     I->second.insert(Node);
00600   }
00601 
00602   void removeFromFrontier(iterator I, BasicBlock *Node) {
00603     assert(I != end() && "BB is not in DominanceFrontier!");
00604     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
00605     I->second.erase(Node);
00606   }
00607 
00608   /// print - Convert to human readable form
00609   ///
00610   virtual void print(std::ostream &OS, const Module* = 0) const;
00611 };
00612 
00613 
00614 //===-------------------------------------
00615 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
00616 /// compute a normal dominator tree.
00617 ///
00618 struct DominanceFrontier : public DominanceFrontierBase {
00619   DominanceFrontier() : DominanceFrontierBase(false) {}
00620 
00621   BasicBlock *getRoot() const {
00622     assert(Roots.size() == 1 && "Should always have entry node!");
00623     return Roots[0];
00624   }
00625 
00626   virtual bool runOnFunction(Function &) {
00627     Frontiers.clear();
00628     DominatorTree &DT = getAnalysis<DominatorTree>();
00629     Roots = DT.getRoots();
00630     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
00631     calculate(DT, DT[Roots[0]]);
00632     return false;
00633   }
00634 
00635   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00636     AU.setPreservesAll();
00637     AU.addRequired<DominatorTree>();
00638   }
00639 private:
00640   const DomSetType &calculate(const DominatorTree &DT,
00641                               const DominatorTree::Node *Node);
00642 };
00643 
00644 
00645 // Make sure that any clients of this file link in Dominators.cpp
00646 static IncludeFile
00647 DOMINATORS_INCLUDE_FILE((void*)&DominatorSet::stub);
00648 } // End llvm namespace
00649 
00650 #endif