From e30c7631898de0a0fb9e4c61b9b8ef4ab4ace5d7 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Thu, 20 Feb 2003 00:17:17 +0000
Subject: [PATCH] Fix bug: 2003-02-19-LoopInfoNestingBug.ll

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5603 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/LoopInfo.cpp | 50 +++++++++++++++++++++++++++------------
 1 file changed, 35 insertions(+), 15 deletions(-)

diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index 002e5536245..21a50967e82 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -37,13 +37,12 @@ unsigned Loop::getNumBackEdges() const {
   unsigned numBackEdges = 0;
   BasicBlock *header = Blocks.front();
 
-  for (std::vector<BasicBlock*>::const_iterator i = Blocks.begin(), e = Blocks.end();
-       i != e; ++i) {
-    for (BasicBlock::succ_iterator Successor = succ_begin(*i), SEnd = succ_end(*i);
-	 Successor != SEnd; ++Successor) {
-      if (header == *Successor)
+  for (std::vector<BasicBlock*>::const_iterator I = Blocks.begin(),
+         E = Blocks.end(); I != E; ++I) {
+    for (BasicBlock::succ_iterator SI = succ_begin(*I), SE = succ_end(*I);
+         SI != SE; ++SI)
+      if (header == *SI)
 	++numBackEdges;
-    }
   }
   return numBackEdges;
 }
@@ -138,17 +137,38 @@ Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS) {
   // they start subloops of their own.
   //
   for (std::vector<BasicBlock*>::reverse_iterator I = L->Blocks.rbegin(),
-	 E = L->Blocks.rend(); I != E; ++I) {
+	 E = L->Blocks.rend(); I != E; ++I)
 
     // Check to see if this block starts a new loop
-    if (Loop *NewLoop = ConsiderForLoop(*I, DS)) {
-      L->SubLoops.push_back(NewLoop);
-      NewLoop->ParentLoop = L;
-    }
-  
-    if (BBMap.find(*I) == BBMap.end())
-      BBMap.insert(std::make_pair(*I, L));
-  }
+    if (*I != BB)
+      if (Loop *NewLoop = ConsiderForLoop(*I, DS)) {
+        L->SubLoops.push_back(NewLoop);
+        NewLoop->ParentLoop = L;
+      } else {
+        std::map<BasicBlock*, Loop*>::iterator BBMI = BBMap.lower_bound(*I);
+        if (BBMI == BBMap.end() || BBMI->first != *I) {  // Not in map yet...
+          BBMap.insert(BBMI, std::make_pair(*I, L));
+        } else {
+          // If this is already in the BBMap then this means that we already added
+          // a loop for it, but incorrectly added the loop to a higher level loop
+          // instead of the current loop we are creating.  Fix this now by moving
+          // the loop into the correct subloop.
+          //
+          Loop *SubLoop = BBMI->second;
+          Loop *OldSubLoopParent = SubLoop->getParentLoop();
+          if (OldSubLoopParent != L) {
+            // Remove SubLoop from OldSubLoopParent's list of subloops...
+            std::vector<Loop*>::iterator I =
+              std::find(OldSubLoopParent->SubLoops.begin(),
+                        OldSubLoopParent->SubLoops.end(), SubLoop);
+            assert(I != OldSubLoopParent->SubLoops.end()
+                   && "Loop parent doesn't contain loop?");
+            OldSubLoopParent->SubLoops.erase(I);
+            SubLoop->ParentLoop = L;
+            L->SubLoops.push_back(SubLoop);
+          }
+        }
+      }
 
   return L;
 }
-- 
2.34.1