Index: llvm/lib/Transforms/IPO/LoopExtractor.cpp =================================================================== --- llvm/lib/Transforms/IPO/LoopExtractor.cpp +++ llvm/lib/Transforms/IPO/LoopExtractor.cpp @@ -15,10 +15,11 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AssumptionCache.h" -#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Module.h" +#include "llvm/IR/OptBisect.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Transforms/IPO.h" @@ -35,16 +36,23 @@ STATISTIC(NumExtracted, "Number of loops extracted"); namespace { - struct LoopExtractor : public LoopPass { + struct LoopExtractor : public ModulePass { static char ID; // Pass identification, replacement for typeid + + // The number of natural loops to extract from the program into functions. unsigned NumLoops; explicit LoopExtractor(unsigned numLoops = ~0) - : LoopPass(ID), NumLoops(numLoops) { - initializeLoopExtractorPass(*PassRegistry::getPassRegistry()); - } + : ModulePass(ID), NumLoops(numLoops) { + initializeLoopExtractorPass(*PassRegistry::getPassRegistry()); + } - bool runOnLoop(Loop *L, LPPassManager &) override; + bool runOnModule(Module &M) override; + bool runOnFunction(Function &F); + + bool extractLoops(Loop::iterator From, Loop::iterator To, LoopInfo &LI, + DominatorTree &DT); + bool extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT); void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequiredID(BreakCriticalEdgesID); @@ -62,6 +70,7 @@ INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_END(LoopExtractor, "loop-extract", "Extract loops into new functions", false, false) @@ -82,81 +91,129 @@ // Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } -bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) { - if (skipLoop(L)) +bool LoopExtractor::runOnModule(Module &M) { + if (skipModule(M)) return false; - // Only visit top-level loops. - if (L->getParentLoop()) + if (M.empty()) return false; - // If LoopSimplify form is not available, stay out of trouble. - if (!L->isLoopSimplifyForm()) + if (!NumLoops) return false; - DominatorTree &DT = getAnalysis().getDomTree(); - LoopInfo &LI = getAnalysis().getLoopInfo(); bool Changed = false; + // The end of the function list may change (new functions will be added at the + // end), so we run from the first to the current last. + auto I = M.begin(), E = --M.end(); + while (true) { + Function &F = *I; + + Changed |= runOnFunction(F); + if (!NumLoops) + break; + + // If this is the last function. + if (I == E) + break; + + ++I; + } + return Changed; +} + +bool LoopExtractor::runOnFunction(Function &F) { + // Do not modify `optnone` functions. + if (F.hasOptNone()) + return false; + + if (F.empty()) + return false; + + LoopInfo &LI = getAnalysis(F).getLoopInfo(); + + // If there are no loops in the function. + if (LI.empty()) + return false; + + DominatorTree &DT = getAnalysis(F).getDomTree(); + // If there is more than one top-level loop in this function, extract all of - // the loops. Otherwise there is exactly one top-level loop; in this case if - // this function is more than a minimal wrapper around the loop, extract - // the loop. - bool ShouldExtractLoop = false; - - // Extract the loop if the entry block doesn't branch to the loop header. - Instruction *EntryTI = - L->getHeader()->getParent()->getEntryBlock().getTerminator(); - if (!isa(EntryTI) || - !cast(EntryTI)->isUnconditional() || - EntryTI->getSuccessor(0) != L->getHeader()) { - ShouldExtractLoop = true; - } else { - // Check to see if any exits from the loop are more than just return - // blocks. - SmallVector ExitBlocks; - L->getExitBlocks(ExitBlocks); - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (!isa(ExitBlocks[i]->getTerminator())) { - ShouldExtractLoop = true; - break; - } + // the loops. + if (std::distance(LI.begin(), LI.end()) > 1) + return extractLoops(LI.begin(), LI.end(), LI, DT); + + // Otherwise there is exactly one top-level loop; in this case if this + // function is more than a minimal wrapper around the loop, extract the loop. + Loop *TLL = *LI.begin(); + + // If LoopSimplify form is not available, stay out of trouble. + if (TLL->isLoopSimplifyForm()) { + bool ShouldExtractLoop = false; + + // Extract the loop if the entry block doesn't branch to the loop header. + Instruction *EntryTI = F.getEntryBlock().getTerminator(); + if (!isa(EntryTI) || + !cast(EntryTI)->isUnconditional() || + EntryTI->getSuccessor(0) != TLL->getHeader()) { + ShouldExtractLoop = true; + } else { + // Check to see if any exits from the loop are more than just return + // blocks. + SmallVector ExitBlocks; + TLL->getExitBlocks(ExitBlocks); + for (auto *ExitBlock : ExitBlocks) + if (!isa(ExitBlock->getTerminator())) { + ShouldExtractLoop = true; + break; + } + } + + if (ShouldExtractLoop) + return extractLoop(TLL, LI, DT); } - if (ShouldExtractLoop) { - // We must omit EH pads. EH pads must accompany the invoke - // instruction. But this would result in a loop in the extracted - // function. An infinite cycle occurs when it tries to extract that loop as - // well. - SmallVector ExitBlocks; - L->getExitBlocks(ExitBlocks); - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (ExitBlocks[i]->isEHPad()) { - ShouldExtractLoop = false; - break; - } + // Okay, this function is a minimal container around the specified loop. + // If we extract the loop, we will continue to just keep extracting it + // infinitely... so don't extract it. However, if the loop contains any + // sub-loops, extract them. + return extractLoops(TLL->begin(), TLL->end(), LI, DT); +} + +bool LoopExtractor::extractLoops(Loop::iterator From, Loop::iterator To, + LoopInfo &LI, DominatorTree &DT) { + bool Changed = false; + SmallVector Loops; + + // Save the list of loops, as it may change. + Loops.assign(From, To); + for (Loop *L : Loops) { + // If LoopSimplify form is not available, stay out of trouble. + if (L->isLoopSimplifyForm()) + continue; + + Changed |= extractLoop(L, LI, DT); + if (!NumLoops) + break; } + return Changed; +} - if (ShouldExtractLoop) { - if (NumLoops == 0) return Changed; +bool LoopExtractor::extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT) { + assert(NumLoops != 0); + AssumptionCache *AC = nullptr; + Function &Func = *L->getHeader()->getParent(); + if (auto *ACT = getAnalysisIfAvailable()) + AC = ACT->lookupAssumptionCache(Func); + CodeExtractorAnalysisCache CEAC(Func); + CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC); + if (Extractor.extractCodeRegion(CEAC)) { + LI.erase(L); --NumLoops; - AssumptionCache *AC = nullptr; - Function &Func = *L->getHeader()->getParent(); - if (auto *ACT = getAnalysisIfAvailable()) - AC = ACT->lookupAssumptionCache(Func); - CodeExtractorAnalysisCache CEAC(Func); - CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC); - if (Extractor.extractCodeRegion(CEAC) != nullptr) { - Changed = true; - // After extraction, the loop is replaced by a function call, so - // we shouldn't try to run any more loop passes on it. - LPM.markLoopAsDeleted(*L); - LI.erase(L); - } ++NumExtracted; + return true; } - - return Changed; + return false; } // createSingleLoopExtractorPass - This pass extracts one natural loop from the