lib/Transforms/IPO/LoopExtractor.cpp

   1 //===- LoopExtractor.cpp - Extract each loop into a new function ----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // A pass wrapper around the ExtractLoop() scalar transformation to extract each
  10 // top-level loop into its own new function. If the loop is the ONLY loop in a
  11 // given function, it is not touched. This is a pass most useful for debugging
  12 // via bugpoint.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/ADT/Statistic.h"
  17 #include "llvm/Analysis/AssumptionCache.h"
  18 #include "llvm/Analysis/LoopPass.h"
  19 #include "llvm/IR/Dominators.h"
  20 #include "llvm/IR/Instructions.h"
  21 #include "llvm/IR/Module.h"
  22 #include "llvm/Pass.h"
  23 #include "llvm/Support/CommandLine.h"
  24 #include "llvm/Transforms/IPO.h"
  25 #include "llvm/Transforms/Scalar.h"
  26 #include "llvm/Transforms/Utils.h"
  27 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  28 #include "llvm/Transforms/Utils/CodeExtractor.h"
  29 #include <fstream>
  30 #include <set>
  31 using namespace llvm;
  32
  33 #define DEBUG_TYPE "loop-extract"
  34
  35 STATISTIC(NumExtracted, "Number of loops extracted");
  36
  37 namespace {
  38   struct LoopExtractor : public LoopPass {
  39     static char ID; // Pass identification, replacement for typeid
  40     unsigned NumLoops;
  41
  42     explicit LoopExtractor(unsigned numLoops = ~0)
  43       : LoopPass(ID), NumLoops(numLoops) {
  44         initializeLoopExtractorPass(*PassRegistry::getPassRegistry());
  45       }
  46
  47     bool runOnLoop(Loop *L, LPPassManager &) override;
  48
  49     void getAnalysisUsage(AnalysisUsage &AU) const override {
  50       AU.addRequiredID(BreakCriticalEdgesID);
  51       AU.addRequiredID(LoopSimplifyID);
  52       AU.addRequired<DominatorTreeWrapperPass>();
  53       AU.addRequired<LoopInfoWrapperPass>();
  54       AU.addUsedIfAvailable<AssumptionCacheTracker>();
  55     }
  56   };
  57 }
  58
  59 char LoopExtractor::ID = 0;
  60 INITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract",
  61                       "Extract loops into new functions", false, false)
  62 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
  63 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
  64 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  65 INITIALIZE_PASS_END(LoopExtractor, "loop-extract",
  66                     "Extract loops into new functions", false, false)
  67
  68 namespace {
  69   /// SingleLoopExtractor - For bugpoint.
  70   struct SingleLoopExtractor : public LoopExtractor {
  71     static char ID; // Pass identification, replacement for typeid
  72     SingleLoopExtractor() : LoopExtractor(1) {}
  73   };
  74 } // End anonymous namespace
  75
  76 char SingleLoopExtractor::ID = 0;
  77 INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single",
  78                 "Extract at most one loop into a new function", false, false)
  79
  80 // createLoopExtractorPass - This pass extracts all natural loops from the
  81 // program into a function if it can.
  82 //
  83 Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); }
  84
  85 bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) {
  86   if (skipLoop(L))
  87     return false;
  88
  89   // Only visit top-level loops.
  90   if (L->getParentLoop())
  91     return false;
  92
  93   // If LoopSimplify form is not available, stay out of trouble.
  94   if (!L->isLoopSimplifyForm())
  95     return false;
  96
  97   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  98   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  99   bool Changed = false;
 100
 101   // If there is more than one top-level loop in this function, extract all of
 102   // the loops. Otherwise there is exactly one top-level loop; in this case if
 103   // this function is more than a minimal wrapper around the loop, extract
 104   // the loop.
 105   bool ShouldExtractLoop = false;
 106
 107   // Extract the loop if the entry block doesn't branch to the loop header.
 108   Instruction *EntryTI =
 109       L->getHeader()->getParent()->getEntryBlock().getTerminator();
 110   if (!isa<BranchInst>(EntryTI) ||
 111       !cast<BranchInst>(EntryTI)->isUnconditional() ||
 112       EntryTI->getSuccessor(0) != L->getHeader()) {
 113     ShouldExtractLoop = true;
 114   } else {
 115     // Check to see if any exits from the loop are more than just return
 116     // blocks.
 117     SmallVector<BasicBlock*, 8> ExitBlocks;
 118     L->getExitBlocks(ExitBlocks);
 119     for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 120       if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) {
 121         ShouldExtractLoop = true;
 122         break;
 123       }
 124   }
 125
 126   if (ShouldExtractLoop) {
 127     // We must omit EH pads. EH pads must accompany the invoke
 128     // instruction. But this would result in a loop in the extracted
 129     // function. An infinite cycle occurs when it tries to extract that loop as
 130     // well.
 131     SmallVector<BasicBlock*, 8> ExitBlocks;
 132     L->getExitBlocks(ExitBlocks);
 133     for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 134       if (ExitBlocks[i]->isEHPad()) {
 135         ShouldExtractLoop = false;
 136         break;
 137       }
 138   }
 139
 140   if (ShouldExtractLoop) {
 141     if (NumLoops == 0) return Changed;
 142     --NumLoops;
 143     AssumptionCache *AC = nullptr;
 144     if (auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>())
 145       AC = ACT->lookupAssumptionCache(*L->getHeader()->getParent());
 146     CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC);
 147     if (Extractor.extractCodeRegion() != nullptr) {
 148       Changed = true;
 149       // After extraction, the loop is replaced by a function call, so
 150       // we shouldn't try to run any more loop passes on it.
 151       LPM.markLoopAsDeleted(*L);
 152       LI.erase(L);
 153     }
 154     ++NumExtracted;
 155   }
 156
 157   return Changed;
 158 }
 159
 160 // createSingleLoopExtractorPass - This pass extracts one natural loop from the
 161 // program into a function if it can.  This is used by bugpoint.
 162 //
 163 Pass *llvm::createSingleLoopExtractorPass() {
 164   return new SingleLoopExtractor();
 165 }