Dominators.h revision c5a22ce2b97ca477af345ad8b4dd357fa4561fcd
1//===- llvm/Analysis/DominatorSet.h - Dominator Set Calculation --*- C++ -*--=// 2// 3// This file defines the following classes: 4// 1. DominatorSet: Calculates the [reverse] dominator set for a method 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// method. 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 <set> 22#include <map> 23#include <vector> 24class Method; 25class BasicBlock; 26 27namespace cfg { 28 29//===----------------------------------------------------------------------===// 30// 31// DominatorBase - Base class that other, more interesting dominator analyses 32// inherit from. 33// 34class DominatorBase { 35protected: 36 const BasicBlock *Root; 37 inline DominatorBase(const BasicBlock *root = 0) : Root(root) {} 38public: 39 inline const BasicBlock *getRoot() const { return Root; } 40 bool isPostDominator() const; // Returns true if analysis based of postdoms 41}; 42 43//===----------------------------------------------------------------------===// 44// 45// DominatorSet - Maintain a set<const BasicBlock*> for every basic block in a 46// method, that represents the blocks that dominate the block. 47// 48class DominatorSet : public DominatorBase { 49public: 50 typedef set<const BasicBlock*> DomSetType; // Dom set for a bb 51 typedef map<const BasicBlock *, DomSetType> DomSetMapType; // Map of dom sets 52private: 53 DomSetMapType Doms; 54 55 void calcForwardDominatorSet(const Method *M); 56public: 57 // DominatorSet ctor - Build either the dominator set or the post-dominator 58 // set for a method... Building the postdominator set may require the analysis 59 // routine to modify the method so that there is only a single return in the 60 // method. 61 // 62 DominatorSet(const Method *M); 63 DominatorSet( Method *M, bool PostDomSet); 64 65 // Accessor interface: 66 typedef DomSetMapType::const_iterator const_iterator; 67 inline const_iterator begin() const { return Doms.begin(); } 68 inline const_iterator end() const { return Doms.end(); } 69 inline const_iterator find(const BasicBlock* B) const { return Doms.find(B); } 70 71 // getDominators - Return the set of basic blocks that dominate the specified 72 // block. 73 // 74 inline const DomSetType &getDominators(const BasicBlock *BB) const { 75 const_iterator I = find(BB); 76 assert(I != end() && "BB not in method!"); 77 return I->second; 78 } 79 80 // dominates - Return true if A dominates B. 81 // 82 inline bool dominates(const BasicBlock *A, const BasicBlock *B) const { 83 return getDominators(B).count(A) != 0; 84 } 85}; 86 87 88//===----------------------------------------------------------------------===// 89// 90// ImmediateDominators - Calculate the immediate dominator for each node in a 91// method. 92// 93class ImmediateDominators : public DominatorBase { 94 map<const BasicBlock*, const BasicBlock*> IDoms; 95 void calcIDoms(const DominatorSet &DS); 96public: 97 98 // ImmediateDominators ctor - Calculate the idom mapping, for a method, or 99 // from a dominator set calculated for something else... 100 // 101 inline ImmediateDominators(const DominatorSet &DS) 102 : DominatorBase(DS.getRoot()) { 103 calcIDoms(DS); // Can be used to make rev-idoms 104 } 105 106 // Accessor interface: 107 typedef map<const BasicBlock*, const BasicBlock*> IDomMapType; 108 typedef IDomMapType::const_iterator const_iterator; 109 inline const_iterator begin() const { return IDoms.begin(); } 110 inline const_iterator end() const { return IDoms.end(); } 111 inline const_iterator find(const BasicBlock* B) const { return IDoms.find(B);} 112 113 // operator[] - Return the idom for the specified basic block. The start 114 // node returns null, because it does not have an immediate dominator. 115 // 116 inline const BasicBlock *operator[](const BasicBlock *BB) const { 117 map<const BasicBlock*, const BasicBlock*>::const_iterator I = 118 IDoms.find(BB); 119 return I != IDoms.end() ? I->second : 0; 120 } 121}; 122 123 124//===----------------------------------------------------------------------===// 125// 126// DominatorTree - Calculate the immediate dominator tree for a method. 127// 128class DominatorTree : public DominatorBase { 129 class Node2; 130public: 131 typedef Node2 Node; 132private: 133 map<const BasicBlock*, Node*> Nodes; 134 void calculate(const DominatorSet &DS); 135 typedef map<const BasicBlock*, Node*> NodeMapType; 136public: 137 class Node2 : public vector<Node*> { 138 friend class DominatorTree; 139 const BasicBlock *TheNode; 140 Node2 * const IDom; 141 public: 142 inline const BasicBlock *getNode() const { return TheNode; } 143 inline Node2 *getIDom() const { return IDom; } 144 inline const vector<Node*> &getChildren() const { return *this; } 145 146 // dominates - Returns true iff this dominates N. Note that this is not a 147 // constant time operation! 148 inline bool dominates(const Node2 *N) const { 149 const Node2 *IDom; 150 while ((IDom = N->getIDom()) != 0 && IDom != this) 151 N = IDom; // Walk up the tree 152 return IDom != 0; 153 } 154 155 private: 156 inline Node2(const BasicBlock *node, Node *iDom) 157 : TheNode(node), IDom(iDom) {} 158 inline Node2 *addChild(Node *C) { push_back(C); return C; } 159 }; 160 161public: 162 // DominatorTree ctors - Compute a dominator tree, given various amounts of 163 // previous knowledge... 164 inline DominatorTree(const DominatorSet &DS) : DominatorBase(DS.getRoot()) { 165 calculate(DS); 166 } 167 168 DominatorTree(const ImmediateDominators &IDoms); 169 ~DominatorTree(); 170 171 inline const Node *operator[](const BasicBlock *BB) const { 172 NodeMapType::const_iterator i = Nodes.find(BB); 173 return (i != Nodes.end()) ? i->second : 0; 174 } 175}; 176 177 178//===----------------------------------------------------------------------===// 179// 180// DominanceFrontier - Calculate the dominance frontiers for a method. 181// 182class DominanceFrontier : public DominatorBase { 183public: 184 typedef set<const BasicBlock*> DomSetType; // Dom set for a bb 185 typedef map<const BasicBlock *, DomSetType> DomSetMapType; // Map of dom sets 186private: 187 DomSetMapType Frontiers; 188 const DomSetType &calcDomFrontier(const DominatorTree &DT, 189 const DominatorTree::Node *Node); 190 const DomSetType &calcPostDomFrontier(const DominatorTree &DT, 191 const DominatorTree::Node *Node); 192public: 193 DominanceFrontier(const DominatorSet &DS) : DominatorBase(DS.getRoot()) { 194 const DominatorTree DT(DS); 195 if (isPostDominator()) 196 calcPostDomFrontier(DT, DT[Root]); 197 else 198 calcDomFrontier(DT, DT[Root]); 199 } 200 DominanceFrontier(const ImmediateDominators &ID) 201 : DominatorBase(ID.getRoot()) { 202 const DominatorTree DT(ID); 203 if (isPostDominator()) 204 calcPostDomFrontier(DT, DT[Root]); 205 else 206 calcDomFrontier(DT, DT[Root]); 207 } 208 DominanceFrontier(const DominatorTree &DT) : DominatorBase(DT.getRoot()) { 209 if (isPostDominator()) 210 calcPostDomFrontier(DT, DT[Root]); 211 else 212 calcDomFrontier(DT, DT[Root]); 213 } 214 215 // Accessor interface: 216 typedef DomSetMapType::const_iterator const_iterator; 217 inline const_iterator begin() const { return Frontiers.begin(); } 218 inline const_iterator end() const { return Frontiers.end(); } 219 inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B);} 220}; 221 222} // End namespace cfg 223 224#endif 225