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

diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 0ea513368dc7ddb348139f9d2de3aff666054aa6..a91c201e0cfd1fb5fb0759c924245e72fcb79ea4 100644 (file)
--- 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);
 }