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.

llvm-svn: 29645

1 files changed, 9 insertions, 3 deletions

diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp
index 0ea513368dc..a91c201e0cf 100644
--- a/llvm/lib/Analysis/LoopInfo.cpp
+++ b/llvm/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);
 }