PostDominators.cpp revision c444a4228f31656f854d15eac671b450df557346
1//===- PostDominators.cpp - Post-Dominator Calculation --------------------===// 2// 3// This file implements the post-dominator construction algorithms. 4// 5//===----------------------------------------------------------------------===// 6 7#include "llvm/Analysis/PostDominators.h" 8#include "llvm/iTerminators.h" 9#include "llvm/Support/CFG.h" 10#include "Support/DepthFirstIterator.h" 11#include "Support/SetOperations.h" 12 13//===----------------------------------------------------------------------===// 14// PostDominatorSet Implementation 15//===----------------------------------------------------------------------===// 16 17static RegisterAnalysis<PostDominatorSet> 18B("postdomset", "Post-Dominator Set Construction", true); 19 20// Postdominator set construction. This converts the specified function to only 21// have a single exit node (return stmt), then calculates the post dominance 22// sets for the function. 23// 24bool PostDominatorSet::runOnFunction(Function &F) { 25 Doms.clear(); // Reset from the last time we were run... 26 27 // Scan the function looking for the root nodes of the post-dominance 28 // relationships. These blocks end with return and unwind instructions. 29 // While we are iterating over the function, we also initialize all of the 30 // domsets to empty. 31 Roots.clear(); 32 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 33 Doms[I]; // Initialize to empty 34 35 if (isa<ReturnInst>(I->getTerminator()) || 36 isa<UnwindInst>(I->getTerminator())) 37 Roots.push_back(I); 38 } 39 40 // If there are no exit nodes for the function, postdomsets are all empty. 41 // This can happen if the function just contains an infinite loop, for 42 // example. 43 if (Roots.empty()) return false; 44 45 // If we have more than one root, we insert an artificial "null" exit, which 46 // has "virtual edges" to each of the real exit nodes. 47 if (Roots.size() > 1) 48 Doms[0].insert(0); 49 50 bool Changed; 51 do { 52 Changed = false; 53 54 std::set<const BasicBlock*> Visited; 55 DomSetType WorkingSet; 56 57 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 58 for (idf_iterator<BasicBlock*> It = idf_begin(Roots[i]), 59 E = idf_end(Roots[i]); It != E; ++It) { 60 BasicBlock *BB = *It; 61 succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 62 if (SI != SE) { // Is there SOME successor? 63 // Loop until we get to a successor that has had it's dom set filled 64 // in at least once. We are guaranteed to have this because we are 65 // traversing the graph in DFO and have handled start nodes specially. 66 // 67 while (Doms[*SI].size() == 0) ++SI; 68 WorkingSet = Doms[*SI]; 69 70 for (++SI; SI != SE; ++SI) { // Intersect all of the successor sets 71 DomSetType &SuccSet = Doms[*SI]; 72 if (SuccSet.size()) 73 set_intersect(WorkingSet, SuccSet); 74 } 75 } else { 76 // If this node has no successors, it must be one of the root nodes. 77 // We will already take care of the notion that the node 78 // post-dominates itself. The only thing we have to add is that if 79 // there are multiple root nodes, we want to insert a special "null" 80 // exit node which dominates the roots as well. 81 if (Roots.size() > 1) 82 WorkingSet.insert(0); 83 } 84 85 WorkingSet.insert(BB); // A block always dominates itself 86 DomSetType &BBSet = Doms[BB]; 87 if (BBSet != WorkingSet) { 88 BBSet.swap(WorkingSet); // Constant time operation! 89 Changed = true; // The sets changed. 90 } 91 WorkingSet.clear(); // Clear out the set for next iteration 92 } 93 } while (Changed); 94 return false; 95} 96 97//===----------------------------------------------------------------------===// 98// ImmediatePostDominators Implementation 99//===----------------------------------------------------------------------===// 100 101static RegisterAnalysis<ImmediatePostDominators> 102D("postidom", "Immediate Post-Dominators Construction", true); 103 104//===----------------------------------------------------------------------===// 105// PostDominatorTree Implementation 106//===----------------------------------------------------------------------===// 107 108static RegisterAnalysis<PostDominatorTree> 109F("postdomtree", "Post-Dominator Tree Construction", true); 110 111void PostDominatorTree::calculate(const PostDominatorSet &DS) { 112 if (Roots.empty()) return; 113 BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0; 114 115 Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... 116 117 // Iterate over all nodes in depth first order... 118 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 119 for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]), 120 E = idf_end(Roots[i]); I != E; ++I) { 121 BasicBlock *BB = *I; 122 const DominatorSet::DomSetType &Dominators = DS.getDominators(BB); 123 unsigned DomSetSize = Dominators.size(); 124 if (DomSetSize == 1) continue; // Root node... IDom = null 125 126 // If we have already computed the immediate dominator for this node, 127 // don't revisit. This can happen due to nodes reachable from multiple 128 // roots, but which the idf_iterator doesn't know about. 129 if (Nodes.find(BB) != Nodes.end()) continue; 130 131 // Loop over all dominators of this node. This corresponds to looping 132 // over nodes in the dominator chain, looking for a node whose dominator 133 // set is equal to the current nodes, except that the current node does 134 // not exist in it. This means that it is one level higher in the dom 135 // chain than the current node, and it is our idom! We know that we have 136 // already added a DominatorTree node for our idom, because the idom must 137 // be a predecessor in the depth first order that we are iterating through 138 // the function. 139 // 140 DominatorSet::DomSetType::const_iterator I = Dominators.begin(); 141 DominatorSet::DomSetType::const_iterator End = Dominators.end(); 142 for (; I != End; ++I) { // Iterate over dominators... 143 // All of our dominators should form a chain, where the number 144 // of elements in the dominator set indicates what level the 145 // node is at in the chain. We want the node immediately 146 // above us, so it will have an identical dominator set, 147 // except that BB will not dominate it... therefore it's 148 // dominator set size will be one less than BB's... 149 // 150 if (DS.getDominators(*I).size() == DomSetSize - 1) { 151 // We know that the immediate dominator should already have a node, 152 // because we are traversing the CFG in depth first order! 153 // 154 Node *IDomNode = Nodes[*I]; 155 assert(IDomNode && "No node for IDOM?"); 156 157 // Add a new tree node for this BasicBlock, and link it as a child of 158 // IDomNode 159 Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode)); 160 break; 161 } 162 } 163 } 164} 165 166//===----------------------------------------------------------------------===// 167// PostDominanceFrontier Implementation 168//===----------------------------------------------------------------------===// 169 170static RegisterAnalysis<PostDominanceFrontier> 171H("postdomfrontier", "Post-Dominance Frontier Construction", true); 172 173const DominanceFrontier::DomSetType & 174PostDominanceFrontier::calculate(const PostDominatorTree &DT, 175 const DominatorTree::Node *Node) { 176 // Loop over CFG successors to calculate DFlocal[Node] 177 BasicBlock *BB = Node->getBlock(); 178 DomSetType &S = Frontiers[BB]; // The new set to fill in... 179 if (getRoots().empty()) return S; 180 181 if (BB) 182 for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); 183 SI != SE; ++SI) 184 // Does Node immediately dominate this predeccessor? 185 if (DT[*SI]->getIDom() != Node) 186 S.insert(*SI); 187 188 // At this point, S is DFlocal. Now we union in DFup's of our children... 189 // Loop through and visit the nodes that Node immediately dominates (Node's 190 // children in the IDomTree) 191 // 192 for (PostDominatorTree::Node::const_iterator 193 NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { 194 DominatorTree::Node *IDominee = *NI; 195 const DomSetType &ChildDF = calculate(DT, IDominee); 196 197 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 198 for (; CDFI != CDFE; ++CDFI) { 199 if (!Node->dominates(DT[*CDFI])) 200 S.insert(*CDFI); 201 } 202 } 203 204 return S; 205} 206 207// stub - a dummy function to make linking work ok. 208void PostDominanceFrontier::stub() { 209} 210