From 5156c39d6419c891b3004da505487091c418bf63 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Mon, 15 Mar 2004 00:02:02 +0000
Subject: [PATCH] Fix several bugs in the loop extractor.  In particular,
 subloops were never extracted, and a function that contained a single
 top-level loop never had the loop extracted, regardless of how much non-loop
 code there was.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12403 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/IPO/LoopExtractor.cpp | 56 ++++++++++++++++++++++++----
 1 file changed, 48 insertions(+), 8 deletions(-)

diff --git a/lib/Transforms/IPO/LoopExtractor.cpp b/lib/Transforms/IPO/LoopExtractor.cpp
index ce4d0f7e328..4161e41930e 100644
--- a/lib/Transforms/IPO/LoopExtractor.cpp
+++ b/lib/Transforms/IPO/LoopExtractor.cpp
@@ -15,6 +15,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO.h"
+#include "llvm/iTerminators.h"
 #include "llvm/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Analysis/LoopInfo.h"
@@ -54,17 +55,56 @@ namespace {
 bool LoopExtractor::runOnFunction(Function &F) {
   LoopInfo &LI = getAnalysis<LoopInfo>();
 
-  // We don't want to keep extracting the only loop of a function into a new one
-  if (LI.begin() == LI.end() || LI.begin() + 1 == LI.end())
+  // If this function has no loops, there is nothing to do.
+  if (LI.begin() == LI.end())
     return false;
 
+  // If there is more than one top-level loop in this function, extract all of
+  // the loops.
   bool Changed = false;
-
-  // Try to move each loop out of the code into separate function
-  for (LoopInfo::iterator i = LI.begin(), e = LI.end(); i != e; ++i) {
-    if (NumLoops == 0) return Changed;
-    --NumLoops;
-    Changed |= (ExtractLoop(*i) != 0);
+  if (LI.end()-LI.begin() > 1) {
+    for (LoopInfo::iterator i = LI.begin(), e = LI.end(); i != e; ++i) {
+      if (NumLoops == 0) return Changed;
+      --NumLoops;
+      Changed |= (ExtractLoop(*i) != 0);
+    }
+  } else {
+    // Otherwise there is exactly one top-level loop.  If this function is more
+    // than a minimal wrapper around the loop, extract the loop.
+    Loop *TLL = *LI.begin();
+    bool ShouldExtractLoop = false;
+    
+    // Extract the loop if the entry block doesn't branch to the loop header.
+    TerminatorInst *EntryTI = F.getEntryBlock().getTerminator();
+    if (!isa<BranchInst>(EntryTI) ||
+        !cast<BranchInst>(EntryTI)->isUnconditional() || 
+        EntryTI->getSuccessor(0) != TLL->getHeader())
+      ShouldExtractLoop = true;
+    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())) {
+          ShouldExtractLoop = true;
+          break;
+        }
+    }
+    
+    if (ShouldExtractLoop) {
+      if (NumLoops == 0) return Changed;
+      --NumLoops;
+      Changed |= (ExtractLoop(TLL) != 0);
+    } else {
+      // Okay, this function is a minimal container around the specified loop.
+      // If we extract the loop, we will continue to just keep extracting it
+      // infinitely... so don't extract it.  However, if the loop contains any
+      // subloops, extract them.
+      for (Loop::iterator i = TLL->begin(), e = TLL->end(); i != e; ++i) {
+        if (NumLoops == 0) return Changed;
+        --NumLoops;
+        Changed |= (ExtractLoop(*i) != 0);
+      }
+    }
   }
 
   return Changed;
-- 
2.34.1