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 bool LoopExtractor::runOnFunction(Function &F) { 00062 LoopInfo &LI = getAnalysis<LoopInfo>(); 00063 00064 // If this function has no loops, there is nothing to do. 00065 if (LI.begin() == LI.end()) 00066 return false; 00067 00068 DominatorSet &DS = getAnalysis<DominatorSet>(); 00069 00070 // If there is more than one top-level loop in this function, extract all of 00071 // the loops. 00072 bool Changed = false; 00073 if (LI.end()-LI.begin() > 1) { 00074 for (LoopInfo::iterator i = LI.begin(), e = LI.end(); i != e; ++i) { 00075 if (NumLoops == 0) return Changed; 00076 --NumLoops; 00077 Changed |= ExtractLoop(DS, *i) != 0; 00078 ++NumExtracted; 00079 } 00080 } else { 00081 // Otherwise there is exactly one top-level loop. If this function is more 00082 // than a minimal wrapper around the loop, extract the loop. 00083 Loop *TLL = *LI.begin(); 00084 bool ShouldExtractLoop = false; 00085 00086 // Extract the loop if the entry block doesn't branch to the loop header. 00087 TerminatorInst *EntryTI = F.getEntryBlock().getTerminator(); 00088 if (!isa<BranchInst>(EntryTI) || 00089 !cast<BranchInst>(EntryTI)->isUnconditional() || 00090 EntryTI->getSuccessor(0) != TLL->getHeader()) 00091 ShouldExtractLoop = true; 00092 else { 00093 // Check to see if any exits from the loop are more than just return 00094 // blocks. 00095 std::vector<BasicBlock*> ExitBlocks; 00096 TLL->getExitBlocks(ExitBlocks); 00097 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 00098 if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) { 00099 ShouldExtractLoop = true; 00100 break; 00101 } 00102 } 00103 00104 if (ShouldExtractLoop) { 00105 if (NumLoops == 0) return Changed; 00106 --NumLoops; 00107 Changed |= ExtractLoop(DS, TLL) != 0; 00108 ++NumExtracted; 00109 } else { 00110 // Okay, this function is a minimal container around the specified loop. 00111 // If we extract the loop, we will continue to just keep extracting it 00112 // infinitely... so don't extract it. However, if the loop contains any 00113 // subloops, extract them. 00114 for (Loop::iterator i = TLL->begin(), e = TLL->end(); i != e; ++i) { 00115 if (NumLoops == 0) return Changed; 00116 --NumLoops; 00117 Changed |= ExtractLoop(DS, *i) != 0; 00118 ++NumExtracted; 00119 } 00120 } 00121 } 00122 00123 return Changed; 00124 } 00125 00126 // createSingleLoopExtractorPass - This pass extracts one natural loop from the 00127 // program into a function if it can. This is used by bugpoint. 00128 // 00129 ModulePass *llvm::createSingleLoopExtractorPass() { 00130 return new SingleLoopExtractor(); 00131 } 00132 00133 00134 namespace { 00135 /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 00136 /// from the module into their own functions except for those specified by the 00137 /// BlocksToNotExtract list. 00138 class BlockExtractorPass : public ModulePass { 00139 std::vector<BasicBlock*> BlocksToNotExtract; 00140 public: 00141 BlockExtractorPass(std::vector<BasicBlock*> &B) : BlocksToNotExtract(B) {} 00142 BlockExtractorPass() {} 00143 00144 bool runOnModule(Module &M); 00145 }; 00146 RegisterOpt<BlockExtractorPass> 00147 XX("extract-blocks", "Extract Basic Blocks From Module (for bugpoint use)"); 00148 } 00149 00150 // createBlockExtractorPass - This pass extracts all blocks (except those 00151 // specified in the argument list) from the functions in the module. 00152 // 00153 ModulePass *llvm::createBlockExtractorPass(std::vector<BasicBlock*> &BTNE) { 00154 return new BlockExtractorPass(BTNE); 00155 } 00156 00157 bool BlockExtractorPass::runOnModule(Module &M) { 00158 std::set<BasicBlock*> TranslatedBlocksToNotExtract; 00159 for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 00160 BasicBlock *BB = BlocksToNotExtract[i]; 00161 Function *F = BB->getParent(); 00162 00163 // Map the corresponding function in this module. 00164 Function *MF = M.getFunction(F->getName(), F->getFunctionType()); 00165 00166 // Figure out which index the basic block is in its function. 00167 Function::iterator BBI = MF->begin(); 00168 std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 00169 TranslatedBlocksToNotExtract.insert(BBI); 00170 } 00171 00172 // Now that we know which blocks to not extract, figure out which ones we WANT 00173 // to extract. 00174 std::vector<BasicBlock*> BlocksToExtract; 00175 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 00176 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 00177 if (!TranslatedBlocksToNotExtract.count(BB)) 00178 BlocksToExtract.push_back(BB); 00179 00180 for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) 00181 ExtractBasicBlock(BlocksToExtract[i]); 00182 00183 return !BlocksToExtract.empty(); 00184 }