LLVM API Documentation
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