Dominators.h revision d472e47b6cb59a7cc214cc50db222eb86ddcf748
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 // print - Convert to human readable form 86 virtual void print(std::ostream &OS) const; 87 88 // dominates - Return true if A dominates B. This performs the special checks 89 // neccesary if A and B are in the same basic block. 90 // 91 bool dominates(Instruction *A, Instruction *B) const; 92}; 93 94 95//===------------------------------------- 96// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 97// compute a normal dominator set. 98// 99struct DominatorSet : public DominatorSetBase { 100 static AnalysisID ID; // Build dominator set 101 102 DominatorSet() : DominatorSetBase(false) {} 103 104 virtual bool runOnFunction(Function &F); 105 106 // getAnalysisUsage - This simply provides a dominator set 107 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 108 AU.setPreservesAll(); 109 } 110}; 111 112 113//===------------------------------------- 114// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to 115// compute the post-dominator set. 116// 117struct PostDominatorSet : public DominatorSetBase { 118 static AnalysisID ID; // Build post-dominator set 119 120 PostDominatorSet() : DominatorSetBase(true) {} 121 122 virtual bool runOnFunction(Function &F); 123 124 // getAnalysisUsage - This obviously provides a dominator set, but it also 125 // uses the UnifyFunctionExitNode pass if building post-dominators 126 // 127 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 128}; 129 130 131 132 133 134//===----------------------------------------------------------------------===// 135// 136// ImmediateDominators - Calculate the immediate dominator for each node in a 137// function. 138// 139class ImmediateDominatorsBase : public DominatorBase { 140protected: 141 std::map<BasicBlock*, BasicBlock*> IDoms; 142 void calcIDoms(const DominatorSetBase &DS); 143public: 144 ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {} 145 146 virtual void releaseMemory() { IDoms.clear(); } 147 148 // Accessor interface: 149 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType; 150 typedef IDomMapType::const_iterator const_iterator; 151 inline const_iterator begin() const { return IDoms.begin(); } 152 inline const_iterator end() const { return IDoms.end(); } 153 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);} 154 155 // operator[] - Return the idom for the specified basic block. The start 156 // node returns null, because it does not have an immediate dominator. 157 // 158 inline BasicBlock *operator[](BasicBlock *BB) const { 159 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); 160 return I != IDoms.end() ? I->second : 0; 161 } 162 163 // print - Convert to human readable form 164 virtual void print(std::ostream &OS) const; 165}; 166 167//===------------------------------------- 168// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that 169// is used to compute a normal immediate dominator set. 170// 171struct ImmediateDominators : public ImmediateDominatorsBase { 172 static AnalysisID ID; // Build immediate dominators 173 174 ImmediateDominators() : ImmediateDominatorsBase(false) {} 175 176 virtual bool runOnFunction(Function &F) { 177 IDoms.clear(); // Reset from the last time we were run... 178 DominatorSet &DS = getAnalysis<DominatorSet>(); 179 Root = DS.getRoot(); 180 calcIDoms(DS); 181 return false; 182 } 183 184 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 185 AU.setPreservesAll(); 186 AU.addRequired(DominatorSet::ID); 187 } 188}; 189 190 191//===------------------------------------- 192// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase 193// that is used to compute the immediate post-dominators. 194// 195struct ImmediatePostDominators : public ImmediateDominatorsBase { 196 static AnalysisID ID; // Build immediate postdominators 197 198 ImmediatePostDominators() : ImmediateDominatorsBase(true) {} 199 200 virtual bool runOnFunction(Function &F) { 201 IDoms.clear(); // Reset from the last time we were run... 202 PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); 203 Root = DS.getRoot(); 204 calcIDoms(DS); 205 return false; 206 } 207 208 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 209 AU.setPreservesAll(); 210 AU.addRequired(PostDominatorSet::ID); 211 } 212}; 213 214 215 216//===----------------------------------------------------------------------===// 217// 218// DominatorTree - Calculate the immediate dominator tree for a function. 219// 220class DominatorTreeBase : public DominatorBase { 221protected: 222 class Node2; 223public: 224 typedef Node2 Node; 225protected: 226 std::map<BasicBlock*, Node*> Nodes; 227 void reset(); 228 typedef std::map<BasicBlock*, Node*> NodeMapType; 229public: 230 class Node2 : public std::vector<Node*> { 231 friend class DominatorTree; 232 friend class PostDominatorTree; 233 BasicBlock *TheNode; 234 Node2 *IDom; 235 public: 236 inline BasicBlock *getNode() const { return TheNode; } 237 inline Node2 *getIDom() const { return IDom; } 238 inline const std::vector<Node*> &getChildren() const { return *this; } 239 240 // dominates - Returns true iff this dominates N. Note that this is not a 241 // constant time operation! 242 inline bool dominates(const Node2 *N) const { 243 const Node2 *IDom; 244 while ((IDom = N->getIDom()) != 0 && IDom != this) 245 N = IDom; // Walk up the tree 246 return IDom != 0; 247 } 248 249 private: 250 inline Node2(BasicBlock *node, Node *iDom) 251 : TheNode(node), IDom(iDom) {} 252 inline Node2 *addChild(Node *C) { push_back(C); return C; } 253 }; 254 255public: 256 DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {} 257 ~DominatorTreeBase() { reset(); } 258 259 virtual void releaseMemory() { reset(); } 260 261 inline Node *operator[](BasicBlock *BB) const { 262 NodeMapType::const_iterator i = Nodes.find(BB); 263 return (i != Nodes.end()) ? i->second : 0; 264 } 265 266 // print - Convert to human readable form 267 virtual void print(std::ostream &OS) const; 268}; 269 270 271//===------------------------------------- 272// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 273// compute a normal dominator tree. 274// 275struct DominatorTree : public DominatorTreeBase { 276 static AnalysisID ID; // Build dominator tree 277 278 DominatorTree() : DominatorTreeBase(false) {} 279 280 virtual bool runOnFunction(Function &F) { 281 reset(); // Reset from the last time we were run... 282 DominatorSet &DS = getAnalysis<DominatorSet>(); 283 Root = DS.getRoot(); 284 calculate(DS); 285 return false; 286 } 287 288 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 289 AU.setPreservesAll(); 290 AU.addRequired(DominatorSet::ID); 291 } 292private: 293 void calculate(const DominatorSet &DS); 294}; 295 296 297//===------------------------------------- 298// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 299// compute the a post-dominator tree. 300// 301struct PostDominatorTree : public DominatorTreeBase { 302 static AnalysisID ID; // Build immediate postdominators 303 304 PostDominatorTree() : DominatorTreeBase(true) {} 305 306 virtual bool runOnFunction(Function &F) { 307 reset(); // Reset from the last time we were run... 308 PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); 309 Root = DS.getRoot(); 310 calculate(DS); 311 return false; 312 } 313 314 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 315 AU.setPreservesAll(); 316 AU.addRequired(PostDominatorSet::ID); 317 } 318private: 319 void calculate(const PostDominatorSet &DS); 320}; 321 322 323//===----------------------------------------------------------------------===// 324// 325// DominanceFrontier - Calculate the dominance frontiers for a function. 326// 327class DominanceFrontierBase : public DominatorBase { 328public: 329 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 330 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 331protected: 332 DomSetMapType Frontiers; 333public: 334 DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {} 335 336 virtual void releaseMemory() { Frontiers.clear(); } 337 338 // Accessor interface: 339 typedef DomSetMapType::const_iterator const_iterator; 340 inline const_iterator begin() const { return Frontiers.begin(); } 341 inline const_iterator end() const { return Frontiers.end(); } 342 inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); } 343 344 // print - Convert to human readable form 345 virtual void print(std::ostream &OS) const; 346}; 347 348 349//===------------------------------------- 350// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 351// compute a normal dominator tree. 352// 353struct DominanceFrontier : public DominanceFrontierBase { 354 static AnalysisID ID; // Build dominance frontier 355 356 DominanceFrontier() : DominanceFrontierBase(false) {} 357 358 virtual bool runOnFunction(Function &) { 359 Frontiers.clear(); 360 DominatorTree &DT = getAnalysis<DominatorTree>(); 361 Root = DT.getRoot(); 362 calculate(DT, DT[Root]); 363 return false; 364 } 365 366 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 367 AU.setPreservesAll(); 368 AU.addRequired(DominatorTree::ID); 369 } 370private: 371 const DomSetType &calculate(const DominatorTree &DT, 372 const DominatorTree::Node *Node); 373}; 374 375 376//===------------------------------------- 377 378// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 379// used to compute the a post-dominance frontier. 380// 381struct PostDominanceFrontier : public DominanceFrontierBase { 382 static AnalysisID ID; // Build post dominance frontier 383 384 PostDominanceFrontier() : DominanceFrontierBase(true) {} 385 386 virtual bool runOnFunction(Function &) { 387 Frontiers.clear(); 388 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 389 Root = DT.getRoot(); 390 calculate(DT, DT[Root]); 391 return false; 392 } 393 394 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 395 AU.setPreservesAll(); 396 AU.addRequired(PostDominatorTree::ID); 397 } 398private: 399 const DomSetType &calculate(const PostDominatorTree &DT, 400 const DominatorTree::Node *Node); 401}; 402 403#endif 404