Dominators.cpp revision dc4a745ffe4732c24cd854305f119f142b7daf71
14c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner//===- Dominators.cpp - Dominator Calculation -----------------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 91715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 104c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// This file implements simple dominator construction algorithms for finding 114c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// forward dominators. Postdominators are available in libanalysis, but are not 124c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// included in libvmcore, because it's not needed. Forward dominators are 134c9df7c619ba827729490757dae6dc35bb068a9fChris Lattner// needed to support the Verifier pass. 141715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// 151715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 161715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 171715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner#include "llvm/Analysis/Dominators.h" 18221d688a5ef21a22c2368c9fff0e92d7966c95e5Chris Lattner#include "llvm/Support/CFG.h" 1949b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson#include "llvm/Support/Compiler.h" 20551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DepthFirstIterator.h" 21551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SetOperations.h" 222ad28e6c486f91d83b2d5bcd30612049a686ad64Devang Patel#include "llvm/ADT/SmallPtrSet.h" 233e089ae0b8aa6d9daf0b8ca8f6059422c45936f0Chris Lattner#include "llvm/ADT/SmallVector.h" 249cb7f49ee9d8c77f5ae82e36befde2b3094fdd02Owen Anderson#include "llvm/Analysis/DominatorInternals.h" 25b9dbc4deccefc062a29bce49dc60bf9d5627e603Devang Patel#include "llvm/Instructions.h" 26791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner#include "llvm/Support/raw_ostream.h" 279450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#include "llvm/Support/CommandLine.h" 288e72749fc0b44ac8b7a5ffbb275f2ad60f2fa41eChris Lattner#include <algorithm> 2931f8499e83dc4dccbb57ea7e76d1fd49b7010d0cChris Lattnerusing namespace llvm; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 319450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman// Always verify dominfo if expensive checking is enabled. 329450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#ifdef XDEBUG 339450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohmanbool VerifyDomInfo = true; 349450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#else 359450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohmanbool VerifyDomInfo = false; 369450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman#endif 379450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohmanstatic cl::opt<bool,true> 389450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan GohmanVerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), 399450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman cl::desc("Verify dominator info (time consuming)")); 409450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 4194108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner//===----------------------------------------------------------------------===// 423dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson// DominatorTree Implementation 4316addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 4416addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 45d20c824b201b1408d7ea7a4e2d601aee14db5cecOwen Anderson// Provide public access to DominatorTree information. Implementation details 46d20c824b201b1408d7ea7a4e2d601aee14db5cecOwen Anderson// can be found in DominatorCalculation.h. 4716addf87bf331645de63575aa15627c74b9cab66Chris Lattner// 4816addf87bf331645de63575aa15627c74b9cab66Chris Lattner//===----------------------------------------------------------------------===// 4916addf87bf331645de63575aa15627c74b9cab66Chris Lattner 5049b653aa6aaaed17be1c611c5722b5b9ff31a905Owen AndersonTEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); 5149b653aa6aaaed17be1c611c5722b5b9ff31a905Owen AndersonTEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); 5249b653aa6aaaed17be1c611c5722b5b9ff31a905Owen Anderson 531997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar DominatorTree::ID = 0; 543dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonstatic RegisterPass<DominatorTree> 559f83512ce80279aa5ff243d4285283438360d015Devang PatelE("domtree", "Dominator Tree Construction", true, true); 5616addf87bf331645de63575aa15627c74b9cab66Chris Lattner 573dc6776b338f81e2d47daa42cc12c9f91053043dOwen Andersonbool DominatorTree::runOnFunction(Function &F) { 58d20cc14dbf6d54d896e67b9920cd9bccdc14c41aOwen Anderson DT->recalculate(F); 593dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson return false; 603dc6776b338f81e2d47daa42cc12c9f91053043dOwen Anderson} 611715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 629450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohmanvoid DominatorTree::verifyAnalysis() const { 63a9245d63f64dc8af8ddd877b94523fcc52c1d702Dan Gohman if (!VerifyDomInfo) return; 649450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 659450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman Function &F = *getRoot()->getParent(); 669450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 679450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman DominatorTree OtherDT; 689450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman OtherDT.getBase().recalculate(F); 699450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman assert(!compare(OtherDT) && "Invalid DominatorTree info!"); 709450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman} 719450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 7245cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid DominatorTree::print(raw_ostream &OS, const Module *) const { 7345cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner DT->print(OS); 74791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner} 75791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner 76850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3aChris Lattner// dominates - Return true if A dominates a use in B. This performs the 7775c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner// special checks necessary if A and B are in the same basic block. 7875c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattnerbool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{ 7975c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner const BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 80850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3aChris Lattner 81850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3aChris Lattner // If A is an invoke instruction, its value is only available in this normal 82850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3aChris Lattner // successor block. 83850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3aChris Lattner if (const InvokeInst *II = dyn_cast<InvokeInst>(A)) 84850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3aChris Lattner BBA = II->getNormalDest(); 85850c9178dc5bc8a49fc41c7cf606bfdd7cd1de3aChris Lattner 8675c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner if (BBA != BBB) return dominates(BBA, BBB); 8775c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner 8875c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner // It is not possible to determine dominance between two PHI nodes 8975c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner // based on their ordering. 9075c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner if (isa<PHINode>(A) && isa<PHINode>(B)) 9175c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner return false; 9275c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner 9375c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner // Loop through the basic block until we find A or B. 9475c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner BasicBlock::const_iterator I = BBA->begin(); 9575c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner for (; &*I != A && &*I != B; ++I) 9675c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner /*empty*/; 9775c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner 9875c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner return &*I == A; 9975c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner} 10075c7c995b7ed5a5b7527a80d2bbc2b60720b1312Chris Lattner 101791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner 102791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner 1031715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 1041715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner// DominanceFrontier Implementation 1051715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner//===----------------------------------------------------------------------===// 1061715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 1071997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar DominanceFrontier::ID = 0; 1085d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattnerstatic RegisterPass<DominanceFrontier> 1092527e884169eee65f790a16b81daca2d5652eb6dDevang PatelG("domfrontier", "Dominance Frontier Construction", true, true); 11093193f806378e06092820c099e437886c7309b94Chris Lattner 1119450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohmanvoid DominanceFrontier::verifyAnalysis() const { 1129450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman if (!VerifyDomInfo) return; 1139450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 1149450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman DominatorTree &DT = getAnalysis<DominatorTree>(); 1159450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 1169450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman DominanceFrontier OtherDF; 1179450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman const std::vector<BasicBlock*> &DTRoots = DT.getRoots(); 1189450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman OtherDF.calculate(DT, DT.getNode(DTRoots[0])); 1199450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman assert(!compare(OtherDF) && "Invalid DominanceFrontier info!"); 1209450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman} 1219450b0e1a6154192ca597ad27f8eb6e6e807f7a4Dan Gohman 1220e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel// NewBB is split and now it has one successor. Update dominace frontier to 1230e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel// reflect this change. 1240e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patelvoid DominanceFrontier::splitBlock(BasicBlock *NewBB) { 1250e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel assert(NewBB->getTerminator()->getNumSuccessors() == 1 1260e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel && "NewBB should have a single successor!"); 1270e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); 1280e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 12920e8d5a8cc36c9e39cae1dd99527a4ac0a9d770fChris Lattner SmallVector<BasicBlock*, 8> PredBlocks; 1300e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); 1310e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PI != PE; ++PI) 1320e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PredBlocks.push_back(*PI); 1330e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 134c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel if (PredBlocks.empty()) 135c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel // If NewBB does not have any predecessors then it is a entry block. 136c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel // In this case, NewBB and its successor NewBBSucc dominates all 137c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel // other blocks. 138c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel return; 1390e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 1407ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // NewBBSucc inherits original NewBB frontier. 1411ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel DominanceFrontier::iterator NewBBI = find(NewBB); 1421ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel if (NewBBI != end()) { 1431ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel DominanceFrontier::DomSetType NewBBSet = NewBBI->second; 1441ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel DominanceFrontier::DomSetType NewBBSuccSet; 1451ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end()); 1461ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel addBasicBlock(NewBBSucc, NewBBSuccSet); 1471ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel } 1481ff61385c8feb655a1e70cc67999680cc93f0f67Devang Patel 1490e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 1500e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // DF(PredBlocks[0]) without the stuff that the new block does not dominate 1510e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // a predecessor of. 1527ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 1537ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (DT.dominates(NewBB, NewBBSucc)) { 1540e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::iterator DFI = find(PredBlocks[0]); 1550e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DFI != end()) { 1560e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::DomSetType Set = DFI->second; 1570e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Filter out stuff in Set that we do not dominate a predecessor of. 1580e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 1590e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel E = Set.end(); SetI != E;) { 1600e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel bool DominatesPred = false; 1610e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 1620e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel PI != E; ++PI) 1630e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DT.dominates(NewBB, *PI)) 1640e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominatesPred = true; 1650e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (!DominatesPred) 1660e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel Set.erase(SetI++); 1670e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel else 1680e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel ++SetI; 1690e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 170c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel 171c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel if (NewBBI != end()) { 1725c4cd0d82e22a50e95a1acffa3364e4f7658ab32Devang Patel for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 1735c4cd0d82e22a50e95a1acffa3364e4f7658ab32Devang Patel E = Set.end(); SetI != E; ++SetI) { 1745c4cd0d82e22a50e95a1acffa3364e4f7658ab32Devang Patel BasicBlock *SB = *SetI; 1755c4cd0d82e22a50e95a1acffa3364e4f7658ab32Devang Patel addToFrontier(NewBBI, SB); 1765c4cd0d82e22a50e95a1acffa3364e4f7658ab32Devang Patel } 177c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel } else 178c61ce1ad091ad1faaca8d73447f53d43020ddffaDevang Patel addBasicBlock(NewBB, Set); 1790e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1800e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 1810e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } else { 1820e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 1830e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 1840e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // NewBBSucc)). NewBBSucc is the single successor of NewBB. 1850e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::DomSetType NewDFSet; 1860e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel NewDFSet.insert(NewBBSucc); 1870e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel addBasicBlock(NewBB, NewDFSet); 1880e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 1890e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 1900e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // Now we must loop over all of the dominance frontiers in the function, 1910e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // replacing occurrences of NewBBSucc with NewBB in some cases. All 1920e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // blocks that dominate a block in PredBlocks and contained NewBBSucc in 1930e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // their dominance frontier must be updated to contain NewBB instead. 1940e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel // 1950e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel for (Function::iterator FI = NewBB->getParent()->begin(), 1960e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel FE = NewBB->getParent()->end(); FI != FE; ++FI) { 1970e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DominanceFrontier::iterator DFI = find(FI); 1980e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DFI == end()) continue; // unreachable block. 1990e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 2007ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Only consider nodes that have NewBBSucc in their dominator frontier. 2010e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (!DFI->second.count(NewBBSucc)) continue; 2020e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 2037ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Verify whether this block dominates a block in predblocks. If not, do 2047ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // not update it. 2050e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel bool BlockDominatesAny = false; 20620e8d5a8cc36c9e39cae1dd99527a4ac0a9d770fChris Lattner for (SmallVectorImpl<BasicBlock*>::const_iterator BI = PredBlocks.begin(), 2070e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BE = PredBlocks.end(); BI != BE; ++BI) { 2080e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DT.dominates(FI, *BI)) { 2090e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel BlockDominatesAny = true; 2100e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel break; 2110e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 2120e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 2130f4012ca9d0e7a6dba7862201d8267681c0e43b0Eli Friedman 2147ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // If NewBBSucc should not stay in our dominator frontier, remove it. 2157ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // We remove it unless there is a predecessor of NewBBSucc that we 2167ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // dominate, but we don't strictly dominate NewBBSucc. 2177ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner bool ShouldRemove = true; 2187ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) { 2197ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Okay, we know that PredDom does not strictly dominate NewBBSucc. 2207ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner // Check to see if it dominates any predecessors of NewBBSucc. 2217ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner for (pred_iterator PI = pred_begin(NewBBSucc), 2227ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner E = pred_end(NewBBSucc); PI != E; ++PI) 2237ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (DT.dominates(FI, *PI)) { 2247ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner ShouldRemove = false; 2257ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner break; 2267ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner } 2270e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 2287ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner 2297ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner if (ShouldRemove) 2307ed54a0ece41faeaac4eec1a1e39789a64c1876eChris Lattner removeFromFrontier(DFI, NewBBSucc); 2310f4012ca9d0e7a6dba7862201d8267681c0e43b0Eli Friedman if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB))) 2320f4012ca9d0e7a6dba7862201d8267681c0e43b0Eli Friedman addToFrontier(DFI, NewBB); 2330e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel } 2340e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel} 2350e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel 2368645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattnernamespace { 2378645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner class DFCalculateWorkObject { 2388645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner public: 2398645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner DFCalculateWorkObject(BasicBlock *B, BasicBlock *P, 24026042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *N, 24126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *PN) 24226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel : currentBB(B), parentBB(P), Node(N), parentNode(PN) {} 2438645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner BasicBlock *currentBB; 2448645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner BasicBlock *parentBB; 24526042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node; 24626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *parentNode; 2478645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner }; 2488645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner} 2498645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner 2501b7f7dc4b45a900fae2e9b062d588a995935727aChris Lattnerconst DominanceFrontier::DomSetType & 251fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha BrukmanDominanceFrontier::calculate(const DominatorTree &DT, 25226042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *Node) { 253c444a4228f31656f854d15eac671b450df557346Chris Lattner BasicBlock *BB = Node->getBlock(); 254cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType *Result = NULL; 255cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 2569be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel std::vector<DFCalculateWorkObject> workList; 2572ad28e6c486f91d83b2d5bcd30612049a686ad64Devang Patel SmallPtrSet<BasicBlock *, 32> visited; 258cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 2599be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL)); 260cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel do { 2619be98dd9c01e41c126fa3da0d794bdbeb5665c11Devang Patel DFCalculateWorkObject *currentW = &workList.back(); 262cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentW && "Missing work object."); 263cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 264cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *currentBB = currentW->currentBB; 265cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *parentBB = currentW->parentBB; 26626042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *currentNode = currentW->Node; 26726042420d642e810f5cdfb2da6156b74aaf80945Devang Patel const DomTreeNode *parentNode = currentW->parentNode; 268cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentBB && "Invalid work object. Missing current Basic Block"); 269cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel assert (currentNode && "Invalid work object. Missing current Node"); 270cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType &S = Frontiers[currentBB]; 271cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 272cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Visit each block only once. 273cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (visited.count(currentBB) == 0) { 274cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel visited.insert(currentBB); 275cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 276cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Loop over CFG successors to calculate DFlocal[currentNode] 277cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB); 278cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel SI != SE; ++SI) { 279cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Does Node immediately dominate this successor? 280cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (DT[*SI]->getIDom() != currentNode) 281cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel S.insert(*SI); 282cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 283cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 2841715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 285cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // At this point, S is DFlocal. Now we union in DFup's of our children... 286cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // Loop through and visit the nodes that Node immediately dominates (Node's 287cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // children in the IDomTree) 288cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel bool visitChild = false; 28926042420d642e810f5cdfb2da6156b74aaf80945Devang Patel for (DomTreeNode::const_iterator NI = currentNode->begin(), 290cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel NE = currentNode->end(); NI != NE; ++NI) { 29126042420d642e810f5cdfb2da6156b74aaf80945Devang Patel DomTreeNode *IDominee = *NI; 292cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel BasicBlock *childBB = IDominee->getBlock(); 293cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (visited.count(childBB) == 0) { 2948645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner workList.push_back(DFCalculateWorkObject(childBB, currentBB, 2958645fb95243d0c5b23aa10c48226c84c7fc20f17Chris Lattner IDominee, currentNode)); 296cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel visitChild = true; 297cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 298cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 2991715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 300cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // If all children are visited or there is any child then pop this block 301cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel // from the workList. 302cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (!visitChild) { 303cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 304cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel if (!parentBB) { 305cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel Result = &S; 306cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel break; 307cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 308cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 309cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end(); 310cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel DomSetType &parentSet = Frontiers[parentBB]; 311cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel for (; CDFI != CDFE; ++CDFI) { 3129a51157db555395f7a6ad89faec40b3afa121091Devang Patel if (!DT.properlyDominates(parentNode, DT[*CDFI])) 313cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel parentSet.insert(*CDFI); 314cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } 315cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel workList.pop_back(); 3161715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner } 3171715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner 318cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel } while (!workList.empty()); 319cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel 320cbdfb8a9d5e9159f8bbd9b20c9b979e45a4d943cDevang Patel return *Result; 3211715229db9c04e73ba8acb8579eb2b9465209785Chris Lattner} 32294108ab8a36806d5c7fb56bed4ddffda064f5c5dChris Lattner 32345cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const { 324a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 325dc4a745ffe4732c24cd854305f119f142b7daf71Dan Gohman OS << " DomFrontier for BB "; 326b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner if (I->first) 327791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner WriteAsOperand(OS, I->first, false); 328b884f597d62e8596df0b3856e9ca1b2496f81361Chris Lattner else 329791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner OS << " <<exit node>>"; 330791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner OS << " is:\t"; 331791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner 332791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner const std::set<BasicBlock*> &BBs = I->second; 333791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner 334791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 335dc4a745ffe4732c24cd854305f119f142b7daf71Dan Gohman I != E; ++I) { 336dc4a745ffe4732c24cd854305f119f142b7daf71Dan Gohman OS << ' '; 337791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner if (*I) 338791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner WriteAsOperand(OS, *I, false); 339791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner else 340dc4a745ffe4732c24cd854305f119f142b7daf71Dan Gohman OS << "<<exit node>>"; 341dc4a745ffe4732c24cd854305f119f142b7daf71Dan Gohman } 342791102fb1192ac9483274e54cbc42480c9b1af10Chris Lattner OS << "\n"; 343a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner } 344a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner} 345d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 346