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