X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopPass.cpp;h=5ba1f4045d1a49aca20a5dd18a71247bdb82566f;hb=4032eaf98c63b0fb1f2418a1cdc56b72bc76c329;hp=7ebd4d39427bd171e55a9a22b5f6e4a6806e0299;hpb=ae73dc1448d25b02cabc7c64c86c64371453dda8;p=oota-llvm.git diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp index 7ebd4d39427..5ba1f4045d1 100644 --- a/lib/Analysis/LoopPass.cpp +++ b/lib/Analysis/LoopPass.cpp @@ -14,83 +14,88 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopPass.h" -#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/DebugInfoProbe.h" +#include "llvm/Assembly/PrintModulePass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/Timer.h" using namespace llvm; +namespace { + +/// PrintLoopPass - Print a Function corresponding to a Loop. +/// +class PrintLoopPass : public LoopPass { +private: + std::string Banner; + raw_ostream &Out; // raw_ostream to print on. + +public: + static char ID; + PrintLoopPass(const std::string &B, raw_ostream &o) + : LoopPass(ID), Banner(B), Out(o) {} + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } + + bool runOnLoop(Loop *L, LPPassManager &) { + Out << Banner; + for (Loop::block_iterator b = L->block_begin(), be = L->block_end(); + b != be; + ++b) { + (*b)->print(Out); + } + return false; + } +}; + +char PrintLoopPass::ID = 0; +} + +//===----------------------------------------------------------------------===// +// DebugInfoProbe + +static DebugInfoProbeInfo *TheDebugProbe; +static void createDebugInfoProbe() { + if (TheDebugProbe) return; + + // Constructed the first time this is called. This guarantees that the + // object will be constructed, if -enable-debug-info-probe is set, + // before static globals, thus it will be destroyed before them. + static ManagedStatic DIP; + TheDebugProbe = &*DIP; +} + //===----------------------------------------------------------------------===// // LPPassManager // char LPPassManager::ID = 0; -/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. -LPPassManager::LPPassManager(int Depth) - : FunctionPass(&ID), PMDataManager(Depth) { +LPPassManager::LPPassManager() + : FunctionPass(ID), PMDataManager() { skipThisLoop = false; redoThisLoop = false; LI = NULL; CurrentLoop = NULL; } -/// 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)); - } - - delete L; + LI->updateUnloop(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) { @@ -112,17 +117,21 @@ void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { else LI->addTopLevelLoop(L); + insertLoopIntoQueue(L); +} + +void LPPassManager::insertLoopIntoQueue(Loop *L) { // Insert L into loop queue - if (L == CurrentLoop) + if (L == CurrentLoop) redoLoop(L); - else if (!ParentLoop) - // This is top level loop. + else if (!L->getParentLoop()) + // This is top level loop. LQ.push_front(L); else { - // Insert L after ParentLoop + // Insert L after the parent loop. for (std::deque::iterator I = LQ.begin(), E = LQ.end(); I != E; ++I) { - if (*I == ParentLoop) { + if (*I == L->getParentLoop()) { // deque does not support insert after. ++I; LQ.insert(I, 1, L); @@ -142,20 +151,25 @@ 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) { - Pass *P = getContainedPass(Index); - LoopPass *LP = dynamic_cast(P); + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *LP = getContainedPass(Index); 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); + 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 = getContainedPass(Index); LP->deleteAnalysisValue(V, L); } } @@ -170,11 +184,9 @@ static void addLoopIntoQueue(Loop *L, std::deque &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(); - // Used by IndVar doInitialization. - Info.addRequired(); Info.setPreservesAll(); } @@ -183,6 +195,7 @@ void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { bool LPPassManager::runOnFunction(Function &F) { LI = &getAnalysis(); bool Changed = false; + createDebugInfoProbe(); // Collect inherited analysis from Module level pass manager. populateInheritedAnalysis(TPM->activeStack); @@ -191,80 +204,122 @@ bool LPPassManager::runOnFunction(Function &F) { 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; + // 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) { - Pass *P = getContainedPass(Index); - LoopPass *LP = dynamic_cast(P); - if (LP) - Changed |= LP->doInitialization(L, *this); + 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 current SCC - for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { - - Pass *P = getContainedPass(Index); - - dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, ""); + // Run all passes on the current Loop. + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + LoopPass *P = getContainedPass(Index); + dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, + CurrentLoop->getHeader()->getName()); dumpRequiredSet(P); initializeAnalysisImpl(P); + if (TheDebugProbe) + TheDebugProbe->initialize(P, F); + { + PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader()); + TimeRegion PassTimer(getPassTimer(P)); - StartPassTimer(P); - LoopPass *LP = dynamic_cast(P); - assert (LP && "Invalid LPPassManager member"); - Changed |= LP->runOnLoop(CurrentLoop, *this); - StopPassTimer(P); + Changed |= P->runOnLoop(CurrentLoop, *this); + } + if (TheDebugProbe) + TheDebugProbe->finalize(P, F); if (Changed) - dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, ""); + dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, + skipThisLoop ? "" : + CurrentLoop->getHeader()->getName()); dumpPreservedSet(P); - verifyPreservedAnalysis(LP); + 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. + { + TimeRegion PassTimer(getPassTimer(LI)); + CurrentLoop->verifyLoop(); + } + + // Then call the regular verifyAnalysis functions. + verifyPreservedAnalysis(P); + } + removeNotPreservedAnalysis(P); recordAvailableAnalysis(P); - removeDeadPasses(P, "", ON_LOOP_MSG); - - // If dominator information is available then verify the info if requested. - verifyDomInfo(*LP, F); + removeDeadPasses(P, + skipThisLoop ? "" : + CurrentLoop->getHeader()->getName(), + 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) { - Pass *P = getContainedPass(Index); - LoopPass *LP = dynamic_cast (P); - if (LP) - Changed |= LP->doFinalization(); + LoopPass *P = 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 +Pass *LoopPass::createPrinterPass(raw_ostream &O, + const std::string &Banner) const { + return new PrintLoopPass(Banner, O); +} + // 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 @@ -273,38 +328,37 @@ bool LPPassManager::runOnFunction(Function &F) { // LPPassManger as expected. void LoopPass::preparePassManager(PMStack &PMS) { - // Find LPPassManager + // Find LPPassManager while (!PMS.empty() && PMS.top()->getPassManagerType() > PMT_LoopPassManager) PMS.pop(); - LPPassManager *LPPM = dynamic_cast(PMS.top()); - // 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 (LPPM && !LPPM->preserveHigherLevelAnalysis(this)) + 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 + // Find LPPassManager while (!PMS.empty() && PMS.top()->getPassManagerType() > PMT_LoopPassManager) PMS.pop(); - LPPassManager *LPPM = dynamic_cast(PMS.top()); - - // Create new Loop Pass Manager if it does not exist. - if (!LPPM) { - + 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); + // [1] Create new Loop Pass Manager + LPPM = new LPPassManager(); LPPM->populateInheritedAnalysis(PMS); // [2] Set up new manager's top level manager @@ -313,7 +367,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); + Pass *P = LPPM->getAsPass(); TPM->schedulePass(P); // [4] Push new manager into PMS