LLVM API Documentation
00001 //===- Dominators.cpp - 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 simple dominator construction algorithms for finding 00011 // forward dominators. Postdominators are available in libanalysis, but are not 00012 // included in libvmcore, because it's not needed. Forward dominators are 00013 // needed to support the Verifier pass. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/Dominators.h" 00018 #include "llvm/Support/CFG.h" 00019 #include "llvm/Assembly/Writer.h" 00020 #include "llvm/ADT/DepthFirstIterator.h" 00021 #include "llvm/ADT/SetOperations.h" 00022 #include <algorithm> 00023 using namespace llvm; 00024 00025 //===----------------------------------------------------------------------===// 00026 // ImmediateDominators Implementation 00027 //===----------------------------------------------------------------------===// 00028 // 00029 // Immediate Dominators construction - This pass constructs immediate dominator 00030 // information for a flow-graph based on the algorithm described in this 00031 // document: 00032 // 00033 // A Fast Algorithm for Finding Dominators in a Flowgraph 00034 // T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. 00035 // 00036 // This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and 00037 // LINK, but it turns out that the theoretically slower O(n*log(n)) 00038 // implementation is actually faster than the "efficient" algorithm (even for 00039 // large CFGs) because the constant overheads are substantially smaller. The 00040 // lower-complexity version can be enabled with the following #define: 00041 // 00042 #define BALANCE_IDOM_TREE 0 00043 // 00044 //===----------------------------------------------------------------------===// 00045 00046 static RegisterAnalysis<ImmediateDominators> 00047 C("idom", "Immediate Dominators Construction", true); 00048 00049 unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo, 00050 unsigned N) { 00051 VInfo.Semi = ++N; 00052 VInfo.Label = V; 00053 00054 Vertex.push_back(V); // Vertex[n] = V; 00055 //Info[V].Ancestor = 0; // Ancestor[n] = 0 00056 //Child[V] = 0; // Child[v] = 0 00057 VInfo.Size = 1; // Size[v] = 1 00058 00059 for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { 00060 InfoRec &SuccVInfo = Info[*SI]; 00061 if (SuccVInfo.Semi == 0) { 00062 SuccVInfo.Parent = V; 00063 N = DFSPass(*SI, SuccVInfo, N); 00064 } 00065 } 00066 return N; 00067 } 00068 00069 void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) { 00070 BasicBlock *VAncestor = VInfo.Ancestor; 00071 InfoRec &VAInfo = Info[VAncestor]; 00072 if (VAInfo.Ancestor == 0) 00073 return; 00074 00075 Compress(VAncestor, VAInfo); 00076 00077 BasicBlock *VAncestorLabel = VAInfo.Label; 00078 BasicBlock *VLabel = VInfo.Label; 00079 if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) 00080 VInfo.Label = VAncestorLabel; 00081 00082 VInfo.Ancestor = VAInfo.Ancestor; 00083 } 00084 00085 BasicBlock *ImmediateDominators::Eval(BasicBlock *V) { 00086 InfoRec &VInfo = Info[V]; 00087 #if !BALANCE_IDOM_TREE 00088 // Higher-complexity but faster implementation 00089 if (VInfo.Ancestor == 0) 00090 return V; 00091 Compress(V, VInfo); 00092 return VInfo.Label; 00093 #else 00094 // Lower-complexity but slower implementation 00095 if (VInfo.Ancestor == 0) 00096 return VInfo.Label; 00097 Compress(V, VInfo); 00098 BasicBlock *VLabel = VInfo.Label; 00099 00100 BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; 00101 if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) 00102 return VLabel; 00103 else 00104 return VAncestorLabel; 00105 #endif 00106 } 00107 00108 void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ 00109 #if !BALANCE_IDOM_TREE 00110 // Higher-complexity but faster implementation 00111 WInfo.Ancestor = V; 00112 #else 00113 // Lower-complexity but slower implementation 00114 BasicBlock *WLabel = WInfo.Label; 00115 unsigned WLabelSemi = Info[WLabel].Semi; 00116 BasicBlock *S = W; 00117 InfoRec *SInfo = &Info[S]; 00118 00119 BasicBlock *SChild = SInfo->Child; 00120 InfoRec *SChildInfo = &Info[SChild]; 00121 00122 while (WLabelSemi < Info[SChildInfo->Label].Semi) { 00123 BasicBlock *SChildChild = SChildInfo->Child; 00124 if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { 00125 SChildInfo->Ancestor = S; 00126 SInfo->Child = SChild = SChildChild; 00127 SChildInfo = &Info[SChild]; 00128 } else { 00129 SChildInfo->Size = SInfo->Size; 00130 S = SInfo->Ancestor = SChild; 00131 SInfo = SChildInfo; 00132 SChild = SChildChild; 00133 SChildInfo = &Info[SChild]; 00134 } 00135 } 00136 00137 InfoRec &VInfo = Info[V]; 00138 SInfo->Label = WLabel; 00139 00140 assert(V != W && "The optimization here will not work in this case!"); 00141 unsigned WSize = WInfo.Size; 00142 unsigned VSize = (VInfo.Size += WSize); 00143 00144 if (VSize < 2*WSize) 00145 std::swap(S, VInfo.Child); 00146 00147 while (S) { 00148 SInfo = &Info[S]; 00149 SInfo->Ancestor = V; 00150 S = SInfo->Child; 00151 } 00152 #endif 00153 } 00154 00155 00156 00157 bool ImmediateDominators::runOnFunction(Function &F) { 00158 IDoms.clear(); // Reset from the last time we were run... 00159 BasicBlock *Root = &F.getEntryBlock(); 00160 Roots.clear(); 00161 Roots.push_back(Root); 00162 00163 Vertex.push_back(0); 00164 00165 // Step #1: Number blocks in depth-first order and initialize variables used 00166 // in later stages of the algorithm. 00167 unsigned N = 0; 00168 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00169 N = DFSPass(Roots[i], Info[Roots[i]], 0); 00170 00171 for (unsigned i = N; i >= 2; --i) { 00172 BasicBlock *W = Vertex[i]; 00173 InfoRec &WInfo = Info[W]; 00174 00175 // Step #2: Calculate the semidominators of all vertices 00176 for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) 00177 if (Info.count(*PI)) { // Only if this predecessor is reachable! 00178 unsigned SemiU = Info[Eval(*PI)].Semi; 00179 if (SemiU < WInfo.Semi) 00180 WInfo.Semi = SemiU; 00181 } 00182 00183 Info[Vertex[WInfo.Semi]].Bucket.push_back(W); 00184 00185 BasicBlock *WParent = WInfo.Parent; 00186 Link(WParent, W, WInfo); 00187 00188 // Step #3: Implicitly define the immediate dominator of vertices 00189 std::vector<BasicBlock*> &WParentBucket = Info[WParent].Bucket; 00190 while (!WParentBucket.empty()) { 00191 BasicBlock *V = WParentBucket.back(); 00192 WParentBucket.pop_back(); 00193 BasicBlock *U = Eval(V); 00194 IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; 00195 } 00196 } 00197 00198 // Step #4: Explicitly define the immediate dominator of each vertex 00199 for (unsigned i = 2; i <= N; ++i) { 00200 BasicBlock *W = Vertex[i]; 00201 BasicBlock *&WIDom = IDoms[W]; 00202 if (WIDom != Vertex[Info[W].Semi]) 00203 WIDom = IDoms[WIDom]; 00204 } 00205 00206 // Free temporary memory used to construct idom's 00207 Info.clear(); 00208 std::vector<BasicBlock*>().swap(Vertex); 00209 00210 return false; 00211 } 00212 00213 void ImmediateDominatorsBase::print(std::ostream &o) const { 00214 Function *F = getRoots()[0]->getParent(); 00215 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 00216 o << " Immediate Dominator For Basic Block:"; 00217 WriteAsOperand(o, I, false); 00218 o << " is:"; 00219 if (BasicBlock *ID = get(I)) 00220 WriteAsOperand(o, ID, false); 00221 else 00222 o << " <<exit node>>"; 00223 o << "\n"; 00224 } 00225 o << "\n"; 00226 } 00227 00228 00229 00230 //===----------------------------------------------------------------------===// 00231 // DominatorSet Implementation 00232 //===----------------------------------------------------------------------===// 00233 00234 static RegisterAnalysis<DominatorSet> 00235 B("domset", "Dominator Set Construction", true); 00236 00237 // dominates - Return true if A dominates B. This performs the special checks 00238 // necessary if A and B are in the same basic block. 00239 // 00240 bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const { 00241 BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 00242 if (BBA != BBB) return dominates(BBA, BBB); 00243 00244 // Loop through the basic block until we find A or B. 00245 BasicBlock::iterator I = BBA->begin(); 00246 for (; &*I != A && &*I != B; ++I) /*empty*/; 00247 00248 // A dominates B if it is found first in the basic block... 00249 return &*I == A; 00250 } 00251 00252 00253 // runOnFunction - This method calculates the forward dominator sets for the 00254 // specified function. 00255 // 00256 bool DominatorSet::runOnFunction(Function &F) { 00257 BasicBlock *Root = &F.getEntryBlock(); 00258 Roots.clear(); 00259 Roots.push_back(Root); 00260 assert(pred_begin(Root) == pred_end(Root) && 00261 "Root node has predecessors in function!"); 00262 00263 ImmediateDominators &ID = getAnalysis<ImmediateDominators>(); 00264 Doms.clear(); 00265 if (Roots.empty()) return false; 00266 00267 // Root nodes only dominate themselves. 00268 for (unsigned i = 0, e = Roots.size(); i != e; ++i) 00269 Doms[Roots[i]].insert(Roots[i]); 00270 00271 // Loop over all of the blocks in the function, calculating dominator sets for 00272 // each function. 00273 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00274 if (BasicBlock *IDom = ID[I]) { // Get idom if block is reachable 00275 DomSetType &DS = Doms[I]; 00276 assert(DS.empty() && "Domset already filled in for this block?"); 00277 DS.insert(I); // Blocks always dominate themselves 00278 00279 // Insert all dominators into the set... 00280 while (IDom) { 00281 // If we have already computed the dominator sets for our immediate 00282 // dominator, just use it instead of walking all the way up to the root. 00283 DomSetType &IDS = Doms[IDom]; 00284 if (!IDS.empty()) { 00285 DS.insert(IDS.begin(), IDS.end()); 00286 break; 00287 } else { 00288 DS.insert(IDom); 00289 IDom = ID[IDom]; 00290 } 00291 } 00292 } else { 00293 // Ensure that every basic block has at least an empty set of nodes. This 00294 // is important for the case when there is unreachable blocks. 00295 Doms[I]; 00296 } 00297 00298 return false; 00299 } 00300 00301 void DominatorSet::stub() {} 00302 00303 namespace llvm { 00304 static std::ostream &operator<<(std::ostream &o, 00305 const std::set<BasicBlock*> &BBs) { 00306 for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 00307 I != E; ++I) 00308 if (*I) 00309 WriteAsOperand(o, *I, false); 00310 else 00311 o << " <<exit node>>"; 00312 return o; 00313 } 00314 } 00315 00316 void DominatorSetBase::print(std::ostream &o) const { 00317 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00318 o << " DomSet For BB: "; 00319 if (I->first) 00320 WriteAsOperand(o, I->first, false); 00321 else 00322 o << " <<exit node>>"; 00323 o << " is:\t" << I->second << "\n"; 00324 } 00325 } 00326 00327 //===----------------------------------------------------------------------===// 00328 // DominatorTree Implementation 00329 //===----------------------------------------------------------------------===// 00330 00331 static RegisterAnalysis<DominatorTree> 00332 E("domtree", "Dominator Tree Construction", true); 00333 00334 // DominatorTreeBase::reset - Free all of the tree node memory. 00335 // 00336 void DominatorTreeBase::reset() { 00337 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) 00338 delete I->second; 00339 Nodes.clear(); 00340 RootNode = 0; 00341 } 00342 00343 void DominatorTreeBase::Node::setIDom(Node *NewIDom) { 00344 assert(IDom && "No immediate dominator?"); 00345 if (IDom != NewIDom) { 00346 std::vector<Node*>::iterator I = 00347 std::find(IDom->Children.begin(), IDom->Children.end(), this); 00348 assert(I != IDom->Children.end() && 00349 "Not in immediate dominator children set!"); 00350 // I am no longer your child... 00351 IDom->Children.erase(I); 00352 00353 // Switch to new dominator 00354 IDom = NewIDom; 00355 IDom->Children.push_back(this); 00356 } 00357 } 00358 00359 DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) { 00360 Node *&BBNode = Nodes[BB]; 00361 if (BBNode) return BBNode; 00362 00363 // Haven't calculated this node yet? Get or calculate the node for the 00364 // immediate dominator. 00365 BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB]; 00366 Node *IDomNode = getNodeForBlock(IDom); 00367 00368 // Add a new tree node for this BasicBlock, and link it as a child of 00369 // IDomNode 00370 return BBNode = IDomNode->addChild(new Node(BB, IDomNode)); 00371 } 00372 00373 void DominatorTree::calculate(const ImmediateDominators &ID) { 00374 assert(Roots.size() == 1 && "DominatorTree should have 1 root block!"); 00375 BasicBlock *Root = Roots[0]; 00376 Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root... 00377 00378 Function *F = Root->getParent(); 00379 // Loop over all of the reachable blocks in the function... 00380 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00381 if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block. 00382 Node *&BBNode = Nodes[I]; 00383 if (!BBNode) { // Haven't calculated this node yet? 00384 // Get or calculate the node for the immediate dominator 00385 Node *IDomNode = getNodeForBlock(ImmDom); 00386 00387 // Add a new tree node for this BasicBlock, and link it as a child of 00388 // IDomNode 00389 BBNode = IDomNode->addChild(new Node(I, IDomNode)); 00390 } 00391 } 00392 } 00393 00394 static std::ostream &operator<<(std::ostream &o, 00395 const DominatorTreeBase::Node *Node) { 00396 if (Node->getBlock()) 00397 WriteAsOperand(o, Node->getBlock(), false); 00398 else 00399 o << " <<exit node>>"; 00400 return o << "\n"; 00401 } 00402 00403 static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o, 00404 unsigned Lev) { 00405 o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; 00406 for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end(); 00407 I != E; ++I) 00408 PrintDomTree(*I, o, Lev+1); 00409 } 00410 00411 void DominatorTreeBase::print(std::ostream &o) const { 00412 o << "=============================--------------------------------\n" 00413 << "Inorder Dominator Tree:\n"; 00414 PrintDomTree(getRootNode(), o, 1); 00415 } 00416 00417 00418 //===----------------------------------------------------------------------===// 00419 // DominanceFrontier Implementation 00420 //===----------------------------------------------------------------------===// 00421 00422 static RegisterAnalysis<DominanceFrontier> 00423 G("domfrontier", "Dominance Frontier Construction", true); 00424 00425 const DominanceFrontier::DomSetType & 00426 DominanceFrontier::calculate(const DominatorTree &DT, 00427 const DominatorTree::Node *Node) { 00428 // Loop over CFG successors to calculate DFlocal[Node] 00429 BasicBlock *BB = Node->getBlock(); 00430 DomSetType &S = Frontiers[BB]; // The new set to fill in... 00431 00432 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 00433 SI != SE; ++SI) { 00434 // Does Node immediately dominate this successor? 00435 if (DT[*SI]->getIDom() != Node) 00436 S.insert(*SI); 00437 } 00438 00439 // At this point, S is DFlocal. Now we union in DFup's of our children... 00440 // Loop through and visit the nodes that Node immediately dominates (Node's 00441 // children in the IDomTree) 00442 // 00443 for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end(); 00444 NI != NE; ++NI) { 00445 DominatorTree::Node *IDominee = *NI; 00446 const DomSetType &ChildDF = calculate(DT, IDominee); 00447 00448 DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end(); 00449 for (; CDFI != CDFE; ++CDFI) { 00450 if (!Node->dominates(DT[*CDFI])) 00451 S.insert(*CDFI); 00452 } 00453 } 00454 00455 return S; 00456 } 00457 00458 void DominanceFrontierBase::print(std::ostream &o) const { 00459 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00460 o << " DomFrontier for BB"; 00461 if (I->first) 00462 WriteAsOperand(o, I->first, false); 00463 else 00464 o << " <<exit node>>"; 00465 o << " is:\t" << I->second << "\n"; 00466 } 00467 } 00468