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