X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopPass.cpp;h=2d613f6de71a856c2070ab271467745f6f88427b;hb=5c213dc78cc717c30908212049e35cfdb950fa24;hp=2e3df71c87cf47b756af02a1d55e8f7a64cef0e5;hpb=d0e6e33043aa8cca678face8dce205155e2a69b3;p=oota-llvm.git diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp index 2e3df71c87c..2d613f6de71 100644 --- a/lib/Analysis/LoopPass.cpp +++ b/lib/Analysis/LoopPass.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Devang Patel and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -14,92 +14,349 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopPass.h" -#include using namespace llvm; //===----------------------------------------------------------------------===// -// LoopQueue +// LPPassManager +// + +char LPPassManager::ID = 0; + +LPPassManager::LPPassManager(int Depth) + : FunctionPass(&ID), PMDataManager(Depth) { + skipThisLoop = false; + redoThisLoop = false; + LI = NULL; + CurrentLoop = NULL; +} -namespace llvm { +/// Delete loop from the loop queue and loop hierarchy (LoopInfo). +void LPPassManager::deleteLoopFromQueue(Loop *L) { -// Compare Two loops based on their depth in loop nest. -class LoopCompare { -public: - bool operator()( Loop *L1, Loop *L2) const { - return L1->getLoopDepth() > L2->getLoopDepth(); + 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)); } -}; -// Loop queue used by Loop Pass Manager. This is a wrapper class -// that hides implemenation detail (use of priority_queue) inside .cpp file. -class LoopQueue { + delete L; - inline void push(Loop *L) { LPQ.push(L); } - inline void pop() { LPQ.pop(); } - inline Loop *top() { return LPQ.top(); } + // 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) { + skipThisLoop = true; + return; + } -private: - std::priority_queue, LoopCompare> LPQ; -}; + for (std::deque::iterator I = LQ.begin(), + E = LQ.end(); I != E; ++I) { + if (*I == L) { + LQ.erase(I); + break; + } + } +} -} // End of LLVM namespace +// Inset loop into loop nest (LoopInfo) and loop queue (LQ). +void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { -//===----------------------------------------------------------------------===// -// LPPassManager -// -/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. + assert (CurrentLoop != L && "Cannot insert CurrentLoop"); -LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { - LQ = new LoopQueue(); + // Insert into loop nest + if (ParentLoop) + ParentLoop->addChildLoop(L); + else + LI->addTopLevelLoop(L); + + insertLoopIntoQueue(L); +} + +void LPPassManager::insertLoopIntoQueue(Loop *L) { + // Insert L into loop queue + if (L == CurrentLoop) + redoLoop(L); + else if (!L->getParentLoop()) + // This is top level loop. + LQ.push_front(L); + else { + // Insert L after the parent loop. + for (std::deque::iterator I = LQ.begin(), + E = LQ.end(); I != E; ++I) { + if (*I == L->getParentLoop()) { + // deque does not support insert after. + ++I; + LQ.insert(I, 1, L); + break; + } + } + } } -LPPassManager::~LPPassManager() { - delete LQ; +// Reoptimize this loop. LPPassManager will re-insert this loop into the +// queue. This allows LoopPass to change loop nest for the loop. This +// utility may send LPPassManager into infinite loops so use caution. +void LPPassManager::redoLoop(Loop *L) { + assert (CurrentLoop == L && "Can redo only CurrentLoop"); + redoThisLoop = true; +} + +/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for +/// all loop passes. +void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, + BasicBlock *To, Loop *L) { + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *LP = (LoopPass *)getContainedPass(Index); + LP->cloneBasicBlockAnalysis(From, To, L); + } +} + +/// 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; + ++BI) { + Instruction &I = *BI; + deleteSimpleAnalysisValue(&I, L); + } + } + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *LP = (LoopPass *)getContainedPass(Index); + LP->deleteAnalysisValue(V, 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) + 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 + // become part of LPPassManager. + 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) { - LoopInfo &LI = getAnalysis(); + LI = &getAnalysis(); bool Changed = false; - std::string Msg1 = "Executing Pass '"; - std::string Msg3 = "' Made Modification '"; + // Collect inherited analysis from Module level pass manager. + populateInheritedAnalysis(TPM->activeStack); - // Walk Loops - for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) { + // Populate Loop Queue + for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) + addLoopIntoQueue(*I, LQ); + + if (LQ.empty()) // No loops, skip calling finalizers + return false; - Loop *L = *I; - // Run all passes on current SCC + // Initialization + 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); + Changed |= P->doInitialization(L, *this); + } + } - Pass *P = getContainedPass(Index); - AnalysisUsage AnUsage; - P->getAnalysisUsage(AnUsage); + // 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); - std::string Msg2 = "' on Loop ...\n'"; - dumpPassInfo(P, Msg1, Msg2); - dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet()); + dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, + CurrentLoop->getHeader()->getNameStr()); + dumpRequiredSet(P); initializeAnalysisImpl(P); - StartPassTimer(P); - LoopPass *LP = dynamic_cast(P); - assert (LP && "Invalid LPPassManager member"); - LP->runOnLoop(*L, *this); - StopPassTimer(P); + { + PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader()); + Timer *T = StartPassTimer(P); + Changed |= P->runOnLoop(CurrentLoop, *this); + StopPassTimer(P, T); + } if (Changed) - dumpPassInfo(P, Msg3, Msg2); - dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet()); - + dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, + skipThisLoop ? "" : + CurrentLoop->getHeader()->getNameStr()); + dumpPreservedSet(P); + + if (!skipThisLoop) { + // Manually check that this loop is still healthy. This is done + // instead of relying on LoopInfo::verifyLoop since LoopInfo + // is a function pass and it's really expensive to verify every + // loop in the function every time. That level of checking can be + // enabled with the -verify-loop-info option. + Timer *T = StartPassTimer(LI); + CurrentLoop->verifyLoop(); + StopPassTimer(LI, T); + + // Then call the regular verifyAnalysis functions. + verifyPreservedAnalysis(P); + } + removeNotPreservedAnalysis(P); recordAvailableAnalysis(P); - removeDeadPasses(P, Msg2); + removeDeadPasses(P, + skipThisLoop ? "" : + CurrentLoop->getHeader()->getNameStr(), + ON_LOOP_MSG); + + if (skipThisLoop) + // 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) { + 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); + Changed |= P->doFinalization(); } return Changed; } +/// Print passes managed by this manager +void LPPassManager::dumpPassStructure(unsigned Offset) { + errs().indent(Offset*2) << "Loop Pass Manager\n"; + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + Pass *P = getContainedPass(Index); + P->dumpPassStructure(Offset + 1); + dumpLastUses(P, Offset+1); + } +} + + +//===----------------------------------------------------------------------===// +// LoopPass + +// Check if this pass is suitable for the current LPPassManager, if +// available. This pass P is not suitable for a LPPassManager if P +// is not preserving higher level analysis info used by other +// LPPassManager passes. In such case, pop LPPassManager from the +// stack. This will force assignPassManager() to create new +// LPPassManger as expected. +void LoopPass::preparePassManager(PMStack &PMS) { + + // Find LPPassManager + while (!PMS.empty() && + PMS.top()->getPassManagerType() > PMT_LoopPassManager) + PMS.pop(); + + // If this pass is destroying high level information that is used + // 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.pop(); +} +/// Assign pass manager to manage this pass. +void LoopPass::assignPassManager(PMStack &PMS, + PassManagerType PreferredType) { + // Find LPPassManager + while (!PMS.empty() && + PMS.top()->getPassManagerType() > PMT_LoopPassManager) + PMS.pop(); + + LPPassManager *LPPM; + if (PMS.top()->getPassManagerType() == PMT_LoopPassManager) + LPPM = (LPPassManager*)PMS.top(); + else { + // 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); + LPPM->populateInheritedAnalysis(PMS); + + // [2] Set up new manager's top level manager + PMTopLevelManager *TPM = PMD->getTopLevelManager(); + TPM->addIndirectPassManager(LPPM); + + // [3] Assign manager to manage this new manager. This may create + // and push new managers into PMS + Pass *P = LPPM->getAsPass(); + TPM->schedulePass(P); + + // [4] Push new manager into PMS + PMS.push(LPPM); + } + + LPPM->add(this); +}