Dominators.h revision e33b7968514580c8b7f0c6529ddeeb7537ecfb9b
1//===- llvm/Analysis/Dominators.h - Dominator Info Calculation ---*- C++ -*--=// 2// 3// This file defines the following classes: 4// 1. DominatorSet: Calculates the [reverse] dominator set for a function 5// 2. ImmediateDominators: Calculates and holds a mapping between BasicBlocks 6// and their immediate dominator. 7// 3. DominatorTree: Represent the ImmediateDominator as an explicit tree 8// structure. 9// 4. DominanceFrontier: Calculate and hold the dominance frontier for a 10// function. 11// 12// These data structures are listed in increasing order of complexity. It 13// takes longer to calculate the dominator frontier, for example, than the 14// ImmediateDominator mapping. 15// 16//===----------------------------------------------------------------------===// 17 18#ifndef LLVM_ANALYSIS_DOMINATORS_H 19#define LLVM_ANALYSIS_DOMINATORS_H 20 21#include "llvm/Pass.h" 22#include <set> 23class Instruction; 24 25template <typename GraphType> struct GraphTraits; 26 27//===----------------------------------------------------------------------===// 28// 29// DominatorBase - Base class that other, more interesting dominator analyses 30// inherit from. 31// 32class DominatorBase : public FunctionPass { 33protected: 34 BasicBlock *Root; 35 const bool IsPostDominators; 36 37 inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {} 38public: 39 inline BasicBlock *getRoot() const { return Root; } 40 41 // Returns true if analysis based of postdoms 42 bool isPostDominator() const { return IsPostDominators; } 43}; 44 45//===----------------------------------------------------------------------===// 46// 47// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a 48// function, that represents the blocks that dominate the block. 49// 50class DominatorSetBase : public DominatorBase { 51public: 52 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 53 // Map of dom sets 54 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; 55protected: 56 DomSetMapType Doms; 57public: 58 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} 59 60 virtual void releaseMemory() { Doms.clear(); } 61 62 // Accessor interface: 63 typedef DomSetMapType::const_iterator const_iterator; 64 typedef DomSetMapType::iterator iterator; 65 inline const_iterator begin() const { return Doms.begin(); } 66 inline iterator begin() { return Doms.begin(); } 67 inline const_iterator end() const { return Doms.end(); } 68 inline iterator end() { return Doms.end(); } 69 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); } 70 inline iterator find(BasicBlock* B) { return Doms.find(B); } 71 72 73 /// getDominators - Return the set of basic blocks that dominate the specified 74 /// block. 75 /// 76 inline const DomSetType &getDominators(BasicBlock *BB) const { 77 const_iterator I = find(BB); 78 assert(I != end() && "BB not in function!"); 79 return I->second; 80 } 81 82 /// dominates - Return true if A dominates B. 83 /// 84 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 85 return getDominators(B).count(A) != 0; 86 } 87 88 /// properlyDominates - Return true if A dominates B and A != B. 89 /// 90 bool properlyDominates(BasicBlock *A, BasicBlock *B) const { 91 return dominates(A, B) && A != B; 92 } 93 94 /// print - Convert to human readable form 95 virtual void print(std::ostream &OS) const; 96 97 /// dominates - Return true if A dominates B. This performs the special 98 /// checks neccesary if A and B are in the same basic block. 99 /// 100 bool dominates(Instruction *A, Instruction *B) const; 101 102 //===--------------------------------------------------------------------===// 103 // API to update (Post)DominatorSet information based on modifications to 104 // the CFG... 105 106 /// addBasicBlock - Call to update the dominator set with information about a 107 /// new block that was inserted into the function. 108 void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) { 109 assert(find(BB) == end() && "Block already in DominatorSet!"); 110 Doms.insert(std::make_pair(BB, Dominators)); 111 } 112 113 // addDominator - If a new block is inserted into the CFG, then method may be 114 // called to notify the blocks it dominates that it is in their set. 115 // 116 void addDominator(BasicBlock *BB, BasicBlock *NewDominator) { 117 iterator I = find(BB); 118 assert(I != end() && "BB is not in DominatorSet!"); 119 I->second.insert(NewDominator); 120 } 121}; 122 123 124//===------------------------------------- 125// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 126// compute a normal dominator set. 127// 128struct DominatorSet : public DominatorSetBase { 129 DominatorSet() : DominatorSetBase(false) {} 130 131 virtual bool runOnFunction(Function &F); 132 133 /// recalculate - This method may be called by external passes that modify the 134 /// CFG and then need dominator information recalculated. This method is 135 /// obviously really slow, so it should be avoided if at all possible. 136 void recalculate(); 137 138 // getAnalysisUsage - This simply provides a dominator set 139 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 140 AU.setPreservesAll(); 141 } 142private: 143 void calculateDominatorsFromBlock(BasicBlock *BB); 144}; 145 146 147//===----------------------------------------------------------------------===// 148// 149// ImmediateDominators - Calculate the immediate dominator for each node in a 150// function. 151// 152class ImmediateDominatorsBase : public DominatorBase { 153protected: 154 std::map<BasicBlock*, BasicBlock*> IDoms; 155 void calcIDoms(const DominatorSetBase &DS); 156public: 157 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} 158 159 virtual void releaseMemory() { IDoms.clear(); } 160 161 // Accessor interface: 162 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType; 163 typedef IDomMapType::const_iterator const_iterator; 164 inline const_iterator begin() const { return IDoms.begin(); } 165 inline const_iterator end() const { return IDoms.end(); } 166 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);} 167 168 // operator[] - Return the idom for the specified basic block. The start 169 // node returns null, because it does not have an immediate dominator. 170 // 171 inline BasicBlock *operator[](BasicBlock *BB) const { 172 return get(BB); 173 } 174 175 // get() - Synonym for operator[]. 176 inline BasicBlock *get(BasicBlock *BB) const { 177 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); 178 return I != IDoms.end() ? I->second : 0; 179 } 180 181 //===--------------------------------------------------------------------===// 182 // API to update Immediate(Post)Dominators information based on modifications 183 // to the CFG... 184 185 /// addNewBlock - Add a new block to the CFG, with the specified immediate 186 /// dominator. 187 /// 188 void addNewBlock(BasicBlock *BB, BasicBlock *IDom) { 189 assert(get(BB) == 0 && "BasicBlock already in idom info!"); 190 IDoms[BB] = IDom; 191 } 192 193 /// setImmediateDominator - Update the immediate dominator information to 194 /// change the current immediate dominator for the specified block to another 195 /// block. This method requires that BB already have an IDom, otherwise just 196 /// use addNewBlock. 197 void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) { 198 assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!"); 199 IDoms[BB] = NewIDom; 200 } 201 202 // print - Convert to human readable form 203 virtual void print(std::ostream &OS) const; 204}; 205 206//===------------------------------------- 207// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that 208// is used to compute a normal immediate dominator set. 209// 210struct ImmediateDominators : public ImmediateDominatorsBase { 211 ImmediateDominators() : ImmediateDominatorsBase(false) {} 212 213 virtual bool runOnFunction(Function &F) { 214 IDoms.clear(); // Reset from the last time we were run... 215 DominatorSet &DS = getAnalysis<DominatorSet>(); 216 Root = DS.getRoot(); 217 calcIDoms(DS); 218 return false; 219 } 220 221 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 222 AU.setPreservesAll(); 223 AU.addRequired<DominatorSet>(); 224 } 225}; 226 227 228//===----------------------------------------------------------------------===// 229// 230// DominatorTree - Calculate the immediate dominator tree for a function. 231// 232class DominatorTreeBase : public DominatorBase { 233protected: 234 class Node2; 235public: 236 typedef Node2 Node; 237protected: 238 std::map<BasicBlock*, Node*> Nodes; 239 void reset(); 240 typedef std::map<BasicBlock*, Node*> NodeMapType; 241public: 242 class Node2 { 243 friend class DominatorTree; 244 friend class PostDominatorTree; 245 friend class DominatorTreeBase; 246 BasicBlock *TheNode; 247 Node2 *IDom; 248 std::vector<Node*> Children; 249 public: 250 typedef std::vector<Node*>::iterator iterator; 251 typedef std::vector<Node*>::const_iterator const_iterator; 252 253 iterator begin() { return Children.begin(); } 254 iterator end() { return Children.end(); } 255 const_iterator begin() const { return Children.begin(); } 256 const_iterator end() const { return Children.end(); } 257 258 inline BasicBlock *getNode() const { return TheNode; } 259 inline Node2 *getIDom() const { return IDom; } 260 inline const std::vector<Node*> &getChildren() const { return Children; } 261 262 // dominates - Returns true iff this dominates N. Note that this is not a 263 // constant time operation! 264 inline bool dominates(const Node2 *N) const { 265 const Node2 *IDom; 266 while ((IDom = N->getIDom()) != 0 && IDom != this) 267 N = IDom; // Walk up the tree 268 return IDom != 0; 269 } 270 271 private: 272 inline Node2(BasicBlock *node, Node *iDom) 273 : TheNode(node), IDom(iDom) {} 274 inline Node2 *addChild(Node *C) { Children.push_back(C); return C; } 275 276 void setIDom(Node2 *NewIDom); 277 }; 278 279public: 280 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} 281 ~DominatorTreeBase() { reset(); } 282 283 virtual void releaseMemory() { reset(); } 284 285 /// getNode - return the (Post)DominatorTree node for the specified basic 286 /// block. This is the same as using operator[] on this class. 287 /// 288 inline Node *getNode(BasicBlock *BB) const { 289 NodeMapType::const_iterator i = Nodes.find(BB); 290 return (i != Nodes.end()) ? i->second : 0; 291 } 292 293 inline Node *operator[](BasicBlock *BB) const { 294 return getNode(BB); 295 } 296 297 //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to 298 // the CFG... 299 300 /// createNewNode - Add a new node to the dominator tree information. This 301 /// creates a new node as a child of IDomNode, linking it into the children 302 /// list of the immediate dominator. 303 /// 304 Node *createNewNode(BasicBlock *BB, Node *IDomNode) { 305 assert(getNode(BB) == 0 && "Block already in dominator tree!"); 306 assert(IDomNode && "Not immediate dominator specified for block!"); 307 return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 308 } 309 310 /// changeImmediateDominator - This method is used to update the dominator 311 /// tree information when a node's immediate dominator changes. 312 /// 313 void changeImmediateDominator(Node *Node, Node *NewIDom) { 314 assert(Node && NewIDom && "Cannot change null node pointers!"); 315 Node->setIDom(NewIDom); 316 } 317 318 /// print - Convert to human readable form 319 virtual void print(std::ostream &OS) const; 320}; 321 322 323//===------------------------------------- 324// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 325// compute a normal dominator tree. 326// 327struct DominatorTree : public DominatorTreeBase { 328 DominatorTree() : DominatorTreeBase(false) {} 329 330 virtual bool runOnFunction(Function &F) { 331 reset(); // Reset from the last time we were run... 332 DominatorSet &DS = getAnalysis<DominatorSet>(); 333 Root = DS.getRoot(); 334 calculate(DS); 335 return false; 336 } 337 338 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 339 AU.setPreservesAll(); 340 AU.addRequired<DominatorSet>(); 341 } 342private: 343 void calculate(const DominatorSet &DS); 344}; 345 346//===------------------------------------- 347// DominatorTree GraphTraits specialization so the DominatorTree can be 348// iterable by generic graph iterators. 349 350template <> struct GraphTraits<DominatorTree::Node*> { 351 typedef DominatorTree::Node NodeType; 352 typedef NodeType::iterator ChildIteratorType; 353 354 static NodeType *getEntryNode(NodeType *N) { 355 return N; 356 } 357 static inline ChildIteratorType child_begin(NodeType* N) { 358 return N->begin(); 359 } 360 static inline ChildIteratorType child_end(NodeType* N) { 361 return N->end(); 362 } 363}; 364 365template <> struct GraphTraits<DominatorTree*> 366 : public GraphTraits<DominatorTree::Node*> { 367 static NodeType *getEntryNode(DominatorTree *DT) { 368 return DT->getNode(DT->getRoot()); 369 } 370}; 371 372//===----------------------------------------------------------------------===// 373// 374// DominanceFrontier - Calculate the dominance frontiers for a function. 375// 376class DominanceFrontierBase : public DominatorBase { 377public: 378 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 379 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 380protected: 381 DomSetMapType Frontiers; 382public: 383 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} 384 385 virtual void releaseMemory() { Frontiers.clear(); } 386 387 // Accessor interface: 388 typedef DomSetMapType::iterator iterator; 389 typedef DomSetMapType::const_iterator const_iterator; 390 iterator begin() { return Frontiers.begin(); } 391 const_iterator begin() const { return Frontiers.begin(); } 392 iterator end() { return Frontiers.end(); } 393 const_iterator end() const { return Frontiers.end(); } 394 iterator find(BasicBlock *B) { return Frontiers.find(B); } 395 const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } 396 397 void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 398 assert(find(BB) == end() && "Block already in DominanceFrontier!"); 399 Frontiers.insert(std::make_pair(BB, frontier)); 400 } 401 402 void addToFrontier(iterator I, BasicBlock *Node) { 403 assert(I != end() && "BB is not in DominanceFrontier!"); 404 I->second.insert(Node); 405 } 406 407 void removeFromFrontier(iterator I, BasicBlock *Node) { 408 assert(I != end() && "BB is not in DominanceFrontier!"); 409 assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); 410 I->second.erase(Node); 411 } 412 413 // print - Convert to human readable form 414 virtual void print(std::ostream &OS) const; 415}; 416 417 418//===------------------------------------- 419// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 420// compute a normal dominator tree. 421// 422struct DominanceFrontier : public DominanceFrontierBase { 423 DominanceFrontier() : DominanceFrontierBase(false) {} 424 425 virtual bool runOnFunction(Function &) { 426 Frontiers.clear(); 427 DominatorTree &DT = getAnalysis<DominatorTree>(); 428 Root = DT.getRoot(); 429 calculate(DT, DT[Root]); 430 return false; 431 } 432 433 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 434 AU.setPreservesAll(); 435 AU.addRequired<DominatorTree>(); 436 } 437private: 438 const DomSetType &calculate(const DominatorTree &DT, 439 const DominatorTree::Node *Node); 440}; 441 442#endif 443