LLVM API Documentation
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 }