LoopExtractor.cpp revision 3e15bf33e024b9df9e89351a165acfdb1dde51ed
1//===- LoopExtractor.cpp - Extract each loop into a new function ----------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/LoopInfo.h" 24#include "llvm/Support/Compiler.h" 25#include "llvm/Transforms/Scalar.h" 26#include "llvm/Transforms/Utils/FunctionUtils.h" 27#include "llvm/ADT/Statistic.h" 28using namespace llvm; 29 30STATISTIC(NumExtracted, "Number of loops extracted"); 31 32namespace { 33 // FIXME: This is not a function pass, but the PassManager doesn't allow 34 // Module passes to require FunctionPasses, so we can't get loop info if we're 35 // not a function pass. 36 struct VISIBILITY_HIDDEN LoopExtractor : public FunctionPass { 37 static const char ID; // Pass identifcation, replacement for typeid 38 unsigned NumLoops; 39 40 LoopExtractor(unsigned numLoops = ~0) 41 : FunctionPass((intptr_t)&ID), NumLoops(numLoops) {} 42 43 virtual bool runOnFunction(Function &F); 44 45 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 46 AU.addRequiredID(BreakCriticalEdgesID); 47 AU.addRequiredID(LoopSimplifyID); 48 AU.addRequired<ETForest>(); 49 AU.addRequired<DominatorTree>(); 50 AU.addRequired<LoopInfo>(); 51 } 52 }; 53 54 const char LoopExtractor::ID = 0; 55 RegisterPass<LoopExtractor> 56 X("loop-extract", "Extract loops into new functions"); 57 58 /// SingleLoopExtractor - For bugpoint. 59 struct SingleLoopExtractor : public LoopExtractor { 60 static const char ID; // Pass identifcation, replacement for typeid 61 SingleLoopExtractor() : LoopExtractor(1) {} 62 }; 63 64 const char SingleLoopExtractor::ID = 0; 65 RegisterPass<SingleLoopExtractor> 66 Y("loop-extract-single", "Extract at most one loop into a new function"); 67} // End anonymous namespace 68 69// createLoopExtractorPass - This pass extracts all natural loops from the 70// program into a function if it can. 71// 72FunctionPass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } 73 74bool LoopExtractor::runOnFunction(Function &F) { 75 LoopInfo &LI = getAnalysis<LoopInfo>(); 76 77 // If this function has no loops, there is nothing to do. 78 if (LI.begin() == LI.end()) 79 return false; 80 81 ETForest &EF = getAnalysis<ETForest>(); 82 DominatorTree &DT = getAnalysis<DominatorTree>(); 83 84 // If there is more than one top-level loop in this function, extract all of 85 // the loops. 86 bool Changed = false; 87 if (LI.end()-LI.begin() > 1) { 88 for (LoopInfo::iterator i = LI.begin(), e = LI.end(); i != e; ++i) { 89 if (NumLoops == 0) return Changed; 90 --NumLoops; 91 Changed |= ExtractLoop(EF, DT, *i) != 0; 92 ++NumExtracted; 93 } 94 } else { 95 // Otherwise there is exactly one top-level loop. If this function is more 96 // than a minimal wrapper around the loop, extract the loop. 97 Loop *TLL = *LI.begin(); 98 bool ShouldExtractLoop = false; 99 100 // Extract the loop if the entry block doesn't branch to the loop header. 101 TerminatorInst *EntryTI = F.getEntryBlock().getTerminator(); 102 if (!isa<BranchInst>(EntryTI) || 103 !cast<BranchInst>(EntryTI)->isUnconditional() || 104 EntryTI->getSuccessor(0) != TLL->getHeader()) 105 ShouldExtractLoop = true; 106 else { 107 // Check to see if any exits from the loop are more than just return 108 // blocks. 109 std::vector<BasicBlock*> ExitBlocks; 110 TLL->getExitBlocks(ExitBlocks); 111 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 112 if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) { 113 ShouldExtractLoop = true; 114 break; 115 } 116 } 117 118 if (ShouldExtractLoop) { 119 if (NumLoops == 0) return Changed; 120 --NumLoops; 121 Changed |= ExtractLoop(EF, DT, TLL) != 0; 122 ++NumExtracted; 123 } else { 124 // Okay, this function is a minimal container around the specified loop. 125 // If we extract the loop, we will continue to just keep extracting it 126 // infinitely... so don't extract it. However, if the loop contains any 127 // subloops, extract them. 128 for (Loop::iterator i = TLL->begin(), e = TLL->end(); i != e; ++i) { 129 if (NumLoops == 0) return Changed; 130 --NumLoops; 131 Changed |= ExtractLoop(EF, DT, *i) != 0; 132 ++NumExtracted; 133 } 134 } 135 } 136 137 return Changed; 138} 139 140// createSingleLoopExtractorPass - This pass extracts one natural loop from the 141// program into a function if it can. This is used by bugpoint. 142// 143FunctionPass *llvm::createSingleLoopExtractorPass() { 144 return new SingleLoopExtractor(); 145} 146 147 148namespace { 149 /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 150 /// from the module into their own functions except for those specified by the 151 /// BlocksToNotExtract list. 152 class BlockExtractorPass : public ModulePass { 153 std::vector<BasicBlock*> BlocksToNotExtract; 154 public: 155 static const char ID; // Pass identifcation, replacement for typeid 156 BlockExtractorPass(std::vector<BasicBlock*> &B) 157 : ModulePass((intptr_t)&ID), BlocksToNotExtract(B) {} 158 BlockExtractorPass() : ModulePass((intptr_t)&ID) {} 159 160 bool runOnModule(Module &M); 161 }; 162 163 const char BlockExtractorPass::ID = 0; 164 RegisterPass<BlockExtractorPass> 165 XX("extract-blocks", "Extract Basic Blocks From Module (for bugpoint use)"); 166} 167 168// createBlockExtractorPass - This pass extracts all blocks (except those 169// specified in the argument list) from the functions in the module. 170// 171ModulePass *llvm::createBlockExtractorPass(std::vector<BasicBlock*> &BTNE) { 172 return new BlockExtractorPass(BTNE); 173} 174 175bool BlockExtractorPass::runOnModule(Module &M) { 176 std::set<BasicBlock*> TranslatedBlocksToNotExtract; 177 for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 178 BasicBlock *BB = BlocksToNotExtract[i]; 179 Function *F = BB->getParent(); 180 181 // Map the corresponding function in this module. 182 Function *MF = M.getFunction(F->getName()); 183 assert(MF->getFunctionType() == F->getFunctionType() && "Wrong function?"); 184 185 // Figure out which index the basic block is in its function. 186 Function::iterator BBI = MF->begin(); 187 std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 188 TranslatedBlocksToNotExtract.insert(BBI); 189 } 190 191 // Now that we know which blocks to not extract, figure out which ones we WANT 192 // to extract. 193 std::vector<BasicBlock*> BlocksToExtract; 194 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 195 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 196 if (!TranslatedBlocksToNotExtract.count(BB)) 197 BlocksToExtract.push_back(BB); 198 199 for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) 200 ExtractBasicBlock(BlocksToExtract[i]); 201 202 return !BlocksToExtract.empty(); 203} 204