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