Index: include/llvm/Analysis/LoopInfo.h =================================================================== --- include/llvm/Analysis/LoopInfo.h +++ include/llvm/Analysis/LoopInfo.h @@ -69,6 +69,8 @@ // Blocks - The list of blocks in this loop. First entry is the header node. std::vector Blocks; + const static unsigned SmallDenseBlockSize = 8; + LoopBase(const LoopBase &) LLVM_DELETED_FUNCTION; const LoopBase& operator=(const LoopBase &) LLVM_DELETED_FUNCTION; @@ -111,6 +113,27 @@ return std::find(block_begin(), block_end(), BB) != block_end(); } + /// quick_contains - similar to contains(const BlockT *BB) + /// 1. If the block size is small, use linear search similar to contains(const BlockT *BB) + /// This way is similar to SmallPtrSet, but avoid to construct SmallPtrSet which is dupilcate of Blocks vector + /// 2. otherwise construct a denseset first, then use hash to have quick search + /// DenseSet is more suitable here since set size is known + /// It could be used when contains() is called frequently, make_dense_blocks() must be called beforehand + /// + bool quick_contains(DenseSet &DenseBlockSet, BlockT *BB) const { + if (Blocks.size() < SmallDenseBlockSize) + return std::find(block_begin(), block_end(), BB) != block_end(); + /// Use DenseSet to implement quick search. + return DenseBlockSet.count(BB); + } + + void make_dense_blockset(DenseSet &DenseBlockSet) const { + if (Blocks.size() < SmallDenseBlockSize) + return; + DenseBlockSet.resize(Blocks.size() << 1); + DenseBlockSet.insert(block_begin(), block_end()); + } + /// contains - Return true if the specified instruction is in this loop. /// template Index: include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- include/llvm/Analysis/LoopInfoImpl.h +++ include/llvm/Analysis/LoopInfoImpl.h @@ -31,17 +31,14 @@ template void LoopBase:: getExitingBlocks(SmallVectorImpl &ExitingBlocks) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - + DenseSet DenseBlockSet; + make_dense_blockset(DenseBlockSet); typedef GraphTraits 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 (!quick_contains(DenseBlockSet, *I)) { // Not in current loop? It must be an exit block. ExitingBlocks.push_back(*BI); break; @@ -65,17 +62,14 @@ template void LoopBase:: getExitBlocks(SmallVectorImpl &ExitBlocks) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - + DenseSet DenseBlockSet; + make_dense_blockset(DenseBlockSet); typedef GraphTraits 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 (!quick_contains(DenseBlockSet, *I)) // Not in current loop? It must be an exit block. ExitBlocks.push_back(*I); } @@ -95,17 +89,14 @@ template void LoopBase:: getExitEdges(SmallVectorImpl &ExitEdges) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector LoopBBs(block_begin(), block_end()); - array_pod_sort(LoopBBs.begin(), LoopBBs.end()); - + DenseSet DenseBlockSet; + make_dense_blockset(DenseBlockSet); typedef GraphTraits 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 (!quick_contains(DenseBlockSet, *I)) // Not in current loop? It must be an exit block. ExitEdges.push_back(Edge(*BI, *I)); } @@ -250,12 +241,8 @@ // 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 LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - - // Check the individual blocks. + DenseSet DenseBlockSet; + make_dense_blockset(DenseBlockSet); // Check the individual blocks. for ( ; BI != BE; ++BI) { BlockT *BB = *BI; bool HasInsideLoopSuccs = false; @@ -266,7 +253,7 @@ 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 (quick_contains(DenseBlockSet, *SI)) { HasInsideLoopSuccs = true; break; } @@ -275,7 +262,7 @@ 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 (quick_contains(DenseBlockSet, N)) HasInsideLoopPreds = true; else OutsideLoopPreds.push_back(N); @@ -309,7 +296,7 @@ // 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(quick_contains(DenseBlockSet, *BI) && "Loop does not contain all the blocks of a subloop!"); } Index: lib/Analysis/LoopInfo.cpp =================================================================== --- lib/Analysis/LoopInfo.cpp +++ lib/Analysis/LoopInfo.cpp @@ -177,10 +177,8 @@ /// isLCSSAForm - Return true if the Loop is in LCSSA form bool Loop::isLCSSAForm(DominatorTree &DT) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallPtrSet LoopBBs(block_begin(), block_end()); - + DenseSet DenseBlockSet; + make_dense_blockset(DenseBlockSet); for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { BasicBlock *BB = *BI; for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) @@ -196,7 +194,7 @@ // block they are defined in. Also, blocks not reachable from the // entry are special; uses in them don't need to go through PHIs. if (UserBB != BB && - !LoopBBs.count(UserBB) && + !quick_contains(DenseBlockSet, UserBB) && DT.isReachableFromEntry(UserBB)) return false; } @@ -337,9 +335,8 @@ /// hasDedicatedExits - Return true if no exit block for the loop /// has a predecessor that is outside the loop. bool Loop::hasDedicatedExits() const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallPtrSet LoopBBs(block_begin(), block_end()); + DenseSet DenseBlockSet; + make_dense_blockset(DenseBlockSet); // Each predecessor of each exit block of a normal loop is contained // within the loop. SmallVector ExitBlocks; @@ -347,7 +344,7 @@ for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) for (pred_iterator PI = pred_begin(ExitBlocks[i]), PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) - if (!LoopBBs.count(*PI)) + if (!quick_contains(DenseBlockSet, *PI)) return false; // All the requirements are met. return true; @@ -362,11 +359,8 @@ assert(hasDedicatedExits() && "getUniqueExitBlocks assumes the loop has canonical form exits!"); - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - + DenseSet DenseBlockSet; + make_dense_blockset(DenseBlockSet); SmallVector switchExitBlocks; for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { @@ -376,7 +370,7 @@ for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { // If block is inside the loop then it is not a exit block. - if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) + if (quick_contains(DenseBlockSet, *I)) continue; pred_iterator PI = pred_begin(*I);