LLVM API Documentation
00001 //===- LoopExtractor.cpp - Extract each loop into a new function ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // A pass wrapper around the ExtractLoop() scalar transformation to extract each 00011 // top-level loop into its own new function. If the loop is the ONLY loop in a 00012 // given function, it is not touched. This is a pass most useful for debugging 00013 // via bugpoint. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Transforms/IPO.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/Module.h" 00020 #include "llvm/Pass.h" 00021 #include "llvm/Analysis/Dominators.h" 00022 #include "llvm/Analysis/LoopInfo.h" 00023 #include "llvm/Transforms/Scalar.h" 00024 #include "llvm/Transforms/Utils/FunctionUtils.h" 00025 #include "llvm/ADT/Statistic.h" 00026 using namespace llvm; 00027 00028 namespace { 00029 Statistic<> NumExtracted("loop-extract", "Number of loops extracted"); 00030 00031 // FIXME: This is not a function pass, but the PassManager doesn't allow 00032 // Module passes to require FunctionPasses, so we can't get loop info if we're 00033 // not a function pass. 00034 struct LoopExtractor : public FunctionPass { 00035 unsigned NumLoops; 00036 00037 LoopExtractor(unsigned numLoops = ~0) : NumLoops(numLoops) {} 00038 00039 virtual bool runOnFunction(Function &F); 00040 00041 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00042 AU.addRequiredID(BreakCriticalEdgesID); 00043 AU.addRequiredID(LoopSimplifyID); 00044 AU.addRequired<DominatorSet>(); 00045 AU.addRequired<LoopInfo>(); 00046 } 00047 }; 00048 00049 RegisterOpt<LoopExtractor> 00050 X("loop-extract", "Extract loops into new functions"); 00051 00052 /// SingleLoopExtractor - For bugpoint. 00053 struct SingleLoopExtractor : public LoopExtractor { 00054 SingleLoopExtractor() : LoopExtractor(1) {} 00055 }; 00056 00057 RegisterOpt<SingleLoopExtractor> 00058 Y("loop-extract-single", "Extract at most one loop into a new function"); 00059 } // End anonymous namespace 00060 00061 // createLoopExtractorPass - This pass extracts all natural loops from the 00062 // program into a function if it can. 00063 // 00064 FunctionPass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } 00065 00066 bool LoopExtractor::runOnFunction(Function &F) { 00067 LoopInfo &LI = getAnalysis<LoopInfo>(); 00068 00069 // If this function has no loops, there is nothing to do. 00070 if (LI.begin() == LI.end()) 00071 return false; 00072 00073 DominatorSet &DS = getAnalysis<DominatorSet>(); 00074 00075 // If there is more than one top-level loop in this function, extract all of 00076 // the loops. 00077 bool Changed = false; 00078 if (LI.end()-LI.begin() > 1) { 00079 for (LoopInfo::iterator i = LI.begin(), e = LI.end(); i != e; ++i) { 00080 if (NumLoops == 0) return Changed; 00081 --NumLoops; 00082 Changed |= ExtractLoop(DS, *i) != 0; 00083 ++NumExtracted; 00084 } 00085 } else { 00086 // Otherwise there is exactly one top-level loop. If this function is more 00087 // than a minimal wrapper around the loop, extract the loop. 00088 Loop *TLL = *LI.begin(); 00089 bool ShouldExtractLoop = false; 00090 00091 // Extract the loop if the entry block doesn't branch to the loop header. 00092 TerminatorInst *EntryTI = F.getEntryBlock().getTerminator(); 00093 if (!isa<BranchInst>(EntryTI) || 00094 !cast<BranchInst>(EntryTI)->isUnconditional() || 00095 EntryTI->getSuccessor(0) != TLL->getHeader()) 00096 ShouldExtractLoop = true; 00097 else { 00098 // Check to see if any exits from the loop are more than just return 00099 // blocks. 00100 std::vector<BasicBlock*> ExitBlocks; 00101 TLL->getExitBlocks(ExitBlocks); 00102 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 00103 if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) { 00104 ShouldExtractLoop = true; 00105 break; 00106 } 00107 } 00108 00109 if (ShouldExtractLoop) { 00110 if (NumLoops == 0) return Changed; 00111 --NumLoops; 00112 Changed |= ExtractLoop(DS, TLL) != 0; 00113 ++NumExtracted; 00114 } else { 00115 // Okay, this function is a minimal container around the specified loop. 00116 // If we extract the loop, we will continue to just keep extracting it 00117 // infinitely... so don't extract it. However, if the loop contains any 00118 // subloops, extract them. 00119 for (Loop::iterator i = TLL->begin(), e = TLL->end(); i != e; ++i) { 00120 if (NumLoops == 0) return Changed; 00121 --NumLoops; 00122 Changed |= ExtractLoop(DS, *i) != 0; 00123 ++NumExtracted; 00124 } 00125 } 00126 } 00127 00128 return Changed; 00129 } 00130 00131 // createSingleLoopExtractorPass - This pass extracts one natural loop from the 00132 // program into a function if it can. This is used by bugpoint. 00133 // 00134 FunctionPass *llvm::createSingleLoopExtractorPass() { 00135 return new SingleLoopExtractor(); 00136 } 00137 00138 00139 namespace { 00140 /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 00141 /// from the module into their own functions except for those specified by the 00142 /// BlocksToNotExtract list. 00143 class BlockExtractorPass : public ModulePass { 00144 std::vector<BasicBlock*> BlocksToNotExtract; 00145 public: 00146 BlockExtractorPass(std::vector<BasicBlock*> &B) : BlocksToNotExtract(B) {} 00147 BlockExtractorPass() {} 00148 00149 bool runOnModule(Module &M); 00150 }; 00151 RegisterOpt<BlockExtractorPass> 00152 XX("extract-blocks", "Extract Basic Blocks From Module (for bugpoint use)"); 00153 } 00154 00155 // createBlockExtractorPass - This pass extracts all blocks (except those 00156 // specified in the argument list) from the functions in the module. 00157 // 00158 ModulePass *llvm::createBlockExtractorPass(std::vector<BasicBlock*> &BTNE) { 00159 return new BlockExtractorPass(BTNE); 00160 } 00161 00162 bool BlockExtractorPass::runOnModule(Module &M) { 00163 std::set<BasicBlock*> TranslatedBlocksToNotExtract; 00164 for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 00165 BasicBlock *BB = BlocksToNotExtract[i]; 00166 Function *F = BB->getParent(); 00167 00168 // Map the corresponding function in this module. 00169 Function *MF = M.getFunction(F->getName(), F->getFunctionType()); 00170 00171 // Figure out which index the basic block is in its function. 00172 Function::iterator BBI = MF->begin(); 00173 std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 00174 TranslatedBlocksToNotExtract.insert(BBI); 00175 } 00176 00177 // Now that we know which blocks to not extract, figure out which ones we WANT 00178 // to extract. 00179 std::vector<BasicBlock*> BlocksToExtract; 00180 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 00181 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 00182 if (!TranslatedBlocksToNotExtract.count(BB)) 00183 BlocksToExtract.push_back(BB); 00184 00185 for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) 00186 ExtractBasicBlock(BlocksToExtract[i]); 00187 00188 return !BlocksToExtract.empty(); 00189 }