Quick look-up for block in loop.

This patch implements quick look-up for block in loop by maintaining a hash set for blocks.
It improves the efficiency of loop analysis a lot, the biggest improvement could be 5-6%(458.sjeng).
Below are the compilation time for our benchmark in llc before & after the patch.

Benchmark	llc - trunk		llc - patched	
401.bzip2	0.339081	100.00%	0.329657	102.86%
403.gcc		19.853966	100.00%	19.605466	101.27%
429.mcf		0.049823	100.00%	0.048451	102.83%
433.milc	0.514898	100.00%	0.510217	100.92%
444.namd	1.109328	100.00%	1.103481	100.53%
445.gobmk	4.988028	100.00%	4.929114	101.20%
456.hmmer	0.843871	100.00%	0.825865	102.18%
458.sjeng	0.754238	100.00%	0.714095	105.62%
464.h264ref	2.9668		100.00%	2.90612		102.09%
471.omnetpp	4.556533	100.00%	4.511886	100.99%
bitmnp01	0.038168	100.00%	0.0357		106.91%
idctrn01	0.037745	100.00%	0.037332	101.11%
libquake2	3.78689		100.00%	3.76209		100.66%
libquake_	2.251525	100.00%	2.234104	100.78%
linpack		0.033159	100.00%	0.032788	101.13%
matrix01	0.045319	100.00%	0.043497	104.19%
nbench		0.333161	100.00%	0.329799	101.02%
tblook01	0.017863	100.00%	0.017666	101.12%
ttsprk01	0.054337	100.00%	0.053057	102.41%

Reviewer	: Andrew Trick <atrick@apple.com>, Hal Finkel <hfinkel@anl.gov>
Approver	: Andrew Trick <atrick@apple.com>
Test		: Pass make check-all & llvm test-suite


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193460 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 10 insertions, 31 deletions

diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h
index 5485f3c..c98cb58 100644
--- a/include/llvm/Analysis/LoopInfoImpl.h
+++ b/include/llvm/Analysis/LoopInfoImpl.h
@@ -31,17 +31,12 @@ namespace llvm {
 template<class BlockT, class LoopT>
 void LoopBase<BlockT, LoopT>::
 getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
-  // Sort the blocks vector so that we can use binary search to do quick
-  // lookups.
-  SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
-  std::sort(LoopBBs.begin(), LoopBBs.end());
-
   typedef GraphTraits<BlockT*> BlockTraits;
   for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
     for (typename BlockTraits::ChildIteratorType I =
            BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
          I != E; ++I)
-      if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
+      if (!contains(*I)) {
         // Not in current loop? It must be an exit block.
         ExitingBlocks.push_back(*BI);
         break;
@@ -65,17 +60,12 @@ BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
 template<class BlockT, class LoopT>
 void LoopBase<BlockT, LoopT>::
 getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
-  // Sort the blocks vector so that we can use binary search to do quick
-  // lookups.
-  SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
-  std::sort(LoopBBs.begin(), LoopBBs.end());
-
   typedef GraphTraits<BlockT*> BlockTraits;
   for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
     for (typename BlockTraits::ChildIteratorType I =
            BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
          I != E; ++I)
-      if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+      if (!contains(*I))
         // Not in current loop? It must be an exit block.
         ExitBlocks.push_back(*I);
 }
@@ -95,17 +85,12 @@ BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
 template<class BlockT, class LoopT>
 void LoopBase<BlockT, LoopT>::
 getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
-  // Sort the blocks vector so that we can use binary search to do quick
-  // lookups.
-  SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
-  array_pod_sort(LoopBBs.begin(), LoopBBs.end());
-
   typedef GraphTraits<BlockT*> BlockTraits;
   for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
     for (typename BlockTraits::ChildIteratorType I =
            BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
          I != E; ++I)
-      if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+      if (!contains(*I))
         // Not in current loop? It must be an exit block.
         ExitEdges.push_back(Edge(*BI, *I));
 }
@@ -210,7 +195,7 @@ addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
 
   // Add the basic block to this loop and all parent loops...
   while (L) {
-    L->Blocks.push_back(NewBB);
+    L->addBlockEntry(NewBB);
     L = L->getParentLoop();
   }
 }
@@ -250,11 +235,6 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const {
   // Keep track of the number of BBs visited.
   unsigned NumVisited = 0;
 
-  // Sort the blocks vector so that we can use binary search to do quick
-  // lookups.
-  SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
-  std::sort(LoopBBs.begin(), LoopBBs.end());
-
   // Check the individual blocks.
   for ( ; BI != BE; ++BI) {
     BlockT *BB = *BI;
@@ -266,7 +246,7 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const {
     for (typename BlockTraits::ChildIteratorType SI =
            BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
          SI != SE; ++SI)
-      if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {
+      if (contains(*SI)) {
         HasInsideLoopSuccs = true;
         break;
       }
@@ -275,7 +255,7 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const {
            InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
          PI != PE; ++PI) {
       BlockT *N = *PI;
-      if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
+      if (contains(N))
         HasInsideLoopPreds = true;
       else
         OutsideLoopPreds.push_back(N);
@@ -309,7 +289,7 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const {
     // Each block in each subloop should be contained within this loop.
     for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
          BI != BE; ++BI) {
-        assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&
+        assert(contains(*BI) &&
                "Loop does not contain all the blocks of a subloop!");
     }
 
@@ -418,7 +398,7 @@ static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges,
     }
   }
   L->getSubLoopsVector().reserve(NumSubloops);
-  L->getBlocksVector().reserve(NumBlocks);
+  L->reserveBlocks(NumBlocks);
 }
 
 namespace {
@@ -489,15 +469,14 @@ void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
 
     // For convenience, Blocks and Subloops are inserted in postorder. Reverse
     // the lists, except for the loop header, which is always at the beginning.
-    std::reverse(Subloop->getBlocksVector().begin()+1,
-                 Subloop->getBlocksVector().end());
+    Subloop->reverseBlock(1);
     std::reverse(Subloop->getSubLoopsVector().begin(),
                  Subloop->getSubLoopsVector().end());
 
     Subloop = Subloop->getParentLoop();
   }
   for (; Subloop; Subloop = Subloop->getParentLoop())
-    Subloop->getBlocksVector().push_back(Block);
+    Subloop->addBlockEntry(Block);
 }
 
 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal