LLVM API Documentation

LoopPass.cpp

Go to the documentation of this file.
00001 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements LoopPass and LPPassManager. All loop optimization
00011 // and transformation passes are derived from LoopPass. LPPassManager is
00012 // responsible for managing LoopPasses.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Analysis/LoopPass.h"
00017 using namespace llvm;
00018 
00019 //===----------------------------------------------------------------------===//
00020 // LPPassManager
00021 //
00022 
00023 char LPPassManager::ID = 0;
00024 /// LPPassManager manages FPPassManagers and CalLGraphSCCPasses.
00025 
00026 LPPassManager::LPPassManager(int Depth) 
00027   : FunctionPass(&ID), PMDataManager(Depth) { 
00028   skipThisLoop = false;
00029   redoThisLoop = false;
00030   LI = NULL;
00031   CurrentLoop = NULL;
00032 }
00033 
00034 /// Delete loop from the loop queue and loop hierarchy (LoopInfo). 
00035 void LPPassManager::deleteLoopFromQueue(Loop *L) {
00036 
00037   if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop.
00038     // Reparent all of the blocks in this loop.  Since BBLoop had a parent,
00039     // they are now all in it.
00040     for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 
00041          I != E; ++I)
00042       if (LI->getLoopFor(*I) == L)    // Don't change blocks in subloops.
00043         LI->changeLoopFor(*I, ParentLoop);
00044     
00045     // Remove the loop from its parent loop.
00046     for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();;
00047          ++I) {
00048       assert(I != E && "Couldn't find loop");
00049       if (*I == L) {
00050         ParentLoop->removeChildLoop(I);
00051         break;
00052       }
00053     }
00054     
00055     // Move all subloops into the parent loop.
00056     while (!L->empty())
00057       ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1));
00058   } else {
00059     // Reparent all of the blocks in this loop.  Since BBLoop had no parent,
00060     // they no longer in a loop at all.
00061     
00062     for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
00063       // Don't change blocks in subloops.
00064       if (LI->getLoopFor(L->getBlocks()[i]) == L) {
00065         LI->removeBlock(L->getBlocks()[i]);
00066         --i;
00067       }
00068     }
00069 
00070     // Remove the loop from the top-level LoopInfo object.
00071     for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) {
00072       assert(I != E && "Couldn't find loop");
00073       if (*I == L) {
00074         LI->removeLoop(I);
00075         break;
00076       }
00077     }
00078 
00079     // Move all of the subloops to the top-level.
00080     while (!L->empty())
00081       LI->addTopLevelLoop(L->removeChildLoop(L->end()-1));
00082   }
00083 
00084   delete L;
00085 
00086   // If L is current loop then skip rest of the passes and let
00087   // runOnFunction remove L from LQ. Otherwise, remove L from LQ now
00088   // and continue applying other passes on CurrentLoop.
00089   if (CurrentLoop == L) {
00090     skipThisLoop = true;
00091     return;
00092   }
00093 
00094   for (std::deque<Loop *>::iterator I = LQ.begin(),
00095          E = LQ.end(); I != E; ++I) {
00096     if (*I == L) {
00097       LQ.erase(I);
00098       break;
00099     }
00100   }
00101 }
00102 
00103 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).
00104 void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) {
00105 
00106   assert (CurrentLoop != L && "Cannot insert CurrentLoop");
00107 
00108   // Insert into loop nest
00109   if (ParentLoop)
00110     ParentLoop->addChildLoop(L);
00111   else
00112     LI->addTopLevelLoop(L);
00113 
00114   // Insert L into loop queue
00115   if (L == CurrentLoop) 
00116     redoLoop(L);
00117   else if (!ParentLoop)
00118     // This is top level loop. 
00119     LQ.push_front(L);
00120   else {
00121     // Insert L after ParentLoop
00122     for (std::deque<Loop *>::iterator I = LQ.begin(),
00123            E = LQ.end(); I != E; ++I) {
00124       if (*I == ParentLoop) {
00125         // deque does not support insert after.
00126         ++I;
00127         LQ.insert(I, 1, L);
00128         break;
00129       }
00130     }
00131   }
00132 }
00133 
00134 // Reoptimize this loop. LPPassManager will re-insert this loop into the
00135 // queue. This allows LoopPass to change loop nest for the loop. This
00136 // utility may send LPPassManager into infinite loops so use caution.
00137 void LPPassManager::redoLoop(Loop *L) {
00138   assert (CurrentLoop == L && "Can redo only CurrentLoop");
00139   redoThisLoop = true;
00140 }
00141 
00142 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
00143 /// all loop passes.
00144 void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, 
00145                                                   BasicBlock *To, Loop *L) {
00146   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
00147     Pass *P = getContainedPass(Index);
00148     LoopPass *LP = dynamic_cast<LoopPass *>(P);
00149     LP->cloneBasicBlockAnalysis(From, To, L);
00150   }
00151 }
00152 
00153 /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
00154 void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
00155   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
00156     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; 
00157          ++BI) {
00158       Instruction &I = *BI;
00159       deleteSimpleAnalysisValue(&I, L);
00160     }
00161   }
00162   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
00163     Pass *P = getContainedPass(Index);
00164     LoopPass *LP = dynamic_cast<LoopPass *>(P);
00165     LP->deleteAnalysisValue(V, L);
00166   }
00167 }
00168 
00169 
00170 // Recurse through all subloops and all loops  into LQ.
00171 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
00172   LQ.push_back(L);
00173   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
00174     addLoopIntoQueue(*I, LQ);
00175 }
00176 
00177 /// Pass Manager itself does not invalidate any analysis info.
00178 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
00179   // LPPassManager needs LoopInfo. In the long term LoopInfo class will 
00180   // become part of LPPassManager.
00181   Info.addRequired<LoopInfo>();
00182   Info.setPreservesAll();
00183 }
00184 
00185 /// run - Execute all of the passes scheduled for execution.  Keep track of
00186 /// whether any of the passes modifies the function, and if so, return true.
00187 bool LPPassManager::runOnFunction(Function &F) {
00188   LI = &getAnalysis<LoopInfo>();
00189   bool Changed = false;
00190 
00191   // Collect inherited analysis from Module level pass manager.
00192   populateInheritedAnalysis(TPM->activeStack);
00193 
00194   // Populate Loop Queue
00195   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
00196     addLoopIntoQueue(*I, LQ);
00197 
00198   if (LQ.empty()) // No loops, skip calling finalizers
00199     return false;
00200 
00201   // Initialization
00202   for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end();
00203        I != E; ++I) {
00204     Loop *L = *I;
00205     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
00206       Pass *P = getContainedPass(Index);
00207       LoopPass *LP = dynamic_cast<LoopPass *>(P);
00208       if (LP)
00209         Changed |= LP->doInitialization(L, *this);
00210     }
00211   }
00212 
00213   // Walk Loops
00214   while (!LQ.empty()) {
00215       
00216     CurrentLoop  = LQ.back();
00217     skipThisLoop = false;
00218     redoThisLoop = false;
00219 
00220     // Run all passes on current SCC
00221     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {  
00222       Pass *P = getContainedPass(Index);
00223 
00224       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, "");
00225       dumpRequiredSet(P);
00226 
00227       initializeAnalysisImpl(P);
00228 
00229       LoopPass *LP = dynamic_cast<LoopPass *>(P);
00230       {
00231         PassManagerPrettyStackEntry X(LP, *CurrentLoop->getHeader());
00232         StartPassTimer(P);
00233         assert(LP && "Invalid LPPassManager member");
00234         Changed |= LP->runOnLoop(CurrentLoop, *this);
00235         StopPassTimer(P);
00236       }
00237 
00238       if (Changed)
00239         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, "");
00240       dumpPreservedSet(P);
00241 
00242       verifyPreservedAnalysis(LP);
00243       removeNotPreservedAnalysis(P);
00244       recordAvailableAnalysis(P);
00245       removeDeadPasses(P, "", ON_LOOP_MSG);
00246 
00247       // If dominator information is available then verify the info if requested.
00248       verifyDomInfo(*LP, F);
00249 
00250       if (skipThisLoop)
00251         // Do not run other passes on this loop.
00252         break;
00253     }
00254     
00255     // Pop the loop from queue after running all passes.
00256     LQ.pop_back();
00257     
00258     if (redoThisLoop)
00259       LQ.push_back(CurrentLoop);
00260   }
00261   
00262   // Finalization
00263   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00264     Pass *P = getContainedPass(Index);
00265     LoopPass *LP = dynamic_cast <LoopPass *>(P);
00266     if (LP)
00267       Changed |= LP->doFinalization();
00268   }
00269 
00270   return Changed;
00271 }
00272 
00273 /// Print passes managed by this manager
00274 void LPPassManager::dumpPassStructure(unsigned Offset) {
00275   llvm::cerr << std::string(Offset*2, ' ') << "Loop Pass Manager\n";
00276   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
00277     Pass *P = getContainedPass(Index);
00278     P->dumpPassStructure(Offset + 1);
00279     dumpLastUses(P, Offset+1);
00280   }
00281 }
00282 
00283 
00284 //===----------------------------------------------------------------------===//
00285 // LoopPass
00286 
00287 // Check if this pass is suitable for the current LPPassManager, if
00288 // available. This pass P is not suitable for a LPPassManager if P
00289 // is not preserving higher level analysis info used by other
00290 // LPPassManager passes. In such case, pop LPPassManager from the
00291 // stack. This will force assignPassManager() to create new
00292 // LPPassManger as expected.
00293 void LoopPass::preparePassManager(PMStack &PMS) {
00294 
00295   // Find LPPassManager 
00296   while (!PMS.empty() &&
00297          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
00298     PMS.pop();
00299 
00300   LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
00301 
00302   // If this pass is destroying high level information that is used
00303   // by other passes that are managed by LPM then do not insert
00304   // this pass in current LPM. Use new LPPassManager.
00305   if (LPPM && !LPPM->preserveHigherLevelAnalysis(this)) 
00306     PMS.pop();
00307 }
00308 
00309 /// Assign pass manager to manage this pass.
00310 void LoopPass::assignPassManager(PMStack &PMS,
00311                                  PassManagerType PreferredType) {
00312   // Find LPPassManager 
00313   while (!PMS.empty() &&
00314          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
00315     PMS.pop();
00316 
00317   LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top());
00318 
00319   // Create new Loop Pass Manager if it does not exist. 
00320   if (!LPPM) {
00321 
00322     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
00323     PMDataManager *PMD = PMS.top();
00324 
00325     // [1] Create new Call Graph Pass Manager
00326     LPPM = new LPPassManager(PMD->getDepth() + 1);
00327     LPPM->populateInheritedAnalysis(PMS);
00328 
00329     // [2] Set up new manager's top level manager
00330     PMTopLevelManager *TPM = PMD->getTopLevelManager();
00331     TPM->addIndirectPassManager(LPPM);
00332 
00333     // [3] Assign manager to manage this new manager. This may create
00334     // and push new managers into PMS
00335     Pass *P = dynamic_cast<Pass *>(LPPM);
00336     TPM->schedulePass(P);
00337 
00338     // [4] Push new manager into PMS
00339     PMS.push(LPPM);
00340   }
00341 
00342   LPPM->add(this);
00343 }