LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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. DominanceFrontier: Calculate and hold the dominance frontier for a 
00017 //     function.
00018 //
00019 //  These data structures are listed in increasing order of complexity.  It
00020 //  takes longer to calculate the dominator frontier, for example, than the 
00021 //  ImmediateDominator mapping.
00022 // 
00023 //===----------------------------------------------------------------------===//
00024 
00025 #ifndef LLVM_ANALYSIS_DOMINATORS_H
00026 #define LLVM_ANALYSIS_DOMINATORS_H
00027 
00028 #include "llvm/Pass.h"
00029 #include <set>
00030 
00031 namespace llvm {
00032 
00033 class Instruction;
00034 
00035 template <typename GraphType> struct GraphTraits;
00036 
00037 //===----------------------------------------------------------------------===//
00038 /// DominatorBase - Base class that other, more interesting dominator analyses
00039 /// inherit from.
00040 ///
00041 class DominatorBase : public FunctionPass {
00042 protected:
00043   std::vector<BasicBlock*> Roots;
00044   const bool IsPostDominators;
00045 
00046   inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
00047 public:
00048   /// getRoots -  Return the root blocks of the current CFG.  This may include
00049   /// multiple blocks if we are computing post dominators.  For forward
00050   /// dominators, this will always be a single block (the entry node).
00051   ///
00052   inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
00053 
00054   /// isPostDominator - Returns true if analysis based of postdoms
00055   ///
00056   bool isPostDominator() const { return IsPostDominators; }
00057 };
00058 
00059 
00060 //===----------------------------------------------------------------------===//
00061 /// ImmediateDominators - Calculate the immediate dominator for each node in a
00062 /// function.
00063 ///
00064 class ImmediateDominatorsBase : public DominatorBase {
00065 protected:
00066   std::map<BasicBlock*, BasicBlock*> IDoms;
00067 public:
00068   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
00069 
00070   virtual void releaseMemory() { IDoms.clear(); }
00071 
00072   // Accessor interface:
00073   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
00074   typedef IDomMapType::const_iterator const_iterator;
00075   inline const_iterator begin() const { return IDoms.begin(); }
00076   inline const_iterator end()   const { return IDoms.end(); }
00077   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
00078 
00079   /// operator[] - Return the idom for the specified basic block.  The start
00080   /// node returns null, because it does not have an immediate dominator.
00081   ///
00082   inline BasicBlock *operator[](BasicBlock *BB) const {
00083     return get(BB);
00084   }
00085 
00086   /// get() - Synonym for operator[].
00087   ///
00088   inline BasicBlock *get(BasicBlock *BB) const {
00089     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
00090     return I != IDoms.end() ? I->second : 0;
00091   }
00092 
00093   //===--------------------------------------------------------------------===//
00094   // API to update Immediate(Post)Dominators information based on modifications
00095   // to the CFG...
00096 
00097   /// addNewBlock - Add a new block to the CFG, with the specified immediate
00098   /// dominator.
00099   ///
00100   void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
00101     assert(get(BB) == 0 && "BasicBlock already in idom info!");
00102     IDoms[BB] = IDom;
00103   }
00104 
00105   /// setImmediateDominator - Update the immediate dominator information to
00106   /// change the current immediate dominator for the specified block to another
00107   /// block.  This method requires that BB already have an IDom, otherwise just
00108   /// use addNewBlock.
00109   ///
00110   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
00111     assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
00112     IDoms[BB] = NewIDom;
00113   }
00114 
00115   /// print - Convert to human readable form
00116   ///
00117   virtual void print(std::ostream &OS) const;
00118 };
00119 
00120 //===-------------------------------------
00121 /// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
00122 /// that is used to compute a normal immediate dominator set.
00123 ///
00124 struct ImmediateDominators : public ImmediateDominatorsBase {
00125   ImmediateDominators() : ImmediateDominatorsBase(false) {}
00126 
00127   BasicBlock *getRoot() const {
00128     assert(Roots.size() == 1 && "Should always have entry node!");
00129     return Roots[0];
00130   }
00131 
00132   virtual bool runOnFunction(Function &F);
00133 
00134   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00135     AU.setPreservesAll();
00136   }
00137 
00138 private:
00139   struct InfoRec {
00140     unsigned Semi;
00141     unsigned Size;
00142     BasicBlock *Label, *Parent, *Child, *Ancestor;
00143     
00144     std::vector<BasicBlock*> Bucket;
00145     
00146     InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
00147   };
00148 
00149   // Vertex - Map the DFS number to the BasicBlock*
00150   std::vector<BasicBlock*> Vertex;
00151 
00152   // Info - Collection of information used during the computation of idoms.
00153   std::map<BasicBlock*, InfoRec> Info;
00154 
00155   unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
00156   void Compress(BasicBlock *V, InfoRec &VInfo);
00157   BasicBlock *Eval(BasicBlock *v);
00158   void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
00159 };
00160 
00161 
00162 
00163 //===----------------------------------------------------------------------===//
00164 /// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
00165 /// function, that represents the blocks that dominate the block.  If the block
00166 /// is unreachable in this function, the set will be empty.  This cannot happen
00167 /// for reachable code, because every block dominates at least itself.
00168 ///
00169 struct DominatorSetBase : public DominatorBase {
00170   typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
00171   // Map of dom sets
00172   typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
00173 protected:
00174   DomSetMapType Doms;
00175 public:
00176   DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
00177 
00178   virtual void releaseMemory() { Doms.clear(); }
00179 
00180   // Accessor interface:
00181   typedef DomSetMapType::const_iterator const_iterator;
00182   typedef DomSetMapType::iterator iterator;
00183   inline const_iterator begin() const { return Doms.begin(); }
00184   inline       iterator begin()       { return Doms.begin(); }
00185   inline const_iterator end()   const { return Doms.end(); }
00186   inline       iterator end()         { return Doms.end(); }
00187   inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
00188   inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
00189 
00190 
00191   /// getDominators - Return the set of basic blocks that dominate the specified
00192   /// block.
00193   ///
00194   inline const DomSetType &getDominators(BasicBlock *BB) const {
00195     const_iterator I = find(BB);
00196     assert(I != end() && "BB not in function!");
00197     return I->second;
00198   }
00199 
00200   /// isReachable - Return true if the specified basicblock is reachable.  If
00201   /// the block is reachable, we have dominator set information for it.
00202   ///
00203   bool isReachable(BasicBlock *BB) const {
00204     return !getDominators(BB).empty();
00205   }
00206 
00207   /// dominates - Return true if A dominates B.
00208   ///
00209   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
00210     return getDominators(B).count(A) != 0;
00211   }
00212 
00213   /// properlyDominates - Return true if A dominates B and A != B.
00214   ///
00215   bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
00216     return dominates(A, B) && A != B;
00217   }
00218 
00219   /// print - Convert to human readable form
00220   ///
00221   virtual void print(std::ostream &OS) const;
00222 
00223   /// dominates - Return true if A dominates B.  This performs the special
00224   /// checks necessary if A and B are in the same basic block.
00225   ///
00226   bool dominates(Instruction *A, Instruction *B) const;
00227 
00228   //===--------------------------------------------------------------------===//
00229   // API to update (Post)DominatorSet information based on modifications to
00230   // the CFG...
00231 
00232   /// addBasicBlock - Call to update the dominator set with information about a
00233   /// new block that was inserted into the function.
00234   ///
00235   void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
00236     assert(find(BB) == end() && "Block already in DominatorSet!");
00237     Doms.insert(std::make_pair(BB, Dominators));
00238   }
00239 
00240   /// addDominator - If a new block is inserted into the CFG, then method may be
00241   /// called to notify the blocks it dominates that it is in their set.
00242   ///
00243   void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
00244     iterator I = find(BB);
00245     assert(I != end() && "BB is not in DominatorSet!");
00246     I->second.insert(NewDominator);
00247   }
00248 };
00249 
00250 
00251 //===-------------------------------------
00252 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
00253 /// compute a normal dominator set.
00254 ///
00255 struct DominatorSet : public DominatorSetBase {
00256   DominatorSet() : DominatorSetBase(false) {}
00257 
00258   virtual bool runOnFunction(Function &F);
00259 
00260   BasicBlock *getRoot() const {
00261     assert(Roots.size() == 1 && "Should always have entry node!");
00262     return Roots[0];
00263   }
00264 
00265   /// getAnalysisUsage - This simply provides a dominator set
00266   ///
00267   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00268     AU.addRequired<ImmediateDominators>();
00269     AU.setPreservesAll();
00270   }
00271 
00272   // stub - dummy function, just ignore it
00273   static void stub();
00274 };
00275 
00276 
00277 //===----------------------------------------------------------------------===//
00278 /// DominatorTree - Calculate the immediate dominator tree for a function.
00279 ///
00280 struct DominatorTreeBase : public DominatorBase {
00281   class Node;
00282 protected:
00283   std::map<BasicBlock*, Node*> Nodes;
00284   void reset();
00285   typedef std::map<BasicBlock*, Node*> NodeMapType;
00286 
00287   Node *RootNode;
00288 public:
00289   class Node {
00290     friend struct DominatorTree;
00291     friend struct PostDominatorTree;
00292     friend struct DominatorTreeBase;
00293     BasicBlock *TheBB;
00294     Node *IDom;
00295     std::vector<Node*> Children;
00296   public:
00297     typedef std::vector<Node*>::iterator iterator;
00298     typedef std::vector<Node*>::const_iterator const_iterator;
00299 
00300     iterator begin()             { return Children.begin(); }
00301     iterator end()               { return Children.end(); }
00302     const_iterator begin() const { return Children.begin(); }
00303     const_iterator end()   const { return Children.end(); }
00304 
00305     inline BasicBlock *getBlock() const { return TheBB; }
00306     inline Node *getIDom() const { return IDom; }
00307     inline const std::vector<Node*> &getChildren() const { return Children; }
00308 
00309     /// dominates - Returns true iff this dominates N.  Note that this is not a 
00310     /// constant time operation!
00311     ///
00312     inline bool dominates(const Node *N) const {
00313       const Node *IDom;
00314       while ((IDom = N->getIDom()) != 0 && IDom != this)
00315       N = IDom;   // Walk up the tree
00316       return IDom != 0;
00317     }
00318 
00319   private:
00320     inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
00321     inline Node *addChild(Node *C) { Children.push_back(C); return C; }
00322 
00323     void setIDom(Node *NewIDom);
00324   };
00325 
00326 public:
00327   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
00328   ~DominatorTreeBase() { reset(); }
00329 
00330   virtual void releaseMemory() { reset(); }
00331 
00332   /// getNode - return the (Post)DominatorTree node for the specified basic
00333   /// block.  This is the same as using operator[] on this class.
00334   ///
00335   inline Node *getNode(BasicBlock *BB) const {
00336     NodeMapType::const_iterator i = Nodes.find(BB);
00337     return (i != Nodes.end()) ? i->second : 0;
00338   }
00339 
00340   inline Node *operator[](BasicBlock *BB) const {
00341     return getNode(BB);
00342   }
00343 
00344   /// getRootNode - This returns the entry node for the CFG of the function.  If
00345   /// this tree represents the post-dominance relations for a function, however,
00346   /// this root may be a node with the block == NULL.  This is the case when
00347   /// there are multiple exit nodes from a particular function.  Consumers of
00348   /// post-dominance information must be capable of dealing with this
00349   /// possibility.
00350   ///
00351   Node *getRootNode() { return RootNode; }
00352   const Node *getRootNode() const { return RootNode; }
00353 
00354   //===--------------------------------------------------------------------===//
00355   // API to update (Post)DominatorTree information based on modifications to
00356   // the CFG...
00357 
00358   /// createNewNode - Add a new node to the dominator tree information.  This
00359   /// creates a new node as a child of IDomNode, linking it into the children
00360   /// list of the immediate dominator.
00361   ///
00362   Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
00363     assert(getNode(BB) == 0 && "Block already in dominator tree!");
00364     assert(IDomNode && "Not immediate dominator specified for block!");
00365     return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
00366   }
00367 
00368   /// changeImmediateDominator - This method is used to update the dominator
00369   /// tree information when a node's immediate dominator changes.
00370   ///
00371   void changeImmediateDominator(Node *N, Node *NewIDom) {
00372     assert(N && NewIDom && "Cannot change null node pointers!");
00373     N->setIDom(NewIDom);
00374   }
00375 
00376   /// print - Convert to human readable form
00377   ///
00378   virtual void print(std::ostream &OS) const;
00379 };
00380 
00381 
00382 //===-------------------------------------
00383 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
00384 /// compute a normal dominator tree.
00385 ///
00386 struct DominatorTree : public DominatorTreeBase {
00387   DominatorTree() : DominatorTreeBase(false) {}
00388 
00389   BasicBlock *getRoot() const {
00390     assert(Roots.size() == 1 && "Should always have entry node!");
00391     return Roots[0];
00392   }
00393 
00394   virtual bool runOnFunction(Function &F) {
00395     reset();     // Reset from the last time we were run...
00396     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
00397     Roots = ID.getRoots();
00398     calculate(ID);
00399     return false;
00400   }
00401 
00402   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00403     AU.setPreservesAll();
00404     AU.addRequired<ImmediateDominators>();
00405   }
00406 private:
00407   void calculate(const ImmediateDominators &ID);
00408   Node *getNodeForBlock(BasicBlock *BB);
00409 };
00410 
00411 //===-------------------------------------
00412 /// DominatorTree GraphTraits specialization so the DominatorTree can be
00413 /// iterable by generic graph iterators.
00414 ///
00415 template <> struct GraphTraits<DominatorTree::Node*> {
00416   typedef DominatorTree::Node NodeType;
00417   typedef NodeType::iterator  ChildIteratorType;
00418 
00419   static NodeType *getEntryNode(NodeType *N) {
00420     return N;
00421   }
00422   static inline ChildIteratorType child_begin(NodeType* N) {
00423     return N->begin();
00424   }
00425   static inline ChildIteratorType child_end(NodeType* N) {
00426     return N->end();
00427   }
00428 };
00429 
00430 template <> struct GraphTraits<DominatorTree*>
00431   : public GraphTraits<DominatorTree::Node*> {
00432   static NodeType *getEntryNode(DominatorTree *DT) {
00433     return DT->getRootNode();
00434   }
00435 };
00436 
00437 //===----------------------------------------------------------------------===//
00438 /// DominanceFrontier - Calculate the dominance frontiers for a function.
00439 ///
00440 struct DominanceFrontierBase : public DominatorBase {
00441   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
00442   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
00443 protected:
00444   DomSetMapType Frontiers;
00445 public:
00446   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
00447 
00448   virtual void releaseMemory() { Frontiers.clear(); }
00449 
00450   // Accessor interface:
00451   typedef DomSetMapType::iterator iterator;
00452   typedef DomSetMapType::const_iterator const_iterator;
00453   iterator       begin()       { return Frontiers.begin(); }
00454   const_iterator begin() const { return Frontiers.begin(); }
00455   iterator       end()         { return Frontiers.end(); }
00456   const_iterator end()   const { return Frontiers.end(); }
00457   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
00458   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
00459 
00460   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
00461     assert(find(BB) == end() && "Block already in DominanceFrontier!");
00462     Frontiers.insert(std::make_pair(BB, frontier));
00463   }
00464 
00465   void addToFrontier(iterator I, BasicBlock *Node) {
00466     assert(I != end() && "BB is not in DominanceFrontier!");
00467     I->second.insert(Node);
00468   }
00469 
00470   void removeFromFrontier(iterator I, BasicBlock *Node) {
00471     assert(I != end() && "BB is not in DominanceFrontier!");
00472     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
00473     I->second.erase(Node);
00474   }
00475 
00476   /// print - Convert to human readable form
00477   ///
00478   virtual void print(std::ostream &OS) const;
00479 };
00480 
00481 
00482 //===-------------------------------------
00483 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
00484 /// compute a normal dominator tree.
00485 ///
00486 struct DominanceFrontier : public DominanceFrontierBase {
00487   DominanceFrontier() : DominanceFrontierBase(false) {}
00488 
00489   BasicBlock *getRoot() const {
00490     assert(Roots.size() == 1 && "Should always have entry node!");
00491     return Roots[0];
00492   }
00493 
00494   virtual bool runOnFunction(Function &) {
00495     Frontiers.clear();
00496     DominatorTree &DT = getAnalysis<DominatorTree>();
00497     Roots = DT.getRoots();
00498     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
00499     calculate(DT, DT[Roots[0]]);
00500     return false;
00501   }
00502 
00503   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00504     AU.setPreservesAll();
00505     AU.addRequired<DominatorTree>();
00506   }
00507 private:
00508   const DomSetType &calculate(const DominatorTree &DT,
00509                               const DominatorTree::Node *Node);
00510 };
00511 
00512 // Make sure that any clients of this file link in Dominators.cpp
00513 static IncludeFile
00514 DOMINATORS_INCLUDE_FILE((void*)&DominatorSet::stub);
00515 } // End llvm namespace
00516 
00517 #endif