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