LLVM API Documentation
00001 //===- Dominators.cpp - Dominator Calculation -----------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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/Support/Compiler.h" 00020 #include "llvm/ADT/DepthFirstIterator.h" 00021 #include "llvm/ADT/SetOperations.h" 00022 #include "llvm/ADT/SmallPtrSet.h" 00023 #include "llvm/ADT/SmallVector.h" 00024 #include "llvm/Analysis/DominatorInternals.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/Support/Streams.h" 00027 #include <algorithm> 00028 using namespace llvm; 00029 00030 namespace llvm { 00031 static std::ostream &operator<<(std::ostream &o, 00032 const std::set<BasicBlock*> &BBs) { 00033 for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 00034 I != E; ++I) 00035 if (*I) 00036 WriteAsOperand(o, *I, false); 00037 else 00038 o << " <<exit node>>"; 00039 return o; 00040 } 00041 } 00042 00043 //===----------------------------------------------------------------------===// 00044 // DominatorTree Implementation 00045 //===----------------------------------------------------------------------===// 00046 // 00047 // Provide public access to DominatorTree information. Implementation details 00048 // can be found in DominatorCalculation.h. 00049 // 00050 //===----------------------------------------------------------------------===// 00051 00052 TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); 00053 TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); 00054 00055 char DominatorTree::ID = 0; 00056 static RegisterPass<DominatorTree> 00057 E("domtree", "Dominator Tree Construction", true, true); 00058 00059 bool DominatorTree::runOnFunction(Function &F) { 00060 DT->recalculate(F); 00061 return false; 00062 } 00063 00064 //===----------------------------------------------------------------------===// 00065 // DominanceFrontier Implementation 00066 //===----------------------------------------------------------------------===// 00067 00068 char DominanceFrontier::ID = 0; 00069 static RegisterPass<DominanceFrontier> 00070 G("domfrontier", "Dominance Frontier Construction", true, true); 00071 00072 // NewBB is split and now it has one successor. Update dominace frontier to 00073 // reflect this change. 00074 void DominanceFrontier::splitBlock(BasicBlock *NewBB) { 00075 assert(NewBB->getTerminator()->getNumSuccessors() == 1 00076 && "NewBB should have a single successor!"); 00077 BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); 00078 00079 SmallVector<BasicBlock*, 8> PredBlocks; 00080 for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); 00081 PI != PE; ++PI) 00082 PredBlocks.push_back(*PI); 00083 00084 if (PredBlocks.empty()) 00085 // If NewBB does not have any predecessors then it is a entry block. 00086 // In this case, NewBB and its successor NewBBSucc dominates all 00087 // other blocks. 00088 return; 00089 00090 // NewBBSucc inherits original NewBB frontier. 00091 DominanceFrontier::iterator NewBBI = find(NewBB); 00092 if (NewBBI != end()) { 00093 DominanceFrontier::DomSetType NewBBSet = NewBBI->second; 00094 DominanceFrontier::DomSetType NewBBSuccSet; 00095 NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end()); 00096 addBasicBlock(NewBBSucc, NewBBSuccSet); 00097 } 00098 00099 // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 00100 // DF(PredBlocks[0]) without the stuff that the new block does not dominate 00101 // a predecessor of. 00102 DominatorTree &DT = getAnalysis<DominatorTree>(); 00103 if (DT.dominates(NewBB, NewBBSucc)) { 00104 DominanceFrontier::iterator DFI = find(PredBlocks[0]); 00105 if (DFI != end()) { 00106 DominanceFrontier::DomSetType Set = DFI->second; 00107 // Filter out stuff in Set that we do not dominate a predecessor of. 00108 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 00109 E = Set.end(); SetI != E;) { 00110 bool DominatesPred = false; 00111 for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 00112 PI != E; ++PI) 00113 if (DT.dominates(NewBB, *PI)) 00114 DominatesPred = true; 00115 if (!DominatesPred) 00116 Set.erase(SetI++); 00117 else 00118 ++SetI; 00119 } 00120 00121 if (NewBBI != end()) { 00122 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 00123 E = Set.end(); SetI != E; ++SetI) { 00124 BasicBlock *SB = *SetI; 00125 addToFrontier(NewBBI, SB); 00126 } 00127 } else 00128 addBasicBlock(NewBB, Set); 00129 } 00130 00131 } else { 00132 // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 00133 // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 00134 // NewBBSucc)). NewBBSucc is the single successor of NewBB. 00135 DominanceFrontier::DomSetType NewDFSet; 00136 NewDFSet.insert(NewBBSucc); 00137 addBasicBlock(NewBB, NewDFSet); 00138 } 00139 00140 // Now we must loop over all of the dominance frontiers in the function, 00141 // replacing occurrences of NewBBSucc with NewBB in some cases. All 00142 // blocks that dominate a block in PredBlocks and contained NewBBSucc in 00143 // their dominance frontier must be updated to contain NewBB instead. 00144 // 00145 for (Function::iterator FI = NewBB->getParent()->begin(), 00146 FE = NewBB->getParent()->end(); FI != FE; ++FI) { 00147 DominanceFrontier::iterator DFI = find(FI); 00148 if (DFI == end()) continue; // unreachable block. 00149 00150 // Only consider nodes that have NewBBSucc in their dominator frontier. 00151 if (!DFI->second.count(NewBBSucc)) continue; 00152 00153 // Verify whether this block dominates a block in predblocks. If not, do 00154 // not update it. 00155 bool BlockDominatesAny = false; 00156 for (SmallVectorImpl<BasicBlock*>::const_iterator BI = PredBlocks.begin(), 00157 BE = PredBlocks.end(); BI != BE; ++BI) { 00158 if (DT.dominates(FI, *BI)) { 00159 BlockDominatesAny = true; 00160 break; 00161 } 00162 } 00163 00164 // If NewBBSucc should not stay in our dominator frontier, remove it. 00165 // We remove it unless there is a predecessor of NewBBSucc that we 00166 // dominate, but we don't strictly dominate NewBBSucc. 00167 bool ShouldRemove = true; 00168 if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) { 00169 // Okay, we know that PredDom does not strictly dominate NewBBSucc. 00170 // Check to see if it dominates any predecessors of NewBBSucc. 00171 for (pred_iterator PI = pred_begin(NewBBSucc), 00172 E = pred_end(NewBBSucc); PI != E; ++PI) 00173 if (DT.dominates(FI, *PI)) { 00174 ShouldRemove = false; 00175 break; 00176 } 00177 } 00178 00179 if (ShouldRemove) 00180 removeFromFrontier(DFI, NewBBSucc); 00181 if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB))) 00182 addToFrontier(DFI, NewBB); 00183 } 00184 } 00185 00186 namespace { 00187 class DFCalculateWorkObject { 00188 public: 00189 DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 00190 const DomTreeNode *N, 00191 const DomTreeNode *PN) 00192 : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 00193 BasicBlock *currentBB; 00194 BasicBlock *parentBB; 00195 const DomTreeNode *Node; 00196 const DomTreeNode *parentNode; 00197 }; 00198 } 00199 00200 const DominanceFrontier::DomSetType & 00201 DominanceFrontier::calculate(const DominatorTree &DT, 00202 const DomTreeNode *Node) { 00203 BasicBlock *BB = Node->getBlock(); 00204 DomSetType *Result = NULL; 00205 00206 std::vector<DFCalculateWorkObject> workList; 00207 SmallPtrSet<BasicBlock *, 32> visited; 00208 00209 workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 00210 do { 00211 DFCalculateWorkObject *currentW = &workList.back(); 00212 assert (currentW && "Missing work object."); 00213 00214 BasicBlock *currentBB = currentW->currentBB; 00215 BasicBlock *parentBB = currentW->parentBB; 00216 const DomTreeNode *currentNode = currentW->Node; 00217 const DomTreeNode *parentNode = currentW->parentNode; 00218 assert (currentBB && "Invalid work object. Missing current Basic Block"); 00219 assert (currentNode && "Invalid work object. Missing current Node"); 00220 DomSetType &S = Frontiers[currentBB]; 00221 00222 // Visit each block only once. 00223 if (visited.count(currentBB) == 0) { 00224 visited.insert(currentBB); 00225 00226 // Loop over CFG successors to calculate DFlocal[currentNode] 00227 for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 00228 SI != SE; ++SI) { 00229 // Does Node immediately dominate this successor? 00230 if (DT[*SI]->getIDom() != currentNode) 00231 S.insert(*SI); 00232 } 00233 } 00234 00235 // At this point, S is DFlocal. Now we union in DFup's of our children... 00236 // Loop through and visit the nodes that Node immediately dominates (Node's 00237 // children in the IDomTree) 00238 bool visitChild = false; 00239 for (DomTreeNode::const_iterator NI = currentNode->begin(), 00240 NE = currentNode->end(); NI != NE; ++NI) { 00241 DomTreeNode *IDominee = *NI; 00242 BasicBlock *childBB = IDominee->getBlock(); 00243 if (visited.count(childBB) == 0) { 00244 workList.push_back(DFCalculateWorkObject(childBB, currentBB, 00245 IDominee, currentNode)); 00246 visitChild = true; 00247 } 00248 } 00249 00250 // If all children are visited or there is any child then pop this block 00251 // from the workList. 00252 if (!visitChild) { 00253 00254 if (!parentBB) { 00255 Result = &S; 00256 break; 00257 } 00258 00259 DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 00260 DomSetType &parentSet = Frontiers[parentBB]; 00261 for (; CDFI != CDFE; ++CDFI) { 00262 if (!DT.properlyDominates(parentNode, DT[*CDFI])) 00263 parentSet.insert(*CDFI); 00264 } 00265 workList.pop_back(); 00266 } 00267 00268 } while (!workList.empty()); 00269 00270 return *Result; 00271 } 00272 00273 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { 00274 for (const_iterator I = begin(), E = end(); I != E; ++I) { 00275 o << " DomFrontier for BB"; 00276 if (I->first) 00277 WriteAsOperand(o, I->first, false); 00278 else 00279 o << " <<exit node>>"; 00280 o << " is:\t" << I->second << "\n"; 00281 } 00282 } 00283 00284 void DominanceFrontierBase::dump() { 00285 print (llvm::cerr); 00286 } 00287