Changes in directory llvm/lib/Analysis:
LoopInfo.cpp updated: 1.75 -> 1.76
---
Log message:
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.
---
Diffs of the changes: (+9 -3)
LoopInfo.cpp | 12 +++++++++---
1 files changed, 9 insertions(+), 3 deletions(-)
Index: llvm/lib/Analysis/LoopInfo.cpp
diff -u llvm/lib/Analysis/LoopInfo.cpp:1.75 llvm/lib/Analysis/LoopInfo.cpp:1.76
--- llvm/lib/Analysis/LoopInfo.cpp:1.75 Tue Aug 1 19:14:16 2006
+++ llvm/lib/Analysis/LoopInfo.cpp Sat Aug 12 00:02:03 2006
@@ -336,11 +336,17 @@
/// 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);
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
