X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopPass.cpp;h=fc431035c0729db33510b35707f04f389f0c6d98;hb=3fefc182a00663bfadbcbe17711b6d08469c9727;hp=de062baec8ef351cd1d548e7b21f62d6e73ab4e8;hpb=22033be445aea2a28e8d11d2e2453382a1515f12;p=oota-llvm.git diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp index de062baec8e..fc431035c07 100644 --- a/lib/Analysis/LoopPass.cpp +++ b/lib/Analysis/LoopPass.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" using namespace llvm; //===----------------------------------------------------------------------===// @@ -24,37 +25,143 @@ using namespace llvm; LPPassManager::LPPassManager(int Depth) : PMDataManager(Depth) { skipThisLoop = false; redoThisLoop = false; + LI = NULL; + CurrentLoop = NULL; } -/// 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. +/// Delete loop from the loop queue and loop hierarcy (LoopInfo). void LPPassManager::deleteLoopFromQueue(Loop *L) { - // Do not pop loop from LQ here. It will be done by runOnFunction while loop. - skipThisLoop = true; + + 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->begin() != L->end()) + 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->begin() != L->end()) + LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); + } + + delete 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; + return; + } + + for (std::deque::iterator I = LQ.begin(), + E = LQ.end(); I != E; ++I) { + if (*I == L) { + LQ.erase(I); + break; + } + } +} + +// 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; } // 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 @@ -72,7 +179,7 @@ bool LPPassManager::runOnFunction(Function &F) { // Walk Loops while (!LQ.empty()) { - Loop *L = LQ.back(); + CurrentLoop = LQ.back(); skipThisLoop = false; redoThisLoop = false; @@ -91,7 +198,7 @@ bool LPPassManager::runOnFunction(Function &F) { StartPassTimer(P); LoopPass *LP = dynamic_cast(P); assert (LP && "Invalid LPPassManager member"); - LP->runOnLoop(L, *this); + LP->runOnLoop(CurrentLoop, *this); StopPassTimer(P); if (Changed) @@ -111,7 +218,7 @@ bool LPPassManager::runOnFunction(Function &F) { LQ.pop_back(); if (redoThisLoop) - LQ.push_back(L); + LQ.push_back(CurrentLoop); } // Finalization @@ -175,6 +282,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(); @@ -183,7 +291,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);