PostDominators.cpp revision 221d688a5ef21a22c2368c9fff0e92d7966c95e5
1//===- DominatorSet.cpp - Dominator Set Calculation --------------*- C++ -*--=// 2// 3// This file provides a simple class to calculate the dominator set of a method. 4// 5//===----------------------------------------------------------------------===// 6 7#include "llvm/Analysis/Dominators.h" 8#include "llvm/Transforms/UnifyMethodExitNodes.h" 9#include "llvm/Method.h" 10#include "llvm/Support/CFG.h" 11#include "Support/DepthFirstIterator.h" 12#include "Support/STLExtras.h" 13#include "Support/SetOperations.h" 14#include <algorithm> 15using std::set; 16 17//===----------------------------------------------------------------------===// 18// DominatorSet Implementation 19//===----------------------------------------------------------------------===// 20 21AnalysisID cfg::DominatorSet::ID(AnalysisID::create<cfg::DominatorSet>()); 22AnalysisID cfg::DominatorSet::PostDomID(AnalysisID::create<cfg::DominatorSet>()); 23 24bool cfg::DominatorSet::runOnMethod(Method *M) { 25 Doms.clear(); // Reset from the last time we were run... 26 27 if (isPostDominator()) 28 calcPostDominatorSet(M); 29 else 30 calcForwardDominatorSet(M); 31 return false; 32} 33 34 35// calcForwardDominatorSet - This method calculates the forward dominator sets 36// for the specified method. 37// 38void cfg::DominatorSet::calcForwardDominatorSet(Method *M) { 39 Root = M->getEntryNode(); 40 assert(Root->pred_begin() == Root->pred_end() && 41 "Root node has predecessors in method!"); 42 43 bool Changed; 44 do { 45 Changed = false; 46 47 DomSetType WorkingSet; 48 df_iterator<Method*> It = df_begin(M), End = df_end(M); 49 for ( ; It != End; ++It) { 50 const BasicBlock *BB = *It; 51 BasicBlock::pred_const_iterator PI = BB->pred_begin(), 52 PEnd = BB->pred_end(); 53 if (PI != PEnd) { // Is there SOME predecessor? 54 // Loop until we get to a predecessor that has had it's dom set filled 55 // in at least once. We are guaranteed to have this because we are 56 // traversing the graph in DFO and have handled start nodes specially. 57 // 58 while (Doms[*PI].size() == 0) ++PI; 59 WorkingSet = Doms[*PI]; 60 61 for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets 62 DomSetType &PredSet = Doms[*PI]; 63 if (PredSet.size()) 64 set_intersect(WorkingSet, PredSet); 65 } 66 } 67 68 WorkingSet.insert(BB); // A block always dominates itself 69 DomSetType &BBSet = Doms[BB]; 70 if (BBSet != WorkingSet) { 71 BBSet.swap(WorkingSet); // Constant time operation! 72 Changed = true; // The sets changed. 73 } 74 WorkingSet.clear(); // Clear out the set for next iteration 75 } 76 } while (Changed); 77} 78 79// Postdominator set constructor. This ctor converts the specified method to 80// only have a single exit node (return stmt), then calculates the post 81// dominance sets for the method. 82// 83void cfg::DominatorSet::calcPostDominatorSet(Method *M) { 84 // Since we require that the unify all exit nodes pass has been run, we know 85 // that there can be at most one return instruction in the method left. 86 // Get it. 87 // 88 Root = getAnalysis<UnifyMethodExitNodes>().getExitNode(); 89 90 if (Root == 0) { // No exit node for the method? Postdomsets are all empty 91 for (Method::const_iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) 92 Doms[*MI] = DomSetType(); 93 return; 94 } 95 96 bool Changed; 97 do { 98 Changed = false; 99 100 set<const BasicBlock*> Visited; 101 DomSetType WorkingSet; 102 idf_iterator<BasicBlock*> It = idf_begin(Root), End = idf_end(Root); 103 for ( ; It != End; ++It) { 104 const BasicBlock *BB = *It; 105 BasicBlock::succ_const_iterator PI = BB->succ_begin(), 106 PEnd = BB->succ_end(); 107 if (PI != PEnd) { // Is there SOME predecessor? 108 // Loop until we get to a successor that has had it's dom set filled 109 // in at least once. We are guaranteed to have this because we are 110 // traversing the graph in DFO and have handled start nodes specially. 111 // 112 while (Doms[*PI].size() == 0) ++PI; 113 WorkingSet = Doms[*PI]; 114 115 for (++PI; PI != PEnd; ++PI) { // Intersect all of the successor sets 116 DomSetType &PredSet = Doms[*PI]; 117 if (PredSet.size()) 118 set_intersect(WorkingSet, PredSet); 119 } 120 } 121 122 WorkingSet.insert(BB); // A block always dominates itself 123 DomSetType &BBSet = Doms[BB]; 124 if (BBSet != WorkingSet) { 125 BBSet.swap(WorkingSet); // Constant time operation! 126 Changed = true; // The sets changed. 127 } 128 WorkingSet.clear(); // Clear out the set for next iteration 129 } 130 } while (Changed); 131} 132 133// getAnalysisUsageInfo - This obviously provides a dominator set, but it also 134// uses the UnifyMethodExitNodes pass if building post-dominators 135// 136void cfg::DominatorSet::getAnalysisUsageInfo(Pass::AnalysisSet &Requires, 137 Pass::AnalysisSet &Destroyed, 138 Pass::AnalysisSet &Provided) { 139 if (isPostDominator()) { 140 Provided.push_back(PostDomID); 141 Requires.push_back(UnifyMethodExitNodes::ID); 142 } else { 143 Provided.push_back(ID); 144 } 145} 146 147 148//===----------------------------------------------------------------------===// 149// ImmediateDominators Implementation 150//===----------------------------------------------------------------------===// 151 152AnalysisID cfg::ImmediateDominators::ID(AnalysisID::create<cfg::ImmediateDominators>()); 153AnalysisID cfg::ImmediateDominators::PostDomID(AnalysisID::create<cfg::ImmediateDominators>()); 154 155// calcIDoms - Calculate the immediate dominator mapping, given a set of 156// dominators for every basic block. 157void cfg::ImmediateDominators::calcIDoms(const DominatorSet &DS) { 158 // Loop over all of the nodes that have dominators... figuring out the IDOM 159 // for each node... 160 // 161 for (DominatorSet::const_iterator DI = DS.begin(), DEnd = DS.end(); 162 DI != DEnd; ++DI) { 163 const BasicBlock *BB = DI->first; 164 const DominatorSet::DomSetType &Dominators = DI->second; 165 unsigned DomSetSize = Dominators.size(); 166 if (DomSetSize == 1) continue; // Root node... IDom = null 167 168 // Loop over all dominators of this node. This corresponds to looping over 169 // nodes in the dominator chain, looking for a node whose dominator set is 170 // equal to the current nodes, except that the current node does not exist 171 // in it. This means that it is one level higher in the dom chain than the 172 // current node, and it is our idom! 173 // 174 DominatorSet::DomSetType::const_iterator I = Dominators.begin(); 175 DominatorSet::DomSetType::const_iterator End = Dominators.end(); 176 for (; I != End; ++I) { // Iterate over dominators... 177 // All of our dominators should form a chain, where the number of elements 178 // in the dominator set indicates what level the node is at in the chain. 179 // We want the node immediately above us, so it will have an identical 180 // dominator set, except that BB will not dominate it... therefore it's 181 // dominator set size will be one less than BB's... 182 // 183 if (DS.getDominators(*I).size() == DomSetSize - 1) { 184 IDoms[BB] = *I; 185 break; 186 } 187 } 188 } 189} 190 191 192//===----------------------------------------------------------------------===// 193// DominatorTree Implementation 194//===----------------------------------------------------------------------===// 195 196AnalysisID cfg::DominatorTree::ID(AnalysisID::create<cfg::DominatorTree>()); 197AnalysisID cfg::DominatorTree::PostDomID(AnalysisID::create<cfg::DominatorTree>()); 198 199// DominatorTree::reset - Free all of the tree node memory. 200// 201void cfg::DominatorTree::reset() { 202 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) 203 delete I->second; 204 Nodes.clear(); 205} 206 207 208#if 0 209// Given immediate dominators, we can also calculate the dominator tree 210cfg::DominatorTree::DominatorTree(const ImmediateDominators &IDoms) 211 : DominatorBase(IDoms.getRoot()) { 212 const Method *M = Root->getParent(); 213 214 Nodes[Root] = new Node(Root, 0); // Add a node for the root... 215 216 // Iterate over all nodes in depth first order... 217 for (df_iterator<const Method*> I = df_begin(M), E = df_end(M); I != E; ++I) { 218 const BasicBlock *BB = *I, *IDom = IDoms[*I]; 219 220 if (IDom != 0) { // Ignore the root node and other nasty nodes 221 // We know that the immediate dominator should already have a node, 222 // because we are traversing the CFG in depth first order! 223 // 224 assert(Nodes[IDom] && "No node for IDOM?"); 225 Node *IDomNode = Nodes[IDom]; 226 227 // Add a new tree node for this BasicBlock, and link it as a child of 228 // IDomNode 229 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 230 } 231 } 232} 233#endif 234 235void cfg::DominatorTree::calculate(const DominatorSet &DS) { 236 Nodes[Root] = new Node(Root, 0); // Add a node for the root... 237 238 if (!isPostDominator()) { 239 // Iterate over all nodes in depth first order... 240 for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root); 241 I != E; ++I) { 242 const BasicBlock *BB = *I; 243 const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); 244 unsigned DomSetSize = Dominators.size(); 245 if (DomSetSize == 1) continue; // Root node... IDom = null 246 247 // Loop over all dominators of this node. This corresponds to looping over 248 // nodes in the dominator chain, looking for a node whose dominator set is 249 // equal to the current nodes, except that the current node does not exist 250 // in it. This means that it is one level higher in the dom chain than the 251 // current node, and it is our idom! We know that we have already added 252 // a DominatorTree node for our idom, because the idom must be a 253 // predecessor in the depth first order that we are iterating through the 254 // method. 255 // 256 DominatorSet::DomSetType::const_iterator I = Dominators.begin(); 257 DominatorSet::DomSetType::const_iterator End = Dominators.end(); 258 for (; I != End; ++I) { // Iterate over dominators... 259 // All of our dominators should form a chain, where the number of 260 // elements in the dominator set indicates what level the node is at in 261 // the chain. We want the node immediately above us, so it will have 262 // an identical dominator set, except that BB will not dominate it... 263 // therefore it's dominator set size will be one less than BB's... 264 // 265 if (DS.getDominators(*I).size() == DomSetSize - 1) { 266 // We know that the immediate dominator should already have a node, 267 // because we are traversing the CFG in depth first order! 268 // 269 Node *IDomNode = Nodes[*I]; 270 assert(IDomNode && "No node for IDOM?"); 271 272 // Add a new tree node for this BasicBlock, and link it as a child of 273 // IDomNode 274 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 275 break; 276 } 277 } 278 } 279 } else if (Root) { 280 // Iterate over all nodes in depth first order... 281 for (idf_iterator<BasicBlock*> I = idf_begin(Root), E = idf_end(Root); 282 I != E; ++I) { 283 const BasicBlock *BB = *I; 284 const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); 285 unsigned DomSetSize = Dominators.size(); 286 if (DomSetSize == 1) continue; // Root node... IDom = null 287 288 // Loop over all dominators of this node. This corresponds to looping 289 // over nodes in the dominator chain, looking for a node whose dominator 290 // set is equal to the current nodes, except that the current node does 291 // not exist in it. This means that it is one level higher in the dom 292 // chain than the current node, and it is our idom! We know that we have 293 // already added a DominatorTree node for our idom, because the idom must 294 // be a predecessor in the depth first order that we are iterating through 295 // the method. 296 // 297 DominatorSet::DomSetType::const_iterator I = Dominators.begin(); 298 DominatorSet::DomSetType::const_iterator End = Dominators.end(); 299 for (; I != End; ++I) { // Iterate over dominators... 300 // All of our dominators should form a chain, where the number 301 // of elements in the dominator set indicates what level the 302 // node is at in the chain. We want the node immediately 303 // above us, so it will have an identical dominator set, 304 // except that BB will not dominate it... therefore it's 305 // dominator set size will be one less than BB's... 306 // 307 if (DS.getDominators(*I).size() == DomSetSize - 1) { 308 // We know that the immediate dominator should already have a node, 309 // because we are traversing the CFG in depth first order! 310 // 311 Node *IDomNode = Nodes[*I]; 312 assert(IDomNode && "No node for IDOM?"); 313 314 // Add a new tree node for this BasicBlock, and link it as a child of 315 // IDomNode 316 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 317 break; 318 } 319 } 320 } 321 } 322} 323 324 325 326//===----------------------------------------------------------------------===// 327// DominanceFrontier Implementation 328//===----------------------------------------------------------------------===// 329 330AnalysisID cfg::DominanceFrontier::ID(AnalysisID::create<cfg::DominanceFrontier>()); 331AnalysisID cfg::DominanceFrontier::PostDomID(AnalysisID::create<cfg::DominanceFrontier>()); 332 333const cfg::DominanceFrontier::DomSetType & 334cfg::DominanceFrontier::calcDomFrontier(const DominatorTree &DT, 335 const DominatorTree::Node *Node) { 336 // Loop over CFG successors to calculate DFlocal[Node] 337 const BasicBlock *BB = Node->getNode(); 338 DomSetType &S = Frontiers[BB]; // The new set to fill in... 339 340 for (BasicBlock::succ_const_iterator SI = BB->succ_begin(), 341 SE = BB->succ_end(); SI != SE; ++SI) { 342 // Does Node immediately dominate this successor? 343 if (DT[*SI]->getIDom() != Node) 344 S.insert(*SI); 345 } 346 347 // At this point, S is DFlocal. Now we union in DFup's of our children... 348 // Loop through and visit the nodes that Node immediately dominates (Node's 349 // children in the IDomTree) 350 // 351 for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end(); 352 NI != NE; ++NI) { 353 DominatorTree::Node *IDominee = *NI; 354 const DomSetType &ChildDF = calcDomFrontier(DT, IDominee); 355 356 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 357 for (; CDFI != CDFE; ++CDFI) { 358 if (!Node->dominates(DT[*CDFI])) 359 S.insert(*CDFI); 360 } 361 } 362 363 return S; 364} 365 366const cfg::DominanceFrontier::DomSetType & 367cfg::DominanceFrontier::calcPostDomFrontier(const DominatorTree &DT, 368 const DominatorTree::Node *Node) { 369 // Loop over CFG successors to calculate DFlocal[Node] 370 const BasicBlock *BB = Node->getNode(); 371 DomSetType &S = Frontiers[BB]; // The new set to fill in... 372 if (!Root) return S; 373 374 for (BasicBlock::pred_const_iterator SI = BB->pred_begin(), 375 SE = BB->pred_end(); SI != SE; ++SI) { 376 // Does Node immediately dominate this predeccessor? 377 if (DT[*SI]->getIDom() != Node) 378 S.insert(*SI); 379 } 380 381 // At this point, S is DFlocal. Now we union in DFup's of our children... 382 // Loop through and visit the nodes that Node immediately dominates (Node's 383 // children in the IDomTree) 384 // 385 for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end(); 386 NI != NE; ++NI) { 387 DominatorTree::Node *IDominee = *NI; 388 const DomSetType &ChildDF = calcPostDomFrontier(DT, IDominee); 389 390 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 391 for (; CDFI != CDFE; ++CDFI) { 392 if (!Node->dominates(DT[*CDFI])) 393 S.insert(*CDFI); 394 } 395 } 396 397 return S; 398} 399