Dominators.h revision ef704a23b4c3cadf11b093fa628cafa38fa05ad5
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 DominatorSet : 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; 53private: 54 DomSetMapType Doms; 55 56 void calcForwardDominatorSet(Function *F); 57 void calcPostDominatorSet(Function *F); 58public: 59 // DominatorSet ctor - Build either the dominator set or the post-dominator 60 // set for a function... 61 // 62 static AnalysisID ID; // Build dominator set 63 static AnalysisID PostDomID; // Build postdominator set 64 65 DominatorSet(AnalysisID id) : DominatorBase(id == PostDomID) {} 66 67 virtual const char *getPassName() const { 68 if (isPostDominator()) return "Post-Dominator Set Construction"; 69 else return "Dominator Set Construction"; 70 } 71 72 virtual bool runOnFunction(Function *F); 73 74 // Accessor interface: 75 typedef DomSetMapType::const_iterator const_iterator; 76 typedef DomSetMapType::iterator iterator; 77 inline const_iterator begin() const { return Doms.begin(); } 78 inline iterator begin() { return Doms.begin(); } 79 inline const_iterator end() const { return Doms.end(); } 80 inline iterator end() { return Doms.end(); } 81 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); } 82 inline iterator find(BasicBlock* B) { return Doms.find(B); } 83 84 // getDominators - Return the set of basic blocks that dominate the specified 85 // block. 86 // 87 inline const DomSetType &getDominators(BasicBlock *BB) const { 88 const_iterator I = find(BB); 89 assert(I != end() && "BB not in function!"); 90 return I->second; 91 } 92 93 // dominates - Return true if A dominates B. 94 // 95 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 96 return getDominators(B).count(A) != 0; 97 } 98 99 // dominates - Return true if A dominates B. This performs the special checks 100 // neccesary if A and B are in the same basic block. 101 // 102 bool dominates(Instruction *A, Instruction *B) const; 103 104 105 // getAnalysisUsage - This obviously provides a dominator set, but it also 106 // uses the UnifyFunctionExitNode pass if building post-dominators 107 // 108 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 109}; 110 111 112//===----------------------------------------------------------------------===// 113// 114// ImmediateDominators - Calculate the immediate dominator for each node in a 115// function. 116// 117class ImmediateDominators : public DominatorBase { 118 std::map<BasicBlock*, BasicBlock*> IDoms; 119 void calcIDoms(const DominatorSet &DS); 120public: 121 122 // ImmediateDominators ctor - Calculate the idom or post-idom mapping, 123 // for a function... 124 // 125 static AnalysisID ID; // Build immediate dominators 126 static AnalysisID PostDomID; // Build immediate postdominators 127 128 ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {} 129 130 virtual const char *getPassName() const { 131 if (isPostDominator()) return "Immediate Post-Dominators Construction"; 132 else return "Immediate Dominators Construction"; 133 } 134 135 virtual bool runOnFunction(Function *F) { 136 IDoms.clear(); // Reset from the last time we were run... 137 DominatorSet *DS; 138 if (isPostDominator()) 139 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID); 140 else 141 DS = &getAnalysis<DominatorSet>(); 142 143 Root = DS->getRoot(); 144 calcIDoms(*DS); // Can be used to make rev-idoms 145 return false; 146 } 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 // getAnalysisUsage - This obviously provides a dominator tree, but it 164 // can only do so with the input of dominator sets 165 // 166 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 167 AU.setPreservesAll(); 168 if (isPostDominator()) { 169 AU.addRequired(DominatorSet::PostDomID); 170 AU.addProvided(PostDomID); 171 } else { 172 AU.addRequired(DominatorSet::ID); 173 AU.addProvided(ID); 174 } 175 } 176}; 177 178 179//===----------------------------------------------------------------------===// 180// 181// DominatorTree - Calculate the immediate dominator tree for a function. 182// 183class DominatorTree : public DominatorBase { 184 class Node2; 185public: 186 typedef Node2 Node; 187private: 188 std::map<BasicBlock*, Node*> Nodes; 189 void calculate(const DominatorSet &DS); 190 void reset(); 191 typedef std::map<BasicBlock*, Node*> NodeMapType; 192public: 193 class Node2 : public std::vector<Node*> { 194 friend class DominatorTree; 195 BasicBlock *TheNode; 196 Node2 *IDom; 197 public: 198 inline BasicBlock *getNode() const { return TheNode; } 199 inline Node2 *getIDom() const { return IDom; } 200 inline const std::vector<Node*> &getChildren() const { return *this; } 201 202 // dominates - Returns true iff this dominates N. Note that this is not a 203 // constant time operation! 204 inline bool dominates(const Node2 *N) const { 205 const Node2 *IDom; 206 while ((IDom = N->getIDom()) != 0 && IDom != this) 207 N = IDom; // Walk up the tree 208 return IDom != 0; 209 } 210 211 private: 212 inline Node2(BasicBlock *node, Node *iDom) 213 : TheNode(node), IDom(iDom) {} 214 inline Node2 *addChild(Node *C) { push_back(C); return C; } 215 }; 216 217public: 218 // DominatorTree ctor - Compute a dominator tree, given various amounts of 219 // previous knowledge... 220 static AnalysisID ID; // Build dominator tree 221 static AnalysisID PostDomID; // Build postdominator tree 222 223 DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {} 224 ~DominatorTree() { reset(); } 225 226 virtual const char *getPassName() const { 227 if (isPostDominator()) return "Post-Dominator Tree Construction"; 228 else return "Dominator Tree Construction"; 229 } 230 231 virtual bool runOnFunction(Function *F) { 232 reset(); 233 DominatorSet *DS; 234 if (isPostDominator()) 235 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID); 236 else 237 DS = &getAnalysis<DominatorSet>(); 238 Root = DS->getRoot(); 239 calculate(*DS); // Can be used to make rev-idoms 240 return false; 241 } 242 243 inline Node *operator[](BasicBlock *BB) const { 244 NodeMapType::const_iterator i = Nodes.find(BB); 245 return (i != Nodes.end()) ? i->second : 0; 246 } 247 248 // getAnalysisUsage - This obviously provides a dominator tree, but it 249 // uses dominator sets 250 // 251 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 252 AU.setPreservesAll(); 253 if (isPostDominator()) { 254 AU.addRequired(DominatorSet::PostDomID); 255 AU.addProvided(PostDomID); 256 } else { 257 AU.addRequired(DominatorSet::ID); 258 AU.addProvided(ID); 259 } 260 } 261}; 262 263 264//===----------------------------------------------------------------------===// 265// 266// DominanceFrontier - Calculate the dominance frontiers for a function. 267// 268class DominanceFrontier : public DominatorBase { 269public: 270 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 271 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 272private: 273 DomSetMapType Frontiers; 274 const DomSetType &calcDomFrontier(const DominatorTree &DT, 275 const DominatorTree::Node *Node); 276 const DomSetType &calcPostDomFrontier(const DominatorTree &DT, 277 const DominatorTree::Node *Node); 278public: 279 280 // DominatorFrontier ctor - Compute dominator frontiers for a function 281 // 282 static AnalysisID ID; // Build dominator frontier 283 static AnalysisID PostDomID; // Build postdominator frontier 284 285 DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {} 286 287 virtual const char *getPassName() const { 288 if (isPostDominator()) return "Post-Dominance Frontier Construction"; 289 else return "Dominance Frontier Construction"; 290 } 291 292 virtual bool runOnFunction(Function *) { 293 Frontiers.clear(); 294 DominatorTree *DT; 295 if (isPostDominator()) 296 DT = &getAnalysis<DominatorTree>(DominatorTree::PostDomID); 297 else 298 DT = &getAnalysis<DominatorTree>(); 299 Root = DT->getRoot(); 300 301 if (isPostDominator()) 302 calcPostDomFrontier(*DT, (*DT)[Root]); 303 else 304 calcDomFrontier(*DT, (*DT)[Root]); 305 return false; 306 } 307 308 // Accessor interface: 309 typedef DomSetMapType::const_iterator const_iterator; 310 inline const_iterator begin() const { return Frontiers.begin(); } 311 inline const_iterator end() const { return Frontiers.end(); } 312 inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); } 313 314 // getAnalysisUsage - This obviously provides the dominance frontier, but it 315 // uses dominator sets 316 // 317 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 318 AU.setPreservesAll(); 319 if (isPostDominator()) { 320 AU.addRequired(DominatorTree::PostDomID); 321 AU.addProvided(PostDomID); 322 } else { 323 AU.addRequired(DominatorTree::ID); 324 AU.addProvided(ID); 325 } 326 } 327}; 328 329#endif 330