LLVM API Documentation
00001 //===- PostDominators.cpp - Post-Dominator Calculation --------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the post-dominator construction algorithms. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Analysis/PostDominators.h" 00015 #include "llvm/Instructions.h" 00016 #include "llvm/Support/CFG.h" 00017 #include "llvm/ADT/DepthFirstIterator.h" 00018 #include "llvm/ADT/SetOperations.h" 00019 #include <iostream> 00020 using namespace llvm; 00021 00022 //===----------------------------------------------------------------------===// 00023 // ImmediatePostDominators Implementation 00024 //===----------------------------------------------------------------------===// 00025 00026 static RegisterAnalysis<ImmediatePostDominators> 00027 D("postidom", "Immediate Post-Dominators Construction", true); 00028 00029 unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, 00030 unsigned N) { 00031 VInfo.Semi = ++N; 00032 VInfo.Label = V; 00033 00034 Vertex.push_back(V); // Vertex[n] = V; 00035 //Info[V].Ancestor = 0; // Ancestor[n] = 0 00036 //Child[V] = 0; // Child[v] = 0 00037 VInfo.Size = 1; // Size[v] = 1 00038 00039 // For PostDominators, we want to walk predecessors rather than successors 00040 // as we do in forward Dominators. 00041 for (pred_iterator PI = pred_begin(V), PE = pred_end(V); PI != PE; ++PI) { 00042 InfoRec &SuccVInfo = Info[*PI]; 00043 if (SuccVInfo.Semi == 0) { 00044 SuccVInfo.Parent = V; 00045 N = DFSPass(*PI, SuccVInfo, N); 00046 } 00047 } 00048 return N; 00049 } 00050 00051 void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) { 00052 BasicBlock *VAncestor = VInfo.Ancestor; 00053 InfoRec &VAInfo = Info[VAncestor]; 00054 if (VAInfo.Ancestor == 0) 00055 return; 00056 00057 Compress(VAncestor, VAInfo); 00058 00059 BasicBlock *VAncestorLabel = VAInfo.Label; 00060 BasicBlock *VLabel = VInfo.Label; 00061 if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) 00062 VInfo.Label = VAncestorLabel; 00063 00064 VInfo.Ancestor = VAInfo.Ancestor; 00065 } 00066 00067 BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) { 00068 InfoRec &VInfo = Info[V]; 00069 00070 // Higher-complexity but faster implementation 00071 if (VInfo.Ancestor == 0) 00072 return V; 00073 Compress(V, VInfo); 00074 return VInfo.Label; 00075 } 00076 00077 void ImmediatePostDominators::Link(BasicBlock *V, BasicBlock *W, 00078 InfoRec &WInfo) { 00079 // Higher-complexity but faster implementation 00080 WInfo.Ancestor = V; 00081 } 00082 00083 bool ImmediatePostDominators::runOnFunction(Function &F) { 00084 IDoms.clear(); // Reset from the last time we were run... 00085 Roots.clear(); 00086 00087 // Step #0: Scan the function looking for the root nodes of the post-dominance 00088 // relationships. These blocks, which have no successors, end with return and 00089 // unwind instructions. 00090 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00091 if (succ_begin(I) == succ_end(I)) 00092 Roots.push_back(I); 00093 00094 Vertex.push_back(0); 00095 00096 // Step #1: Number blocks in depth-first order and initialize variables used 00097 // in later stages of the algorithm. 00098 unsigned N = 0; 00099 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00100 N = DFSPass(Roots[i], Info[Roots[i]], N); 00101 00102 for (unsigned i = N; i >= 2; --i) { 00103 BasicBlock *W = Vertex[i]; 00104 InfoRec &WInfo = Info[W]; 00105 00106 // Step #2: Calculate the semidominators of all vertices 00107 for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI) 00108 if (Info.count(*SI)) { // Only if this predecessor is reachable! 00109 unsigned SemiU = Info[Eval(*SI)].Semi; 00110 if (SemiU < WInfo.Semi) 00111 WInfo.Semi = SemiU; 00112 } 00113 00114 Info[Vertex[WInfo.Semi]].Bucket.push_back(W); 00115 00116 BasicBlock *WParent = WInfo.Parent; 00117 Link(WParent, W, WInfo); 00118 00119 // Step #3: Implicitly define the immediate dominator of vertices 00120 std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket; 00121 while (!WParentBucket.empty()) { 00122 BasicBlock *V = WParentBucket.back(); 00123 WParentBucket.pop_back(); 00124 BasicBlock *U = Eval(V); 00125 IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; 00126 } 00127 } 00128 00129 // Step #4: Explicitly define the immediate dominator of each vertex 00130 for (unsigned i = 2; i <= N; ++i) { 00131 BasicBlock *W = Vertex[i]; 00132 BasicBlock *&WIDom = IDoms[W]; 00133 if (WIDom != Vertex[Info[W].Semi]) 00134 WIDom = IDoms[WIDom]; 00135 } 00136 00137 // Free temporary memory used to construct idom's 00138 Info.clear(); 00139 std::vector<BasicBlock*>().swap(Vertex); 00140 00141 return false; 00142 } 00143 00144 //===----------------------------------------------------------------------===// 00145 // PostDominatorSet Implementation 00146 //===----------------------------------------------------------------------===// 00147 00148 static RegisterAnalysis<PostDominatorSet> 00149 B("postdomset", "Post-Dominator Set Construction", true); 00150 00151 // Postdominator set construction. This converts the specified function to only 00152 // have a single exit node (return stmt), then calculates the post dominance 00153 // sets for the function. 00154 // 00155 bool PostDominatorSet::runOnFunction(Function &F) { 00156 // Scan the function looking for the root nodes of the post-dominance 00157 // relationships. These blocks end with return and unwind instructions. 00158 // While we are iterating over the function, we also initialize all of the 00159 // domsets to empty. 00160 Roots.clear(); 00161 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00162 if (succ_begin(I) == succ_end(I)) 00163 Roots.push_back(I); 00164 00165 // If there are no exit nodes for the function, postdomsets are all empty. 00166 // This can happen if the function just contains an infinite loop, for 00167 // example. 00168 ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>(); 00169 Doms.clear(); // Reset from the last time we were run... 00170 if (Roots.empty()) return false; 00171 00172 // If we have more than one root, we insert an artificial "null" exit, which 00173 // has "virtual edges" to each of the real exit nodes. 00174 //if (Roots.size() > 1) 00175 // Doms[0].insert(0); 00176 00177 // Root nodes only dominate themselves. 00178 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00179 Doms[Roots[i]].insert(Roots[i]); 00180 00181 // Loop over all of the blocks in the function, calculating dominator sets for 00182 // each function. 00183 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00184 if (BasicBlock *IPDom = IPD[I]) { // Get idom if block is reachable 00185 DomSetType &DS = Doms[I]; 00186 assert(DS.empty() && "PostDomset already filled in for this block?"); 00187 DS.insert(I); // Blocks always dominate themselves 00188 00189 // Insert all dominators into the set... 00190 while (IPDom) { 00191 // If we have already computed the dominator sets for our immediate post 00192 // dominator, just use it instead of walking all the way up to the root. 00193 DomSetType &IPDS = Doms[IPDom]; 00194 if (!IPDS.empty()) { 00195 DS.insert(IPDS.begin(), IPDS.end()); 00196 break; 00197 } else { 00198 DS.insert(IPDom); 00199 IPDom = IPD[IPDom]; 00200 } 00201 } 00202 } else { 00203 // Ensure that every basic block has at least an empty set of nodes. This 00204 // is important for the case when there is unreachable blocks. 00205 Doms[I]; 00206 } 00207 00208 return false; 00209 } 00210 00211 //===----------------------------------------------------------------------===// 00212 // PostDominatorTree Implementation 00213 //===----------------------------------------------------------------------===// 00214 00215 static RegisterAnalysis<PostDominatorTree> 00216 F("postdomtree", "Post-Dominator Tree Construction", true); 00217 00218 DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) { 00219 Node *&BBNode = Nodes[BB]; 00220 if (BBNode) return BBNode; 00221 00222 // Haven't calculated this node yet? Get or calculate the node for the 00223 // immediate postdominator. 00224 BasicBlock *IPDom = getAnalysis<ImmediatePostDominators>()[BB]; 00225 Node *IPDomNode = getNodeForBlock(IPDom); 00226 00227 // Add a new tree node for this BasicBlock, and link it as a child of 00228 // IDomNode 00229 return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode)); 00230 } 00231 00232 void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) { 00233 if (Roots.empty()) return; 00234 00235 // Add a node for the root. This node might be the actual root, if there is 00236 // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) 00237 // which postdominates all real exits if there are multiple exit blocks. 00238 BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0; 00239 Nodes[Root] = RootNode = new Node(Root, 0); 00240 00241 Function *F = Roots[0]->getParent(); 00242 // Loop over all of the reachable blocks in the function... 00243 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00244 if (BasicBlock *ImmPostDom = IPD.get(I)) { // Reachable block. 00245 Node *&BBNode = Nodes[I]; 00246 if (!BBNode) { // Haven't calculated this node yet? 00247 // Get or calculate the node for the immediate dominator 00248 Node *IPDomNode = getNodeForBlock(ImmPostDom); 00249 00250 // Add a new tree node for this BasicBlock, and link it as a child of 00251 // IDomNode 00252 BBNode = IPDomNode->addChild(new Node(I, IPDomNode)); 00253 } 00254 } 00255 } 00256 00257 //===----------------------------------------------------------------------===// 00258 // PostETForest Implementation 00259 //===----------------------------------------------------------------------===// 00260 00261 static RegisterAnalysis<PostETForest> 00262 G("postetforest", "Post-ET-Forest Construction", true); 00263 00264 ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) { 00265 ETNode *&BBNode = Nodes[BB]; 00266 if (BBNode) return BBNode; 00267 00268 // Haven't calculated this node yet? Get or calculate the node for the 00269 // immediate dominator. 00270 BasicBlock *IDom = getAnalysis<ImmediatePostDominators>()[BB]; 00271 00272 // If we are unreachable, we may not have an immediate dominator. 00273 if (!IDom) 00274 return BBNode = new ETNode(BB); 00275 else { 00276 ETNode *IDomNode = getNodeForBlock(IDom); 00277 00278 // Add a new tree node for this BasicBlock, and link it as a child of 00279 // IDomNode 00280 BBNode = new ETNode(BB); 00281 BBNode->setFather(IDomNode); 00282 return BBNode; 00283 } 00284 } 00285 00286 void PostETForest::calculate(const ImmediatePostDominators &ID) { 00287 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00288 Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root 00289 00290 // Iterate over all nodes in inverse depth first order. 00291 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00292 for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]), 00293 E = idf_end(Roots[i]); I != E; ++I) { 00294 BasicBlock *BB = *I; 00295 ETNode *&BBNode = Nodes[BB]; 00296 if (!BBNode) { 00297 ETNode *IDomNode = NULL; 00298 00299 if (ID.get(BB)) 00300 IDomNode = getNodeForBlock(ID.get(BB)); 00301 00302 // Add a new ETNode for this BasicBlock, and set it's parent 00303 // to it's immediate dominator. 00304 BBNode = new ETNode(BB); 00305 if (IDomNode) 00306 BBNode->setFather(IDomNode); 00307 } 00308 } 00309 00310 int dfsnum = 0; 00311 // Iterate over all nodes in depth first order... 00312 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00313 for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]), 00314 E = idf_end(Roots[i]); I != E; ++I) { 00315 if (!getNodeForBlock(*I)->hasFather()) 00316 getNodeForBlock(*I)->assignDFSNumber(dfsnum); 00317 } 00318 DFSInfoValid = true; 00319 } 00320 00321 //===----------------------------------------------------------------------===// 00322 // PostDominanceFrontier Implementation 00323 //===----------------------------------------------------------------------===// 00324 00325 static RegisterAnalysis<PostDominanceFrontier> 00326 H("postdomfrontier", "Post-Dominance Frontier Construction", true); 00327 00328 const DominanceFrontier::DomSetType & 00329 PostDominanceFrontier::calculate(const PostDominatorTree &DT, 00330 const DominatorTree::Node *Node) { 00331 // Loop over CFG successors to calculate DFlocal[Node] 00332 BasicBlock *BB = Node->getBlock(); 00333 DomSetType &S = Frontiers[BB]; // The new set to fill in... 00334 if (getRoots().empty()) return S; 00335 00336 if (BB) 00337 for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB); 00338 SI != SE; ++SI) 00339 // Does Node immediately dominate this predecessor? 00340 if (DT[*SI]->getIDom() != Node) 00341 S.insert(*SI); 00342 00343 // At this point, S is DFlocal. Now we union in DFup's of our children... 00344 // Loop through and visit the nodes that Node immediately dominates (Node's 00345 // children in the IDomTree) 00346 // 00347 for (PostDominatorTree::Node::const_iterator 00348 NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) { 00349 DominatorTree::Node *IDominee = *NI; 00350 const DomSetType &ChildDF = calculate(DT, IDominee); 00351 00352 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 00353 for (; CDFI != CDFE; ++CDFI) { 00354 if (!Node->properlyDominates(DT[*CDFI])) 00355 S.insert(*CDFI); 00356 } 00357 } 00358 00359 return S; 00360 } 00361 00362 // Ensure that this .cpp file gets linked when PostDominators.h is used. 00363 DEFINING_FILE_FOR(PostDominanceFrontier)