Change the ExitBlocks list from being explicitly contained in the Loop

structure to being dynamically computed on demand.  This makes updating
loop information MUCH easier.


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

7 files changed, 45 insertions, 184 deletions

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 13017af504..84865d3a6a 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -44,7 +44,6 @@ class Loop {
   Loop *ParentLoop;
   std::vector<Loop*> SubLoops;       // Loops contained entirely within this one
   std::vector<BasicBlock*> Blocks;   // First entry is the header node
-  std::vector<BasicBlock*> ExitBlocks; // Reachable blocks outside the loop
   unsigned LoopDepth;                // Nesting depth of this loop
 
   Loop(const Loop &);                  // DO NOT IMPLEMENT
@@ -76,14 +75,8 @@ public:
   ///
   const std::vector<BasicBlock*> &getBlocks() const { return Blocks; }
 
-  /// getExitBlocks - Return all of the successor blocks of this loop.  These
-  /// are the blocks _outside of the current loop_ which are branched to.
-  ///
-  const std::vector<BasicBlock*> &getExitBlocks() const { return ExitBlocks; }
-
   /// isLoopExit - True if terminator in the block can branch to another block
-  /// that is outside of the current loop.  The reached block should be in the
-  /// ExitBlocks list.
+  /// that is outside of the current loop.
   ///
   bool isLoopExit(const BasicBlock *BB) const;
 
@@ -91,15 +84,6 @@ public:
   ///
   unsigned getNumBackEdges() const;
 
-  /// hasExitBlock - Return true if the current loop has the specified block as
-  /// an exit block...
-  bool hasExitBlock(BasicBlock *BB) const {
-    for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
-      if (ExitBlocks[i] == BB)
-        return true;
-    return false;
-  }
-
   //===--------------------------------------------------------------------===//
   // APIs for simple analysis of the loop.
   //
@@ -108,6 +92,11 @@ public:
   // induction variable canonicalization pass should be used to normalize loops
   // for easy analysis.  These methods assume canonical loops.
 
+  /// getExitBlocks - Return all of the successor blocks of this loop.  These
+  /// are the blocks _outside of the current loop_ which are branched to.
+  ///
+  void getExitBlocks(std::vector<BasicBlock*> &Blocks) const;
+
   /// 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
@@ -149,12 +138,6 @@ public:
   ///
   void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI);
 
-  /// changeExitBlock - This method is used to update loop information.  All
-  /// instances of the specified Old basic block are removed from the exit list
-  /// and replaced with New.
-  ///
-  void changeExitBlock(BasicBlock *Old, BasicBlock *New);
-
   /// 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.
@@ -171,12 +154,6 @@ public:
   /// into another loop.
   Loop *removeChildLoop(iterator OldChild);
 
-  /// addExitBlock - Add the specified exit block to the loop.
-  ///
-  void addExitBlock(BasicBlock *BB) {
-    ExitBlocks.push_back(BB);
-  }
-
   /// 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.
@@ -185,8 +162,8 @@ public:
   }
 
   /// removeBlockFromLoop - This removes the specified basic block from the
-  /// current loop, updating the Blocks and ExitBlocks lists as appropriate.
-  /// This does not update the mapping in the LoopInfo class.
+  /// current loop, updating the Blocks as appropriate.  This does not update
+  /// the mapping in the LoopInfo class.
   void removeBlockFromLoop(BasicBlock *BB);
 
   void print(std::ostream &O, unsigned Depth = 0) const;
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 012c3dac73..3fc9673d02 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -63,14 +63,6 @@ void Loop::print(std::ostream &OS, unsigned Depth) const {
     if (i) OS << ",";
     WriteAsOperand(OS, getBlocks()[i], false);
   }
-  if (!ExitBlocks.empty()) {
-    OS << "\tExitBlocks: ";
-    for (unsigned i = 0; i < getExitBlocks().size(); ++i) {
-      if (i) OS << ",";
-      WriteAsOperand(OS, getExitBlocks()[i], false);
-    }
-  }
-
   OS << "\n";
 
   for (iterator I = begin(), E = end(); I != E; ++I)
@@ -248,14 +240,6 @@ Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS) {
     }
   }
 
-  // Now that we know all of the blocks that make up this loop, see if there are
-  // any branches to outside of the loop... building the ExitBlocks list.
-  for (std::vector<BasicBlock*>::iterator BI = L->Blocks.begin(),
-         BE = L->Blocks.end(); BI != BE; ++BI)
-    for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I)
-      if (!L->contains(*I))               // Not in current loop?
-        L->ExitBlocks.push_back(*I);      // It must be an exit block...
-
   return L;
 }
 
@@ -344,6 +328,18 @@ void LoopInfo::removeBlock(BasicBlock *BB) {
 // APIs for simple analysis of the loop.
 //
 
+/// getExitBlocks - Return all of the successor blocks of this loop.  These
+/// are the blocks _outside of the current loop_ which are branched to.
+///
+void Loop::getExitBlocks(std::vector<BasicBlock*> &Blocks) const {
+  for (std::vector<BasicBlock*>::const_iterator BI = Blocks.begin(),
+         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?
+        Blocks.push_back(*I);          // It must be an exit block...
+}
+
+
 /// 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
@@ -481,22 +477,6 @@ void Loop::addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI) {
   }
 }
 
-/// changeExitBlock - This method is used to update loop information.  All
-/// instances of the specified Old basic block are removed from the exit list
-/// and replaced with New.
-///
-void Loop::changeExitBlock(BasicBlock *Old, BasicBlock *New) {
-  assert(Old != New && "Cannot changeExitBlock to the same thing!");
-  assert(Old && New && "Cannot changeExitBlock to or from a null node!");
-  assert(hasExitBlock(Old) && "Old exit block not found!");
-  std::vector<BasicBlock*>::iterator
-    I = std::find(ExitBlocks.begin(), ExitBlocks.end(), Old);
-  while (I != ExitBlocks.end()) {
-    *I = New;
-    I = std::find(I+1, ExitBlocks.end(), Old);
-  }
-}
-
 /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
 /// the OldChild entry in our children list with NewChild, and updates the
 /// parent pointers of the two loops as appropriate.
@@ -550,15 +530,4 @@ Loop *Loop::removeChildLoop(iterator I) {
 /// does not update the mapping in the LoopInfo class.
 void Loop::removeBlockFromLoop(BasicBlock *BB) {
   RemoveFromVector(Blocks, BB);
-
-  // If this block branched out of this loop, remove any exit blocks entries due
-  // to it.
-  for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
-    if (!contains(*SI) && *SI != BB)
-      RemoveFromVector(ExitBlocks, *SI);
-
-  // If any blocks in this loop branch to BB, add it to the exit blocks set.
-  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
-    if (contains(*PI))
-      ExitBlocks.push_back(BB);
 }
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index b93deb2d69..2bf5e5486a 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -1452,11 +1452,13 @@ SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) {
 /// will iterate.
 SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
   // If the loop has a non-one exit block count, we can't analyze it.
-  if (L->getExitBlocks().size() != 1) return UnknownValue;
+  std::vector<BasicBlock*> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  if (ExitBlocks.size() != 1) return UnknownValue;
 
   // Okay, there is one exit block.  Try to find the condition that causes the
   // loop to be exited.
-  BasicBlock *ExitBlock = L->getExitBlocks()[0];
+  BasicBlock *ExitBlock = ExitBlocks[0];
 
   BasicBlock *ExitingBlock = 0;
   for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
@@ -2293,7 +2295,10 @@ static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
     PrintLoopInfo(OS, SE, *I);
   
   std::cerr << "Loop " << L->getHeader()->getName() << ": ";
-  if (L->getExitBlocks().size() != 1)
+
+  std::vector<BasicBlock*> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  if (ExitBlocks.size() != 1)
     std::cerr << "<multiple exits> ";
 
   if (SE->hasLoopInvariantIterationCount(L)) {
diff --git a/lib/Transforms/IPO/LoopExtractor.cpp b/lib/Transforms/IPO/LoopExtractor.cpp
index 6b033b4082..65f9514874 100644
--- a/lib/Transforms/IPO/LoopExtractor.cpp
+++ b/lib/Transforms/IPO/LoopExtractor.cpp
@@ -92,8 +92,10 @@ bool LoopExtractor::runOnFunction(Function &F) {
     else {
       // Check to see if any exits from the loop are more than just return
       // blocks.
-      for (unsigned i = 0, e = TLL->getExitBlocks().size(); i != e; ++i)
-        if (!isa<ReturnInst>(TLL->getExitBlocks()[i]->getTerminator())) {
+      std::vector<BasicBlock*> ExitBlocks;
+      TLL->getExitBlocks(ExitBlocks);
+      for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
+        if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) {
           ShouldExtractLoop = true;
           break;
         }
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index d5eb668107..d375dcf4a9 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -185,8 +185,10 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
                                                ScalarEvolutionRewriter &RW) {
   // Find the exit block for the loop.  We can currently only handle loops with
   // a single exit.
-  if (L->getExitBlocks().size() != 1) return;
-  BasicBlock *ExitBlock = L->getExitBlocks()[0];
+  std::vector<BasicBlock*> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  if (ExitBlocks.size() != 1) return;
+  BasicBlock *ExitBlock = ExitBlocks[0];
 
   // Make sure there is only one predecessor block in the loop.
   BasicBlock *ExitingBlock = 0;
@@ -269,8 +271,10 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L) {
   // We insert the code into the preheader of the loop if the loop contains
   // multiple exit blocks, or in the exit block if there is exactly one.
   BasicBlock *BlockToInsertInto;
-  if (L->getExitBlocks().size() == 1)
-    BlockToInsertInto = L->getExitBlocks()[0];
+  std::vector<BasicBlock*> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  if (ExitBlocks.size() == 1)
+    BlockToInsertInto = ExitBlocks[0];
   else
     BlockToInsertInto = Preheader;
   BasicBlock::iterator InsertPt = BlockToInsertInto->begin();
diff --git a/lib/Transforms/Scalar/LoopUnroll.cpp b/lib/Transforms/Scalar/LoopUnroll.cpp
index 3794b81036..8cda34d109 100644
--- a/lib/Transforms/Scalar/LoopUnroll.cpp
+++ b/lib/Transforms/Scalar/LoopUnroll.cpp
@@ -109,18 +109,6 @@ static inline void RemapInstruction(Instruction *I,
   }
 }
 
-static void ChangeExitBlocksFromTo(Loop::iterator I, Loop::iterator E,
-                                   BasicBlock *Old, BasicBlock *New) {
-  for (; I != E; ++I) {
-    Loop *L = *I;
-    if (L->hasExitBlock(Old)) {
-      L->changeExitBlock(Old, New);
-      ChangeExitBlocksFromTo(L->begin(), L->end(), Old, New);
-    }
-  }
-}
-
-
 bool LoopUnroll::visitLoop(Loop *L) {
   bool Changed = false;
 
@@ -157,8 +145,7 @@ bool LoopUnroll::visitLoop(Loop *L) {
   }
   DEBUG(std::cerr << "UNROLLING!\n");
   
-  assert(L->getExitBlocks().size() == 1 && "Must have exactly one exit block!");
-  BasicBlock *LoopExit = L->getExitBlocks()[0];
+  BasicBlock *LoopExit = BI->getSuccessor(L->contains(BI->getSuccessor(0)));
 
   // Create a new basic block to temporarily hold all of the cloned code.
   BasicBlock *NewBlock = new BasicBlock();
@@ -292,14 +279,6 @@ bool LoopUnroll::visitLoop(Loop *L) {
   LI->removeBlock(Preheader);
   LI->removeBlock(BB);
 
-  // If any loops used Preheader as an exit block, update them to use LoopExit.
-  if (Parent)
-    ChangeExitBlocksFromTo(Parent->begin(), Parent->end(),
-                           Preheader, LoopExit);
-  else
-    ChangeExitBlocksFromTo(LI->begin(), LI->end(),
-                           Preheader, LoopExit);
-
   // If the preheader was the entry block of this function, move the exit block
   // to be the new entry of the loop.
   Function *F = LoopExit->getParent();
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index ada9cfd3f1..167075f3be 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -151,8 +151,10 @@ bool LoopSimplify::ProcessLoop(Loop *L) {
   // predecessors that are inside of the loop.  This check guarantees that the
   // loop preheader/header will dominate the exit blocks.  If the exit block has
   // predecessors from outside of the loop, split the edge now.
-  for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i) {
-    BasicBlock *ExitBlock = L->getExitBlocks()[i];
+  std::vector<BasicBlock*> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
+    BasicBlock *ExitBlock = ExitBlocks[i];
     for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
          PI != PE; ++PI)
       if (!L->contains(*PI)) {
@@ -269,19 +271,6 @@ BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB,
   return NewBB;
 }
 
-// ChangeExitBlock - This recursive function is used to change any exit blocks
-// that use OldExit to use NewExit instead.  This is recursive because children
-// may need to be processed as well.
-//
-static void ChangeExitBlock(Loop *L, BasicBlock *OldExit, BasicBlock *NewExit) {
-  if (L->hasExitBlock(OldExit)) {
-    L->changeExitBlock(OldExit, NewExit);
-    for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
-      ChangeExitBlock(*I, OldExit, NewExit);
-  }
-}
-
-
 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
 /// preheader, this method is called to insert one.  This method has two phases:
 /// preheader insertion and analysis updating.
@@ -323,11 +312,6 @@ void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
     ParentLoopsE = getAnalysis<LoopInfo>().end();
   }
 
-  // Loop over all sibling loops, performing the substitution (recursively to
-  // include child loops)...
-  for (; ParentLoops != ParentLoopsE; ++ParentLoops)
-    ChangeExitBlock(*ParentLoops, Header, NewBB);
-  
   DominatorSet &DS = getAnalysis<DominatorSet>();  // Update dominator info
   DominatorTree &DT = getAnalysis<DominatorTree>();
     
@@ -405,8 +389,6 @@ void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
 /// outside of the loop.
 void LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
   DominatorSet &DS = getAnalysis<DominatorSet>();
-  assert(std::find(L->getExitBlocks().begin(), L->getExitBlocks().end(), Exit)
-         != L->getExitBlocks().end() && "Not a current exit block!");
   
   std::vector<BasicBlock*> LoopBlocks;
   for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I)
@@ -421,11 +403,6 @@ void LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
   if (Loop *Parent = L->getParentLoop())
     Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>());
 
-  // Replace any instances of Exit with NewBB in this and any nested loops...
-  for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I)
-    if (I->hasExitBlock(Exit))
-      I->changeExitBlock(Exit, NewBB);   // Update exit block information
-
   // Update dominator information (set, immdom, domtree, and domfrontier)
   UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks);
 }
@@ -442,33 +419,6 @@ static void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock,
     AddBlockAndPredsToSet(*I, StopBlock, Blocks);
 }
 
-static void ReplaceExitBlocksOfLoopAndParents(Loop *L, BasicBlock *Old,
-                                              BasicBlock *New) {
-  if (!L->hasExitBlock(Old)) return;
-  L->changeExitBlock(Old, New);
-  ReplaceExitBlocksOfLoopAndParents(L->getParentLoop(), Old, New);
-}
-
-/// VerifyExitBlocks - This is a function which can be useful for hacking on the
-/// LoopSimplify Code.
-static void VerifyExitBlocks(Loop *L) {
-  std::vector<BasicBlock*> ExitBlocks;
-  for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) {
-    BasicBlock *BB = L->getBlocks()[i];
-    for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
-      if (!L->contains(*SI))
-        ExitBlocks.push_back(*SI);
-  }
-  
-  std::vector<BasicBlock*> EB = L->getExitBlocks();
-  std::sort(EB.begin(), EB.end());
-  std::sort(ExitBlocks.begin(), ExitBlocks.end());
-  assert(EB == ExitBlocks && "Exit blocks were incorrectly updated!");
-
-  for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
-    VerifyExitBlocks(*I);
-}
-
 /// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
 /// PHI node that tells us how to partition the loops.
 static PHINode *FindPHIToPartitionLoops(Loop *L) {
@@ -545,16 +495,6 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
   // L is now a subloop of our outer loop.
   NewOuter->addChildLoop(L);
 
-  // Add all of L's exit blocks to the outer loop.
-  for (unsigned i = 0, e = L->getExitBlocks().size(); i != e; ++i)
-    NewOuter->addExitBlock(L->getExitBlocks()[i]);
-
-  // Add temporary exit block entries for NewBB.  Add one for each edge in L
-  // that goes to NewBB.
-  for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); PI != E; ++PI)
-    if (L->contains(*PI))
-      L->addExitBlock(NewBB);
-
   for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i)
     NewOuter->addBlockEntry(L->getBlocks()[i]);
 
@@ -588,16 +528,6 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
     }
   }
 
-  // Check all subloops of this loop, replacing any exit blocks that got
-  // revectored with the new basic block.
-  for (pred_iterator I = pred_begin(NewBB), E = pred_end(NewBB); I != E; ++I)
-    if (NewOuter->contains(*I)) {
-      // Change any exit blocks that used to go to Header to go to NewBB
-      // instead.
-      ReplaceExitBlocksOfLoopAndParents((Loop*)LI[*I], Header, NewBB);
-    }
-
-  //VerifyExitBlocks(NewOuter);
   return NewOuter;
 }
 
@@ -693,11 +623,6 @@ void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) {
   // loop and all parent loops.
   L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>());
 
-  // Replace any instances of Exit with NewBB in this and any nested loops...
-  for (df_iterator<Loop*> I = df_begin(L), E = df_end(L); I != E; ++I)
-    if (I->hasExitBlock(Header))
-      I->changeExitBlock(Header, BEBlock);   // Update exit block information
-
   // Update dominator information (set, immdom, domtree, and domfrontier)
   UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks);
 }