Dominators.h revision a298d27808ecb8ffb574d6e50f56601db2ec5fda
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> 23 24namespace cfg { 25 26//===----------------------------------------------------------------------===// 27// 28// DominatorBase - Base class that other, more interesting dominator analyses 29// inherit from. 30// 31class DominatorBase : public FunctionPass { 32protected: 33 BasicBlock *Root; 34 const bool IsPostDominators; 35 36 inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {} 37public: 38 inline BasicBlock *getRoot() const { return Root; } 39 40 // Returns true if analysis based of postdoms 41 bool isPostDominator() const { return IsPostDominators; } 42}; 43 44//===----------------------------------------------------------------------===// 45// 46// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a 47// function, that represents the blocks that dominate the block. 48// 49class DominatorSet : public DominatorBase { 50public: 51 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 52 // Map of dom sets 53 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; 54private: 55 DomSetMapType Doms; 56 57 void calcForwardDominatorSet(Function *F); 58 void calcPostDominatorSet(Function *F); 59public: 60 // DominatorSet ctor - Build either the dominator set or the post-dominator 61 // set for a function... 62 // 63 static AnalysisID ID; // Build dominator set 64 static AnalysisID PostDomID; // Build postdominator set 65 66 DominatorSet(AnalysisID id) : DominatorBase(id == PostDomID) {} 67 68 virtual bool runOnFunction(Function *F); 69 70 // Accessor interface: 71 typedef DomSetMapType::const_iterator const_iterator; 72 typedef DomSetMapType::iterator iterator; 73 inline const_iterator begin() const { return Doms.begin(); } 74 inline iterator begin() { return Doms.begin(); } 75 inline const_iterator end() const { return Doms.end(); } 76 inline iterator end() { return Doms.end(); } 77 inline const_iterator find(BasicBlock* B) const { return Doms.find(B); } 78 inline iterator find(BasicBlock* B) { return Doms.find(B); } 79 80 // getDominators - Return the set of basic blocks that dominate the specified 81 // block. 82 // 83 inline const DomSetType &getDominators(BasicBlock *BB) const { 84 const_iterator I = find(BB); 85 assert(I != end() && "BB not in function!"); 86 return I->second; 87 } 88 89 // dominates - Return true if A dominates B. 90 // 91 inline bool dominates(BasicBlock *A, BasicBlock *B) const { 92 return getDominators(B).count(A) != 0; 93 } 94 95 // getAnalysisUsage - This obviously provides a dominator set, but it also 96 // uses the UnifyFunctionExitNode pass if building post-dominators 97 // 98 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 99}; 100 101 102//===----------------------------------------------------------------------===// 103// 104// ImmediateDominators - Calculate the immediate dominator for each node in a 105// function. 106// 107class ImmediateDominators : public DominatorBase { 108 std::map<BasicBlock*, BasicBlock*> IDoms; 109 void calcIDoms(const DominatorSet &DS); 110public: 111 112 // ImmediateDominators ctor - Calculate the idom or post-idom mapping, 113 // for a function... 114 // 115 static AnalysisID ID; // Build immediate dominators 116 static AnalysisID PostDomID; // Build immediate postdominators 117 118 ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {} 119 120 virtual bool runOnFunction(Function *F) { 121 IDoms.clear(); // Reset from the last time we were run... 122 DominatorSet *DS; 123 if (isPostDominator()) 124 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID); 125 else 126 DS = &getAnalysis<DominatorSet>(); 127 128 Root = DS->getRoot(); 129 calcIDoms(*DS); // Can be used to make rev-idoms 130 return false; 131 } 132 133 // Accessor interface: 134 typedef std::map<BasicBlock*, BasicBlock*> IDomMapType; 135 typedef IDomMapType::const_iterator const_iterator; 136 inline const_iterator begin() const { return IDoms.begin(); } 137 inline const_iterator end() const { return IDoms.end(); } 138 inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);} 139 140 // operator[] - Return the idom for the specified basic block. The start 141 // node returns null, because it does not have an immediate dominator. 142 // 143 inline BasicBlock *operator[](BasicBlock *BB) const { 144 std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB); 145 return I != IDoms.end() ? I->second : 0; 146 } 147 148 // getAnalysisUsage - This obviously provides a dominator tree, but it 149 // can only do so with the input of dominator sets 150 // 151 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 152 AU.setPreservesAll(); 153 if (isPostDominator()) { 154 AU.addRequired(DominatorSet::PostDomID); 155 AU.addProvided(PostDomID); 156 } else { 157 AU.addRequired(DominatorSet::ID); 158 AU.addProvided(ID); 159 } 160 } 161}; 162 163 164//===----------------------------------------------------------------------===// 165// 166// DominatorTree - Calculate the immediate dominator tree for a function. 167// 168class DominatorTree : public DominatorBase { 169 class Node2; 170public: 171 typedef Node2 Node; 172private: 173 std::map<BasicBlock*, Node*> Nodes; 174 void calculate(const DominatorSet &DS); 175 void reset(); 176 typedef std::map<BasicBlock*, Node*> NodeMapType; 177public: 178 class Node2 : public std::vector<Node*> { 179 friend class DominatorTree; 180 BasicBlock *TheNode; 181 Node2 *IDom; 182 public: 183 inline BasicBlock *getNode() const { return TheNode; } 184 inline Node2 *getIDom() const { return IDom; } 185 inline const std::vector<Node*> &getChildren() const { return *this; } 186 187 // dominates - Returns true iff this dominates N. Note that this is not a 188 // constant time operation! 189 inline bool dominates(const Node2 *N) const { 190 const Node2 *IDom; 191 while ((IDom = N->getIDom()) != 0 && IDom != this) 192 N = IDom; // Walk up the tree 193 return IDom != 0; 194 } 195 196 private: 197 inline Node2(BasicBlock *node, Node *iDom) 198 : TheNode(node), IDom(iDom) {} 199 inline Node2 *addChild(Node *C) { push_back(C); return C; } 200 }; 201 202public: 203 // DominatorTree ctor - Compute a dominator tree, given various amounts of 204 // previous knowledge... 205 static AnalysisID ID; // Build dominator tree 206 static AnalysisID PostDomID; // Build postdominator tree 207 208 DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {} 209 ~DominatorTree() { reset(); } 210 211 virtual bool runOnFunction(Function *F) { 212 reset(); 213 DominatorSet *DS; 214 if (isPostDominator()) 215 DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID); 216 else 217 DS = &getAnalysis<DominatorSet>(); 218 Root = DS->getRoot(); 219 calculate(*DS); // Can be used to make rev-idoms 220 return false; 221 } 222 223 inline Node *operator[](BasicBlock *BB) const { 224 NodeMapType::const_iterator i = Nodes.find(BB); 225 return (i != Nodes.end()) ? i->second : 0; 226 } 227 228 // getAnalysisUsage - This obviously provides a dominator tree, but it 229 // uses dominator sets 230 // 231 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 232 AU.setPreservesAll(); 233 if (isPostDominator()) { 234 AU.addRequired(DominatorSet::PostDomID); 235 AU.addProvided(PostDomID); 236 } else { 237 AU.addRequired(DominatorSet::ID); 238 AU.addProvided(ID); 239 } 240 } 241}; 242 243 244//===----------------------------------------------------------------------===// 245// 246// DominanceFrontier - Calculate the dominance frontiers for a function. 247// 248class DominanceFrontier : public DominatorBase { 249public: 250 typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb 251 typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map 252private: 253 DomSetMapType Frontiers; 254 const DomSetType &calcDomFrontier(const DominatorTree &DT, 255 const DominatorTree::Node *Node); 256 const DomSetType &calcPostDomFrontier(const DominatorTree &DT, 257 const DominatorTree::Node *Node); 258public: 259 260 // DominatorFrontier ctor - Compute dominator frontiers for a function 261 // 262 static AnalysisID ID; // Build dominator frontier 263 static AnalysisID PostDomID; // Build postdominator frontier 264 265 DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {} 266 267 virtual bool runOnFunction(Function *) { 268 Frontiers.clear(); 269 DominatorTree *DT; 270 if (isPostDominator()) 271 DT = &getAnalysis<DominatorTree>(DominatorTree::PostDomID); 272 else 273 DT = &getAnalysis<DominatorTree>(); 274 Root = DT->getRoot(); 275 276 if (isPostDominator()) 277 calcPostDomFrontier(*DT, (*DT)[Root]); 278 else 279 calcDomFrontier(*DT, (*DT)[Root]); 280 return false; 281 } 282 283 // Accessor interface: 284 typedef DomSetMapType::const_iterator const_iterator; 285 inline const_iterator begin() const { return Frontiers.begin(); } 286 inline const_iterator end() const { return Frontiers.end(); } 287 inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); } 288 289 // getAnalysisUsage - This obviously provides the dominance frontier, but it 290 // uses dominator sets 291 // 292 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 293 AU.setPreservesAll(); 294 if (isPostDominator()) { 295 AU.addRequired(DominatorTree::PostDomID); 296 AU.addProvided(PostDomID); 297 } else { 298 AU.addRequired(DominatorTree::ID); 299 AU.addProvided(ID); 300 } 301 } 302}; 303 304} // End namespace cfg 305 306#endif 307