From b08ba8824e0e8bf1d4a68594c5efb65bf640ecc1 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 26 Jul 2010 17:55:15 +0000 Subject: Fix (at least) quadratic worst-case complexity in DominanceFrontier::splitBlock: don't visit all blocks in the function, and don't iterate over the split blocks' predecessor lists for each block visited. Also, remove the special-case test for the entry block. Splitting the entry block isn't common enough to make this worthwhile. This fixes a major compile-time bottleneck which is exposed now that LoopSimplify isn't being redundantly run both before and after DominanceFrontier. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109408 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/VMCore/Dominators.cpp | 116 +++++++++++++++++++++++++--------------------- 1 file changed, 64 insertions(+), 52 deletions(-) (limited to 'lib/VMCore') diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 8a68b4e9da..f3dad82446 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -127,17 +127,6 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { "NewBB should have a single successor!"); BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); - SmallVector PredBlocks; - for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); - PI != PE; ++PI) - PredBlocks.push_back(*PI); - - if (PredBlocks.empty()) - // If NewBB does not have any predecessors then it is a entry block. - // In this case, NewBB and its successor NewBBSucc dominates all - // other blocks. - return; - // NewBBSucc inherits original NewBB frontier. DominanceFrontier::iterator NewBBI = find(NewBB); if (NewBBI != end()) @@ -147,7 +136,9 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { // DF(NewBBSucc) without the stuff that the new block does not dominate // a predecessor of. DominatorTree &DT = getAnalysis(); - if (DT.dominates(NewBB, NewBBSucc)) { + DomTreeNode *NewBBNode = DT.getNode(NewBB); + DomTreeNode *NewBBSuccNode = DT.getNode(NewBBSucc); + if (DT.dominates(NewBBNode, NewBBSuccNode)) { DominanceFrontier::iterator DFI = find(NewBBSucc); if (DFI != end()) { DominanceFrontier::DomSetType Set = DFI->second; @@ -157,7 +148,7 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { bool DominatesPred = false; for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); PI != E; ++PI) - if (DT.dominates(NewBB, *PI)) { + if (DT.dominates(NewBBNode, DT.getNode(*PI))) { DominatesPred = true; break; } @@ -185,50 +176,71 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) { NewDFSet.insert(NewBBSucc); addBasicBlock(NewBB, NewDFSet); } - - // Now we must loop over all of the dominance frontiers in the function, - // replacing occurrences of NewBBSucc with NewBB in some cases. All - // blocks that dominate a block in PredBlocks and contained NewBBSucc in - // their dominance frontier must be updated to contain NewBB instead. - // - for (Function::iterator FI = NewBB->getParent()->begin(), - FE = NewBB->getParent()->end(); FI != FE; ++FI) { - DominanceFrontier::iterator DFI = find(FI); - if (DFI == end()) continue; // unreachable block. - - // Only consider nodes that have NewBBSucc in their dominator frontier. - if (!DFI->second.count(NewBBSucc)) continue; - - // Verify whether this block dominates a block in predblocks. If not, do - // not update it. - bool BlockDominatesAny = false; - for (SmallVectorImpl::const_iterator BI = PredBlocks.begin(), - BE = PredBlocks.end(); BI != BE; ++BI) { - if (DT.dominates(FI, *BI)) { - BlockDominatesAny = true; + + // Now update dominance frontiers which either used to contain NewBBSucc + // or which now need to include NewBB. + + // Collect the set of blocks which dominate a predecessor of NewBB or + // NewSuccBB and which don't dominate both. This is an initial + // approximation of the blocks whose dominance frontiers will need updates. + SmallVector AllPredDoms; + + // Compute the block which dominates both NewBBSucc and NewBB. This is + // the immediate dominator of NewBBSucc unless NewBB dominates NewBBSucc. + // The code below which climbs dominator trees will stop at this point, + // because from this point up, dominance frontiers are unaffected. + DomTreeNode *DominatesBoth = 0; + if (NewBBSuccNode) { + DominatesBoth = NewBBSuccNode->getIDom(); + if (DominatesBoth == NewBBNode) + DominatesBoth = NewBBNode->getIDom(); + } + + // Collect the set of all blocks which dominate a predecessor of NewBB. + SmallPtrSet NewBBPredDoms; + for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); PI != E; ++PI) + for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) { + if (DTN == DominatesBoth) break; - } + if (!NewBBPredDoms.insert(DTN)) + break; + AllPredDoms.push_back(DTN); } - // If NewBBSucc should not stay in our dominator frontier, remove it. - // We remove it unless there is a predecessor of NewBBSucc that we - // dominate, but we don't strictly dominate NewBBSucc. - bool ShouldRemove = true; - if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) { - // Okay, we know that PredDom does not strictly dominate NewBBSucc. - // Check to see if it dominates any predecessors of NewBBSucc. - for (pred_iterator PI = pred_begin(NewBBSucc), - E = pred_end(NewBBSucc); PI != E; ++PI) - if (DT.dominates(FI, *PI)) { - ShouldRemove = false; - break; - } + // Collect the set of all blocks which dominate a predecessor of NewSuccBB. + SmallPtrSet NewBBSuccPredDoms; + for (pred_iterator PI = pred_begin(NewBBSucc), + E = pred_end(NewBBSucc); PI != E; ++PI) + for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) { + if (DTN == DominatesBoth) + break; + if (!NewBBSuccPredDoms.insert(DTN)) + break; + if (!NewBBPredDoms.count(DTN)) + AllPredDoms.push_back(DTN); } - - if (ShouldRemove) - removeFromFrontier(DFI, NewBBSucc); - if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB))) + + // Visit all relevant dominance frontiers and make any needed updates. + for (SmallVectorImpl::const_iterator I = AllPredDoms.begin(), + E = AllPredDoms.end(); I != E; ++I) { + DomTreeNode *DTN = *I; + iterator DFI = find((*I)->getBlock()); + + // Only consider nodes that have NewBBSucc in their dominator frontier. + if (DFI == end() || !DFI->second.count(NewBBSucc)) continue; + + // If the block dominates a predecessor of NewBB but does not properly + // dominate NewBB itself, add NewBB to its dominance frontier. + if (NewBBPredDoms.count(DTN) && + !DT.properlyDominates(DTN, NewBBNode)) addToFrontier(DFI, NewBB); + + // If the block does not dominate a predecessor of NewBBSucc or + // properly dominates NewBBSucc itself, remove NewBBSucc from its + // dominance frontier. + if (!NewBBSuccPredDoms.count(DTN) || + DT.properlyDominates(DTN, NewBBSuccNode)) + removeFromFrontier(DFI, NewBBSucc); } } -- cgit v1.2.3