Dominators.h revision 0cbc6c2fd8470c62d824667fc600d80a494d26cd
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_DOMINATORS_H 19#define LLVM_DOMINATORS_H 20 21#include "llvm/Pass.h" 22#include <set> 23class Instruction; 24 25//===----------------------------------------------------------------------===// 26// 27// DominatorBase - Base class that other, more interesting dominator analyses 28// inherit from. 29// 30class DominatorBase : public FunctionPass { 31protected: 32 BasicBlock *Root; 33 const bool IsPostDominators; 34 35 inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {} 36public: 37 inline BasicBlock *getRoot() const { return Root; } 38 39 // Returns true if analysis based of postdoms 40 bool isPostDominator() const { return IsPostDominators; } 41}; 42 43//===----------------------------------------------------------------------===// 44// 45// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a 46// function, that represents the blocks that dominate the block. 47// 48class DominatorSetBase : public DominatorBase { 49public: 50 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 51 // Map of dom sets 52 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; 53protected: 54 DomSetMapType Doms; 55public: 56 DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {} 57 58 virtual void releaseMemory() { Doms.clear(); } 59 60 // Accessor interface: 61 typedef DomSetMapType::const_iterator const_iterator; 62 typedef DomSetMapType::iterator iterator; 63 inline const_iterator begin() const { return Doms.begin(); } 64 inline iterator begin() { return Doms.begin(); } 65 inline const_iterator end() const { return Doms.end(); } 66 inline iterator end() { return Doms.end(); } 67 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); } 68 inline iterator find(BasicBlock* B) { return Doms.find(B); } 69 70 // getDominators - Return the set of basic blocks that dominate the specified 71 // block. 72 // 73 inline const DomSetType &getDominators(BasicBlock *BB) const { 74 const_iterator I = find(BB); 75 assert(I != end() && "BB not in function!"); 76 return I->second; 77 } 78 79 // dominates - Return true if A dominates B. 80 // 81 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 82 return getDominators(B).count(A) != 0; 83 } 84 85 // dominates - Return true if A dominates B. This performs the special checks 86 // neccesary if A and B are in the same basic block. 87 // 88 bool dominates(Instruction *A, Instruction *B) const; 89}; 90 91 92//===------------------------------------- 93// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 94// compute a normal dominator set. 95// 96struct DominatorSet : public DominatorSetBase { 97 static AnalysisID ID; // Build dominator set 98 99 DominatorSet(AnalysisID id) : DominatorSetBase(false) { assert(id == ID); } 100 101 virtual const char *getPassName() const { 102 return "Dominator Set Construction"; 103 } 104 105 virtual bool runOnFunction(Function &F); 106 107 // getAnalysisUsage - This simply provides a dominator set 108 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 109 AU.setPreservesAll(); 110 AU.addProvided(ID); 111 } 112}; 113 114 115//===------------------------------------- 116// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 117// compute the post-dominator set. 118// 119struct PostDominatorSet : public DominatorSetBase { 120 static AnalysisID ID; // Build post-dominator set 121 122 PostDominatorSet(AnalysisID id) : DominatorSetBase(true) { assert(id == ID); } 123 124 virtual const char *getPassName() const { 125 return "Post-Dominator Set Construction"; 126 } 127 128 virtual bool runOnFunction(Function &F); 129 130 // getAnalysisUsage - This obviously provides a dominator set, but it also 131 // uses the UnifyFunctionExitNode pass if building post-dominators 132 // 133 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 134}; 135 136 137 138 139 140//===----------------------------------------------------------------------===// 141// 142// ImmediateDominators - Calculate the immediate dominator for each node in a 143// function. 144// 145class ImmediateDominatorsBase : public DominatorBase { 146protected: 147 std::map<BasicBlock*, BasicBlock*> IDoms; 148 void calcIDoms(const DominatorSetBase &DS); 149public: 150 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} 151 152 virtual void releaseMemory() { IDoms.clear(); } 153 154 // Accessor interface: 155 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType; 156 typedef IDomMapType::const_iterator const_iterator; 157 inline const_iterator begin() const { return IDoms.begin(); } 158 inline const_iterator end() const { return IDoms.end(); } 159 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);} 160 161 // operator[] - Return the idom for the specified basic block. The start 162 // node returns null, because it does not have an immediate dominator. 163 // 164 inline BasicBlock *operator[](BasicBlock *BB) const { 165 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); 166 return I != IDoms.end() ? I->second : 0; 167 } 168}; 169 170//===------------------------------------- 171// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that 172// is used to compute a normal immediate dominator set. 173// 174struct ImmediateDominators : public ImmediateDominatorsBase { 175 static AnalysisID ID; // Build immediate dominators 176 177 ImmediateDominators(AnalysisID id) : ImmediateDominatorsBase(false) { 178 assert(id == ID); 179 } 180 181 virtual const char *getPassName() const { 182 return "Immediate Dominators Construction"; 183 } 184 185 virtual bool runOnFunction(Function &F) { 186 IDoms.clear(); // Reset from the last time we were run... 187 DominatorSet &DS = getAnalysis<DominatorSet>(); 188 Root = DS.getRoot(); 189 calcIDoms(DS); 190 return false; 191 } 192 193 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 194 AU.setPreservesAll(); 195 AU.addProvided(ID); 196 AU.addRequired(DominatorSet::ID); 197 } 198}; 199 200 201//===------------------------------------- 202// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase 203// that is used to compute the immediate post-dominators. 204// 205struct ImmediatePostDominators : public ImmediateDominatorsBase { 206 static AnalysisID ID; // Build immediate postdominators 207 208 ImmediatePostDominators(AnalysisID id) : ImmediateDominatorsBase(true) { 209 assert(id == ID); 210 } 211 212 virtual const char *getPassName() const { 213 return "Immediate Post-Dominators Construction"; 214 } 215 216 virtual bool runOnFunction(Function &F) { 217 IDoms.clear(); // Reset from the last time we were run... 218 PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); 219 Root = DS.getRoot(); 220 calcIDoms(DS); 221 return false; 222 } 223 224 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 225 AU.setPreservesAll(); 226 AU.addRequired(PostDominatorSet::ID); 227 AU.addProvided(ID); 228 } 229}; 230 231 232 233//===----------------------------------------------------------------------===// 234// 235// DominatorTree - Calculate the immediate dominator tree for a function. 236// 237class DominatorTreeBase : public DominatorBase { 238protected: 239 class Node2; 240public: 241 typedef Node2 Node; 242protected: 243 std::map<BasicBlock*, Node*> Nodes; 244 void reset(); 245 typedef std::map<BasicBlock*, Node*> NodeMapType; 246public: 247 class Node2 : public std::vector<Node*> { 248 friend class DominatorTree; 249 friend class PostDominatorTree; 250 BasicBlock *TheNode; 251 Node2 *IDom; 252 public: 253 inline BasicBlock *getNode() const { return TheNode; } 254 inline Node2 *getIDom() const { return IDom; } 255 inline const std::vector<Node*> &getChildren() const { return *this; } 256 257 // dominates - Returns true iff this dominates N. Note that this is not a 258 // constant time operation! 259 inline bool dominates(const Node2 *N) const { 260 const Node2 *IDom; 261 while ((IDom = N->getIDom()) != 0 && IDom != this) 262 N = IDom; // Walk up the tree 263 return IDom != 0; 264 } 265 266 private: 267 inline Node2(BasicBlock *node, Node *iDom) 268 : TheNode(node), IDom(iDom) {} 269 inline Node2 *addChild(Node *C) { push_back(C); return C; } 270 }; 271 272public: 273 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} 274 ~DominatorTreeBase() { reset(); } 275 276 virtual void releaseMemory() { reset(); } 277 278 inline Node *operator[](BasicBlock *BB) const { 279 NodeMapType::const_iterator i = Nodes.find(BB); 280 return (i != Nodes.end()) ? i->second : 0; 281 } 282}; 283 284 285//===------------------------------------- 286// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 287// compute a normal dominator tree. 288// 289struct DominatorTree : public DominatorTreeBase { 290 static AnalysisID ID; // Build dominator tree 291 292 DominatorTree(AnalysisID id) : DominatorTreeBase(false) { 293 assert(id == ID); 294 } 295 296 virtual const char *getPassName() const { 297 return "Dominator Tree Construction"; 298 } 299 300 virtual bool runOnFunction(Function &F) { 301 reset(); // Reset from the last time we were run... 302 DominatorSet &DS = getAnalysis<DominatorSet>(); 303 Root = DS.getRoot(); 304 calculate(DS); 305 return false; 306 } 307 308 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 309 AU.setPreservesAll(); 310 AU.addProvided(ID); 311 AU.addRequired(DominatorSet::ID); 312 } 313private: 314 void calculate(const DominatorSet &DS); 315}; 316 317 318//===------------------------------------- 319// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 320// compute the a post-dominator tree. 321// 322struct PostDominatorTree : public DominatorTreeBase { 323 static AnalysisID ID; // Build immediate postdominators 324 325 PostDominatorTree(AnalysisID id) : DominatorTreeBase(true) { 326 assert(id == ID); 327 } 328 329 virtual const char *getPassName() const { 330 return "Post-Dominator Tree Construction"; 331 } 332 333 virtual bool runOnFunction(Function &F) { 334 reset(); // Reset from the last time we were run... 335 PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); 336 Root = DS.getRoot(); 337 calculate(DS); 338 return false; 339 } 340 341 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 342 AU.setPreservesAll(); 343 AU.addRequired(PostDominatorSet::ID); 344 AU.addProvided(ID); 345 } 346private: 347 void calculate(const PostDominatorSet &DS); 348}; 349 350 351//===----------------------------------------------------------------------===// 352// 353// DominanceFrontier - Calculate the dominance frontiers for a function. 354// 355class DominanceFrontierBase : public DominatorBase { 356public: 357 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 358 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 359protected: 360 DomSetMapType Frontiers; 361public: 362 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} 363 364 virtual void releaseMemory() { Frontiers.clear(); } 365 366 // Accessor interface: 367 typedef DomSetMapType::const_iterator const_iterator; 368 inline const_iterator begin() const { return Frontiers.begin(); } 369 inline const_iterator end() const { return Frontiers.end(); } 370 inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); } 371}; 372 373 374//===------------------------------------- 375// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 376// compute a normal dominator tree. 377// 378struct DominanceFrontier : public DominanceFrontierBase { 379 static AnalysisID ID; // Build dominance frontier 380 381 DominanceFrontier(AnalysisID id) : DominanceFrontierBase(false) { 382 assert(id == ID); 383 } 384 385 virtual const char *getPassName() const { 386 return "Dominance Frontier Construction"; 387 } 388 389 virtual bool runOnFunction(Function &) { 390 Frontiers.clear(); 391 DominatorTree &DT = getAnalysis<DominatorTree>(); 392 Root = DT.getRoot(); 393 calculate(DT, DT[Root]); 394 return false; 395 } 396 397 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 398 AU.setPreservesAll(); 399 AU.addProvided(ID); 400 AU.addRequired(DominatorTree::ID); 401 } 402private: 403 const DomSetType &calculate(const DominatorTree &DT, 404 const DominatorTree::Node *Node); 405}; 406 407 408//===------------------------------------- 409 410// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 411// used to compute the a post-dominance frontier. 412// 413struct PostDominanceFrontier : public DominanceFrontierBase { 414 static AnalysisID ID; // Build post dominance frontier 415 416 PostDominanceFrontier(AnalysisID id) : DominanceFrontierBase(true) { 417 assert(id == ID); 418 } 419 420 virtual const char *getPassName() const { 421 return "Post-Dominance Frontier Construction"; 422 } 423 424 virtual bool runOnFunction(Function &) { 425 Frontiers.clear(); 426 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 427 Root = DT.getRoot(); 428 calculate(DT, DT[Root]); 429 return false; 430 } 431 432 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 433 AU.setPreservesAll(); 434 AU.addRequired(PostDominatorTree::ID); 435 AU.addProvided(ID); 436 } 437private: 438 const DomSetType &calculate(const PostDominatorTree &DT, 439 const DominatorTree::Node *Node); 440}; 441 442#endif 443