LoopPass.cpp revision 193323
1139731Simp//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===// 299123Sobrien// 399123Sobrien// The LLVM Compiler Infrastructure 499123Sobrien// 599123Sobrien// This file is distributed under the University of Illinois Open Source 699123Sobrien// License. See LICENSE.TXT for details. 799123Sobrien// 899123Sobrien//===----------------------------------------------------------------------===// 999123Sobrien// 1099123Sobrien// This file implements LoopPass and LPPassManager. All loop optimization 1199123Sobrien// and transformation passes are derived from LoopPass. LPPassManager is 1299123Sobrien// responsible for managing LoopPasses. 1399123Sobrien// 1499123Sobrien//===----------------------------------------------------------------------===// 1599123Sobrien 1699123Sobrien#include "llvm/Analysis/LoopPass.h" 1799123Sobrienusing namespace llvm; 1899123Sobrien 1999123Sobrien//===----------------------------------------------------------------------===// 2099123Sobrien// LPPassManager 2199123Sobrien// 2299123Sobrien 2399123Sobrienchar LPPassManager::ID = 0; 2499123Sobrien/// LPPassManager manages FPPassManagers and CalLGraphSCCPasses. 2599123Sobrien 2699123SobrienLPPassManager::LPPassManager(int Depth) 2799123Sobrien : FunctionPass(&ID), PMDataManager(Depth) { 2899123Sobrien skipThisLoop = false; 2999123Sobrien redoThisLoop = false; 3099123Sobrien LI = NULL; 3199123Sobrien CurrentLoop = NULL; 3299123Sobrien} 3399123Sobrien 3499123Sobrien/// Delete loop from the loop queue and loop hierarchy (LoopInfo). 3599123Sobrienvoid LPPassManager::deleteLoopFromQueue(Loop *L) { 3699123Sobrien 3799123Sobrien if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop. 3899123Sobrien // Reparent all of the blocks in this loop. Since BBLoop had a parent, 3999123Sobrien // they are now all in it. 4099123Sobrien for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 4199123Sobrien I != E; ++I) 4299123Sobrien if (LI->getLoopFor(*I) == L) // Don't change blocks in subloops. 43114349Speter LI->changeLoopFor(*I, ParentLoop); 4499123Sobrien 4599123Sobrien // Remove the loop from its parent loop. 4699123Sobrien for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; 4799123Sobrien ++I) { 4899123Sobrien assert(I != E && "Couldn't find loop"); 4999123Sobrien if (*I == L) { 5099123Sobrien ParentLoop->removeChildLoop(I); 5199123Sobrien break; 5299123Sobrien } 5399123Sobrien } 5499123Sobrien 5599123Sobrien // Move all subloops into the parent loop. 5699123Sobrien while (!L->empty()) 5799123Sobrien ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1)); 58114349Speter } else { 5999123Sobrien // Reparent all of the blocks in this loop. Since BBLoop had no parent, 6099123Sobrien // they no longer in a loop at all. 6199123Sobrien 6299123Sobrien for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 6399123Sobrien // Don't change blocks in subloops. 6499123Sobrien if (LI->getLoopFor(L->getBlocks()[i]) == L) { 6599123Sobrien LI->removeBlock(L->getBlocks()[i]); 6699123Sobrien --i; 6799123Sobrien } 6899123Sobrien } 69154128Simp 70154128Simp // Remove the loop from the top-level LoopInfo object. 71154128Simp for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) { 7299123Sobrien assert(I != E && "Couldn't find loop"); 7399123Sobrien if (*I == L) { 7499123Sobrien LI->removeLoop(I); 7599123Sobrien break; 76114346Speter } 7799123Sobrien } 7899123Sobrien 79114346Speter // Move all of the subloops to the top-level. 8099123Sobrien while (!L->empty()) 8199123Sobrien LI->addTopLevelLoop(L->removeChildLoop(L->end()-1)); 82122849Speter } 83147653Sjhb 84122849Speter delete L; 8599123Sobrien 86122849Speter // If L is current loop then skip rest of the passes and let 8799123Sobrien // runOnFunction remove L from LQ. Otherwise, remove L from LQ now 8899123Sobrien // and continue applying other passes on CurrentLoop. 8999123Sobrien if (CurrentLoop == L) { 90115795Speter skipThisLoop = true; 9199123Sobrien return; 92115251Speter } 93114349Speter 94114349Speter for (std::deque<Loop *>::iterator I = LQ.begin(), 95115251Speter E = LQ.end(); I != E; ++I) { 9699123Sobrien if (*I == L) { 9799123Sobrien LQ.erase(I); 9899123Sobrien break; 99114349Speter } 100114349Speter } 101115251Speter} 102114349Speter 103114349Speter// Inset loop into loop nest (LoopInfo) and loop queue (LQ). 104114349Spetervoid LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { 105114349Speter 106114349Speter assert (CurrentLoop != L && "Cannot insert CurrentLoop"); 107115251Speter 108114349Speter // Insert into loop nest 109114349Speter if (ParentLoop) 110114349Speter ParentLoop->addChildLoop(L); 111114349Speter else 112114349Speter LI->addTopLevelLoop(L); 113115251Speter 114130218Speter // Insert L into loop queue 115130218Speter if (L == CurrentLoop) 116130218Speter redoLoop(L); 11799123Sobrien else if (!ParentLoop) 11899123Sobrien // This is top level loop. 11999123Sobrien LQ.push_front(L); 120118236Speter else { 121114349Speter // Insert L after ParentLoop 122118236Speter for (std::deque<Loop *>::iterator I = LQ.begin(), 123116355Salc E = LQ.end(); I != E; ++I) { 12499123Sobrien if (*I == ParentLoop) { 12599123Sobrien // deque does not support insert after. 126114349Speter ++I; 127114349Speter LQ.insert(I, 1, L); 128114349Speter break; 129114349Speter } 130114349Speter } 131114349Speter } 132114349Speter} 133114349Speter 134114349Speter// Reoptimize this loop. LPPassManager will re-insert this loop into the 135114349Speter// queue. This allows LoopPass to change loop nest for the loop. This 136114349Speter// utility may send LPPassManager into infinite loops so use caution. 137114349Spetervoid LPPassManager::redoLoop(Loop *L) { 138114349Speter assert (CurrentLoop == L && "Can redo only CurrentLoop"); 139123692Salc redoThisLoop = true; 140114349Speter} 141114349Speter 142114349Speter/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for 14399123Sobrien/// all loop passes. 14499123Sobrienvoid LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, 14599123Sobrien BasicBlock *To, Loop *L) { 14699123Sobrien for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 147114349Speter Pass *P = getContainedPass(Index); 148114349Speter LoopPass *LP = dynamic_cast<LoopPass *>(P); 14999123Sobrien LP->cloneBasicBlockAnalysis(From, To, L); 15099123Sobrien } 15199123Sobrien} 15299123Sobrien 153114346Speter/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes. 154114346Spetervoid LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) { 15599123Sobrien if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 156114349Speter for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; 15799123Sobrien ++BI) { 15899123Sobrien Instruction &I = *BI; 15999123Sobrien deleteSimpleAnalysisValue(&I, L); 160 } 161 } 162 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 163 Pass *P = getContainedPass(Index); 164 LoopPass *LP = dynamic_cast<LoopPass *>(P); 165 LP->deleteAnalysisValue(V, L); 166 } 167} 168 169 170// Recurse through all subloops and all loops into LQ. 171static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { 172 LQ.push_back(L); 173 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 174 addLoopIntoQueue(*I, LQ); 175} 176 177/// Pass Manager itself does not invalidate any analysis info. 178void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { 179 // LPPassManager needs LoopInfo. In the long term LoopInfo class will 180 // become part of LPPassManager. 181 Info.addRequired<LoopInfo>(); 182 Info.setPreservesAll(); 183} 184 185/// run - Execute all of the passes scheduled for execution. Keep track of 186/// whether any of the passes modifies the function, and if so, return true. 187bool LPPassManager::runOnFunction(Function &F) { 188 LI = &getAnalysis<LoopInfo>(); 189 bool Changed = false; 190 191 // Collect inherited analysis from Module level pass manager. 192 populateInheritedAnalysis(TPM->activeStack); 193 194 // Populate Loop Queue 195 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 196 addLoopIntoQueue(*I, LQ); 197 198 // Initialization 199 for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end(); 200 I != E; ++I) { 201 Loop *L = *I; 202 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 203 Pass *P = getContainedPass(Index); 204 LoopPass *LP = dynamic_cast<LoopPass *>(P); 205 if (LP) 206 Changed |= LP->doInitialization(L, *this); 207 } 208 } 209 210 // Walk Loops 211 while (!LQ.empty()) { 212 213 CurrentLoop = LQ.back(); 214 skipThisLoop = false; 215 redoThisLoop = false; 216 217 // Run all passes on current SCC 218 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 219 Pass *P = getContainedPass(Index); 220 221 dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, ""); 222 dumpRequiredSet(P); 223 224 initializeAnalysisImpl(P); 225 226 LoopPass *LP = dynamic_cast<LoopPass *>(P); 227 { 228 PassManagerPrettyStackEntry X(LP, *CurrentLoop->getHeader()); 229 StartPassTimer(P); 230 assert(LP && "Invalid LPPassManager member"); 231 Changed |= LP->runOnLoop(CurrentLoop, *this); 232 StopPassTimer(P); 233 } 234 235 if (Changed) 236 dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, ""); 237 dumpPreservedSet(P); 238 239 verifyPreservedAnalysis(LP); 240 removeNotPreservedAnalysis(P); 241 recordAvailableAnalysis(P); 242 removeDeadPasses(P, "", ON_LOOP_MSG); 243 244 // If dominator information is available then verify the info if requested. 245 verifyDomInfo(*LP, F); 246 247 if (skipThisLoop) 248 // Do not run other passes on this loop. 249 break; 250 } 251 252 // Pop the loop from queue after running all passes. 253 LQ.pop_back(); 254 255 if (redoThisLoop) 256 LQ.push_back(CurrentLoop); 257 } 258 259 // Finalization 260 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 261 Pass *P = getContainedPass(Index); 262 LoopPass *LP = dynamic_cast <LoopPass *>(P); 263 if (LP) 264 Changed |= LP->doFinalization(); 265 } 266 267 return Changed; 268} 269 270/// Print passes managed by this manager 271void LPPassManager::dumpPassStructure(unsigned Offset) { 272 llvm::cerr << std::string(Offset*2, ' ') << "Loop Pass Manager\n"; 273 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 274 Pass *P = getContainedPass(Index); 275 P->dumpPassStructure(Offset + 1); 276 dumpLastUses(P, Offset+1); 277 } 278} 279 280 281//===----------------------------------------------------------------------===// 282// LoopPass 283 284// Check if this pass is suitable for the current LPPassManager, if 285// available. This pass P is not suitable for a LPPassManager if P 286// is not preserving higher level analysis info used by other 287// LPPassManager passes. In such case, pop LPPassManager from the 288// stack. This will force assignPassManager() to create new 289// LPPassManger as expected. 290void LoopPass::preparePassManager(PMStack &PMS) { 291 292 // Find LPPassManager 293 while (!PMS.empty() && 294 PMS.top()->getPassManagerType() > PMT_LoopPassManager) 295 PMS.pop(); 296 297 LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 298 299 // If this pass is destroying high level information that is used 300 // by other passes that are managed by LPM then do not insert 301 // this pass in current LPM. Use new LPPassManager. 302 if (LPPM && !LPPM->preserveHigherLevelAnalysis(this)) 303 PMS.pop(); 304} 305 306/// Assign pass manager to manage this pass. 307void LoopPass::assignPassManager(PMStack &PMS, 308 PassManagerType PreferredType) { 309 // Find LPPassManager 310 while (!PMS.empty() && 311 PMS.top()->getPassManagerType() > PMT_LoopPassManager) 312 PMS.pop(); 313 314 LPPassManager *LPPM = dynamic_cast<LPPassManager *>(PMS.top()); 315 316 // Create new Loop Pass Manager if it does not exist. 317 if (!LPPM) { 318 319 assert (!PMS.empty() && "Unable to create Loop Pass Manager"); 320 PMDataManager *PMD = PMS.top(); 321 322 // [1] Create new Call Graph Pass Manager 323 LPPM = new LPPassManager(PMD->getDepth() + 1); 324 LPPM->populateInheritedAnalysis(PMS); 325 326 // [2] Set up new manager's top level manager 327 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 328 TPM->addIndirectPassManager(LPPM); 329 330 // [3] Assign manager to manage this new manager. This may create 331 // and push new managers into PMS 332 Pass *P = dynamic_cast<Pass *>(LPPM); 333 TPM->schedulePass(P); 334 335 // [4] Push new manager into PMS 336 PMS.push(LPPM); 337 } 338 339 LPPM->add(this); 340} 341