X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopPass.cpp;h=90f64fb865782bc15c7d2a6e56afa53844656807;hb=cf84b5ba5eecf5ae1b3d8b7af77fbb9f08b48d49;hp=40b38f37930cc1763e21ea8d4fa93607e7c88b3e;hpb=7f99761143cdf1ad23729708e3dcaa055b189406;p=oota-llvm.git diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp index 40b38f37930..90f64fb8657 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,156 +14,341 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopPass.h" -#include +#include "llvm/IR/IRPrintingPasses.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Timer.h" using namespace llvm; -//===----------------------------------------------------------------------===// -// LoopQueue +namespace { -namespace llvm { +/// PrintLoopPass - Print a Function corresponding to a Loop. +/// +class PrintLoopPass : public LoopPass { +private: + std::string Banner; + raw_ostream &Out; // raw_ostream to print on. -// Compare Two loops based on their depth in loop nest. -class LoopCompare { public: - bool operator()( Loop *L1, Loop *L2) const { - // Loops with highest depth has the highest priority. - return L1->getLoopDepth() < L2->getLoopDepth(); + 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(); } -}; -// 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 { -public: - inline void push(Loop *L) { LPQ.push(L); } - inline void pop() { LPQ.pop(); } - inline Loop *top() { return LPQ.top(); } - inline bool empty() { return LPQ.empty(); } -private: - std::priority_queue, LoopCompare> LPQ; + 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; + } }; -} // End of LLVM namespace +char PrintLoopPass::ID = 0; +} //===----------------------------------------------------------------------===// // LPPassManager // -/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. -LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { +char LPPassManager::ID = 0; + +LPPassManager::LPPassManager() + : FunctionPass(ID), PMDataManager() { skipThisLoop = false; redoThisLoop = false; - LQ = new LoopQueue(); + LI = NULL; + CurrentLoop = NULL; +} + +/// Delete loop from the loop queue and loop hierarchy (LoopInfo). +void LPPassManager::deleteLoopFromQueue(Loop *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) + skipThisLoop = true; + + delete L; + + if (skipThisLoop) + return; + + for (std::deque::iterator I = LQ.begin(), + E = LQ.end(); I != E; ++I) { + if (*I == L) { + LQ.erase(I); + break; + } + } } -LPPassManager::~LPPassManager() { - delete LQ; +// 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); + + insertLoopIntoQueue(L); } -/// Delete loop from the loop queue. This is used by Loop pass to inform -/// Loop Pass Manager that it should skip rest of the passes for this loop. -void LPPassManager::deleteLoopFromQueue(Loop *L) { - // Do not pop loop from LQ here. It will be done by runOnFunction while loop. - skipThisLoop = true; +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; + } + } + } } // 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 = 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 = getContainedPass(Index); + LP->deleteAnalysisValue(V, L); + } +} + + // Recurse through all subloops and all loops into LQ. -static void addLoopIntoQueue(Loop *L, LoopQueue *LQ) { - for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) +static void addLoopIntoQueue(Loop *L, std::deque &LQ) { + LQ.push_back(L); + for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I) addLoopIntoQueue(*I, LQ); - LQ->push(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(); + 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) + // Collect inherited analysis from Module level pass manager. + populateInheritedAnalysis(TPM->activeStack); + + // 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 + 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) { + LoopPass *P = getContainedPass(Index); + Changed |= P->doInitialization(L, *this); + } + } + // Walk Loops - while (!LQ->empty()) { - - Loop *L = LQ->top(); + 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); - AnalysisUsage AnUsage; - P->getAnalysisUsage(AnUsage); + // 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, ""); - dumpAnalysisSetInfo("Required", P, AnUsage.getRequiredSet()); + dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, + CurrentLoop->getHeader()->getName()); + 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()); + TimeRegion PassTimer(getPassTimer(P)); + + Changed |= P->runOnLoop(CurrentLoop, *this); + } if (Changed) - dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, ""); - dumpAnalysisSetInfo("Preserved", P, AnUsage.getPreservedSet()); - + dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, + skipThisLoop ? "" : + CurrentLoop->getHeader()->getName()); + 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. + { + TimeRegion PassTimer(getPassTimer(LI)); + CurrentLoop->verifyLoop(); + } + + // Then call the regular verifyAnalysis functions. + verifyPreservedAnalysis(P); + } + removeNotPreservedAnalysis(P); recordAvailableAnalysis(P); - removeDeadPasses(P, "", ON_LOOP_MSG); + 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(); - + LQ.pop_back(); + if (redoThisLoop) - LQ->push(L); + LQ.push_back(CurrentLoop); + } + + // Finalization + for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { + 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 +// 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()) { - if (PMS.top()->getPassManagerType() > PMT_LoopPassManager) - PMS.pop(); - else; - break; - } - - LPPassManager *LPPM = dynamic_cast(PMS.top()); - - // Create new Loop Pass Manager if it does not exist. - if (!LPPM) { - + // 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); + // [1] Create new Loop Pass Manager + LPPM = new LPPassManager(); + LPPM->populateInheritedAnalysis(PMS); // [2] Set up new manager's top level manager PMTopLevelManager *TPM = PMD->getTopLevelManager(); @@ -171,8 +356,8 @@ 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); + Pass *P = LPPM->getAsPass(); + TPM->schedulePass(P); // [4] Push new manager into PMS PMS.push(LPPM); @@ -181,3 +366,16 @@ 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; +}