From bd0fe01dafb7f115a882865494d139edd8a7f0a2 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%. llvm-svn: 40826 --- llvm/lib/Analysis/PostDominators.cpp | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'llvm/lib/Analysis/PostDominators.cpp') diff --git a/llvm/lib/Analysis/PostDominators.cpp b/llvm/lib/Analysis/PostDominators.cpp index 1188cff0303..e3169a5c838 100644 --- a/llvm/lib/Analysis/PostDominators.cpp +++ b/llvm/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