Quick look-up for block in loop

[shawfly]

Summary

In LoopInfo.cpp and LoopInfoImpl.h, it is frequently to judge a specified block is in a loop or not, eg. getExitBlocks();

Currently the implementation is like this:
a. Copy all blocks into a vector and sort it, then use binary search to look up it.
b. Construct SmallPtrSet to implement quick search, when the set is small, it is same as the linear search in vector.

These two ways are proven very inefficient, it causes 2~4% performance penalty of llc for the cases with many loops; such as 458.sjeng, 429.mcf, 456.hmmer in CPUSpec2006.

This patch implement quick_contains() to look up a block in loop:

1. when the block size is small, look up the block vector directly to avoid construction of any other data container.
2. otherwise construct DenseSet to implement quick look-up.

This patch could introduce 2~3% compilation time improvement in llc for the benchmark with many loops.

[hfinkel]

Wan,

Do you think that it would be worthwhile to cache the DenseSet once constructed?

Also, in LCSSA, we currently keep a cache of the sorted loop blocks array, solely for the purpose of this function:

/// inLoop - returns true if the given block is within the current loop
bool inLoop(BasicBlock *B) const {
  return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
}

With this new, more-efficient, functionality in LoopInfo, especially if we cache the resulting set, I think that it would make sense to remove this inLoop implementation from LCSSA and let it call the regular contains(BB) function.

Finally, when you post patches to llvm-reviews, please generate them with -U999999 so that we can see the full context in the web interface.

Thanks,
Hal

• Original Message -----

Hi atrick,

In LoopInfo.cpp and LoopInfoImpl.h, it is frequently to judge a
specified block is in a loop or not, eg. getExitBlocks();

Currently the implementation is like this:
a. Copy all blocks into a vector and sort it, then use binary search
to look up it.
b. Construct SmallPtrSet to implement quick search, when the set is
small, it is same as the linear search in vector.

These two ways are proven very inefficient, it causes 2~4%
performance penalty of llc for the cases with many loops; such as
458.sjeng, 429.mcf, 456.hmmer in CPUSpec2006.

This patch implement quick_contains() to look up a block in loop:

1. when the block size is small, look up the block vector directly to

avoid construction of any other data container.

2. otherwise construct DenseSet to implement quick look-up.

This patch could introduce 2~3% compilation time improvement in llc
for the benchmark with many loops.

http://llvm-reviews.chandlerc.com/D2014

Files:

include/llvm/Analysis/LoopInfo.h
include/llvm/Analysis/LoopInfoImpl.h
lib/Analysis/LoopInfo.cpp

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[shawfly]

Hal:

Thanks for your comments, I don't think the DenseSet could be cached since the blocks in loop may be changed.

Finally, when you post patches to llvm-reviews, please generate them with -U999999 so that we can see the full context in the web interface.
~~~~What diff tool do you usually use, it seems svn diff has no option -U999999, thanks.

Thanks
Wan Xiaofei

[hfinkel]

• Original Message -----

Hal:

Thanks for your comments, I don't think the DenseSet could be
cached since the blocks in loop may be changed.

I think that, normally, blocks can't be added or removed from a loop without either invalidating the LoopInfo, or updating it (calling LoopInfo::removeBlock, changeLoopFor, etc.). I think that to get a mutable copy of the blocks array directly, getBlocksVector needs to be called (and it could invalidate the cache, and prevent further caching after it is called).

Finally, when you post patches to llvm-reviews, please generate
them with -U999999 so that we can see the full context in the web
interface.
~~~~What diff tool do you usually use, it seems svn diff has no
option -U999999, thanks.

http://llvm.org/docs/Phabricator.html says:

svn diff --diff-cmd=diff -x -U999999

Personally, I use git-svn, so it is a bit easier.

Thanks,
Hal

Thanks
Wan Xiaofei

http://llvm-reviews.chandlerc.com/D2014

[shawfly]

How do you think only exposing two write interfaces for block vector (remove block & add block, it is enough); then the DenseSet could be cached and maintained easily.

It could introduce some extra performance benefit if the DenseSet needn't be constructed each time.
Take 458.sjeng as example, the time in LoopInfo is about ~4% without this patch, now it is ~1% with this patch, so it may introduce ~1% extra performance gain if DenseSet is cached.

Thanks
Wan Xiaofei

[shawfly]

Show full context for this patch

[shawfly]

Remove getBlocksVector() to make it easier to cache the DenseSet.

[hfinkel]

Wan,

Please remove the tabs.

-Hal

• Original Message -----

Remove getBlocksVector() to make it easier to cache the DenseSet.

Hi atrick,

http://llvm-reviews.chandlerc.com/D2014

CHANGE SINCE LAST DIFF

http://llvm-reviews.chandlerc.com/D2014?vs=5126&id=5131#toc

Files:

include/llvm/Analysis/LoopInfoImpl.h
include/llvm/Analysis/LoopInfo.h
lib/Transforms/Vectorize/LoopVectorize.cpp
lib/Transforms/Utils/LCSSA.cpp
lib/Analysis/LoopInfo.cpp

[shawfly]

Remove tabs

[atrick]

Thanks Xiaofei. If you address my two inline comments, I think this is ready to checkin.

include/llvm/Analysis/LoopInfo.h

278–281

Why does this clear the cache?

include/llvm/Analysis/LoopInfoImpl.h

421

Oh no. Why don't we reserve the block vector any more? Can you just add an API for it?

[shawfly]

Update according Andy's comments.

[atrick]

LGTM. When you commit, please do s/reserveBlock/reserveBlocks/g.

[Eugene.Zelenko]

Committed in rL193460.

include/llvm/Analysis/LoopInfo.h

 class LoopBase {
   LoopT *ParentLoop;
   // SubLoops - Loops contained entirely within this one.
   std::vector<LoopT *> SubLoops;
 
   // Blocks - The list of blocks in this loop.  First entry is the header node.
   std::vector<BlockT*> Blocks;
 
+  SmallPtrSet<const BlockT*, 8> DenseBlockSet;
+
   LoopBase(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION;
   const LoopBase<BlockT, LoopT>&
     operator=(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION;
 public:
   /// Loop ctor - This creates an empty loop.
   LoopBase() : ParentLoop(0) {}
   ~LoopBase() {
     for (size_t i = 0, e = SubLoops.size(); i != e; ++i)
bool contains(const LoopT *L) const {
     if (L == this) return true;
     if (L == 0)    return false;
     return contains(L->getParentLoop());
   }
 
   /// contains - Return true if the specified basic block is in this loop.
   ///
   bool contains(const BlockT *BB) const {
-    return std::find(block_begin(), block_end(), BB) != block_end();
+    return DenseBlockSet.count(BB);
   }
 
   /// contains - Return true if the specified instruction is in this loop.
   ///
   template<class InstT>
   bool contains(const InstT *Inst) const {
     return contains(Inst->getParent());
   }
public:
   iterator end() const { return SubLoops.end(); }
   reverse_iterator rbegin() const { return SubLoops.rbegin(); }
   reverse_iterator rend() const { return SubLoops.rend(); }
   bool empty() const { return SubLoops.empty(); }
 
   /// getBlocks - Get a list of the basic blocks which make up this loop.
   ///
   const std::vector<BlockT*> &getBlocks() const { return Blocks; }
-  std::vector<BlockT*> &getBlocksVector() { return Blocks; }
   typedef typename std::vector<BlockT*>::const_iterator block_iterator;
   block_iterator block_begin() const { return Blocks.begin(); }
   block_iterator block_end() const { return Blocks.end(); }
 
   /// getNumBlocks - Get the number of blocks in this loop in constant time.
   unsigned getNumBlocks() const {
     return Blocks.size();
   }
LoopT *removeChildLoop(iterator I) {
     return Child;
   }
 
   /// addBlockEntry - This adds a basic block directly to the basic block list.
   /// This should only be used by transformations that create new loops.  Other
   /// transformations should use addBasicBlockToLoop.
   void addBlockEntry(BlockT *BB) {
     Blocks.push_back(BB);
+    DenseBlockSet.insert(BB);
+  }
+
+  void reverseBlock(unsigned from) {
+    std::reverse(Blocks.begin() + from, Blocks.end());
+  }
+
+  void reserveBlock(unsigned size) {
+    Blocks.reserve(size);
   }
 
   /// moveToHeader - This method is used to move BB (which must be part of this
   /// loop) to be the loop header of the loop (the block that dominates all
   /// others).
   void moveToHeader(BlockT *BB) {
     if (Blocks[0] == BB) return;
     for (unsigned i = 0; ; ++i) {
       assert(i != Blocks.size() && "Loop does not contain BB!");
       if (Blocks[i] == BB) {
         Blocks[i] = Blocks[0];
         Blocks[0] = BB;
         return;
       }
     }
   }
 
   /// removeBlockFromLoop - This removes the specified basic block from the
   /// current loop, updating the Blocks as appropriate.  This does not update
   /// the mapping in the LoopInfo class.
   void removeBlockFromLoop(BlockT *BB) {
     RemoveFromVector(Blocks, BB);
+    DenseBlockSet.erase(BB);
   }
 
   /// verifyLoop - Verify loop structure
   void verifyLoop() const;
 
   /// verifyLoop - Verify loop structure of this loop and all nested loops.
   void verifyLoopNest(DenseSet<const LoopT*> *Loops) const;
 
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
 protected:
   friend class LoopInfoBase<BlockT, LoopT>;
   explicit LoopBase(BlockT *BB) : ParentLoop(0) {
     Blocks.push_back(BB);
+    DenseBlockSet.insert(BB);
   }
 };
 
 template<class BlockT, class LoopT>
 raw_ostream& operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
   Loop.print(OS);
   return OS;
 }

include/llvm/Analysis/LoopInfoImpl.h

 
 /// getExitingBlocks - Return all blocks inside the loop that have successors
 /// outside of the loop.  These are the blocks _inside of the current loop_
 /// which branch out.  The returned list is always unique.
 ///
 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;
       }
 }
 
 /// getExitingBlock - If getExitingBlocks would return exactly one block,
 /// return that block. Otherwise return null.
 template<class BlockT, class LoopT>
 BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
   SmallVector<BlockT*, 8> ExitingBlocks;
   getExitingBlocks(ExitingBlocks);
   if (ExitingBlocks.size() == 1)
     return ExitingBlocks[0];
   return 0;
 }
 
 /// getExitBlocks - Return all of the successor blocks of this loop.  These
 /// are the blocks _outside of the current loop_ which are branched to.
 ///
 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);
 }
 
 /// getExitBlock - If getExitBlocks would return exactly one block,
 /// return that block. Otherwise return null.
 template<class BlockT, class LoopT>
 BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
   SmallVector<BlockT*, 8> ExitBlocks;
   getExitBlocks(ExitBlocks);
   if (ExitBlocks.size() == 1)
     return ExitBlocks[0];
   return 0;
 }
 
 /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
 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));
 }
 
 /// getLoopPreheader - If there is a preheader for this loop, return it.  A
 /// loop has a preheader if there is only one edge to the header of the loop
 /// from outside of the loop.  If this is the case, the block branching to the
 /// header of the loop is the preheader node.
addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
 
   LoopT *L = static_cast<LoopT *>(this);
 
   // Add the loop mapping to the LoopInfo object...
   LIB.BBMap[NewBB] = L;
 
   // Add the basic block to this loop and all parent loops...
   while (L) {
-    L->Blocks.push_back(NewBB);
+    L->addBlockEntry(NewBB);
     L = L->getParentLoop();
   }
 }
 
 /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
 /// the OldChild entry in our children list with NewChild, and updates the
 /// parent pointer of OldChild to be null and the NewChild to be this loop.
 /// This updates the loop depth of the new child.
#ifndef NDEBUG
   VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
   df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> >
     BI = df_ext_begin(getHeader(), VisitSet),
     BE = df_ext_end(getHeader(), VisitSet);
 
   // 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;
     bool HasInsideLoopSuccs = false;
     bool HasInsideLoopPreds = false;
     SmallVector<BlockT *, 2> OutsideLoopPreds;
 
     typedef GraphTraits<BlockT*> BlockTraits;
     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;
       }
     typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
     for (typename InvBlockTraits::ChildIteratorType PI =
            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);
     }
 
     if (BB == getHeader()) {
         assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
     } else if (!OutsideLoopPreds.empty()) {
#ifndef NDEBUG
 
   assert(NumVisited == getNumBlocks() && "Unreachable block in loop");
 
   // Check the subloops.
   for (iterator I = begin(), E = end(); I != E; ++I)
     // 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!");
     }
 
   // Check the parent loop pointer.
   if (ParentLoop) {
     assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
            ParentLoop->end() &&
            "Loop is not a subloop of its parent!");
else {
              InvBlockTraits::child_begin(PredBB),
              PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) {
         if (LI->getLoopFor(*PI) != Subloop)
           ReverseCFGWorklist.push_back(*PI);
       }
     }
   }
   L->getSubLoopsVector().reserve(NumSubloops);
-  L->getBlocksVector().reserve(NumBlocks);
+  L->reserveBlock(NumBlocks);
 }
 
 namespace {
 /// Populate all loop data in a stable order during a single forward DFS.
 template<class BlockT, class LoopT>
 class PopulateLoopsDFS {
   typedef GraphTraits<BlockT*> BlockTraits;
   typedef typename BlockTraits::ChildIteratorType SuccIterTy;
if (Subloop && Block == Subloop->getHeader()) {
     // the subloop.
     if (Subloop->getParentLoop())
       Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
     else
       LI->addTopLevelLoop(Subloop);
 
     // 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
 /// interleaved with backward CFG traversals within each subloop
 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
 /// this part of the algorithm is linear in the number of CFG edges. Subloop and
 /// Block vectors are then populated during a single forward CFG traversal
 /// (PopulateLoopDFS).

lib/Analysis/LoopInfo.cpp

if (ConstantInt *CI =
               if (CI->equalsInt(1))
                 return PN;
   }
   return 0;
 }
 
 /// 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<BasicBlock*, 16> LoopBBs(block_begin(), block_end());
-
   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)
       for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
            ++UI) {
         User *U = *UI;
         BasicBlock *UserBB = cast<Instruction>(U)->getParent();
         if (PHINode *P = dyn_cast<PHINode>(U))
           UserBB = P->getIncomingBlock(UI);
 
         // Check the current block, as a fast-path, before checking whether
         // the use is anywhere in the loop.  Most values are used in the same
         // 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) &&
+            !contains(UserBB) &&
             DT.isReachableFromEntry(UserBB))
           return false;
       }
   }
 
   return true;
 }
 
bool Loop::isAnnotatedParallel() const {
   }
   return true;
 }
 
 
 /// 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<BasicBlock *, 16> LoopBBs(block_begin(), block_end());
   // Each predecessor of each exit block of a normal loop is contained
   // within the loop.
   SmallVector<BasicBlock *, 4> ExitBlocks;
   getExitBlocks(ExitBlocks);
   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 (!contains(*PI))
         return false;
   // All the requirements are met.
   return true;
 }
 
 /// getUniqueExitBlocks - Return all unique successor blocks of this loop.
 /// These are the blocks _outside of the current loop_ which are branched to.
 /// This assumes that loop exits are in canonical form.
 ///
 void
 Loop::getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const {
   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<BasicBlock *, 128> LoopBBs(block_begin(), block_end());
-  std::sort(LoopBBs.begin(), LoopBBs.end());
-
   SmallVector<BasicBlock *, 32> switchExitBlocks;
 
   for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) {
 
     BasicBlock *current = *BI;
     switchExitBlocks.clear();
 
     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 (contains(*I))
         continue;
 
       pred_iterator PI = pred_begin(*I);
       BasicBlock *firstPred = *PI;
 
       // If current basic block is this exit block's first predecessor
       // then only insert exit block in to the output ExitBlocks vector.
       // This ensures that same exit block is not inserted twice into

lib/Transforms/Utils/LCSSA.cpp

struct LCSSA : public LoopPass {
     LCSSA() : LoopPass(ID) {
       initializeLCSSAPass(*PassRegistry::getPassRegistry());
     }
 
     // Cached analysis information for the current function.
     DominatorTree *DT;
     LoopInfo *LI;
     ScalarEvolution *SE;
-    std::vector<BasicBlock*> LoopBlocks;
     PredIteratorCache PredCache;
     Loop *L;
     
     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
 
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG.  It maintains both of these,
     /// as well as the CFG.  It also requires dominator information.
private:
     bool ProcessInstruction(Instruction *Inst,
                             const SmallVectorImpl<BasicBlock*> &ExitBlocks);
     
     /// verifyAnalysis() - Verify loop nest.
     virtual void verifyAnalysis() const {
       // Check the special guarantees that LCSSA makes.
       assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!");
     }
-
-    /// inLoop - returns true if the given block is within the current loop
-    bool inLoop(BasicBlock *B) const {
-      return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
-    }
   };
 }
   
 char LCSSA::ID = 0;
 INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 INITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
bool LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) {
 
   // Get the set of exiting blocks.
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getExitBlocks(ExitBlocks);
   
   if (ExitBlocks.empty())
     return false;
   
-  // Speed up queries by creating a sorted vector of blocks.
-  LoopBlocks.clear();
-  LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
-  array_pod_sort(LoopBlocks.begin(), LoopBlocks.end());
-  
   // Look at all the instructions in the loop, checking to see if they have uses
   // outside the loop.  If so, rewrite those uses.
   bool MadeChange = false;
   
   for (Loop::block_iterator BBI = L->block_begin(), E = L->block_end();
        BBI != E; ++BBI) {
     BasicBlock *BB = *BBI;
     
bool LCSSA::ProcessInstruction(Instruction *Inst,
   
   for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end();
        UI != E; ++UI) {
     User *U = *UI;
     BasicBlock *UserBB = cast<Instruction>(U)->getParent();
     if (PHINode *PN = dyn_cast<PHINode>(U))
       UserBB = PN->getIncomingBlock(UI);
     
-    if (InstBB != UserBB && !inLoop(UserBB))
+    if (InstBB != UserBB && !L->contains(UserBB))
       UsesToRewrite.push_back(&UI.getUse());
   }
 
   // If there are no uses outside the loop, exit with no change.
   if (UsesToRewrite.empty()) return false;
   
   ++NumLCSSA; // We are applying the transformation
 
for (SmallVectorImpl<BasicBlock*>::const_iterator BBI = ExitBlocks.begin(),
 
     // Add inputs from inside the loop for this PHI.
     for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) {
       PN->addIncoming(Inst, *PI);
 
       // If the exit block has a predecessor not within the loop, arrange for
       // the incoming value use corresponding to that predecessor to be
       // rewritten in terms of a different LCSSA PHI.
-      if (!inLoop(*PI))
+      if (!L->contains(*PI))
         UsesToRewrite.push_back(
           &PN->getOperandUse(
             PN->getOperandNumForIncomingValue(PN->getNumIncomingValues()-1)));
     }
 
     AddedPHIs.push_back(PN);
     
     // Remember that this phi makes the value alive in this block.

lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::updateAnalysis() {
   DEBUG(DT->verifyAnalysis());
 }
 
 bool LoopVectorizationLegality::canVectorizeWithIfConvert() {
   if (!EnableIfConversion)
     return false;
 
   assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable");
-  std::vector<BasicBlock*> &LoopBlocks = TheLoop->getBlocksVector();
 
   // A list of pointers that we can safely read and write to.
   SmallPtrSet<Value *, 8> SafePointes;
 
   // Collect safe addresses.
-  for (unsigned i = 0, e = LoopBlocks.size(); i < e; ++i) {
-    BasicBlock *BB = LoopBlocks[i];
+  for (Loop::block_iterator BI = TheLoop->block_begin(),
+         BE = TheLoop->block_end(); BI != BE; ++BI) {
+    BasicBlock *BB = *BI;
 
     if (blockNeedsPredication(BB))
       continue;
 
     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
       if (LoadInst *LI = dyn_cast<LoadInst>(I))
         SafePointes.insert(LI->getPointerOperand());
       else if (StoreInst *SI = dyn_cast<StoreInst>(I))
         SafePointes.insert(SI->getPointerOperand());
     }
   }
 
   // Collect the blocks that need predication.
-  for (unsigned i = 0, e = LoopBlocks.size(); i < e; ++i) {
-    BasicBlock *BB = LoopBlocks[i];
+  for (Loop::block_iterator BI = TheLoop->block_begin(),
+         BE = TheLoop->block_end(); BI != BE; ++BI) {
+    BasicBlock *BB = *BI;
 
     // We don't support switch statements inside loops.
     if (!isa<BranchInst>(BB->getTerminator()))
       return false;
 
     // We must be able to predicate all blocks that need to be predicated.
     if (blockNeedsPredication(BB) && !blockCanBePredicated(BB, SafePointes))
       return false;