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 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