diff options
author | Chris Lattner <sabre@nondot.org> | 2006-08-12 05:02:03 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2006-08-12 05:02:03 +0000 |
commit | 69b3992154d4a136cd18448b4fc796afd1efb5ea (patch) | |
tree | 0bb4dded3f22d77608f3d96b3c342577bbef3726 /lib/Analysis/LoopInfo.cpp | |
parent | fa78946482a2cc73a1485887dfd12edd12b742a4 (diff) | |
download | external_llvm-69b3992154d4a136cd18448b4fc796afd1efb5ea.zip external_llvm-69b3992154d4a136cd18448b4fc796afd1efb5ea.tar.gz external_llvm-69b3992154d4a136cd18448b4fc796afd1efb5ea.tar.bz2 |
Make Loop::getExitBlocks significantly faster for large loops. Instead of
pounding on Loop::contains (which is O(n) in the size of the loop), use a
sorted vector, which is O(log(N)) for each query. This speeds up Duraid's
horrible testcase from ~72s to ~31s in a debug build.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29645 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/LoopInfo.cpp')
-rw-r--r-- | lib/Analysis/LoopInfo.cpp | 12 |
1 files changed, 9 insertions, 3 deletions
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index 0ea5133..a91c201 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -336,11 +336,17 @@ void LoopInfo::removeBlock(BasicBlock *BB) { /// are the blocks _outside of the current loop_ which are branched to. /// void Loop::getExitBlocks(std::vector<BasicBlock*> &ExitBlocks) const { + // Sort the blocks vector so that we can use binary search to do quick + // lookups. + std::vector<BasicBlock*> LoopBBs(block_begin(), block_end()); + std::sort(LoopBBs.begin(), LoopBBs.end()); + for (std::vector<BasicBlock*>::const_iterator BI = Blocks.begin(), - BE = Blocks.end(); BI != BE; ++BI) + BE = Blocks.end(); BI != BE; ++BI) for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) - if (!contains(*I)) // Not in current loop? - ExitBlocks.push_back(*I); // It must be an exit block... + if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) + // Not in current loop? It must be an exit block. + ExitBlocks.push_back(*I); } |