lib/Transforms/IPO/LoopExtractor.cpp

   1 //===- LoopExtractor.cpp - Extract each loop into a new function ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // A pass wrapper around the ExtractLoop() scalar transformation to extract each
  11 // top-level loop into its own new function. If the loop is the ONLY loop in a
  12 // given function, it is not touched. This is a pass most useful for debugging
  13 // via bugpoint.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "loop-extract"
  18 #include "llvm/Transforms/IPO.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Module.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/Analysis/Dominators.h"
  23 #include "llvm/Analysis/LoopPass.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/Compiler.h"
  26 #include "llvm/Transforms/Scalar.h"
  27 #include "llvm/Transforms/Utils/FunctionUtils.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include <fstream>
  30 #include <set>
  31 using namespace llvm;
  32
  33 STATISTIC(NumExtracted, "Number of loops extracted");
  34
  35 namespace {
  36   struct VISIBILITY_HIDDEN LoopExtractor : public LoopPass {
  37     static char ID; // Pass identification, replacement for typeid
  38     unsigned NumLoops;
  39
  40     explicit LoopExtractor(unsigned numLoops = ~0)
  41       : LoopPass(&ID), NumLoops(numLoops) {}
  42
  43     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
  44
  45     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  46       AU.addRequiredID(BreakCriticalEdgesID);
  47       AU.addRequiredID(LoopSimplifyID);
  48       AU.addRequired<DominatorTree>();
  49     }
  50   };
  51 }
  52
  53 char LoopExtractor::ID = 0;
  54 static RegisterPass<LoopExtractor>
  55 X("loop-extract", "Extract loops into new functions");
  56
  57 namespace {
  58   /// SingleLoopExtractor - For bugpoint.
  59   struct SingleLoopExtractor : public LoopExtractor {
  60     static char ID; // Pass identification, replacement for typeid
  61     SingleLoopExtractor() : LoopExtractor(1) {}
  62   };
  63 } // End anonymous namespace
  64
  65 char SingleLoopExtractor::ID = 0;
  66 static RegisterPass<SingleLoopExtractor>
  67 Y("loop-extract-single", "Extract at most one loop into a new function");
  68
  69 // createLoopExtractorPass - This pass extracts all natural loops from the
  70 // program into a function if it can.
  71 //
  72 Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); }
  73
  74 bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) {
  75   // Only visit top-level loops.
  76   if (L->getParentLoop())
  77     return false;
  78
  79   DominatorTree &DT = getAnalysis<DominatorTree>();
  80   bool Changed = false;
  81
  82   // If there is more than one top-level loop in this function, extract all of
  83   // the loops. Otherwise there is exactly one top-level loop; in this case if
  84   // this function is more than a minimal wrapper around the loop, extract
  85   // the loop.
  86   bool ShouldExtractLoop = false;
  87
  88   // Extract the loop if the entry block doesn't branch to the loop header.
  89   TerminatorInst *EntryTI =
  90     L->getHeader()->getParent()->getEntryBlock().getTerminator();
  91   if (!isa<BranchInst>(EntryTI) ||
  92       !cast<BranchInst>(EntryTI)->isUnconditional() ||
  93       EntryTI->getSuccessor(0) != L->getHeader())
  94     ShouldExtractLoop = true;
  95   else {
  96     // Check to see if any exits from the loop are more than just return
  97     // blocks.
  98     SmallVector<BasicBlock*, 8> ExitBlocks;
  99     L->getExitBlocks(ExitBlocks);
 100     for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 101       if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) {
 102         ShouldExtractLoop = true;
 103         break;
 104       }
 105   }
 106   if (ShouldExtractLoop) {
 107     if (NumLoops == 0) return Changed;
 108     --NumLoops;
 109     if (ExtractLoop(DT, L) != 0) {
 110       Changed = true;
 111       // After extraction, the loop is replaced by a function call, so
 112       // we shouldn't try to run any more loop passes on it.
 113       LPM.deleteLoopFromQueue(L);
 114     }
 115     ++NumExtracted;
 116   }
 117
 118   return Changed;
 119 }
 120
 121 // createSingleLoopExtractorPass - This pass extracts one natural loop from the
 122 // program into a function if it can.  This is used by bugpoint.
 123 //
 124 Pass *llvm::createSingleLoopExtractorPass() {
 125   return new SingleLoopExtractor();
 126 }
 127
 128
 129 // BlockFile - A file which contains a list of blocks that should not be
 130 // extracted.
 131 static cl::opt<std::string>
 132 BlockFile("extract-blocks-file", cl::value_desc("filename"),
 133           cl::desc("A file containing list of basic blocks to not extract"),
 134           cl::Hidden);
 135
 136 namespace {
 137   /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks
 138   /// from the module into their own functions except for those specified by the
 139   /// BlocksToNotExtract list.
 140   class BlockExtractorPass : public ModulePass {
 141     void LoadFile(const char *Filename);
 142
 143     std::vector<BasicBlock*> BlocksToNotExtract;
 144     std::vector<std::pair<std::string, std::string> > BlocksToNotExtractByName;
 145   public:
 146     static char ID; // Pass identification, replacement for typeid
 147     explicit BlockExtractorPass(const std::vector<BasicBlock*> &B)
 148       : ModulePass(&ID), BlocksToNotExtract(B) {
 149       if (!BlockFile.empty())
 150         LoadFile(BlockFile.c_str());
 151     }
 152     BlockExtractorPass() : ModulePass(&ID) {}
 153
 154     bool runOnModule(Module &M);
 155   };
 156 }
 157
 158 char BlockExtractorPass::ID = 0;
 159 static RegisterPass<BlockExtractorPass>
 160 XX("extract-blocks", "Extract Basic Blocks From Module (for bugpoint use)");
 161
 162 // createBlockExtractorPass - This pass extracts all blocks (except those
 163 // specified in the argument list) from the functions in the module.
 164 //
 165 ModulePass *llvm::createBlockExtractorPass(const std::vector<BasicBlock*> &BTNE)
 166 {
 167   return new BlockExtractorPass(BTNE);
 168 }
 169
 170 void BlockExtractorPass::LoadFile(const char *Filename) {
 171   // Load the BlockFile...
 172   std::ifstream In(Filename);
 173   if (!In.good()) {
 174     errs() << "WARNING: BlockExtractor couldn't load file '" << Filename
 175            << "'!\n";
 176     return;
 177   }
 178   while (In) {
 179     std::string FunctionName, BlockName;
 180     In >> FunctionName;
 181     In >> BlockName;
 182     if (!BlockName.empty())
 183       BlocksToNotExtractByName.push_back(
 184           std::make_pair(FunctionName, BlockName));
 185   }
 186 }
 187
 188 bool BlockExtractorPass::runOnModule(Module &M) {
 189   std::set<BasicBlock*> TranslatedBlocksToNotExtract;
 190   for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) {
 191     BasicBlock *BB = BlocksToNotExtract[i];
 192     Function *F = BB->getParent();
 193
 194     // Map the corresponding function in this module.
 195     Function *MF = M.getFunction(F->getName());
 196     assert(MF->getFunctionType() == F->getFunctionType() && "Wrong function?");
 197
 198     // Figure out which index the basic block is in its function.
 199     Function::iterator BBI = MF->begin();
 200     std::advance(BBI, std::distance(F->begin(), Function::iterator(BB)));
 201     TranslatedBlocksToNotExtract.insert(BBI);
 202   }
 203
 204   while (!BlocksToNotExtractByName.empty()) {
 205     // There's no way to find BBs by name without looking at every BB inside
 206     // every Function. Fortunately, this is always empty except when used by
 207     // bugpoint in which case correctness is more important than performance.
 208
 209     std::string &FuncName  = BlocksToNotExtractByName.back().first;
 210     std::string &BlockName = BlocksToNotExtractByName.back().second;
 211
 212     for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) {
 213       Function &F = *FI;
 214       if (F.getName() != FuncName) continue;
 215
 216       for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
 217         BasicBlock &BB = *BI;
 218         if (BB.getName() != BlockName) continue;
 219
 220         TranslatedBlocksToNotExtract.insert(BI);
 221       }
 222     }
 223
 224     BlocksToNotExtractByName.pop_back();
 225   }
 226
 227   // Now that we know which blocks to not extract, figure out which ones we WANT
 228   // to extract.
 229   std::vector<BasicBlock*> BlocksToExtract;
 230   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
 231     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 232       if (!TranslatedBlocksToNotExtract.count(BB))
 233         BlocksToExtract.push_back(BB);
 234
 235   for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i)
 236     ExtractBasicBlock(BlocksToExtract[i]);
 237
 238   return !BlocksToExtract.empty();
 239 }