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/Analysis/LoopAnalysisManager.h" 18 #include "llvm/IR/Dominators.h" 19 #include "llvm/IR/IRPrintingPasses.h" 20 #include "llvm/IR/LLVMContext.h" 21 #include "llvm/IR/OptBisect.h" 22 #include "llvm/IR/PassManager.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/Timer.h" 25 #include "llvm/Support/raw_ostream.h" 26 using namespace llvm; 27 28 #define DEBUG_TYPE "loop-pass-manager" 29 30 namespace { 31 32 /// PrintLoopPass - Print a Function corresponding to a Loop. 33 /// 34 class PrintLoopPassWrapper : public LoopPass { 35 raw_ostream &OS; 36 std::string Banner; 37 38 public: 39 static char ID; 40 PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {} 41 PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner) 42 : LoopPass(ID), OS(OS), Banner(Banner) {} 43 44 void getAnalysisUsage(AnalysisUsage &AU) const override { 45 AU.setPreservesAll(); 46 } 47 48 bool runOnLoop(Loop *L, LPPassManager &) override { 49 auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; }); 50 if (BBI != L->blocks().end() && 51 isFunctionInPrintList((*BBI)->getParent()->getName())) { 52 printLoop(*L, OS, Banner); 53 } 54 return false; 55 } 56 57 StringRef getPassName() const override { return "Print Loop IR"; } 58 }; 59 60 char PrintLoopPassWrapper::ID = 0; 61 } 62 63 //===----------------------------------------------------------------------===// 64 // LPPassManager 65 // 66 67 char LPPassManager::ID = 0; 68 69 LPPassManager::LPPassManager() 70 : FunctionPass(ID), PMDataManager() { 71 LI = nullptr; 72 CurrentLoop = nullptr; 73 } 74 75 // Insert loop into loop nest (LoopInfo) and loop queue (LQ). 76 void LPPassManager::addLoop(Loop &L) { 77 if (!L.getParentLoop()) { 78 // This is the top level loop. 79 LQ.push_front(&L); 80 return; 81 } 82 83 // Insert L into the loop queue after the parent loop. 84 for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) { 85 if (*I == L.getParentLoop()) { 86 // deque does not support insert after. 87 ++I; 88 LQ.insert(I, 1, &L); 89 return; 90 } 91 } 92 } 93 94 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for 95 /// all loop passes. 96 void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From, 97 BasicBlock *To, Loop *L) { 98 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 99 LoopPass *LP = getContainedPass(Index); 100 LP->cloneBasicBlockAnalysis(From, To, L); 101 } 102 } 103 104 /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes. 105 void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) { 106 if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) { 107 for (Instruction &I : *BB) { 108 deleteSimpleAnalysisValue(&I, L); 109 } 110 } 111 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 112 LoopPass *LP = getContainedPass(Index); 113 LP->deleteAnalysisValue(V, L); 114 } 115 } 116 117 /// Invoke deleteAnalysisLoop hook for all passes. 118 void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) { 119 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 120 LoopPass *LP = getContainedPass(Index); 121 LP->deleteAnalysisLoop(L); 122 } 123 } 124 125 126 // Recurse through all subloops and all loops into LQ. 127 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) { 128 LQ.push_back(L); 129 for (Loop *I : reverse(*L)) 130 addLoopIntoQueue(I, LQ); 131 } 132 133 /// Pass Manager itself does not invalidate any analysis info. 134 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { 135 // LPPassManager needs LoopInfo. In the long term LoopInfo class will 136 // become part of LPPassManager. 137 Info.addRequired<LoopInfoWrapperPass>(); 138 Info.addRequired<DominatorTreeWrapperPass>(); 139 Info.setPreservesAll(); 140 } 141 142 void LPPassManager::markLoopAsDeleted(Loop &L) { 143 assert((&L == CurrentLoop || CurrentLoop->contains(&L)) && 144 "Must not delete loop outside the current loop tree!"); 145 // If this loop appears elsewhere within the queue, we also need to remove it 146 // there. However, we have to be careful to not remove the back of the queue 147 // as that is assumed to match the current loop. 148 assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!"); 149 LQ.erase(std::remove(LQ.begin(), LQ.end(), &L), LQ.end()); 150 151 if (&L == CurrentLoop) { 152 CurrentLoopDeleted = true; 153 // Add this loop back onto the back of the queue to preserve our invariants. 154 LQ.push_back(&L); 155 } 156 } 157 158 /// run - Execute all of the passes scheduled for execution. Keep track of 159 /// whether any of the passes modifies the function, and if so, return true. 160 bool LPPassManager::runOnFunction(Function &F) { 161 auto &LIWP = getAnalysis<LoopInfoWrapperPass>(); 162 LI = &LIWP.getLoopInfo(); 163 Module &M = *F.getParent(); 164 #if 0 165 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 166 #endif 167 bool Changed = false; 168 169 // Collect inherited analysis from Module level pass manager. 170 populateInheritedAnalysis(TPM->activeStack); 171 172 // Populate the loop queue in reverse program order. There is no clear need to 173 // process sibling loops in either forward or reverse order. There may be some 174 // advantage in deleting uses in a later loop before optimizing the 175 // definitions in an earlier loop. If we find a clear reason to process in 176 // forward order, then a forward variant of LoopPassManager should be created. 177 // 178 // Note that LoopInfo::iterator visits loops in reverse program 179 // order. Here, reverse_iterator gives us a forward order, and the LoopQueue 180 // reverses the order a third time by popping from the back. 181 for (Loop *L : reverse(*LI)) 182 addLoopIntoQueue(L, LQ); 183 184 if (LQ.empty()) // No loops, skip calling finalizers 185 return false; 186 187 // Initialization 188 for (Loop *L : LQ) { 189 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 190 LoopPass *P = getContainedPass(Index); 191 Changed |= P->doInitialization(L, *this); 192 } 193 } 194 195 // Walk Loops 196 unsigned InstrCount = 0; 197 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark(); 198 while (!LQ.empty()) { 199 CurrentLoopDeleted = false; 200 CurrentLoop = LQ.back(); 201 202 // Run all passes on the current Loop. 203 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 204 LoopPass *P = getContainedPass(Index); 205 206 dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG, 207 CurrentLoop->getHeader()->getName()); 208 dumpRequiredSet(P); 209 210 initializeAnalysisImpl(P); 211 212 { 213 PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader()); 214 TimeRegion PassTimer(getPassTimer(P)); 215 if (EmitICRemark) 216 InstrCount = initSizeRemarkInfo(M); 217 Changed |= P->runOnLoop(CurrentLoop, *this); 218 if (EmitICRemark) 219 emitInstrCountChangedRemark(P, M, InstrCount); 220 } 221 222 if (Changed) 223 dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, 224 CurrentLoopDeleted ? "<deleted loop>" 225 : CurrentLoop->getName()); 226 dumpPreservedSet(P); 227 228 if (CurrentLoopDeleted) { 229 // Notify passes that the loop is being deleted. 230 deleteSimpleAnalysisLoop(CurrentLoop); 231 } else { 232 // Manually check that this loop is still healthy. This is done 233 // instead of relying on LoopInfo::verifyLoop since LoopInfo 234 // is a function pass and it's really expensive to verify every 235 // loop in the function every time. That level of checking can be 236 // enabled with the -verify-loop-info option. 237 { 238 TimeRegion PassTimer(getPassTimer(&LIWP)); 239 CurrentLoop->verifyLoop(); 240 } 241 // Here we apply same reasoning as in the above case. Only difference 242 // is that LPPassManager might run passes which do not require LCSSA 243 // form (LoopPassPrinter for example). We should skip verification for 244 // such passes. 245 // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the 246 // verification! 247 #if 0 248 if (mustPreserveAnalysisID(LCSSAVerificationPass::ID)) 249 assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI)); 250 #endif 251 252 // Then call the regular verifyAnalysis functions. 253 verifyPreservedAnalysis(P); 254 255 F.getContext().yield(); 256 } 257 258 removeNotPreservedAnalysis(P); 259 recordAvailableAnalysis(P); 260 removeDeadPasses(P, 261 CurrentLoopDeleted ? "<deleted>" 262 : CurrentLoop->getHeader()->getName(), 263 ON_LOOP_MSG); 264 265 if (CurrentLoopDeleted) 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 (CurrentLoopDeleted) { 274 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 275 Pass *P = getContainedPass(Index); 276 freePass(P, "<deleted>", ON_LOOP_MSG); 277 } 278 } 279 280 // Pop the loop from queue after running all passes. 281 LQ.pop_back(); 282 } 283 284 // Finalization 285 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 286 LoopPass *P = getContainedPass(Index); 287 Changed |= P->doFinalization(); 288 } 289 290 return Changed; 291 } 292 293 /// Print passes managed by this manager 294 void LPPassManager::dumpPassStructure(unsigned Offset) { 295 errs().indent(Offset*2) << "Loop Pass Manager\n"; 296 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 297 Pass *P = getContainedPass(Index); 298 P->dumpPassStructure(Offset + 1); 299 dumpLastUses(P, Offset+1); 300 } 301 } 302 303 304 //===----------------------------------------------------------------------===// 305 // LoopPass 306 307 Pass *LoopPass::createPrinterPass(raw_ostream &O, 308 const std::string &Banner) const { 309 return new PrintLoopPassWrapper(O, Banner); 310 } 311 312 // Check if this pass is suitable for the current LPPassManager, if 313 // available. This pass P is not suitable for a LPPassManager if P 314 // is not preserving higher level analysis info used by other 315 // LPPassManager passes. In such case, pop LPPassManager from the 316 // stack. This will force assignPassManager() to create new 317 // LPPassManger as expected. 318 void LoopPass::preparePassManager(PMStack &PMS) { 319 320 // Find LPPassManager 321 while (!PMS.empty() && 322 PMS.top()->getPassManagerType() > PMT_LoopPassManager) 323 PMS.pop(); 324 325 // If this pass is destroying high level information that is used 326 // by other passes that are managed by LPM then do not insert 327 // this pass in current LPM. Use new LPPassManager. 328 if (PMS.top()->getPassManagerType() == PMT_LoopPassManager && 329 !PMS.top()->preserveHigherLevelAnalysis(this)) 330 PMS.pop(); 331 } 332 333 /// Assign pass manager to manage this pass. 334 void LoopPass::assignPassManager(PMStack &PMS, 335 PassManagerType PreferredType) { 336 // Find LPPassManager 337 while (!PMS.empty() && 338 PMS.top()->getPassManagerType() > PMT_LoopPassManager) 339 PMS.pop(); 340 341 LPPassManager *LPPM; 342 if (PMS.top()->getPassManagerType() == PMT_LoopPassManager) 343 LPPM = (LPPassManager*)PMS.top(); 344 else { 345 // Create new Loop Pass Manager if it does not exist. 346 assert (!PMS.empty() && "Unable to create Loop Pass Manager"); 347 PMDataManager *PMD = PMS.top(); 348 349 // [1] Create new Loop Pass Manager 350 LPPM = new LPPassManager(); 351 LPPM->populateInheritedAnalysis(PMS); 352 353 // [2] Set up new manager's top level manager 354 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 355 TPM->addIndirectPassManager(LPPM); 356 357 // [3] Assign manager to manage this new manager. This may create 358 // and push new managers into PMS 359 Pass *P = LPPM->getAsPass(); 360 TPM->schedulePass(P); 361 362 // [4] Push new manager into PMS 363 PMS.push(LPPM); 364 } 365 366 LPPM->add(this); 367 } 368 369 bool LoopPass::skipLoop(const Loop *L) const { 370 const Function *F = L->getHeader()->getParent(); 371 if (!F) 372 return false; 373 // Check the opt bisect limit. 374 LLVMContext &Context = F->getContext(); 375 if (!Context.getOptPassGate().shouldRunPass(this, *L)) 376 return true; 377 // Check for the OptimizeNone attribute. 378 if (F->hasFnAttribute(Attribute::OptimizeNone)) { 379 // FIXME: Report this to dbgs() only once per function. 380 LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function " 381 << F->getName() << "\n"); 382 // FIXME: Delete loop from pass manager's queue? 383 return true; 384 } 385 return false; 386 } 387 388 char LCSSAVerificationPass::ID = 0; 389 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier", 390 false, false) 391