1 files changed, 125 insertions, 67 deletions

diff --git a/llvm/lib/Transforms/IPO/LoopExtractor.cpp b/llvm/lib/Transforms/IPO/LoopExtractor.cpp
index f7108e8002ac9..f7f5b4cf67041 100644
--- a/llvm/lib/Transforms/IPO/LoopExtractor.cpp
+++ b/llvm/lib/Transforms/IPO/LoopExtractor.cpp
@@ -15,7 +15,7 @@
 
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
@@ -36,22 +36,30 @@ using namespace llvm;
 STATISTIC(NumExtracted, "Number of loops extracted");
 
 namespace {
-  struct LoopExtractor : public LoopPass {
+  struct LoopExtractor : public ModulePass {
     static char ID; // Pass identification, replacement for typeid
+
+    // The number of natural loops to extract from the program into functions.
     unsigned NumLoops;
 
     explicit LoopExtractor(unsigned numLoops = ~0)
-      : LoopPass(ID), NumLoops(numLoops) {
-        initializeLoopExtractorPass(*PassRegistry::getPassRegistry());
-      }
+        : ModulePass(ID), NumLoops(numLoops) {
+      initializeLoopExtractorPass(*PassRegistry::getPassRegistry());
+    }
 
-    bool runOnLoop(Loop *L, LPPassManager &) override;
+    bool runOnModule(Module &M) override;
+    bool runOnFunction(Function &F);
+
+    bool extractLoops(Loop::iterator From, Loop::iterator To, LoopInfo &LI,
+                      DominatorTree &DT);
+    bool extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT);
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequiredID(BreakCriticalEdgesID);
-      AU.addRequiredID(LoopSimplifyID);
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addRequired<LoopInfoWrapperPass>();
+      AU.addPreserved<LoopInfoWrapperPass>();
+      AU.addRequiredID(LoopSimplifyID);
       AU.addUsedIfAvailable<AssumptionCacheTracker>();
     }
   };
@@ -61,8 +69,9 @@ char LoopExtractor::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract",
                       "Extract loops into new functions", false, false)
 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
-INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_END(LoopExtractor, "loop-extract",
                     "Extract loops into new functions", false, false)
 
@@ -83,81 +92,130 @@ INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single",
 //
 Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); }
 
-bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) {
-  if (skipLoop(L))
+bool LoopExtractor::runOnModule(Module &M) {
+  if (skipModule(M))
+    return false;
+
+  if (M.empty())
+    return false;
+
+  if (!NumLoops)
     return false;
 
-  // Only visit top-level loops.
-  if (L->getParentLoop())
+  bool Changed = false;
+
+  // The end of the function list may change (new functions will be added at the
+  // end), so we run from the first to the current last.
+  auto I = M.begin(), E = --M.end();
+  while (true) {
+    Function &F = *I;
+
+    Changed |= runOnFunction(F);
+    if (!NumLoops)
+      break;
+
+    // If this is the last function.
+    if (I == E)
+      break;
+
+    ++I;
+  }
+  return Changed;
+}
+
+bool LoopExtractor::runOnFunction(Function &F) {
+  // Do not modify `optnone` functions.
+  if (F.hasOptNone())
     return false;
 
-  // If LoopSimplify form is not available, stay out of trouble.
-  if (!L->isLoopSimplifyForm())
+  if (F.empty())
     return false;
 
-  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   bool Changed = false;
+  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>(F, &Changed).getLoopInfo();
+
+  // If there are no loops in the function.
+  if (LI.empty())
+    return Changed;
+
+  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 
   // If there is more than one top-level loop in this function, extract all of
-  // the loops. Otherwise there is exactly one top-level loop; in this case if
-  // this function is more than a minimal wrapper around the loop, extract
-  // the loop.
-  bool ShouldExtractLoop = false;
-
-  // Extract the loop if the entry block doesn't branch to the loop header.
-  Instruction *EntryTI =
-      L->getHeader()->getParent()->getEntryBlock().getTerminator();
-  if (!isa<BranchInst>(EntryTI) ||
-      !cast<BranchInst>(EntryTI)->isUnconditional() ||
-      EntryTI->getSuccessor(0) != L->getHeader()) {
-    ShouldExtractLoop = true;
-  } else {
-    // Check to see if any exits from the loop are more than just return
-    // blocks.
-    SmallVector<BasicBlock*, 8> ExitBlocks;
-    L->getExitBlocks(ExitBlocks);
-    for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
-      if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) {
-        ShouldExtractLoop = true;
-        break;
-      }
+  // the loops.
+  if (std::next(LI.begin()) != LI.end())
+    return Changed | extractLoops(LI.begin(), LI.end(), LI, DT);
+
+  // Otherwise there is exactly one top-level loop.
+  Loop *TLL = *LI.begin();
+
+  // If the loop is in LoopSimplify form, then extract it only if this function
+  // is more than a minimal wrapper around the loop.
+  if (TLL->isLoopSimplifyForm()) {
+    bool ShouldExtractLoop = false;
+
+    // Extract the loop if the entry block doesn't branch to the loop header.
+    Instruction *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.
+      SmallVector<BasicBlock *, 8> ExitBlocks;
+      TLL->getExitBlocks(ExitBlocks);
+      for (auto *ExitBlock : ExitBlocks)
+        if (!isa<ReturnInst>(ExitBlock->getTerminator())) {
+          ShouldExtractLoop = true;
+          break;
+        }
+    }
+
+    if (ShouldExtractLoop)
+      return Changed | extractLoop(TLL, LI, DT);
   }
 
-  if (ShouldExtractLoop) {
-    // We must omit EH pads. EH pads must accompany the invoke
-    // instruction. But this would result in a loop in the extracted
-    // function. An infinite cycle occurs when it tries to extract that loop as
-    // well.
-    SmallVector<BasicBlock*, 8> ExitBlocks;
-    L->getExitBlocks(ExitBlocks);
-    for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
-      if (ExitBlocks[i]->isEHPad()) {
-        ShouldExtractLoop = false;
-        break;
-      }
+  // 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
+  // sub-loops, extract them.
+  return Changed | extractLoops(TLL->begin(), TLL->end(), LI, DT);
+}
+
+bool LoopExtractor::extractLoops(Loop::iterator From, Loop::iterator To,
+                                 LoopInfo &LI, DominatorTree &DT) {
+  bool Changed = false;
+  SmallVector<Loop *, 8> Loops;
+
+  // Save the list of loops, as it may change.
+  Loops.assign(From, To);
+  for (Loop *L : Loops) {
+    // If LoopSimplify form is not available, stay out of trouble.
+    if (!L->isLoopSimplifyForm())
+      continue;
+
+    Changed |= extractLoop(L, LI, DT);
+    if (!NumLoops)
+      break;
   }
+  return Changed;
+}
 
-  if (ShouldExtractLoop) {
-    if (NumLoops == 0) return Changed;
+bool LoopExtractor::extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT) {
+  assert(NumLoops != 0);
+  AssumptionCache *AC = nullptr;
+  Function &Func = *L->getHeader()->getParent();
+  if (auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>())
+    AC = ACT->lookupAssumptionCache(Func);
+  CodeExtractorAnalysisCache CEAC(Func);
+  CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC);
+  if (Extractor.extractCodeRegion(CEAC)) {
+    LI.erase(L);
     --NumLoops;
-    AssumptionCache *AC = nullptr;
-    Function &Func = *L->getHeader()->getParent();
-    if (auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>())
-      AC = ACT->lookupAssumptionCache(Func);
-    CodeExtractorAnalysisCache CEAC(Func);
-    CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC);
-    if (Extractor.extractCodeRegion(CEAC) != nullptr) {
-      Changed = true;
-      // After extraction, the loop is replaced by a function call, so
-      // we shouldn't try to run any more loop passes on it.
-      LPM.markLoopAsDeleted(*L);
-      LI.erase(L);
-    }
     ++NumExtracted;
+    return true;
   }
-
-  return Changed;
+  return false;
 }
 
 // createSingleLoopExtractorPass - This pass extracts one natural loop from the