X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopPass.cpp;h=a99c949e10f759bda04a127a78a8a5f818203644;hb=0ea25c2e64c98d820a5cac6d5ce229a7d8f4e3e4;hp=2727d2f9465c13102724455a981e0b755465d56e;hpb=434bd8551d71384648f2e155d76b5ddbc4d1b258;p=oota-llvm.git diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp index 2727d2f9465..a99c949e10f 100644 --- a/lib/Analysis/LoopPass.cpp +++ b/lib/Analysis/LoopPass.cpp @@ -14,11 +14,14 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopPass.h" -#include "llvm/Assembly/PrintModulePass.h" +#include "llvm/IR/IRPrintingPasses.h" +#include "llvm/IR/LLVMContext.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Timer.h" using namespace llvm; +#define DEBUG_TYPE "loop-pass-manager" + namespace { /// PrintLoopPass - Print a Function corresponding to a Loop. @@ -30,20 +33,22 @@ private: public: static char ID; - PrintLoopPass() : LoopPass(&ID), Out(dbgs()) {} PrintLoopPass(const std::string &B, raw_ostream &o) - : LoopPass(&ID), Banner(B), Out(o) {} + : LoopPass(ID), Banner(B), Out(o) {} - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); } - bool runOnLoop(Loop *L, LPPassManager &) { + bool runOnLoop(Loop *L, LPPassManager &) override { Out << Banner; for (Loop::block_iterator b = L->block_begin(), be = L->block_end(); b != be; ++b) { - (*b)->print(Out); + if (*b) + (*b)->print(Out); + else + Out << "Printing block"; } return false; } @@ -58,73 +63,32 @@ char PrintLoopPass::ID = 0; char LPPassManager::ID = 0; -LPPassManager::LPPassManager(int Depth) - : FunctionPass(&ID), PMDataManager(Depth) { +LPPassManager::LPPassManager() + : FunctionPass(ID), PMDataManager() { skipThisLoop = false; redoThisLoop = false; - LI = NULL; - CurrentLoop = NULL; + LI = nullptr; + CurrentLoop = nullptr; } -/// Delete loop from the loop queue and loop hierarchy (LoopInfo). +/// Delete loop from the loop queue and loop hierarchy (LoopInfo). void LPPassManager::deleteLoopFromQueue(Loop *L) { - if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop. - // Reparent all of the blocks in this loop. Since BBLoop had a parent, - // they are now all in it. - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) - if (LI->getLoopFor(*I) == L) // Don't change blocks in subloops. - LI->changeLoopFor(*I, ParentLoop); - - // Remove the loop from its parent loop. - for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; - ++I) { - assert(I != E && "Couldn't find loop"); - if (*I == L) { - ParentLoop->removeChildLoop(I); - break; - } - } - - // Move all subloops into the parent loop. - while (!L->empty()) - ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1)); - } else { - // Reparent all of the blocks in this loop. Since BBLoop had no parent, - // they no longer in a loop at all. - - for (unsigned i = 0; i != L->getBlocks().size(); ++i) { - // Don't change blocks in subloops. - if (LI->getLoopFor(L->getBlocks()[i]) == L) { - LI->removeBlock(L->getBlocks()[i]); - --i; - } - } - - // Remove the loop from the top-level LoopInfo object. - for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) { - assert(I != E && "Couldn't find loop"); - if (*I == L) { - LI->removeLoop(I); - break; - } - } - - // Move all of the subloops to the top-level. - while (!L->empty()) - LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); - } + LI->updateUnloop(L); - delete L; + // Notify passes that the loop is being deleted. + deleteSimpleAnalysisLoop(L); // If L is current loop then skip rest of the passes and let // runOnFunction remove L from LQ. Otherwise, remove L from LQ now // and continue applying other passes on CurrentLoop. - if (CurrentLoop == L) { + if (CurrentLoop == L) skipThisLoop = true; + + delete L; + + if (skipThisLoop) return; - } for (std::deque::iterator I = LQ.begin(), E = LQ.end(); I != E; ++I) { @@ -151,10 +115,10 @@ void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { void LPPassManager::insertLoopIntoQueue(Loop *L) { // Insert L into loop queue - if (L == CurrentLoop) + if (L == CurrentLoop) redoLoop(L); else if (!L->getParentLoop()) - // This is top level loop. + // This is top level loop. LQ.push_front(L); else { // Insert L after the parent loop. @@ -180,10 +144,10 @@ void LPPassManager::redoLoop(Loop *L) { /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for /// all loop passes. -void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, +void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { - for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { - LoopPass *LP = (LoopPass *)getContainedPass(Index); + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *LP = getContainedPass(Index); LP->cloneBasicBlockAnalysis(From, To, L); } } @@ -191,45 +155,62 @@ void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes. void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) { if (BasicBlock *BB = dyn_cast(V)) { - for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; + for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) { Instruction &I = *BI; deleteSimpleAnalysisValue(&I, L); } } - for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { - LoopPass *LP = (LoopPass *)getContainedPass(Index); + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *LP = getContainedPass(Index); LP->deleteAnalysisValue(V, L); } } +/// Invoke deleteAnalysisLoop hook for all passes. +void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) { + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *LP = getContainedPass(Index); + LP->deleteAnalysisLoop(L); + } +} + // Recurse through all subloops and all loops into LQ. static void addLoopIntoQueue(Loop *L, std::deque &LQ) { LQ.push_back(L); - for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) + for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I) addLoopIntoQueue(*I, LQ); } /// Pass Manager itself does not invalidate any analysis info. void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { - // LPPassManager needs LoopInfo. In the long term LoopInfo class will + // LPPassManager needs LoopInfo. In the long term LoopInfo class will // become part of LPPassManager. - Info.addRequired(); + Info.addRequired(); Info.setPreservesAll(); } /// run - Execute all of the passes scheduled for execution. Keep track of /// whether any of the passes modifies the function, and if so, return true. bool LPPassManager::runOnFunction(Function &F) { - LI = &getAnalysis(); + auto &LIWP = getAnalysis(); + LI = &LIWP.getLoopInfo(); bool Changed = false; // Collect inherited analysis from Module level pass manager. populateInheritedAnalysis(TPM->activeStack); - // Populate Loop Queue - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) + // Populate the loop queue in reverse program order. There is no clear need to + // process sibling loops in either forward or reverse order. There may be some + // advantage in deleting uses in a later loop before optimizing the + // definitions in an earlier loop. If we find a clear reason to process in + // forward order, then a forward variant of LoopPassManager should be created. + // + // Note that LoopInfo::iterator visits loops in reverse program + // order. Here, reverse_iterator gives us a forward order, and the LoopQueue + // reverses the order a third time by popping from the back. + for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I) addLoopIntoQueue(*I, LQ); if (LQ.empty()) // No loops, skip calling finalizers @@ -239,22 +220,22 @@ bool LPPassManager::runOnFunction(Function &F) { for (std::deque::const_iterator I = LQ.begin(), E = LQ.end(); I != E; ++I) { Loop *L = *I; - for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { - LoopPass *P = (LoopPass*)getContainedPass(Index); + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *P = getContainedPass(Index); Changed |= P->doInitialization(L, *this); } } // Walk Loops while (!LQ.empty()) { - + CurrentLoop = LQ.back(); skipThisLoop = false; redoThisLoop = false; // Run all passes on the current Loop. - for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { - LoopPass *P = (LoopPass*)getContainedPass(Index); + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *P = getContainedPass(Index); dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, CurrentLoop->getHeader()->getName()); @@ -282,12 +263,14 @@ bool LPPassManager::runOnFunction(Function &F) { // loop in the function every time. That level of checking can be // enabled with the -verify-loop-info option. { - TimeRegion PassTimer(getPassTimer(LI)); + TimeRegion PassTimer(getPassTimer(&LIWP)); CurrentLoop->verifyLoop(); } // Then call the regular verifyAnalysis functions. verifyPreservedAnalysis(P); + + F.getContext().yield(); } removeNotPreservedAnalysis(P); @@ -301,26 +284,26 @@ bool LPPassManager::runOnFunction(Function &F) { // Do not run other passes on this loop. break; } - + // If the loop was deleted, release all the loop passes. This frees up // some memory, and avoids trouble with the pass manager trying to call // verifyAnalysis on them. if (skipThisLoop) - for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { Pass *P = getContainedPass(Index); freePass(P, "", ON_LOOP_MSG); } // Pop the loop from queue after running all passes. LQ.pop_back(); - + if (redoThisLoop) LQ.push_back(CurrentLoop); } - + // Finalization for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { - LoopPass *P = (LoopPass *)getContainedPass(Index); + LoopPass *P = getContainedPass(Index); Changed |= P->doFinalization(); } @@ -354,7 +337,7 @@ Pass *LoopPass::createPrinterPass(raw_ostream &O, // LPPassManger as expected. void LoopPass::preparePassManager(PMStack &PMS) { - // Find LPPassManager + // Find LPPassManager while (!PMS.empty() && PMS.top()->getPassManagerType() > PMT_LoopPassManager) PMS.pop(); @@ -363,14 +346,14 @@ void LoopPass::preparePassManager(PMStack &PMS) { // by other passes that are managed by LPM then do not insert // this pass in current LPM. Use new LPPassManager. if (PMS.top()->getPassManagerType() == PMT_LoopPassManager && - !PMS.top()->preserveHigherLevelAnalysis(this)) + !PMS.top()->preserveHigherLevelAnalysis(this)) PMS.pop(); } /// Assign pass manager to manage this pass. void LoopPass::assignPassManager(PMStack &PMS, PassManagerType PreferredType) { - // Find LPPassManager + // Find LPPassManager while (!PMS.empty() && PMS.top()->getPassManagerType() > PMT_LoopPassManager) PMS.pop(); @@ -379,12 +362,12 @@ void LoopPass::assignPassManager(PMStack &PMS, if (PMS.top()->getPassManagerType() == PMT_LoopPassManager) LPPM = (LPPassManager*)PMS.top(); else { - // Create new Loop Pass Manager if it does not exist. + // Create new Loop Pass Manager if it does not exist. assert (!PMS.empty() && "Unable to create Loop Pass Manager"); PMDataManager *PMD = PMS.top(); - // [1] Create new Call Graph Pass Manager - LPPM = new LPPassManager(PMD->getDepth() + 1); + // [1] Create new Loop Pass Manager + LPPM = new LPPassManager(); LPPM->populateInheritedAnalysis(PMS); // [2] Set up new manager's top level manager @@ -402,3 +385,17 @@ void LoopPass::assignPassManager(PMStack &PMS, LPPM->add(this); } + +// Containing function has Attribute::OptimizeNone and transformation +// passes should skip it. +bool LoopPass::skipOptnoneFunction(const Loop *L) const { + const Function *F = L->getHeader()->getParent(); + if (F && F->hasFnAttribute(Attribute::OptimizeNone)) { + // FIXME: Report this to dbgs() only once per function. + DEBUG(dbgs() << "Skipping pass '" << getPassName() + << "' in function " << F->getName() << "\n"); + // FIXME: Delete loop from pass manager's queue? + return true; + } + return false; +}