X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopPass.cpp;h=b4534cd511f3fc336da2377e160bca97ee846ea8;hb=51cd9d6e073932fcb37f1857c66249d6c7d368ee;hp=4b41a94c70cc036a920daea13e84b10cae62a920;hpb=7a9a0695f2a5af1ab5667e9ce34c84d4f20bff5f;p=oota-llvm.git diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp index 4b41a94c70c..b4534cd511f 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,14 +14,18 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" using namespace llvm; //===----------------------------------------------------------------------===// // LPPassManager // + +char LPPassManager::ID = 0; /// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. -LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { +LPPassManager::LPPassManager(int Depth) + : FunctionPass((intptr_t)&ID), PMDataManager(Depth) { skipThisLoop = false; redoThisLoop = false; LI = NULL; @@ -50,7 +54,7 @@ void LPPassManager::deleteLoopFromQueue(Loop *L) { } // Move all subloops into the parent loop. - while (L->begin() != L->end()) + while (!L->empty()) ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1)); } else { // Reparent all of the blocks in this loop. Since BBLoop had no parent, @@ -74,7 +78,7 @@ void LPPassManager::deleteLoopFromQueue(Loop *L) { } // Move all of the subloops to the top-level. - while (L->begin() != L->end()) + while (!L->empty()) LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); } @@ -97,28 +101,91 @@ void LPPassManager::deleteLoopFromQueue(Loop *L) { } } +// Inset loop into loop nest (LoopInfo) and loop queue (LQ). +void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { + + assert (CurrentLoop != L && "Cannot insert CurrentLoop"); + + // Insert into loop nest + if (ParentLoop) + ParentLoop->addChildLoop(L); + else + LI->addTopLevelLoop(L); + + // Insert L into loop queue + if (L == CurrentLoop) + redoLoop(L); + else if (!ParentLoop) + // This is top level loop. + LQ.push_front(L); + else { + // Insert L after ParentLoop + for (std::deque::iterator I = LQ.begin(), + E = LQ.end(); I != E; ++I) { + if (*I == ParentLoop) { + // deque does not support insert after. + ++I; + LQ.insert(I, 1, L); + break; + } + } + } +} + // 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) { + Pass *P = getContainedPass(Index); + LoopPass *LP = dynamic_cast(P); + LP->cloneBasicBlockAnalysis(From, To, L); + } +} + +/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes. +void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) { + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + Pass *P = getContainedPass(Index); + LoopPass *LP = dynamic_cast(P); + 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); - LQ.push_back(L); +} + +/// 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(); + // Used by IndVar doInitialization. + 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; // Populate Loop Queue - for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) + for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) addLoopIntoQueue(*I, LQ); // Initialization @@ -155,13 +222,14 @@ bool LPPassManager::runOnFunction(Function &F) { StartPassTimer(P); LoopPass *LP = dynamic_cast(P); assert (LP && "Invalid LPPassManager member"); - LP->runOnLoop(CurrentLoop, *this); + Changed |= LP->runOnLoop(CurrentLoop, *this); StopPassTimer(P); if (Changed) dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, ""); dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet()); - + + verifyPreservedAnalysis(LP); removeNotPreservedAnalysis(P); recordAvailableAnalysis(P); removeDeadPasses(P, "", ON_LOOP_MSG); @@ -202,12 +270,9 @@ bool LPPassManager::runOnFunction(Function &F) { void LoopPass::preparePassManager(PMStack &PMS) { // Find LPPassManager - while (!PMS.empty()) { - if (PMS.top()->getPassManagerType() > PMT_LoopPassManager) - PMS.pop(); - else; - break; - } + while (!PMS.empty() && + PMS.top()->getPassManagerType() > PMT_LoopPassManager) + PMS.pop(); LPPassManager *LPPM = dynamic_cast(PMS.top()); @@ -222,12 +287,9 @@ void LoopPass::preparePassManager(PMStack &PMS) { void LoopPass::assignPassManager(PMStack &PMS, PassManagerType PreferredType) { // Find LPPassManager - while (!PMS.empty()) { - if (PMS.top()->getPassManagerType() > PMT_LoopPassManager) - PMS.pop(); - else; - break; - } + while (!PMS.empty() && + PMS.top()->getPassManagerType() > PMT_LoopPassManager) + PMS.pop(); LPPassManager *LPPM = dynamic_cast(PMS.top()); @@ -239,6 +301,7 @@ void LoopPass::assignPassManager(PMStack &PMS, // [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(); @@ -247,7 +310,7 @@ void LoopPass::assignPassManager(PMStack &PMS, // [3] Assign manager to manage this new manager. This may create // and push new managers into PMS Pass *P = dynamic_cast(LPPM); - P->assignPassManager(PMS); + TPM->schedulePass(P); // [4] Push new manager into PMS PMS.push(LPPM); @@ -255,4 +318,3 @@ void LoopPass::assignPassManager(PMStack &PMS, LPPM->add(this); } -