LoopPass.cpp revision 198090
1//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements LoopPass and LPPassManager. All loop optimization 11// and transformation passes are derived from LoopPass. LPPassManager is 12// responsible for managing LoopPasses. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/Analysis/LoopPass.h" 17using namespace llvm; 18 19//===----------------------------------------------------------------------===// 20// LPPassManager 21// 22 23char LPPassManager::ID = 0; 24 25LPPassManager::LPPassManager(int Depth) 26 : FunctionPass(&ID), PMDataManager(Depth) { 27 skipThisLoop = false; 28 redoThisLoop = false; 29 LI = NULL; 30 CurrentLoop = NULL; 31} 32 33/// Delete loop from the loop queue and loop hierarchy (LoopInfo). 34void LPPassManager::deleteLoopFromQueue(Loop *L) { 35 36 if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop. 37 // Reparent all of the blocks in this loop. Since BBLoop had a parent, 38 // they are now all in it. 39 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 40 I != E; ++I) 41 if (LI->getLoopFor(*I) == L) // Don't change blocks in subloops. 42 LI->changeLoopFor(*I, ParentLoop); 43 44 // Remove the loop from its parent loop. 45 for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; 46 ++I) { 47 assert(I != E && "Couldn't find loop"); 48 if (*I == L) { 49 ParentLoop->removeChildLoop(I); 50 break; 51 } 52 } 53 54 // Move all subloops into the parent loop. 55 while (!L->empty()) 56 ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1)); 57 } else { 58 // Reparent all of the blocks in this loop. Since BBLoop had no parent, 59 // they no longer in a loop at all. 60 61 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 62 // Don't change blocks in subloops. 63 if (LI->getLoopFor(L->getBlocks()[i]) == L) { 64 LI->removeBlock(L->getBlocks()[i]); 65 --i; 66 } 67 } 68 69 // Remove the loop from the top-level LoopInfo object. 70 for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) { 71 assert(I != E && "Couldn't find loop"); 72 if (*I == L) { 73 LI->removeLoop(I); 74 break; 75 } 76 } 77 78 // Move all of the subloops to the top-level. 79 while (!L->empty()) 80 LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); 81 } 82 83 delete L; 84 85 // If L is current loop then skip rest of the passes and let 86 // runOnFunction remove L from LQ. Otherwise, remove L from LQ now 87 // and continue applying other passes on CurrentLoop. 88 if (CurrentLoop == L) { 89 skipThisLoop = true; 90 return; 91 } 92 93 for (std::deque<Loop *>::iterator I = LQ.begin(), 94 E = LQ.end(); I != E; ++I) { 95 if (*I == L) { 96 LQ.erase(I); 97 break; 98 } 99 } 100} 101 102// Inset loop into loop nest (LoopInfo) and loop queue (LQ). 103void LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { 104 105 assert (CurrentLoop != L && "Cannot insert CurrentLoop"); 106 107 // Insert into loop nest 108 if (ParentLoop) 109 ParentLoop->addChildLoop(L); 110 else 111 LI->addTopLevelLoop(L); 112 113 insertLoopIntoQueue(L); 114} 115 116void LPPassManager::insertLoopIntoQueue(Loop *L) { 117 // Insert L into loop queue 118 if (L == CurrentLoop) 119 redoLoop(L); 120 else if (!L->getParentLoop()) 121 // This is top level loop. 122 LQ.push_front(L); 123 else { 124 // Insert L after the parent loop. 125 for (std::deque<Loop *>::iterator I = LQ.begin(), 126 E = LQ.end(); I != E; ++I) { 127 if (*I == L->getParentLoop()) { 128 // deque does not support insert after. 129 ++I; 130 LQ.insert(I, 1, L); 131 break; 132 } 133 } 134 } 135} 136 137// Reoptimize this loop. LPPassManager will re-insert this loop into the 138// queue. This allows LoopPass to change loop nest for the loop. This 139// utility may send LPPassManager into infinite loops so use caution. 140void LPPassManager::redoLoop(Loop *L) { 141 assert (CurrentLoop == L && "Can redo only CurrentLoop"); 142 redoThisLoop = true; 143} 144 145/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for 146/// all loop passes. 147void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, 148 BasicBlock *To, Loop *L) { 149 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 150 Pass *P = getContainedPass(Index); 151 LoopPass *LP = dynamic_cast<LoopPass *>(P); 152 LP->cloneBasicBlockAnalysis(From, To, L); 153 } 154} 155 156/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes. 157void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) { 158 if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 159 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; 160 ++BI) { 161 Instruction &I = *BI; 162 deleteSimpleAnalysisValue(&I, L); 163 } 164 } 165 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 166 Pass *P = getContainedPass(Index); 167 LoopPass *LP = dynamic_cast<LoopPass *>(P); 168 LP->deleteAnalysisValue(V, L); 169 } 170} 171 172 173// Recurse through all subloops and all loops into LQ. 174static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { 175 LQ.push_back(L); 176 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 177 addLoopIntoQueue(*I, LQ); 178} 179 180/// Pass Manager itself does not invalidate any analysis info. 181void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { 182 // LPPassManager needs LoopInfo. In the long term LoopInfo class will 183 // become part of LPPassManager. 184 Info.addRequired<LoopInfo>(); 185 Info.setPreservesAll(); 186} 187 188/// run - Execute all of the passes scheduled for execution. Keep track of 189/// whether any of the passes modifies the function, and if so, return true. 190bool LPPassManager::runOnFunction(Function &F) { 191 LI = &getAnalysis<LoopInfo>(); 192 bool Changed = false; 193 194 // Collect inherited analysis from Module level pass manager. 195 populateInheritedAnalysis(TPM->activeStack); 196 197 // Populate Loop Queue 198 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 199 addLoopIntoQueue(*I, LQ); 200 201 if (LQ.empty()) // No loops, skip calling finalizers 202 return false; 203 204 // Initialization 205 for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end(); 206 I != E; ++I) { 207 Loop *L = *I; 208 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 209 Pass *P = getContainedPass(Index); 210 LoopPass *LP = dynamic_cast<LoopPass *>(P); 211 if (LP) 212 Changed |= LP->doInitialization(L, *this); 213 } 214 } 215 216 // Walk Loops 217 while (!LQ.empty()) { 218 219 CurrentLoop = LQ.back(); 220 skipThisLoop = false; 221 redoThisLoop = false; 222 223 // Run all passes on the current Loop. 224 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 225 Pass *P = getContainedPass(Index); 226 227 dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, 228 CurrentLoop->getHeader()->getNameStr()); 229 dumpRequiredSet(P); 230 231 initializeAnalysisImpl(P); 232 233 LoopPass *LP = dynamic_cast<LoopPass *>(P); 234 assert(LP && "Invalid LPPassManager member"); 235 { 236 PassManagerPrettyStackEntry X(LP, *CurrentLoop->getHeader()); 237 Timer *T = StartPassTimer(P); 238 Changed |= LP->runOnLoop(CurrentLoop, *this); 239 StopPassTimer(P, T); 240 } 241 242 if (Changed) 243 dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, 244 skipThisLoop ? "<deleted>" : 245 CurrentLoop->getHeader()->getNameStr()); 246 dumpPreservedSet(P); 247 248 if (!skipThisLoop) { 249 // Manually check that this loop is still healthy. This is done 250 // instead of relying on LoopInfo::verifyLoop since LoopInfo 251 // is a function pass and it's really expensive to verify every 252 // loop in the function every time. That level of checking can be 253 // enabled with the -verify-loop-info option. 254 Timer *T = StartPassTimer(LI); 255 CurrentLoop->verifyLoop(); 256 StopPassTimer(LI, T); 257 258 // Then call the regular verifyAnalysis functions. 259 verifyPreservedAnalysis(LP); 260 } 261 262 removeNotPreservedAnalysis(P); 263 recordAvailableAnalysis(P); 264 removeDeadPasses(P, 265 skipThisLoop ? "<deleted>" : 266 CurrentLoop->getHeader()->getNameStr(), 267 ON_LOOP_MSG); 268 269 if (skipThisLoop) 270 // Do not run other passes on this loop. 271 break; 272 } 273 274 // If the loop was deleted, release all the loop passes. This frees up 275 // some memory, and avoids trouble with the pass manager trying to call 276 // verifyAnalysis on them. 277 if (skipThisLoop) 278 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 279 Pass *P = getContainedPass(Index); 280 freePass(P, "<deleted>", ON_LOOP_MSG); 281 } 282 283 // Pop the loop from queue after running all passes. 284 LQ.pop_back(); 285 286 if (redoThisLoop) 287 LQ.push_back(CurrentLoop); 288 } 289 290 // Finalization 291 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 292 Pass *P = getContainedPass(Index); 293 LoopPass *LP = dynamic_cast <LoopPass *>(P); 294 if (LP) 295 Changed |= LP->doFinalization(); 296 } 297 298 return Changed; 299} 300 301/// Print passes managed by this manager 302void LPPassManager::dumpPassStructure(unsigned Offset) { 303 errs().indent(Offset*2) << "Loop Pass Manager\n"; 304 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 305 Pass *P = getContainedPass(Index); 306 P->dumpPassStructure(Offset + 1); 307 dumpLastUses(P, Offset+1); 308 } 309} 310 311 312//===----------------------------------------------------------------------===// 313// LoopPass 314 315// Check if this pass is suitable for the current LPPassManager, if 316// available. This pass P is not suitable for a LPPassManager if P 317// is not preserving higher level analysis info used by other 318// LPPassManager passes. In such case, pop LPPassManager from the 319// stack. This will force assignPassManager() to create new 320// LPPassManger as expected. 321void LoopPass::preparePassManager(PMStack &PMS) { 322 323 // Find LPPassManager 324 while (!PMS.empty() && 325 PMS.top()->getPassManagerType() > PMT_LoopPassManager) 326 PMS.pop(); 327 328 LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 329 330 // If this pass is destroying high level information that is used 331 // by other passes that are managed by LPM then do not insert 332 // this pass in current LPM. Use new LPPassManager. 333 if (LPPM && !LPPM->preserveHigherLevelAnalysis(this)) 334 PMS.pop(); 335} 336 337/// Assign pass manager to manage this pass. 338void LoopPass::assignPassManager(PMStack &PMS, 339 PassManagerType PreferredType) { 340 // Find LPPassManager 341 while (!PMS.empty() && 342 PMS.top()->getPassManagerType() > PMT_LoopPassManager) 343 PMS.pop(); 344 345 LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 346 347 // Create new Loop Pass Manager if it does not exist. 348 if (!LPPM) { 349 350 assert (!PMS.empty() && "Unable to create Loop Pass Manager"); 351 PMDataManager *PMD = PMS.top(); 352 353 // [1] Create new Call Graph Pass Manager 354 LPPM = new LPPassManager(PMD->getDepth() + 1); 355 LPPM->populateInheritedAnalysis(PMS); 356 357 // [2] Set up new manager's top level manager 358 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 359 TPM->addIndirectPassManager(LPPM); 360 361 // [3] Assign manager to manage this new manager. This may create 362 // and push new managers into PMS 363 Pass *P = dynamic_cast<Pass *>(LPPM); 364 TPM->schedulePass(P); 365 366 // [4] Push new manager into PMS 367 PMS.push(LPPM); 368 } 369 370 LPPM->add(this); 371} 372