1193323Sed//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements LoopPass and LPPassManager. All loop optimization 11193323Sed// and transformation passes are derived from LoopPass. LPPassManager is 12193323Sed// responsible for managing LoopPasses. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#include "llvm/Analysis/LoopPass.h" 17206124Srdivacky#include "llvm/Assembly/PrintModulePass.h" 18206124Srdivacky#include "llvm/Support/Debug.h" 19206083Srdivacky#include "llvm/Support/Timer.h" 20193323Sedusing namespace llvm; 21193323Sed 22206124Srdivackynamespace { 23206124Srdivacky 24206124Srdivacky/// PrintLoopPass - Print a Function corresponding to a Loop. 25206124Srdivacky/// 26206124Srdivackyclass PrintLoopPass : public LoopPass { 27206124Srdivackyprivate: 28206124Srdivacky std::string Banner; 29206124Srdivacky raw_ostream &Out; // raw_ostream to print on. 30206124Srdivacky 31206124Srdivackypublic: 32206124Srdivacky static char ID; 33206124Srdivacky PrintLoopPass(const std::string &B, raw_ostream &o) 34212904Sdim : LoopPass(ID), Banner(B), Out(o) {} 35206124Srdivacky 36206124Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const { 37206124Srdivacky AU.setPreservesAll(); 38206124Srdivacky } 39206124Srdivacky 40206124Srdivacky bool runOnLoop(Loop *L, LPPassManager &) { 41206124Srdivacky Out << Banner; 42206124Srdivacky for (Loop::block_iterator b = L->block_begin(), be = L->block_end(); 43206124Srdivacky b != be; 44206124Srdivacky ++b) { 45206124Srdivacky (*b)->print(Out); 46206124Srdivacky } 47206124Srdivacky return false; 48206124Srdivacky } 49206124Srdivacky}; 50206124Srdivacky 51206124Srdivackychar PrintLoopPass::ID = 0; 52206124Srdivacky} 53206124Srdivacky 54193323Sed//===----------------------------------------------------------------------===// 55193323Sed// LPPassManager 56193323Sed// 57193323Sed 58193323Sedchar LPPassManager::ID = 0; 59193323Sed 60226633SdimLPPassManager::LPPassManager() 61226633Sdim : FunctionPass(ID), PMDataManager() { 62193323Sed skipThisLoop = false; 63193323Sed redoThisLoop = false; 64193323Sed LI = NULL; 65193323Sed CurrentLoop = NULL; 66193323Sed} 67193323Sed 68226633Sdim/// Delete loop from the loop queue and loop hierarchy (LoopInfo). 69193323Sedvoid LPPassManager::deleteLoopFromQueue(Loop *L) { 70193323Sed 71226633Sdim LI->updateUnloop(L); 72193323Sed 73193323Sed // If L is current loop then skip rest of the passes and let 74193323Sed // runOnFunction remove L from LQ. Otherwise, remove L from LQ now 75193323Sed // and continue applying other passes on CurrentLoop. 76226633Sdim if (CurrentLoop == L) 77193323Sed skipThisLoop = true; 78226633Sdim 79226633Sdim delete L; 80226633Sdim 81226633Sdim if (skipThisLoop) 82193323Sed return; 83193323Sed 84193323Sed for (std::deque<Loop *>::iterator I = LQ.begin(), 85193323Sed E = LQ.end(); I != E; ++I) { 86193323Sed if (*I == L) { 87193323Sed LQ.erase(I); 88193323Sed break; 89193323Sed } 90193323Sed } 91193323Sed} 92193323Sed 93193323Sed// Inset loop into loop nest (LoopInfo) and loop queue (LQ). 94193323Sedvoid LPPassManager::insertLoop(Loop *L, Loop *ParentLoop) { 95193323Sed 96193323Sed assert (CurrentLoop != L && "Cannot insert CurrentLoop"); 97193323Sed 98193323Sed // Insert into loop nest 99193323Sed if (ParentLoop) 100193323Sed ParentLoop->addChildLoop(L); 101193323Sed else 102193323Sed LI->addTopLevelLoop(L); 103193323Sed 104198090Srdivacky insertLoopIntoQueue(L); 105198090Srdivacky} 106198090Srdivacky 107198090Srdivackyvoid LPPassManager::insertLoopIntoQueue(Loop *L) { 108193323Sed // Insert L into loop queue 109226633Sdim if (L == CurrentLoop) 110193323Sed redoLoop(L); 111198090Srdivacky else if (!L->getParentLoop()) 112226633Sdim // This is top level loop. 113193323Sed LQ.push_front(L); 114193323Sed else { 115198090Srdivacky // Insert L after the parent loop. 116193323Sed for (std::deque<Loop *>::iterator I = LQ.begin(), 117193323Sed E = LQ.end(); I != E; ++I) { 118198090Srdivacky if (*I == L->getParentLoop()) { 119193323Sed // deque does not support insert after. 120193323Sed ++I; 121193323Sed LQ.insert(I, 1, L); 122193323Sed break; 123193323Sed } 124193323Sed } 125193323Sed } 126193323Sed} 127193323Sed 128193323Sed// Reoptimize this loop. LPPassManager will re-insert this loop into the 129193323Sed// queue. This allows LoopPass to change loop nest for the loop. This 130193323Sed// utility may send LPPassManager into infinite loops so use caution. 131193323Sedvoid LPPassManager::redoLoop(Loop *L) { 132193323Sed assert (CurrentLoop == L && "Can redo only CurrentLoop"); 133193323Sed redoThisLoop = true; 134193323Sed} 135193323Sed 136193323Sed/// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for 137193323Sed/// all loop passes. 138226633Sdimvoid LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, 139193323Sed BasicBlock *To, Loop *L) { 140226633Sdim for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 141212904Sdim LoopPass *LP = getContainedPass(Index); 142193323Sed LP->cloneBasicBlockAnalysis(From, To, L); 143193323Sed } 144193323Sed} 145193323Sed 146193323Sed/// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes. 147193323Sedvoid LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) { 148193323Sed if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 149226633Sdim for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; 150193323Sed ++BI) { 151193323Sed Instruction &I = *BI; 152193323Sed deleteSimpleAnalysisValue(&I, L); 153193323Sed } 154193323Sed } 155226633Sdim for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 156212904Sdim LoopPass *LP = getContainedPass(Index); 157193323Sed LP->deleteAnalysisValue(V, L); 158193323Sed } 159193323Sed} 160193323Sed 161193323Sed 162193323Sed// Recurse through all subloops and all loops into LQ. 163193323Sedstatic void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { 164193323Sed LQ.push_back(L); 165239462Sdim for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I) 166193323Sed addLoopIntoQueue(*I, LQ); 167193323Sed} 168193323Sed 169193323Sed/// Pass Manager itself does not invalidate any analysis info. 170193323Sedvoid LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { 171226633Sdim // LPPassManager needs LoopInfo. In the long term LoopInfo class will 172193323Sed // become part of LPPassManager. 173193323Sed Info.addRequired<LoopInfo>(); 174193323Sed Info.setPreservesAll(); 175193323Sed} 176193323Sed 177193323Sed/// run - Execute all of the passes scheduled for execution. Keep track of 178193323Sed/// whether any of the passes modifies the function, and if so, return true. 179193323Sedbool LPPassManager::runOnFunction(Function &F) { 180193323Sed LI = &getAnalysis<LoopInfo>(); 181193323Sed bool Changed = false; 182193323Sed 183193323Sed // Collect inherited analysis from Module level pass manager. 184193323Sed populateInheritedAnalysis(TPM->activeStack); 185193323Sed 186239462Sdim // Populate the loop queue in reverse program order. There is no clear need to 187239462Sdim // process sibling loops in either forward or reverse order. There may be some 188239462Sdim // advantage in deleting uses in a later loop before optimizing the 189239462Sdim // definitions in an earlier loop. If we find a clear reason to process in 190239462Sdim // forward order, then a forward variant of LoopPassManager should be created. 191263508Sdim // 192263508Sdim // Note that LoopInfo::iterator visits loops in reverse program 193263508Sdim // order. Here, reverse_iterator gives us a forward order, and the LoopQueue 194263508Sdim // reverses the order a third time by popping from the back. 195239462Sdim for (LoopInfo::reverse_iterator I = LI->rbegin(), E = LI->rend(); I != E; ++I) 196193323Sed addLoopIntoQueue(*I, LQ); 197193323Sed 198195340Sed if (LQ.empty()) // No loops, skip calling finalizers 199195340Sed return false; 200195340Sed 201193323Sed // Initialization 202193323Sed for (std::deque<Loop *>::const_iterator I = LQ.begin(), E = LQ.end(); 203193323Sed I != E; ++I) { 204193323Sed Loop *L = *I; 205226633Sdim for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 206212904Sdim LoopPass *P = getContainedPass(Index); 207202878Srdivacky Changed |= P->doInitialization(L, *this); 208193323Sed } 209193323Sed } 210193323Sed 211193323Sed // Walk Loops 212193323Sed while (!LQ.empty()) { 213226633Sdim 214193323Sed CurrentLoop = LQ.back(); 215193323Sed skipThisLoop = false; 216193323Sed redoThisLoop = false; 217193323Sed 218198090Srdivacky // Run all passes on the current Loop. 219226633Sdim for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 220212904Sdim LoopPass *P = getContainedPass(Index); 221234353Sdim 222198090Srdivacky dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, 223206083Srdivacky CurrentLoop->getHeader()->getName()); 224193323Sed dumpRequiredSet(P); 225193323Sed 226193323Sed initializeAnalysisImpl(P); 227234353Sdim 228193323Sed { 229202878Srdivacky PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader()); 230206083Srdivacky TimeRegion PassTimer(getPassTimer(P)); 231206083Srdivacky 232202878Srdivacky Changed |= P->runOnLoop(CurrentLoop, *this); 233193323Sed } 234193323Sed 235193323Sed if (Changed) 236198090Srdivacky dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, 237198090Srdivacky skipThisLoop ? "<deleted>" : 238206083Srdivacky CurrentLoop->getHeader()->getName()); 239193323Sed dumpPreservedSet(P); 240193323Sed 241198090Srdivacky if (!skipThisLoop) { 242198090Srdivacky // Manually check that this loop is still healthy. This is done 243198090Srdivacky // instead of relying on LoopInfo::verifyLoop since LoopInfo 244198090Srdivacky // is a function pass and it's really expensive to verify every 245198090Srdivacky // loop in the function every time. That level of checking can be 246198090Srdivacky // enabled with the -verify-loop-info option. 247206083Srdivacky { 248206083Srdivacky TimeRegion PassTimer(getPassTimer(LI)); 249206083Srdivacky CurrentLoop->verifyLoop(); 250206083Srdivacky } 251198090Srdivacky 252198090Srdivacky // Then call the regular verifyAnalysis functions. 253202878Srdivacky verifyPreservedAnalysis(P); 254198090Srdivacky } 255198090Srdivacky 256193323Sed removeNotPreservedAnalysis(P); 257193323Sed recordAvailableAnalysis(P); 258198090Srdivacky removeDeadPasses(P, 259198090Srdivacky skipThisLoop ? "<deleted>" : 260206083Srdivacky CurrentLoop->getHeader()->getName(), 261198090Srdivacky ON_LOOP_MSG); 262193323Sed 263193323Sed if (skipThisLoop) 264193323Sed // Do not run other passes on this loop. 265193323Sed break; 266193323Sed } 267226633Sdim 268198090Srdivacky // If the loop was deleted, release all the loop passes. This frees up 269198090Srdivacky // some memory, and avoids trouble with the pass manager trying to call 270198090Srdivacky // verifyAnalysis on them. 271198090Srdivacky if (skipThisLoop) 272226633Sdim for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 273198090Srdivacky Pass *P = getContainedPass(Index); 274198090Srdivacky freePass(P, "<deleted>", ON_LOOP_MSG); 275198090Srdivacky } 276198090Srdivacky 277193323Sed // Pop the loop from queue after running all passes. 278193323Sed LQ.pop_back(); 279226633Sdim 280193323Sed if (redoThisLoop) 281193323Sed LQ.push_back(CurrentLoop); 282193323Sed } 283226633Sdim 284193323Sed // Finalization 285193323Sed for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 286212904Sdim LoopPass *P = getContainedPass(Index); 287202878Srdivacky Changed |= P->doFinalization(); 288193323Sed } 289193323Sed 290193323Sed return Changed; 291193323Sed} 292193323Sed 293193323Sed/// Print passes managed by this manager 294193323Sedvoid LPPassManager::dumpPassStructure(unsigned Offset) { 295198090Srdivacky errs().indent(Offset*2) << "Loop Pass Manager\n"; 296193323Sed for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 297193323Sed Pass *P = getContainedPass(Index); 298193323Sed P->dumpPassStructure(Offset + 1); 299193323Sed dumpLastUses(P, Offset+1); 300193323Sed } 301193323Sed} 302193323Sed 303193323Sed 304193323Sed//===----------------------------------------------------------------------===// 305193323Sed// LoopPass 306193323Sed 307206124SrdivackyPass *LoopPass::createPrinterPass(raw_ostream &O, 308206124Srdivacky const std::string &Banner) const { 309206124Srdivacky return new PrintLoopPass(Banner, O); 310206124Srdivacky} 311206124Srdivacky 312193323Sed// Check if this pass is suitable for the current LPPassManager, if 313193323Sed// available. This pass P is not suitable for a LPPassManager if P 314193323Sed// is not preserving higher level analysis info used by other 315193323Sed// LPPassManager passes. In such case, pop LPPassManager from the 316193323Sed// stack. This will force assignPassManager() to create new 317193323Sed// LPPassManger as expected. 318193323Sedvoid LoopPass::preparePassManager(PMStack &PMS) { 319193323Sed 320226633Sdim // Find LPPassManager 321193323Sed while (!PMS.empty() && 322193323Sed PMS.top()->getPassManagerType() > PMT_LoopPassManager) 323193323Sed PMS.pop(); 324193323Sed 325193323Sed // If this pass is destroying high level information that is used 326193323Sed // by other passes that are managed by LPM then do not insert 327193323Sed // this pass in current LPM. Use new LPPassManager. 328202878Srdivacky if (PMS.top()->getPassManagerType() == PMT_LoopPassManager && 329226633Sdim !PMS.top()->preserveHigherLevelAnalysis(this)) 330193323Sed PMS.pop(); 331193323Sed} 332193323Sed 333193323Sed/// Assign pass manager to manage this pass. 334193323Sedvoid LoopPass::assignPassManager(PMStack &PMS, 335193323Sed PassManagerType PreferredType) { 336226633Sdim // Find LPPassManager 337193323Sed while (!PMS.empty() && 338193323Sed PMS.top()->getPassManagerType() > PMT_LoopPassManager) 339193323Sed PMS.pop(); 340193323Sed 341202878Srdivacky LPPassManager *LPPM; 342202878Srdivacky if (PMS.top()->getPassManagerType() == PMT_LoopPassManager) 343202878Srdivacky LPPM = (LPPassManager*)PMS.top(); 344202878Srdivacky else { 345226633Sdim // Create new Loop Pass Manager if it does not exist. 346193323Sed assert (!PMS.empty() && "Unable to create Loop Pass Manager"); 347193323Sed PMDataManager *PMD = PMS.top(); 348193323Sed 349226633Sdim // [1] Create new Loop Pass Manager 350226633Sdim LPPM = new LPPassManager(); 351193323Sed LPPM->populateInheritedAnalysis(PMS); 352193323Sed 353193323Sed // [2] Set up new manager's top level manager 354193323Sed PMTopLevelManager *TPM = PMD->getTopLevelManager(); 355193323Sed TPM->addIndirectPassManager(LPPM); 356193323Sed 357193323Sed // [3] Assign manager to manage this new manager. This may create 358193323Sed // and push new managers into PMS 359202878Srdivacky Pass *P = LPPM->getAsPass(); 360193323Sed TPM->schedulePass(P); 361193323Sed 362193323Sed // [4] Push new manager into PMS 363193323Sed PMS.push(LPPM); 364193323Sed } 365193323Sed 366193323Sed LPPM->add(this); 367193323Sed} 368