From 0a5f83c22cc5d1fe24e57aadde9399fa90eb5c98 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sat, 4 Aug 2007 23:48:07 +0000 Subject: switch the DomTreeNodes and IDoms maps in idom/postidom to a DenseMap instead of an std::map. This speeds up postdomtree by about 25% and domtree by about 23%. It also speeds up clients, for example, domfrontier by 11%, mem2reg by 4% and ADCE by 6%. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40826 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/PostDominators.cpp | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'lib/Analysis/PostDominators.cpp') diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index 1188cff030..e3169a5c83 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -28,7 +28,7 @@ static RegisterPass F("postdomtree", "Post-Dominator Tree Construction", true); unsigned PostDominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, - unsigned N) { + unsigned N) { std::vector > workStack; std::set visited; workStack.push_back(std::make_pair(V, &VInfo)); @@ -111,13 +111,18 @@ void PostDominatorTree::calculate(Function &F) { // Step #0: Scan the function looking for the root nodes of the post-dominance // relationships. These blocks, which have no successors, end with return and // unwind instructions. - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (succ_begin(I) == succ_end(I)) { - Instruction *Insn = I->getTerminator(); + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { + TerminatorInst *Insn = I->getTerminator(); + if (Insn->getNumSuccessors() == 0) { // Unreachable block is not a root node. if (!isa(Insn)) Roots.push_back(I); } + + // Prepopulate maps so that we don't get iterator invalidation issues later. + IDoms[I] = 0; + DomTreeNodes[I] = 0; + } Vertex.push_back(0); -- cgit v1.2.3