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 class ImmediateDominators : public ImmediateDominatorsBase {
00144 public:
00145   ImmediateDominators() : ImmediateDominatorsBase(false) {}
00146 
00147   BasicBlock *getRoot() const {
00148     assert(Roots.size() == 1 && "Should always have entry node!");
00149     return Roots[0];
00150   }
00151 
00152   virtual bool runOnFunction(Function &F);
00153 
00154   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00155     AU.setPreservesAll();
00156   }
00157 
00158 private:
00159   unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
00160   void Compress(BasicBlock *V, InfoRec &VInfo);
00161   BasicBlock *Eval(BasicBlock *v);
00162   void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
00163 };
00164 
00165 
00166 
00167 //===----------------------------------------------------------------------===//
00168 /// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
00169 /// function, that represents the blocks that dominate the block.  If the block
00170 /// is unreachable in this function, the set will be empty.  This cannot happen
00171 /// for reachable code, because every block dominates at least itself.
00172 ///
00173 class DominatorSetBase : public DominatorBase {
00174 public:
00175   typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
00176   // Map of dom sets
00177   typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
00178 protected:
00179   DomSetMapType Doms;
00180 public:
00181   DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
00182 
00183   virtual void releaseMemory() { Doms.clear(); }
00184 
00185   // Accessor interface:
00186   typedef DomSetMapType::const_iterator const_iterator;
00187   typedef DomSetMapType::iterator iterator;
00188   inline const_iterator begin() const { return Doms.begin(); }
00189   inline       iterator begin()       { return Doms.begin(); }
00190   inline const_iterator end()   const { return Doms.end(); }
00191   inline       iterator end()         { return Doms.end(); }
00192   inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
00193   inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
00194 
00195 
00196   /// getDominators - Return the set of basic blocks that dominate the specified
00197   /// block.
00198   ///
00199   inline const DomSetType &getDominators(BasicBlock *BB) const {
00200     const_iterator I = find(BB);
00201     assert(I != end() && "BB not in function!");
00202     return I->second;
00203   }
00204 
00205   /// isReachable - Return true if the specified basicblock is reachable.  If
00206   /// the block is reachable, we have dominator set information for it.
00207   ///
00208   bool isReachable(BasicBlock *BB) const {
00209     return !getDominators(BB).empty();
00210   }
00211 
00212   /// dominates - Return true if A dominates B.
00213   ///
00214   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
00215     return getDominators(B).count(A) != 0;
00216   }
00217 
00218   /// properlyDominates - Return true if A dominates B and A != B.
00219   ///
00220   bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
00221     return dominates(A, B) && A != B;
00222   }
00223 
00224   /// print - Convert to human readable form
00225   ///
00226   virtual void print(std::ostream &OS, const Module* = 0) const;
00227 
00228   /// dominates - Return true if A dominates B.  This performs the special
00229   /// checks necessary if A and B are in the same basic block.
00230   ///
00231   bool dominates(Instruction *A, Instruction *B) const;
00232 
00233   //===--------------------------------------------------------------------===//
00234   // API to update (Post)DominatorSet information based on modifications to
00235   // the CFG...
00236 
00237   /// addBasicBlock - Call to update the dominator set with information about a
00238   /// new block that was inserted into the function.
00239   ///
00240   void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
00241     assert(find(BB) == end() && "Block already in DominatorSet!");
00242     Doms.insert(std::make_pair(BB, Dominators));
00243   }
00244 
00245   /// addDominator - If a new block is inserted into the CFG, then method may be
00246   /// called to notify the blocks it dominates that it is in their set.
00247   ///
00248   void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
00249     iterator I = find(BB);
00250     assert(I != end() && "BB is not in DominatorSet!");
00251     I->second.insert(NewDominator);
00252   }
00253 };
00254 
00255 
00256 //===-------------------------------------
00257 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
00258 /// compute a normal dominator set.
00259 ///
00260 class DominatorSet : public DominatorSetBase {
00261 public:
00262   DominatorSet() : DominatorSetBase(false) {}
00263 
00264   virtual bool runOnFunction(Function &F);
00265 
00266   BasicBlock *getRoot() const {
00267     assert(Roots.size() == 1 && "Should always have entry node!");
00268     return Roots[0];
00269   }
00270 
00271   /// getAnalysisUsage - This simply provides a dominator set
00272   ///
00273   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00274     AU.addRequired<ImmediateDominators>();
00275     AU.setPreservesAll();
00276   }
00277 
00278   // stub - dummy function, just ignore it
00279   static int stub;
00280 };
00281 
00282 
00283 //===----------------------------------------------------------------------===//
00284 /// DominatorTree - Calculate the immediate dominator tree for a function.
00285 ///
00286 class DominatorTreeBase : public DominatorBase {
00287 public:
00288   class Node;
00289 protected:
00290   std::map<BasicBlock*, Node*> Nodes;
00291   void reset();
00292   typedef std::map<BasicBlock*, Node*> NodeMapType;
00293 
00294   Node *RootNode;
00295 public:
00296   class Node {
00297     friend struct DominatorTree;
00298     friend struct PostDominatorTree;
00299     friend struct DominatorTreeBase;
00300     BasicBlock *TheBB;
00301     Node *IDom;
00302     std::vector<Node*> Children;
00303   public:
00304     typedef std::vector<Node*>::iterator iterator;
00305     typedef std::vector<Node*>::const_iterator const_iterator;
00306 
00307     iterator begin()             { return Children.begin(); }
00308     iterator end()               { return Children.end(); }
00309     const_iterator begin() const { return Children.begin(); }
00310     const_iterator end()   const { return Children.end(); }
00311 
00312     inline BasicBlock *getBlock() const { return TheBB; }
00313     inline Node *getIDom() const { return IDom; }
00314     inline const std::vector<Node*> &getChildren() const { return Children; }
00315 
00316     /// properlyDominates - Returns true iff this dominates N and this != N.
00317     /// Note that this is not a constant time operation!
00318     ///
00319     bool properlyDominates(const Node *N) const {
00320       const Node *IDom;
00321       if (this == 0 || N == 0) return false;
00322       while ((IDom = N->getIDom()) != 0 && IDom != this)
00323         N = IDom;   // Walk up the tree
00324       return IDom != 0;
00325     }
00326 
00327     /// dominates - Returns true iff this dominates N.  Note that this is not a
00328     /// constant time operation!
00329     ///
00330     inline bool dominates(const Node *N) const {
00331       if (N == this) return true;  // A node trivially dominates itself.
00332       return properlyDominates(N);
00333     }
00334     
00335   private:
00336     inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
00337     inline Node *addChild(Node *C) { Children.push_back(C); return C; }
00338 
00339     void setIDom(Node *NewIDom);
00340   };
00341 
00342 public:
00343   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
00344   ~DominatorTreeBase() { reset(); }
00345 
00346   virtual void releaseMemory() { reset(); }
00347 
00348   /// getNode - return the (Post)DominatorTree node for the specified basic
00349   /// block.  This is the same as using operator[] on this class.
00350   ///
00351   inline Node *getNode(BasicBlock *BB) const {
00352     NodeMapType::const_iterator i = Nodes.find(BB);
00353     return (i != Nodes.end()) ? i->second : 0;
00354   }
00355 
00356   inline Node *operator[](BasicBlock *BB) const {
00357     return getNode(BB);
00358   }
00359 
00360   /// getRootNode - This returns the entry node for the CFG of the function.  If
00361   /// this tree represents the post-dominance relations for a function, however,
00362   /// this root may be a node with the block == NULL.  This is the case when
00363   /// there are multiple exit nodes from a particular function.  Consumers of
00364   /// post-dominance information must be capable of dealing with this
00365   /// possibility.
00366   ///
00367   Node *getRootNode() { return RootNode; }
00368   const Node *getRootNode() const { return RootNode; }
00369 
00370   //===--------------------------------------------------------------------===//
00371   // API to update (Post)DominatorTree information based on modifications to
00372   // the CFG...
00373 
00374   /// createNewNode - Add a new node to the dominator tree information.  This
00375   /// creates a new node as a child of IDomNode, linking it into the children
00376   /// list of the immediate dominator.
00377   ///
00378   Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
00379     assert(getNode(BB) == 0 && "Block already in dominator tree!");
00380     assert(IDomNode && "Not immediate dominator specified for block!");
00381     return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
00382   }
00383 
00384   /// changeImmediateDominator - This method is used to update the dominator
00385   /// tree information when a node's immediate dominator changes.
00386   ///
00387   void changeImmediateDominator(Node *N, Node *NewIDom) {
00388     assert(N && NewIDom && "Cannot change null node pointers!");
00389     N->setIDom(NewIDom);
00390   }
00391 
00392   /// print - Convert to human readable form
00393   ///
00394   virtual void print(std::ostream &OS, const Module* = 0) const;
00395 };
00396 
00397 
00398 //===-------------------------------------
00399 /// ET-Forest Class - Class used to construct forwards and backwards 
00400 /// ET-Forests
00401 ///
00402 class ETForestBase : public DominatorBase {
00403 public:
00404   ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(), 
00405                                  DFSInfoValid(false), SlowQueries(0) {}
00406   
00407   virtual void releaseMemory() { reset(); }
00408 
00409   typedef std::map<BasicBlock*, ETNode*> ETMapType;
00410 
00411   void updateDFSNumbers();
00412     
00413   /// dominates - Return true if A dominates B.
00414   ///
00415   inline bool dominates(BasicBlock *A, BasicBlock *B) {
00416     if (A == B)
00417       return true;
00418     
00419     ETNode *NodeA = getNode(A);
00420     ETNode *NodeB = getNode(B);
00421     
00422     if (DFSInfoValid)
00423       return NodeB->DominatedBy(NodeA);
00424     else {
00425       // If we end up with too many slow queries, just update the
00426       // DFS numbers on the theory that we are going to keep querying.
00427       SlowQueries++;
00428       if (SlowQueries > 32) {
00429         updateDFSNumbers();
00430         return NodeB->DominatedBy(NodeA);
00431       }
00432       return NodeB->DominatedBySlow(NodeA);
00433     }
00434   }
00435 
00436   /// properlyDominates - Return true if A dominates B and A != B.
00437   ///
00438   bool properlyDominates(BasicBlock *A, BasicBlock *B) {
00439     return dominates(A, B) && A != B;
00440   }
00441 
00442   /// Return the nearest common dominator of A and B.
00443   BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
00444     ETNode *NodeA = getNode(A);
00445     ETNode *NodeB = getNode(B);
00446     
00447     ETNode *Common = NodeA->NCA(NodeB);
00448     if (!Common)
00449       return NULL;
00450     return Common->getData<BasicBlock>();
00451   }
00452 
00453   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00454     AU.setPreservesAll();
00455     AU.addRequired<ImmediateDominators>();
00456   }
00457   //===--------------------------------------------------------------------===//
00458   // API to update Forest information based on modifications
00459   // to the CFG...
00460 
00461   /// addNewBlock - Add a new block to the CFG, with the specified immediate
00462   /// dominator.
00463   ///
00464   void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
00465 
00466   /// setImmediateDominator - Update the immediate dominator information to
00467   /// change the current immediate dominator for the specified block
00468   /// to another block.  This method requires that BB for NewIDom
00469   /// already have an ETNode, otherwise just use addNewBlock.
00470   ///
00471   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
00472   /// print - Convert to human readable form
00473   ///
00474   virtual void print(std::ostream &OS, const Module* = 0) const;
00475 protected:
00476   /// getNode - return the (Post)DominatorTree node for the specified basic
00477   /// block.  This is the same as using operator[] on this class.
00478   ///
00479   inline ETNode *getNode(BasicBlock *BB) const {
00480     ETMapType::const_iterator i = Nodes.find(BB);
00481     return (i != Nodes.end()) ? i->second : 0;
00482   }
00483 
00484   inline ETNode *operator[](BasicBlock *BB) const {
00485     return getNode(BB);
00486   }
00487 
00488   void reset();
00489   ETMapType Nodes;
00490   bool DFSInfoValid;
00491   unsigned int SlowQueries;
00492 
00493 };
00494 
00495 //==-------------------------------------
00496 /// ETForest Class - Concrete subclass of ETForestBase that is used to
00497 /// compute a forwards ET-Forest.
00498 
00499 class ETForest : public ETForestBase {
00500 public:
00501   ETForest() : ETForestBase(false) {}
00502 
00503   BasicBlock *getRoot() const {
00504     assert(Roots.size() == 1 && "Should always have entry node!");
00505     return Roots[0];
00506   }
00507 
00508   virtual bool runOnFunction(Function &F) {
00509     reset();     // Reset from the last time we were run...
00510     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
00511     Roots = ID.getRoots();
00512     calculate(ID);
00513     return false;
00514   }
00515 
00516   void calculate(const ImmediateDominators &ID);
00517   ETNode *getNodeForBlock(BasicBlock *BB);
00518 };
00519 
00520 //===-------------------------------------
00521 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
00522 /// compute a normal dominator tree.
00523 ///
00524 class DominatorTree : public DominatorTreeBase {
00525 public:
00526   DominatorTree() : DominatorTreeBase(false) {}
00527 
00528   BasicBlock *getRoot() const {
00529     assert(Roots.size() == 1 && "Should always have entry node!");
00530     return Roots[0];
00531   }
00532 
00533   virtual bool runOnFunction(Function &F) {
00534     reset();     // Reset from the last time we were run...
00535     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
00536     Roots = ID.getRoots();
00537     calculate(ID);
00538     return false;
00539   }
00540 
00541   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00542     AU.setPreservesAll();
00543     AU.addRequired<ImmediateDominators>();
00544   }
00545 private:
00546   void calculate(const ImmediateDominators &ID);
00547   Node *getNodeForBlock(BasicBlock *BB);
00548 };
00549 
00550 //===-------------------------------------
00551 /// DominatorTree GraphTraits specialization so the DominatorTree can be
00552 /// iterable by generic graph iterators.
00553 ///
00554 template <> struct GraphTraits<DominatorTree::Node*> {
00555   typedef DominatorTree::Node NodeType;
00556   typedef NodeType::iterator  ChildIteratorType;
00557 
00558   static NodeType *getEntryNode(NodeType *N) {
00559     return N;
00560   }
00561   static inline ChildIteratorType child_begin(NodeType* N) {
00562     return N->begin();
00563   }
00564   static inline ChildIteratorType child_end(NodeType* N) {
00565     return N->end();
00566   }
00567 };
00568 
00569 template <> struct GraphTraits<DominatorTree*>
00570   : public GraphTraits<DominatorTree::Node*> {
00571   static NodeType *getEntryNode(DominatorTree *DT) {
00572     return DT->getRootNode();
00573   }
00574 };
00575 
00576 //===----------------------------------------------------------------------===//
00577 /// DominanceFrontierBase - Common base class for computing forward and inverse
00578 /// dominance frontiers for a function.
00579 ///
00580 class DominanceFrontierBase : public DominatorBase {
00581 public:
00582   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
00583   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
00584 protected:
00585   DomSetMapType Frontiers;
00586 public:
00587   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
00588 
00589   virtual void releaseMemory() { Frontiers.clear(); }
00590 
00591   // Accessor interface:
00592   typedef DomSetMapType::iterator iterator;
00593   typedef DomSetMapType::const_iterator const_iterator;
00594   iterator       begin()       { return Frontiers.begin(); }
00595   const_iterator begin() const { return Frontiers.begin(); }
00596   iterator       end()         { return Frontiers.end(); }
00597   const_iterator end()   const { return Frontiers.end(); }
00598   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
00599   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
00600 
00601   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
00602     assert(find(BB) == end() && "Block already in DominanceFrontier!");
00603     Frontiers.insert(std::make_pair(BB, frontier));
00604   }
00605 
00606   void addToFrontier(iterator I, BasicBlock *Node) {
00607     assert(I != end() && "BB is not in DominanceFrontier!");
00608     I->second.insert(Node);
00609   }
00610 
00611   void removeFromFrontier(iterator I, BasicBlock *Node) {
00612     assert(I != end() && "BB is not in DominanceFrontier!");
00613     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
00614     I->second.erase(Node);
00615   }
00616 
00617   /// print - Convert to human readable form
00618   ///
00619   virtual void print(std::ostream &OS, const Module* = 0) const;
00620 };
00621 
00622 
00623 //===-------------------------------------
00624 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
00625 /// used to compute a forward dominator frontiers.
00626 ///
00627 class DominanceFrontier : public DominanceFrontierBase {
00628 public:
00629   DominanceFrontier() : DominanceFrontierBase(false) {}
00630 
00631   BasicBlock *getRoot() const {
00632     assert(Roots.size() == 1 && "Should always have entry node!");
00633     return Roots[0];
00634   }
00635 
00636   virtual bool runOnFunction(Function &) {
00637     Frontiers.clear();
00638     DominatorTree &DT = getAnalysis<DominatorTree>();
00639     Roots = DT.getRoots();
00640     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
00641     calculate(DT, DT[Roots[0]]);
00642     return false;
00643   }
00644 
00645   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00646     AU.setPreservesAll();
00647     AU.addRequired<DominatorTree>();
00648   }
00649 private:
00650   const DomSetType &calculate(const DominatorTree &DT,
00651                               const DominatorTree::Node *Node);
00652 };
00653 
00654 
00655 } // End llvm namespace
00656 
00657 // Make sure that any clients of this file link in Dominators.cpp
00658 FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet)
00659 
00660 #endif