LegacyPassManager.cpp revision 360784
1//===- LegacyPassManager.cpp - LLVM Pass Infrastructure Implementation ----===// 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 the legacy LLVM Pass Manager infrastructure. 10// 11//===----------------------------------------------------------------------===// 12 13#include "llvm/IR/LegacyPassManager.h" 14#include "llvm/ADT/MapVector.h" 15#include "llvm/ADT/Statistic.h" 16#include "llvm/IR/DiagnosticInfo.h" 17#include "llvm/IR/IRPrintingPasses.h" 18#include "llvm/IR/LLVMContext.h" 19#include "llvm/IR/LegacyPassManagers.h" 20#include "llvm/IR/LegacyPassNameParser.h" 21#include "llvm/IR/Module.h" 22#include "llvm/IR/PassTimingInfo.h" 23#include "llvm/Support/Chrono.h" 24#include "llvm/Support/CommandLine.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/Error.h" 27#include "llvm/Support/ErrorHandling.h" 28#include "llvm/Support/ManagedStatic.h" 29#include "llvm/Support/Mutex.h" 30#include "llvm/Support/TimeProfiler.h" 31#include "llvm/Support/Timer.h" 32#include "llvm/Support/raw_ostream.h" 33#include <algorithm> 34#include <unordered_set> 35using namespace llvm; 36using namespace llvm::legacy; 37 38// See PassManagers.h for Pass Manager infrastructure overview. 39 40//===----------------------------------------------------------------------===// 41// Pass debugging information. Often it is useful to find out what pass is 42// running when a crash occurs in a utility. When this library is compiled with 43// debugging on, a command line option (--debug-pass) is enabled that causes the 44// pass name to be printed before it executes. 45// 46 47namespace { 48// Different debug levels that can be enabled... 49enum PassDebugLevel { 50 Disabled, Arguments, Structure, Executions, Details 51}; 52} 53 54static cl::opt<enum PassDebugLevel> 55PassDebugging("debug-pass", cl::Hidden, 56 cl::desc("Print PassManager debugging information"), 57 cl::values( 58 clEnumVal(Disabled , "disable debug output"), 59 clEnumVal(Arguments , "print pass arguments to pass to 'opt'"), 60 clEnumVal(Structure , "print pass structure before run()"), 61 clEnumVal(Executions, "print pass name before it is executed"), 62 clEnumVal(Details , "print pass details when it is executed"))); 63 64namespace { 65typedef llvm::cl::list<const llvm::PassInfo *, bool, PassNameParser> 66PassOptionList; 67} 68 69// Print IR out before/after specified passes. 70static PassOptionList 71PrintBefore("print-before", 72 llvm::cl::desc("Print IR before specified passes"), 73 cl::Hidden); 74 75static PassOptionList 76PrintAfter("print-after", 77 llvm::cl::desc("Print IR after specified passes"), 78 cl::Hidden); 79 80static cl::opt<bool> PrintBeforeAll("print-before-all", 81 llvm::cl::desc("Print IR before each pass"), 82 cl::init(false), cl::Hidden); 83static cl::opt<bool> PrintAfterAll("print-after-all", 84 llvm::cl::desc("Print IR after each pass"), 85 cl::init(false), cl::Hidden); 86 87static cl::opt<bool> 88 PrintModuleScope("print-module-scope", 89 cl::desc("When printing IR for print-[before|after]{-all} " 90 "always print a module IR"), 91 cl::init(false), cl::Hidden); 92 93static cl::list<std::string> 94 PrintFuncsList("filter-print-funcs", cl::value_desc("function names"), 95 cl::desc("Only print IR for functions whose name " 96 "match this for all print-[before|after][-all] " 97 "options"), 98 cl::CommaSeparated, cl::Hidden); 99 100/// This is a helper to determine whether to print IR before or 101/// after a pass. 102 103bool llvm::shouldPrintBeforePass() { 104 return PrintBeforeAll || !PrintBefore.empty(); 105} 106 107bool llvm::shouldPrintAfterPass() { 108 return PrintAfterAll || !PrintAfter.empty(); 109} 110 111static bool ShouldPrintBeforeOrAfterPass(StringRef PassID, 112 PassOptionList &PassesToPrint) { 113 for (auto *PassInf : PassesToPrint) { 114 if (PassInf) 115 if (PassInf->getPassArgument() == PassID) { 116 return true; 117 } 118 } 119 return false; 120} 121 122bool llvm::shouldPrintBeforePass(StringRef PassID) { 123 return PrintBeforeAll || ShouldPrintBeforeOrAfterPass(PassID, PrintBefore); 124} 125 126bool llvm::shouldPrintAfterPass(StringRef PassID) { 127 return PrintAfterAll || ShouldPrintBeforeOrAfterPass(PassID, PrintAfter); 128} 129 130bool llvm::forcePrintModuleIR() { return PrintModuleScope; } 131 132bool llvm::isFunctionInPrintList(StringRef FunctionName) { 133 static std::unordered_set<std::string> PrintFuncNames(PrintFuncsList.begin(), 134 PrintFuncsList.end()); 135 return PrintFuncNames.empty() || PrintFuncNames.count(FunctionName); 136} 137/// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions 138/// or higher is specified. 139bool PMDataManager::isPassDebuggingExecutionsOrMore() const { 140 return PassDebugging >= Executions; 141} 142 143unsigned PMDataManager::initSizeRemarkInfo( 144 Module &M, StringMap<std::pair<unsigned, unsigned>> &FunctionToInstrCount) { 145 // Only calculate getInstructionCount if the size-info remark is requested. 146 unsigned InstrCount = 0; 147 148 // Collect instruction counts for every function. We'll use this to emit 149 // per-function size remarks later. 150 for (Function &F : M) { 151 unsigned FCount = F.getInstructionCount(); 152 153 // Insert a record into FunctionToInstrCount keeping track of the current 154 // size of the function as the first member of a pair. Set the second 155 // member to 0; if the function is deleted by the pass, then when we get 156 // here, we'll be able to let the user know that F no longer contributes to 157 // the module. 158 FunctionToInstrCount[F.getName().str()] = 159 std::pair<unsigned, unsigned>(FCount, 0); 160 InstrCount += FCount; 161 } 162 return InstrCount; 163} 164 165void PMDataManager::emitInstrCountChangedRemark( 166 Pass *P, Module &M, int64_t Delta, unsigned CountBefore, 167 StringMap<std::pair<unsigned, unsigned>> &FunctionToInstrCount, 168 Function *F) { 169 // If it's a pass manager, don't emit a remark. (This hinges on the assumption 170 // that the only passes that return non-null with getAsPMDataManager are pass 171 // managers.) The reason we have to do this is to avoid emitting remarks for 172 // CGSCC passes. 173 if (P->getAsPMDataManager()) 174 return; 175 176 // Set to true if this isn't a module pass or CGSCC pass. 177 bool CouldOnlyImpactOneFunction = (F != nullptr); 178 179 // Helper lambda that updates the changes to the size of some function. 180 auto UpdateFunctionChanges = 181 [&FunctionToInstrCount](Function &MaybeChangedFn) { 182 // Update the total module count. 183 unsigned FnSize = MaybeChangedFn.getInstructionCount(); 184 auto It = FunctionToInstrCount.find(MaybeChangedFn.getName()); 185 186 // If we created a new function, then we need to add it to the map and 187 // say that it changed from 0 instructions to FnSize. 188 if (It == FunctionToInstrCount.end()) { 189 FunctionToInstrCount[MaybeChangedFn.getName()] = 190 std::pair<unsigned, unsigned>(0, FnSize); 191 return; 192 } 193 // Insert the new function size into the second member of the pair. This 194 // tells us whether or not this function changed in size. 195 It->second.second = FnSize; 196 }; 197 198 // We need to initially update all of the function sizes. 199 // If no function was passed in, then we're either a module pass or an 200 // CGSCC pass. 201 if (!CouldOnlyImpactOneFunction) 202 std::for_each(M.begin(), M.end(), UpdateFunctionChanges); 203 else 204 UpdateFunctionChanges(*F); 205 206 // Do we have a function we can use to emit a remark? 207 if (!CouldOnlyImpactOneFunction) { 208 // We need a function containing at least one basic block in order to output 209 // remarks. Since it's possible that the first function in the module 210 // doesn't actually contain a basic block, we have to go and find one that's 211 // suitable for emitting remarks. 212 auto It = std::find_if(M.begin(), M.end(), 213 [](const Function &Fn) { return !Fn.empty(); }); 214 215 // Didn't find a function. Quit. 216 if (It == M.end()) 217 return; 218 219 // We found a function containing at least one basic block. 220 F = &*It; 221 } 222 int64_t CountAfter = static_cast<int64_t>(CountBefore) + Delta; 223 BasicBlock &BB = *F->begin(); 224 OptimizationRemarkAnalysis R("size-info", "IRSizeChange", 225 DiagnosticLocation(), &BB); 226 // FIXME: Move ore namespace to DiagnosticInfo so that we can use it. This 227 // would let us use NV instead of DiagnosticInfoOptimizationBase::Argument. 228 R << DiagnosticInfoOptimizationBase::Argument("Pass", P->getPassName()) 229 << ": IR instruction count changed from " 230 << DiagnosticInfoOptimizationBase::Argument("IRInstrsBefore", CountBefore) 231 << " to " 232 << DiagnosticInfoOptimizationBase::Argument("IRInstrsAfter", CountAfter) 233 << "; Delta: " 234 << DiagnosticInfoOptimizationBase::Argument("DeltaInstrCount", Delta); 235 F->getContext().diagnose(R); // Not using ORE for layering reasons. 236 237 // Emit per-function size change remarks separately. 238 std::string PassName = P->getPassName().str(); 239 240 // Helper lambda that emits a remark when the size of a function has changed. 241 auto EmitFunctionSizeChangedRemark = [&FunctionToInstrCount, &F, &BB, 242 &PassName](const std::string &Fname) { 243 unsigned FnCountBefore, FnCountAfter; 244 std::pair<unsigned, unsigned> &Change = FunctionToInstrCount[Fname]; 245 std::tie(FnCountBefore, FnCountAfter) = Change; 246 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) - 247 static_cast<int64_t>(FnCountBefore); 248 249 if (FnDelta == 0) 250 return; 251 252 // FIXME: We shouldn't use BB for the location here. Unfortunately, because 253 // the function that we're looking at could have been deleted, we can't use 254 // it for the source location. We *want* remarks when a function is deleted 255 // though, so we're kind of stuck here as is. (This remark, along with the 256 // whole-module size change remarks really ought not to have source 257 // locations at all.) 258 OptimizationRemarkAnalysis FR("size-info", "FunctionIRSizeChange", 259 DiagnosticLocation(), &BB); 260 FR << DiagnosticInfoOptimizationBase::Argument("Pass", PassName) 261 << ": Function: " 262 << DiagnosticInfoOptimizationBase::Argument("Function", Fname) 263 << ": IR instruction count changed from " 264 << DiagnosticInfoOptimizationBase::Argument("IRInstrsBefore", 265 FnCountBefore) 266 << " to " 267 << DiagnosticInfoOptimizationBase::Argument("IRInstrsAfter", 268 FnCountAfter) 269 << "; Delta: " 270 << DiagnosticInfoOptimizationBase::Argument("DeltaInstrCount", FnDelta); 271 F->getContext().diagnose(FR); 272 273 // Update the function size. 274 Change.first = FnCountAfter; 275 }; 276 277 // Are we looking at more than one function? If so, emit remarks for all of 278 // the functions in the module. Otherwise, only emit one remark. 279 if (!CouldOnlyImpactOneFunction) 280 std::for_each(FunctionToInstrCount.keys().begin(), 281 FunctionToInstrCount.keys().end(), 282 EmitFunctionSizeChangedRemark); 283 else 284 EmitFunctionSizeChangedRemark(F->getName().str()); 285} 286 287void PassManagerPrettyStackEntry::print(raw_ostream &OS) const { 288 if (!V && !M) 289 OS << "Releasing pass '"; 290 else 291 OS << "Running pass '"; 292 293 OS << P->getPassName() << "'"; 294 295 if (M) { 296 OS << " on module '" << M->getModuleIdentifier() << "'.\n"; 297 return; 298 } 299 if (!V) { 300 OS << '\n'; 301 return; 302 } 303 304 OS << " on "; 305 if (isa<Function>(V)) 306 OS << "function"; 307 else if (isa<BasicBlock>(V)) 308 OS << "basic block"; 309 else 310 OS << "value"; 311 312 OS << " '"; 313 V->printAsOperand(OS, /*PrintType=*/false, M); 314 OS << "'\n"; 315} 316 317namespace llvm { 318namespace legacy { 319//===----------------------------------------------------------------------===// 320// FunctionPassManagerImpl 321// 322/// FunctionPassManagerImpl manages FPPassManagers 323class FunctionPassManagerImpl : public Pass, 324 public PMDataManager, 325 public PMTopLevelManager { 326 virtual void anchor(); 327private: 328 bool wasRun; 329public: 330 static char ID; 331 explicit FunctionPassManagerImpl() : 332 Pass(PT_PassManager, ID), PMDataManager(), 333 PMTopLevelManager(new FPPassManager()), wasRun(false) {} 334 335 /// \copydoc FunctionPassManager::add() 336 void add(Pass *P) { 337 schedulePass(P); 338 } 339 340 /// createPrinterPass - Get a function printer pass. 341 Pass *createPrinterPass(raw_ostream &O, 342 const std::string &Banner) const override { 343 return createPrintFunctionPass(O, Banner); 344 } 345 346 // Prepare for running an on the fly pass, freeing memory if needed 347 // from a previous run. 348 void releaseMemoryOnTheFly(); 349 350 /// run - Execute all of the passes scheduled for execution. Keep track of 351 /// whether any of the passes modifies the module, and if so, return true. 352 bool run(Function &F); 353 354 /// doInitialization - Run all of the initializers for the function passes. 355 /// 356 bool doInitialization(Module &M) override; 357 358 /// doFinalization - Run all of the finalizers for the function passes. 359 /// 360 bool doFinalization(Module &M) override; 361 362 363 PMDataManager *getAsPMDataManager() override { return this; } 364 Pass *getAsPass() override { return this; } 365 PassManagerType getTopLevelPassManagerType() override { 366 return PMT_FunctionPassManager; 367 } 368 369 /// Pass Manager itself does not invalidate any analysis info. 370 void getAnalysisUsage(AnalysisUsage &Info) const override { 371 Info.setPreservesAll(); 372 } 373 374 FPPassManager *getContainedManager(unsigned N) { 375 assert(N < PassManagers.size() && "Pass number out of range!"); 376 FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]); 377 return FP; 378 } 379 380 void dumpPassStructure(unsigned Offset) override { 381 for (unsigned I = 0; I < getNumContainedManagers(); ++I) 382 getContainedManager(I)->dumpPassStructure(Offset); 383 } 384}; 385 386void FunctionPassManagerImpl::anchor() {} 387 388char FunctionPassManagerImpl::ID = 0; 389} // End of legacy namespace 390} // End of llvm namespace 391 392namespace { 393//===----------------------------------------------------------------------===// 394// MPPassManager 395// 396/// MPPassManager manages ModulePasses and function pass managers. 397/// It batches all Module passes and function pass managers together and 398/// sequences them to process one module. 399class MPPassManager : public Pass, public PMDataManager { 400public: 401 static char ID; 402 explicit MPPassManager() : 403 Pass(PT_PassManager, ID), PMDataManager() { } 404 405 // Delete on the fly managers. 406 ~MPPassManager() override { 407 for (auto &OnTheFlyManager : OnTheFlyManagers) { 408 FunctionPassManagerImpl *FPP = OnTheFlyManager.second; 409 delete FPP; 410 } 411 } 412 413 /// createPrinterPass - Get a module printer pass. 414 Pass *createPrinterPass(raw_ostream &O, 415 const std::string &Banner) const override { 416 return createPrintModulePass(O, Banner); 417 } 418 419 /// run - Execute all of the passes scheduled for execution. Keep track of 420 /// whether any of the passes modifies the module, and if so, return true. 421 bool runOnModule(Module &M); 422 423 using llvm::Pass::doInitialization; 424 using llvm::Pass::doFinalization; 425 426 /// Pass Manager itself does not invalidate any analysis info. 427 void getAnalysisUsage(AnalysisUsage &Info) const override { 428 Info.setPreservesAll(); 429 } 430 431 /// Add RequiredPass into list of lower level passes required by pass P. 432 /// RequiredPass is run on the fly by Pass Manager when P requests it 433 /// through getAnalysis interface. 434 void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override; 435 436 /// Return function pass corresponding to PassInfo PI, that is 437 /// required by module pass MP. Instantiate analysis pass, by using 438 /// its runOnFunction() for function F. 439 Pass* getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F) override; 440 441 StringRef getPassName() const override { return "Module Pass Manager"; } 442 443 PMDataManager *getAsPMDataManager() override { return this; } 444 Pass *getAsPass() override { return this; } 445 446 // Print passes managed by this manager 447 void dumpPassStructure(unsigned Offset) override { 448 dbgs().indent(Offset*2) << "ModulePass Manager\n"; 449 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 450 ModulePass *MP = getContainedPass(Index); 451 MP->dumpPassStructure(Offset + 1); 452 MapVector<Pass *, FunctionPassManagerImpl *>::const_iterator I = 453 OnTheFlyManagers.find(MP); 454 if (I != OnTheFlyManagers.end()) 455 I->second->dumpPassStructure(Offset + 2); 456 dumpLastUses(MP, Offset+1); 457 } 458 } 459 460 ModulePass *getContainedPass(unsigned N) { 461 assert(N < PassVector.size() && "Pass number out of range!"); 462 return static_cast<ModulePass *>(PassVector[N]); 463 } 464 465 PassManagerType getPassManagerType() const override { 466 return PMT_ModulePassManager; 467 } 468 469 private: 470 /// Collection of on the fly FPPassManagers. These managers manage 471 /// function passes that are required by module passes. 472 MapVector<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers; 473}; 474 475char MPPassManager::ID = 0; 476} // End anonymous namespace 477 478namespace llvm { 479namespace legacy { 480//===----------------------------------------------------------------------===// 481// PassManagerImpl 482// 483 484/// PassManagerImpl manages MPPassManagers 485class PassManagerImpl : public Pass, 486 public PMDataManager, 487 public PMTopLevelManager { 488 virtual void anchor(); 489 490public: 491 static char ID; 492 explicit PassManagerImpl() : 493 Pass(PT_PassManager, ID), PMDataManager(), 494 PMTopLevelManager(new MPPassManager()) {} 495 496 /// \copydoc PassManager::add() 497 void add(Pass *P) { 498 schedulePass(P); 499 } 500 501 /// createPrinterPass - Get a module printer pass. 502 Pass *createPrinterPass(raw_ostream &O, 503 const std::string &Banner) const override { 504 return createPrintModulePass(O, Banner); 505 } 506 507 /// run - Execute all of the passes scheduled for execution. Keep track of 508 /// whether any of the passes modifies the module, and if so, return true. 509 bool run(Module &M); 510 511 using llvm::Pass::doInitialization; 512 using llvm::Pass::doFinalization; 513 514 /// Pass Manager itself does not invalidate any analysis info. 515 void getAnalysisUsage(AnalysisUsage &Info) const override { 516 Info.setPreservesAll(); 517 } 518 519 PMDataManager *getAsPMDataManager() override { return this; } 520 Pass *getAsPass() override { return this; } 521 PassManagerType getTopLevelPassManagerType() override { 522 return PMT_ModulePassManager; 523 } 524 525 MPPassManager *getContainedManager(unsigned N) { 526 assert(N < PassManagers.size() && "Pass number out of range!"); 527 MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]); 528 return MP; 529 } 530}; 531 532void PassManagerImpl::anchor() {} 533 534char PassManagerImpl::ID = 0; 535} // End of legacy namespace 536} // End of llvm namespace 537 538//===----------------------------------------------------------------------===// 539// PMTopLevelManager implementation 540 541/// Initialize top level manager. Create first pass manager. 542PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) { 543 PMDM->setTopLevelManager(this); 544 addPassManager(PMDM); 545 activeStack.push(PMDM); 546} 547 548/// Set pass P as the last user of the given analysis passes. 549void 550PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) { 551 unsigned PDepth = 0; 552 if (P->getResolver()) 553 PDepth = P->getResolver()->getPMDataManager().getDepth(); 554 555 for (Pass *AP : AnalysisPasses) { 556 LastUser[AP] = P; 557 558 if (P == AP) 559 continue; 560 561 // Update the last users of passes that are required transitive by AP. 562 AnalysisUsage *AnUsage = findAnalysisUsage(AP); 563 const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet(); 564 SmallVector<Pass *, 12> LastUses; 565 SmallVector<Pass *, 12> LastPMUses; 566 for (AnalysisID ID : IDs) { 567 Pass *AnalysisPass = findAnalysisPass(ID); 568 assert(AnalysisPass && "Expected analysis pass to exist."); 569 AnalysisResolver *AR = AnalysisPass->getResolver(); 570 assert(AR && "Expected analysis resolver to exist."); 571 unsigned APDepth = AR->getPMDataManager().getDepth(); 572 573 if (PDepth == APDepth) 574 LastUses.push_back(AnalysisPass); 575 else if (PDepth > APDepth) 576 LastPMUses.push_back(AnalysisPass); 577 } 578 579 setLastUser(LastUses, P); 580 581 // If this pass has a corresponding pass manager, push higher level 582 // analysis to this pass manager. 583 if (P->getResolver()) 584 setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass()); 585 586 587 // If AP is the last user of other passes then make P last user of 588 // such passes. 589 for (auto LU : LastUser) { 590 if (LU.second == AP) 591 // DenseMap iterator is not invalidated here because 592 // this is just updating existing entries. 593 LastUser[LU.first] = P; 594 } 595 } 596} 597 598/// Collect passes whose last user is P 599void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses, 600 Pass *P) { 601 DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI = 602 InversedLastUser.find(P); 603 if (DMI == InversedLastUser.end()) 604 return; 605 606 SmallPtrSet<Pass *, 8> &LU = DMI->second; 607 for (Pass *LUP : LU) { 608 LastUses.push_back(LUP); 609 } 610 611} 612 613AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) { 614 AnalysisUsage *AnUsage = nullptr; 615 auto DMI = AnUsageMap.find(P); 616 if (DMI != AnUsageMap.end()) 617 AnUsage = DMI->second; 618 else { 619 // Look up the analysis usage from the pass instance (different instances 620 // of the same pass can produce different results), but unique the 621 // resulting object to reduce memory usage. This helps to greatly reduce 622 // memory usage when we have many instances of only a few pass types 623 // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set 624 // of dependencies. 625 AnalysisUsage AU; 626 P->getAnalysisUsage(AU); 627 628 AUFoldingSetNode* Node = nullptr; 629 FoldingSetNodeID ID; 630 AUFoldingSetNode::Profile(ID, AU); 631 void *IP = nullptr; 632 if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP)) 633 Node = N; 634 else { 635 Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU); 636 UniqueAnalysisUsages.InsertNode(Node, IP); 637 } 638 assert(Node && "cached analysis usage must be non null"); 639 640 AnUsageMap[P] = &Node->AU; 641 AnUsage = &Node->AU; 642 } 643 return AnUsage; 644} 645 646/// Schedule pass P for execution. Make sure that passes required by 647/// P are run before P is run. Update analysis info maintained by 648/// the manager. Remove dead passes. This is a recursive function. 649void PMTopLevelManager::schedulePass(Pass *P) { 650 651 // TODO : Allocate function manager for this pass, other wise required set 652 // may be inserted into previous function manager 653 654 // Give pass a chance to prepare the stage. 655 P->preparePassManager(activeStack); 656 657 // If P is an analysis pass and it is available then do not 658 // generate the analysis again. Stale analysis info should not be 659 // available at this point. 660 const PassInfo *PI = findAnalysisPassInfo(P->getPassID()); 661 if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) { 662 // Remove any cached AnalysisUsage information. 663 AnUsageMap.erase(P); 664 delete P; 665 return; 666 } 667 668 AnalysisUsage *AnUsage = findAnalysisUsage(P); 669 670 bool checkAnalysis = true; 671 while (checkAnalysis) { 672 checkAnalysis = false; 673 674 const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet(); 675 for (const AnalysisID ID : RequiredSet) { 676 677 Pass *AnalysisPass = findAnalysisPass(ID); 678 if (!AnalysisPass) { 679 const PassInfo *PI = findAnalysisPassInfo(ID); 680 681 if (!PI) { 682 // Pass P is not in the global PassRegistry 683 dbgs() << "Pass '" << P->getPassName() << "' is not initialized." << "\n"; 684 dbgs() << "Verify if there is a pass dependency cycle." << "\n"; 685 dbgs() << "Required Passes:" << "\n"; 686 for (const AnalysisID ID2 : RequiredSet) { 687 if (ID == ID2) 688 break; 689 Pass *AnalysisPass2 = findAnalysisPass(ID2); 690 if (AnalysisPass2) { 691 dbgs() << "\t" << AnalysisPass2->getPassName() << "\n"; 692 } else { 693 dbgs() << "\t" << "Error: Required pass not found! Possible causes:" << "\n"; 694 dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)" << "\n"; 695 dbgs() << "\t\t" << "- Corruption of the global PassRegistry" << "\n"; 696 } 697 } 698 } 699 700 assert(PI && "Expected required passes to be initialized"); 701 AnalysisPass = PI->createPass(); 702 if (P->getPotentialPassManagerType () == 703 AnalysisPass->getPotentialPassManagerType()) 704 // Schedule analysis pass that is managed by the same pass manager. 705 schedulePass(AnalysisPass); 706 else if (P->getPotentialPassManagerType () > 707 AnalysisPass->getPotentialPassManagerType()) { 708 // Schedule analysis pass that is managed by a new manager. 709 schedulePass(AnalysisPass); 710 // Recheck analysis passes to ensure that required analyses that 711 // are already checked are still available. 712 checkAnalysis = true; 713 } else 714 // Do not schedule this analysis. Lower level analysis 715 // passes are run on the fly. 716 delete AnalysisPass; 717 } 718 } 719 } 720 721 // Now all required passes are available. 722 if (ImmutablePass *IP = P->getAsImmutablePass()) { 723 // P is a immutable pass and it will be managed by this 724 // top level manager. Set up analysis resolver to connect them. 725 PMDataManager *DM = getAsPMDataManager(); 726 AnalysisResolver *AR = new AnalysisResolver(*DM); 727 P->setResolver(AR); 728 DM->initializeAnalysisImpl(P); 729 addImmutablePass(IP); 730 DM->recordAvailableAnalysis(IP); 731 return; 732 } 733 734 if (PI && !PI->isAnalysis() && shouldPrintBeforePass(PI->getPassArgument())) { 735 Pass *PP = P->createPrinterPass( 736 dbgs(), ("*** IR Dump Before " + P->getPassName() + " ***").str()); 737 PP->assignPassManager(activeStack, getTopLevelPassManagerType()); 738 } 739 740 // Add the requested pass to the best available pass manager. 741 P->assignPassManager(activeStack, getTopLevelPassManagerType()); 742 743 if (PI && !PI->isAnalysis() && shouldPrintAfterPass(PI->getPassArgument())) { 744 Pass *PP = P->createPrinterPass( 745 dbgs(), ("*** IR Dump After " + P->getPassName() + " ***").str()); 746 PP->assignPassManager(activeStack, getTopLevelPassManagerType()); 747 } 748} 749 750/// Find the pass that implements Analysis AID. Search immutable 751/// passes and all pass managers. If desired pass is not found 752/// then return NULL. 753Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) { 754 // For immutable passes we have a direct mapping from ID to pass, so check 755 // that first. 756 if (Pass *P = ImmutablePassMap.lookup(AID)) 757 return P; 758 759 // Check pass managers 760 for (PMDataManager *PassManager : PassManagers) 761 if (Pass *P = PassManager->findAnalysisPass(AID, false)) 762 return P; 763 764 // Check other pass managers 765 for (PMDataManager *IndirectPassManager : IndirectPassManagers) 766 if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false)) 767 return P; 768 769 return nullptr; 770} 771 772const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const { 773 const PassInfo *&PI = AnalysisPassInfos[AID]; 774 if (!PI) 775 PI = PassRegistry::getPassRegistry()->getPassInfo(AID); 776 else 777 assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) && 778 "The pass info pointer changed for an analysis ID!"); 779 780 return PI; 781} 782 783void PMTopLevelManager::addImmutablePass(ImmutablePass *P) { 784 P->initializePass(); 785 ImmutablePasses.push_back(P); 786 787 // Add this pass to the map from its analysis ID. We clobber any prior runs 788 // of the pass in the map so that the last one added is the one found when 789 // doing lookups. 790 AnalysisID AID = P->getPassID(); 791 ImmutablePassMap[AID] = P; 792 793 // Also add any interfaces implemented by the immutable pass to the map for 794 // fast lookup. 795 const PassInfo *PassInf = findAnalysisPassInfo(AID); 796 assert(PassInf && "Expected all immutable passes to be initialized"); 797 for (const PassInfo *ImmPI : PassInf->getInterfacesImplemented()) 798 ImmutablePassMap[ImmPI->getTypeInfo()] = P; 799} 800 801// Print passes managed by this top level manager. 802void PMTopLevelManager::dumpPasses() const { 803 804 if (PassDebugging < Structure) 805 return; 806 807 // Print out the immutable passes 808 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { 809 ImmutablePasses[i]->dumpPassStructure(0); 810 } 811 812 // Every class that derives from PMDataManager also derives from Pass 813 // (sometimes indirectly), but there's no inheritance relationship 814 // between PMDataManager and Pass, so we have to getAsPass to get 815 // from a PMDataManager* to a Pass*. 816 for (PMDataManager *Manager : PassManagers) 817 Manager->getAsPass()->dumpPassStructure(1); 818} 819 820void PMTopLevelManager::dumpArguments() const { 821 822 if (PassDebugging < Arguments) 823 return; 824 825 dbgs() << "Pass Arguments: "; 826 for (ImmutablePass *P : ImmutablePasses) 827 if (const PassInfo *PI = findAnalysisPassInfo(P->getPassID())) { 828 assert(PI && "Expected all immutable passes to be initialized"); 829 if (!PI->isAnalysisGroup()) 830 dbgs() << " -" << PI->getPassArgument(); 831 } 832 for (PMDataManager *PM : PassManagers) 833 PM->dumpPassArguments(); 834 dbgs() << "\n"; 835} 836 837void PMTopLevelManager::initializeAllAnalysisInfo() { 838 for (PMDataManager *PM : PassManagers) 839 PM->initializeAnalysisInfo(); 840 841 // Initailize other pass managers 842 for (PMDataManager *IPM : IndirectPassManagers) 843 IPM->initializeAnalysisInfo(); 844 845 for (auto LU : LastUser) { 846 SmallPtrSet<Pass *, 8> &L = InversedLastUser[LU.second]; 847 L.insert(LU.first); 848 } 849} 850 851/// Destructor 852PMTopLevelManager::~PMTopLevelManager() { 853 for (PMDataManager *PM : PassManagers) 854 delete PM; 855 856 for (ImmutablePass *P : ImmutablePasses) 857 delete P; 858} 859 860//===----------------------------------------------------------------------===// 861// PMDataManager implementation 862 863/// Augement AvailableAnalysis by adding analysis made available by pass P. 864void PMDataManager::recordAvailableAnalysis(Pass *P) { 865 AnalysisID PI = P->getPassID(); 866 867 AvailableAnalysis[PI] = P; 868 869 assert(!AvailableAnalysis.empty()); 870 871 // This pass is the current implementation of all of the interfaces it 872 // implements as well. 873 const PassInfo *PInf = TPM->findAnalysisPassInfo(PI); 874 if (!PInf) return; 875 const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented(); 876 for (unsigned i = 0, e = II.size(); i != e; ++i) 877 AvailableAnalysis[II[i]->getTypeInfo()] = P; 878} 879 880// Return true if P preserves high level analysis used by other 881// passes managed by this manager 882bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) { 883 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 884 if (AnUsage->getPreservesAll()) 885 return true; 886 887 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 888 for (Pass *P1 : HigherLevelAnalysis) { 889 if (P1->getAsImmutablePass() == nullptr && 890 !is_contained(PreservedSet, P1->getPassID())) 891 return false; 892 } 893 894 return true; 895} 896 897/// verifyPreservedAnalysis -- Verify analysis preserved by pass P. 898void PMDataManager::verifyPreservedAnalysis(Pass *P) { 899 // Don't do this unless assertions are enabled. 900#ifdef NDEBUG 901 return; 902#endif 903 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 904 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 905 906 // Verify preserved analysis 907 for (AnalysisID AID : PreservedSet) { 908 if (Pass *AP = findAnalysisPass(AID, true)) { 909 TimeRegion PassTimer(getPassTimer(AP)); 910 AP->verifyAnalysis(); 911 } 912 } 913} 914 915/// Remove Analysis not preserved by Pass P 916void PMDataManager::removeNotPreservedAnalysis(Pass *P) { 917 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 918 if (AnUsage->getPreservesAll()) 919 return; 920 921 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 922 for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(), 923 E = AvailableAnalysis.end(); I != E; ) { 924 DenseMap<AnalysisID, Pass*>::iterator Info = I++; 925 if (Info->second->getAsImmutablePass() == nullptr && 926 !is_contained(PreservedSet, Info->first)) { 927 // Remove this analysis 928 if (PassDebugging >= Details) { 929 Pass *S = Info->second; 930 dbgs() << " -- '" << P->getPassName() << "' is not preserving '"; 931 dbgs() << S->getPassName() << "'\n"; 932 } 933 AvailableAnalysis.erase(Info); 934 } 935 } 936 937 // Check inherited analysis also. If P is not preserving analysis 938 // provided by parent manager then remove it here. 939 for (unsigned Index = 0; Index < PMT_Last; ++Index) { 940 941 if (!InheritedAnalysis[Index]) 942 continue; 943 944 for (DenseMap<AnalysisID, Pass*>::iterator 945 I = InheritedAnalysis[Index]->begin(), 946 E = InheritedAnalysis[Index]->end(); I != E; ) { 947 DenseMap<AnalysisID, Pass *>::iterator Info = I++; 948 if (Info->second->getAsImmutablePass() == nullptr && 949 !is_contained(PreservedSet, Info->first)) { 950 // Remove this analysis 951 if (PassDebugging >= Details) { 952 Pass *S = Info->second; 953 dbgs() << " -- '" << P->getPassName() << "' is not preserving '"; 954 dbgs() << S->getPassName() << "'\n"; 955 } 956 InheritedAnalysis[Index]->erase(Info); 957 } 958 } 959 } 960} 961 962/// Remove analysis passes that are not used any longer 963void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg, 964 enum PassDebuggingString DBG_STR) { 965 966 SmallVector<Pass *, 12> DeadPasses; 967 968 // If this is a on the fly manager then it does not have TPM. 969 if (!TPM) 970 return; 971 972 TPM->collectLastUses(DeadPasses, P); 973 974 if (PassDebugging >= Details && !DeadPasses.empty()) { 975 dbgs() << " -*- '" << P->getPassName(); 976 dbgs() << "' is the last user of following pass instances."; 977 dbgs() << " Free these instances\n"; 978 } 979 980 for (Pass *P : DeadPasses) 981 freePass(P, Msg, DBG_STR); 982} 983 984void PMDataManager::freePass(Pass *P, StringRef Msg, 985 enum PassDebuggingString DBG_STR) { 986 dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg); 987 988 { 989 // If the pass crashes releasing memory, remember this. 990 PassManagerPrettyStackEntry X(P); 991 TimeRegion PassTimer(getPassTimer(P)); 992 993 P->releaseMemory(); 994 } 995 996 AnalysisID PI = P->getPassID(); 997 if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) { 998 // Remove the pass itself (if it is not already removed). 999 AvailableAnalysis.erase(PI); 1000 1001 // Remove all interfaces this pass implements, for which it is also 1002 // listed as the available implementation. 1003 const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented(); 1004 for (unsigned i = 0, e = II.size(); i != e; ++i) { 1005 DenseMap<AnalysisID, Pass*>::iterator Pos = 1006 AvailableAnalysis.find(II[i]->getTypeInfo()); 1007 if (Pos != AvailableAnalysis.end() && Pos->second == P) 1008 AvailableAnalysis.erase(Pos); 1009 } 1010 } 1011} 1012 1013/// Add pass P into the PassVector. Update 1014/// AvailableAnalysis appropriately if ProcessAnalysis is true. 1015void PMDataManager::add(Pass *P, bool ProcessAnalysis) { 1016 // This manager is going to manage pass P. Set up analysis resolver 1017 // to connect them. 1018 AnalysisResolver *AR = new AnalysisResolver(*this); 1019 P->setResolver(AR); 1020 1021 // If a FunctionPass F is the last user of ModulePass info M 1022 // then the F's manager, not F, records itself as a last user of M. 1023 SmallVector<Pass *, 12> TransferLastUses; 1024 1025 if (!ProcessAnalysis) { 1026 // Add pass 1027 PassVector.push_back(P); 1028 return; 1029 } 1030 1031 // At the moment, this pass is the last user of all required passes. 1032 SmallVector<Pass *, 12> LastUses; 1033 SmallVector<Pass *, 8> UsedPasses; 1034 SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable; 1035 1036 unsigned PDepth = this->getDepth(); 1037 1038 collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P); 1039 for (Pass *PUsed : UsedPasses) { 1040 unsigned RDepth = 0; 1041 1042 assert(PUsed->getResolver() && "Analysis Resolver is not set"); 1043 PMDataManager &DM = PUsed->getResolver()->getPMDataManager(); 1044 RDepth = DM.getDepth(); 1045 1046 if (PDepth == RDepth) 1047 LastUses.push_back(PUsed); 1048 else if (PDepth > RDepth) { 1049 // Let the parent claim responsibility of last use 1050 TransferLastUses.push_back(PUsed); 1051 // Keep track of higher level analysis used by this manager. 1052 HigherLevelAnalysis.push_back(PUsed); 1053 } else 1054 llvm_unreachable("Unable to accommodate Used Pass"); 1055 } 1056 1057 // Set P as P's last user until someone starts using P. 1058 // However, if P is a Pass Manager then it does not need 1059 // to record its last user. 1060 if (!P->getAsPMDataManager()) 1061 LastUses.push_back(P); 1062 TPM->setLastUser(LastUses, P); 1063 1064 if (!TransferLastUses.empty()) { 1065 Pass *My_PM = getAsPass(); 1066 TPM->setLastUser(TransferLastUses, My_PM); 1067 TransferLastUses.clear(); 1068 } 1069 1070 // Now, take care of required analyses that are not available. 1071 for (AnalysisID ID : ReqAnalysisNotAvailable) { 1072 const PassInfo *PI = TPM->findAnalysisPassInfo(ID); 1073 Pass *AnalysisPass = PI->createPass(); 1074 this->addLowerLevelRequiredPass(P, AnalysisPass); 1075 } 1076 1077 // Take a note of analysis required and made available by this pass. 1078 // Remove the analysis not preserved by this pass 1079 removeNotPreservedAnalysis(P); 1080 recordAvailableAnalysis(P); 1081 1082 // Add pass 1083 PassVector.push_back(P); 1084} 1085 1086 1087/// Populate UP with analysis pass that are used or required by 1088/// pass P and are available. Populate RP_NotAvail with analysis 1089/// pass that are required by pass P but are not available. 1090void PMDataManager::collectRequiredAndUsedAnalyses( 1091 SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail, 1092 Pass *P) { 1093 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 1094 1095 for (const auto &UsedID : AnUsage->getUsedSet()) 1096 if (Pass *AnalysisPass = findAnalysisPass(UsedID, true)) 1097 UP.push_back(AnalysisPass); 1098 1099 for (const auto &RequiredID : AnUsage->getRequiredSet()) 1100 if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true)) 1101 UP.push_back(AnalysisPass); 1102 else 1103 RP_NotAvail.push_back(RequiredID); 1104 1105 for (const auto &RequiredID : AnUsage->getRequiredTransitiveSet()) 1106 if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true)) 1107 UP.push_back(AnalysisPass); 1108 else 1109 RP_NotAvail.push_back(RequiredID); 1110} 1111 1112// All Required analyses should be available to the pass as it runs! Here 1113// we fill in the AnalysisImpls member of the pass so that it can 1114// successfully use the getAnalysis() method to retrieve the 1115// implementations it needs. 1116// 1117void PMDataManager::initializeAnalysisImpl(Pass *P) { 1118 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 1119 1120 for (const AnalysisID ID : AnUsage->getRequiredSet()) { 1121 Pass *Impl = findAnalysisPass(ID, true); 1122 if (!Impl) 1123 // This may be analysis pass that is initialized on the fly. 1124 // If that is not the case then it will raise an assert when it is used. 1125 continue; 1126 AnalysisResolver *AR = P->getResolver(); 1127 assert(AR && "Analysis Resolver is not set"); 1128 AR->addAnalysisImplsPair(ID, Impl); 1129 } 1130} 1131 1132/// Find the pass that implements Analysis AID. If desired pass is not found 1133/// then return NULL. 1134Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) { 1135 1136 // Check if AvailableAnalysis map has one entry. 1137 DenseMap<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID); 1138 1139 if (I != AvailableAnalysis.end()) 1140 return I->second; 1141 1142 // Search Parents through TopLevelManager 1143 if (SearchParent) 1144 return TPM->findAnalysisPass(AID); 1145 1146 return nullptr; 1147} 1148 1149// Print list of passes that are last used by P. 1150void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{ 1151 1152 SmallVector<Pass *, 12> LUses; 1153 1154 // If this is a on the fly manager then it does not have TPM. 1155 if (!TPM) 1156 return; 1157 1158 TPM->collectLastUses(LUses, P); 1159 1160 for (Pass *P : LUses) { 1161 dbgs() << "--" << std::string(Offset*2, ' '); 1162 P->dumpPassStructure(0); 1163 } 1164} 1165 1166void PMDataManager::dumpPassArguments() const { 1167 for (Pass *P : PassVector) { 1168 if (PMDataManager *PMD = P->getAsPMDataManager()) 1169 PMD->dumpPassArguments(); 1170 else 1171 if (const PassInfo *PI = 1172 TPM->findAnalysisPassInfo(P->getPassID())) 1173 if (!PI->isAnalysisGroup()) 1174 dbgs() << " -" << PI->getPassArgument(); 1175 } 1176} 1177 1178void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1, 1179 enum PassDebuggingString S2, 1180 StringRef Msg) { 1181 if (PassDebugging < Executions) 1182 return; 1183 dbgs() << "[" << std::chrono::system_clock::now() << "] " << (void *)this 1184 << std::string(getDepth() * 2 + 1, ' '); 1185 switch (S1) { 1186 case EXECUTION_MSG: 1187 dbgs() << "Executing Pass '" << P->getPassName(); 1188 break; 1189 case MODIFICATION_MSG: 1190 dbgs() << "Made Modification '" << P->getPassName(); 1191 break; 1192 case FREEING_MSG: 1193 dbgs() << " Freeing Pass '" << P->getPassName(); 1194 break; 1195 default: 1196 break; 1197 } 1198 switch (S2) { 1199 case ON_FUNCTION_MSG: 1200 dbgs() << "' on Function '" << Msg << "'...\n"; 1201 break; 1202 case ON_MODULE_MSG: 1203 dbgs() << "' on Module '" << Msg << "'...\n"; 1204 break; 1205 case ON_REGION_MSG: 1206 dbgs() << "' on Region '" << Msg << "'...\n"; 1207 break; 1208 case ON_LOOP_MSG: 1209 dbgs() << "' on Loop '" << Msg << "'...\n"; 1210 break; 1211 case ON_CG_MSG: 1212 dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n"; 1213 break; 1214 default: 1215 break; 1216 } 1217} 1218 1219void PMDataManager::dumpRequiredSet(const Pass *P) const { 1220 if (PassDebugging < Details) 1221 return; 1222 1223 AnalysisUsage analysisUsage; 1224 P->getAnalysisUsage(analysisUsage); 1225 dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet()); 1226} 1227 1228void PMDataManager::dumpPreservedSet(const Pass *P) const { 1229 if (PassDebugging < Details) 1230 return; 1231 1232 AnalysisUsage analysisUsage; 1233 P->getAnalysisUsage(analysisUsage); 1234 dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet()); 1235} 1236 1237void PMDataManager::dumpUsedSet(const Pass *P) const { 1238 if (PassDebugging < Details) 1239 return; 1240 1241 AnalysisUsage analysisUsage; 1242 P->getAnalysisUsage(analysisUsage); 1243 dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet()); 1244} 1245 1246void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P, 1247 const AnalysisUsage::VectorType &Set) const { 1248 assert(PassDebugging >= Details); 1249 if (Set.empty()) 1250 return; 1251 dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:"; 1252 for (unsigned i = 0; i != Set.size(); ++i) { 1253 if (i) dbgs() << ','; 1254 const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]); 1255 if (!PInf) { 1256 // Some preserved passes, such as AliasAnalysis, may not be initialized by 1257 // all drivers. 1258 dbgs() << " Uninitialized Pass"; 1259 continue; 1260 } 1261 dbgs() << ' ' << PInf->getPassName(); 1262 } 1263 dbgs() << '\n'; 1264} 1265 1266/// Add RequiredPass into list of lower level passes required by pass P. 1267/// RequiredPass is run on the fly by Pass Manager when P requests it 1268/// through getAnalysis interface. 1269/// This should be handled by specific pass manager. 1270void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 1271 if (TPM) { 1272 TPM->dumpArguments(); 1273 TPM->dumpPasses(); 1274 } 1275 1276 // Module Level pass may required Function Level analysis info 1277 // (e.g. dominator info). Pass manager uses on the fly function pass manager 1278 // to provide this on demand. In that case, in Pass manager terminology, 1279 // module level pass is requiring lower level analysis info managed by 1280 // lower level pass manager. 1281 1282 // When Pass manager is not able to order required analysis info, Pass manager 1283 // checks whether any lower level manager will be able to provide this 1284 // analysis info on demand or not. 1285#ifndef NDEBUG 1286 dbgs() << "Unable to schedule '" << RequiredPass->getPassName(); 1287 dbgs() << "' required by '" << P->getPassName() << "'\n"; 1288#endif 1289 llvm_unreachable("Unable to schedule pass"); 1290} 1291 1292Pass *PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F) { 1293 llvm_unreachable("Unable to find on the fly pass"); 1294} 1295 1296// Destructor 1297PMDataManager::~PMDataManager() { 1298 for (Pass *P : PassVector) 1299 delete P; 1300} 1301 1302//===----------------------------------------------------------------------===// 1303// NOTE: Is this the right place to define this method ? 1304// getAnalysisIfAvailable - Return analysis result or null if it doesn't exist. 1305Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const { 1306 return PM.findAnalysisPass(ID, dir); 1307} 1308 1309Pass *AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI, 1310 Function &F) { 1311 return PM.getOnTheFlyPass(P, AnalysisPI, F); 1312} 1313 1314//===----------------------------------------------------------------------===// 1315// FunctionPassManager implementation 1316 1317/// Create new Function pass manager 1318FunctionPassManager::FunctionPassManager(Module *m) : M(m) { 1319 FPM = new FunctionPassManagerImpl(); 1320 // FPM is the top level manager. 1321 FPM->setTopLevelManager(FPM); 1322 1323 AnalysisResolver *AR = new AnalysisResolver(*FPM); 1324 FPM->setResolver(AR); 1325} 1326 1327FunctionPassManager::~FunctionPassManager() { 1328 delete FPM; 1329} 1330 1331void FunctionPassManager::add(Pass *P) { 1332 FPM->add(P); 1333} 1334 1335/// run - Execute all of the passes scheduled for execution. Keep 1336/// track of whether any of the passes modifies the function, and if 1337/// so, return true. 1338/// 1339bool FunctionPassManager::run(Function &F) { 1340 handleAllErrors(F.materialize(), [&](ErrorInfoBase &EIB) { 1341 report_fatal_error("Error reading bitcode file: " + EIB.message()); 1342 }); 1343 return FPM->run(F); 1344} 1345 1346 1347/// doInitialization - Run all of the initializers for the function passes. 1348/// 1349bool FunctionPassManager::doInitialization() { 1350 return FPM->doInitialization(*M); 1351} 1352 1353/// doFinalization - Run all of the finalizers for the function passes. 1354/// 1355bool FunctionPassManager::doFinalization() { 1356 return FPM->doFinalization(*M); 1357} 1358 1359//===----------------------------------------------------------------------===// 1360// FunctionPassManagerImpl implementation 1361// 1362bool FunctionPassManagerImpl::doInitialization(Module &M) { 1363 bool Changed = false; 1364 1365 dumpArguments(); 1366 dumpPasses(); 1367 1368 for (ImmutablePass *ImPass : getImmutablePasses()) 1369 Changed |= ImPass->doInitialization(M); 1370 1371 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 1372 Changed |= getContainedManager(Index)->doInitialization(M); 1373 1374 return Changed; 1375} 1376 1377bool FunctionPassManagerImpl::doFinalization(Module &M) { 1378 bool Changed = false; 1379 1380 for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index) 1381 Changed |= getContainedManager(Index)->doFinalization(M); 1382 1383 for (ImmutablePass *ImPass : getImmutablePasses()) 1384 Changed |= ImPass->doFinalization(M); 1385 1386 return Changed; 1387} 1388 1389/// cleanup - After running all passes, clean up pass manager cache. 1390void FPPassManager::cleanup() { 1391 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1392 FunctionPass *FP = getContainedPass(Index); 1393 AnalysisResolver *AR = FP->getResolver(); 1394 assert(AR && "Analysis Resolver is not set"); 1395 AR->clearAnalysisImpls(); 1396 } 1397} 1398 1399void FunctionPassManagerImpl::releaseMemoryOnTheFly() { 1400 if (!wasRun) 1401 return; 1402 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 1403 FPPassManager *FPPM = getContainedManager(Index); 1404 for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) { 1405 FPPM->getContainedPass(Index)->releaseMemory(); 1406 } 1407 } 1408 wasRun = false; 1409} 1410 1411// Execute all the passes managed by this top level manager. 1412// Return true if any function is modified by a pass. 1413bool FunctionPassManagerImpl::run(Function &F) { 1414 bool Changed = false; 1415 1416 initializeAllAnalysisInfo(); 1417 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 1418 Changed |= getContainedManager(Index)->runOnFunction(F); 1419 F.getContext().yield(); 1420 } 1421 1422 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 1423 getContainedManager(Index)->cleanup(); 1424 1425 wasRun = true; 1426 return Changed; 1427} 1428 1429//===----------------------------------------------------------------------===// 1430// FPPassManager implementation 1431 1432char FPPassManager::ID = 0; 1433/// Print passes managed by this manager 1434void FPPassManager::dumpPassStructure(unsigned Offset) { 1435 dbgs().indent(Offset*2) << "FunctionPass Manager\n"; 1436 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1437 FunctionPass *FP = getContainedPass(Index); 1438 FP->dumpPassStructure(Offset + 1); 1439 dumpLastUses(FP, Offset+1); 1440 } 1441} 1442 1443 1444/// Execute all of the passes scheduled for execution by invoking 1445/// runOnFunction method. Keep track of whether any of the passes modifies 1446/// the function, and if so, return true. 1447bool FPPassManager::runOnFunction(Function &F) { 1448 if (F.isDeclaration()) 1449 return false; 1450 1451 bool Changed = false; 1452 Module &M = *F.getParent(); 1453 // Collect inherited analysis from Module level pass manager. 1454 populateInheritedAnalysis(TPM->activeStack); 1455 1456 unsigned InstrCount, FunctionSize = 0; 1457 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount; 1458 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark(); 1459 // Collect the initial size of the module. 1460 if (EmitICRemark) { 1461 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount); 1462 FunctionSize = F.getInstructionCount(); 1463 } 1464 1465 llvm::TimeTraceScope FunctionScope("OptFunction", F.getName()); 1466 1467 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1468 FunctionPass *FP = getContainedPass(Index); 1469 bool LocalChanged = false; 1470 1471 llvm::TimeTraceScope PassScope("RunPass", FP->getPassName()); 1472 1473 dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName()); 1474 dumpRequiredSet(FP); 1475 1476 initializeAnalysisImpl(FP); 1477 1478 { 1479 PassManagerPrettyStackEntry X(FP, F); 1480 TimeRegion PassTimer(getPassTimer(FP)); 1481 LocalChanged |= FP->runOnFunction(F); 1482 if (EmitICRemark) { 1483 unsigned NewSize = F.getInstructionCount(); 1484 1485 // Update the size of the function, emit a remark, and update the size 1486 // of the module. 1487 if (NewSize != FunctionSize) { 1488 int64_t Delta = static_cast<int64_t>(NewSize) - 1489 static_cast<int64_t>(FunctionSize); 1490 emitInstrCountChangedRemark(FP, M, Delta, InstrCount, 1491 FunctionToInstrCount, &F); 1492 InstrCount = static_cast<int64_t>(InstrCount) + Delta; 1493 FunctionSize = NewSize; 1494 } 1495 } 1496 } 1497 1498 Changed |= LocalChanged; 1499 if (LocalChanged) 1500 dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName()); 1501 dumpPreservedSet(FP); 1502 dumpUsedSet(FP); 1503 1504 verifyPreservedAnalysis(FP); 1505 removeNotPreservedAnalysis(FP); 1506 recordAvailableAnalysis(FP); 1507 removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG); 1508 } 1509 1510 return Changed; 1511} 1512 1513bool FPPassManager::runOnModule(Module &M) { 1514 bool Changed = false; 1515 1516 for (Function &F : M) 1517 Changed |= runOnFunction(F); 1518 1519 return Changed; 1520} 1521 1522bool FPPassManager::doInitialization(Module &M) { 1523 bool Changed = false; 1524 1525 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 1526 Changed |= getContainedPass(Index)->doInitialization(M); 1527 1528 return Changed; 1529} 1530 1531bool FPPassManager::doFinalization(Module &M) { 1532 bool Changed = false; 1533 1534 for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index) 1535 Changed |= getContainedPass(Index)->doFinalization(M); 1536 1537 return Changed; 1538} 1539 1540//===----------------------------------------------------------------------===// 1541// MPPassManager implementation 1542 1543/// Execute all of the passes scheduled for execution by invoking 1544/// runOnModule method. Keep track of whether any of the passes modifies 1545/// the module, and if so, return true. 1546bool 1547MPPassManager::runOnModule(Module &M) { 1548 llvm::TimeTraceScope TimeScope("OptModule", M.getName()); 1549 1550 bool Changed = false; 1551 1552 // Initialize on-the-fly passes 1553 for (auto &OnTheFlyManager : OnTheFlyManagers) { 1554 FunctionPassManagerImpl *FPP = OnTheFlyManager.second; 1555 Changed |= FPP->doInitialization(M); 1556 } 1557 1558 // Initialize module passes 1559 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 1560 Changed |= getContainedPass(Index)->doInitialization(M); 1561 1562 unsigned InstrCount; 1563 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount; 1564 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark(); 1565 // Collect the initial size of the module. 1566 if (EmitICRemark) 1567 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount); 1568 1569 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 1570 ModulePass *MP = getContainedPass(Index); 1571 bool LocalChanged = false; 1572 1573 dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier()); 1574 dumpRequiredSet(MP); 1575 1576 initializeAnalysisImpl(MP); 1577 1578 { 1579 PassManagerPrettyStackEntry X(MP, M); 1580 TimeRegion PassTimer(getPassTimer(MP)); 1581 1582 LocalChanged |= MP->runOnModule(M); 1583 if (EmitICRemark) { 1584 // Update the size of the module. 1585 unsigned ModuleCount = M.getInstructionCount(); 1586 if (ModuleCount != InstrCount) { 1587 int64_t Delta = static_cast<int64_t>(ModuleCount) - 1588 static_cast<int64_t>(InstrCount); 1589 emitInstrCountChangedRemark(MP, M, Delta, InstrCount, 1590 FunctionToInstrCount); 1591 InstrCount = ModuleCount; 1592 } 1593 } 1594 } 1595 1596 Changed |= LocalChanged; 1597 if (LocalChanged) 1598 dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG, 1599 M.getModuleIdentifier()); 1600 dumpPreservedSet(MP); 1601 dumpUsedSet(MP); 1602 1603 verifyPreservedAnalysis(MP); 1604 removeNotPreservedAnalysis(MP); 1605 recordAvailableAnalysis(MP); 1606 removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG); 1607 } 1608 1609 // Finalize module passes 1610 for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index) 1611 Changed |= getContainedPass(Index)->doFinalization(M); 1612 1613 // Finalize on-the-fly passes 1614 for (auto &OnTheFlyManager : OnTheFlyManagers) { 1615 FunctionPassManagerImpl *FPP = OnTheFlyManager.second; 1616 // We don't know when is the last time an on-the-fly pass is run, 1617 // so we need to releaseMemory / finalize here 1618 FPP->releaseMemoryOnTheFly(); 1619 Changed |= FPP->doFinalization(M); 1620 } 1621 1622 return Changed; 1623} 1624 1625/// Add RequiredPass into list of lower level passes required by pass P. 1626/// RequiredPass is run on the fly by Pass Manager when P requests it 1627/// through getAnalysis interface. 1628void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 1629 assert(RequiredPass && "No required pass?"); 1630 assert(P->getPotentialPassManagerType() == PMT_ModulePassManager && 1631 "Unable to handle Pass that requires lower level Analysis pass"); 1632 assert((P->getPotentialPassManagerType() < 1633 RequiredPass->getPotentialPassManagerType()) && 1634 "Unable to handle Pass that requires lower level Analysis pass"); 1635 1636 FunctionPassManagerImpl *FPP = OnTheFlyManagers[P]; 1637 if (!FPP) { 1638 FPP = new FunctionPassManagerImpl(); 1639 // FPP is the top level manager. 1640 FPP->setTopLevelManager(FPP); 1641 1642 OnTheFlyManagers[P] = FPP; 1643 } 1644 const PassInfo *RequiredPassPI = 1645 TPM->findAnalysisPassInfo(RequiredPass->getPassID()); 1646 1647 Pass *FoundPass = nullptr; 1648 if (RequiredPassPI && RequiredPassPI->isAnalysis()) { 1649 FoundPass = 1650 ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID()); 1651 } 1652 if (!FoundPass) { 1653 FoundPass = RequiredPass; 1654 // This should be guaranteed to add RequiredPass to the passmanager given 1655 // that we checked for an available analysis above. 1656 FPP->add(RequiredPass); 1657 } 1658 // Register P as the last user of FoundPass or RequiredPass. 1659 SmallVector<Pass *, 1> LU; 1660 LU.push_back(FoundPass); 1661 FPP->setLastUser(LU, P); 1662} 1663 1664/// Return function pass corresponding to PassInfo PI, that is 1665/// required by module pass MP. Instantiate analysis pass, by using 1666/// its runOnFunction() for function F. 1667Pass* MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F){ 1668 FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP]; 1669 assert(FPP && "Unable to find on the fly pass"); 1670 1671 FPP->releaseMemoryOnTheFly(); 1672 FPP->run(F); 1673 return ((PMTopLevelManager*)FPP)->findAnalysisPass(PI); 1674} 1675 1676 1677//===----------------------------------------------------------------------===// 1678// PassManagerImpl implementation 1679 1680// 1681/// run - Execute all of the passes scheduled for execution. Keep track of 1682/// whether any of the passes modifies the module, and if so, return true. 1683bool PassManagerImpl::run(Module &M) { 1684 bool Changed = false; 1685 1686 dumpArguments(); 1687 dumpPasses(); 1688 1689 for (ImmutablePass *ImPass : getImmutablePasses()) 1690 Changed |= ImPass->doInitialization(M); 1691 1692 initializeAllAnalysisInfo(); 1693 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 1694 Changed |= getContainedManager(Index)->runOnModule(M); 1695 M.getContext().yield(); 1696 } 1697 1698 for (ImmutablePass *ImPass : getImmutablePasses()) 1699 Changed |= ImPass->doFinalization(M); 1700 1701 return Changed; 1702} 1703 1704//===----------------------------------------------------------------------===// 1705// PassManager implementation 1706 1707/// Create new pass manager 1708PassManager::PassManager() { 1709 PM = new PassManagerImpl(); 1710 // PM is the top level manager 1711 PM->setTopLevelManager(PM); 1712} 1713 1714PassManager::~PassManager() { 1715 delete PM; 1716} 1717 1718void PassManager::add(Pass *P) { 1719 PM->add(P); 1720} 1721 1722/// run - Execute all of the passes scheduled for execution. Keep track of 1723/// whether any of the passes modifies the module, and if so, return true. 1724bool PassManager::run(Module &M) { 1725 return PM->run(M); 1726} 1727 1728//===----------------------------------------------------------------------===// 1729// PMStack implementation 1730// 1731 1732// Pop Pass Manager from the stack and clear its analysis info. 1733void PMStack::pop() { 1734 1735 PMDataManager *Top = this->top(); 1736 Top->initializeAnalysisInfo(); 1737 1738 S.pop_back(); 1739} 1740 1741// Push PM on the stack and set its top level manager. 1742void PMStack::push(PMDataManager *PM) { 1743 assert(PM && "Unable to push. Pass Manager expected"); 1744 assert(PM->getDepth()==0 && "Pass Manager depth set too early"); 1745 1746 if (!this->empty()) { 1747 assert(PM->getPassManagerType() > this->top()->getPassManagerType() 1748 && "pushing bad pass manager to PMStack"); 1749 PMTopLevelManager *TPM = this->top()->getTopLevelManager(); 1750 1751 assert(TPM && "Unable to find top level manager"); 1752 TPM->addIndirectPassManager(PM); 1753 PM->setTopLevelManager(TPM); 1754 PM->setDepth(this->top()->getDepth()+1); 1755 } else { 1756 assert((PM->getPassManagerType() == PMT_ModulePassManager 1757 || PM->getPassManagerType() == PMT_FunctionPassManager) 1758 && "pushing bad pass manager to PMStack"); 1759 PM->setDepth(1); 1760 } 1761 1762 S.push_back(PM); 1763} 1764 1765// Dump content of the pass manager stack. 1766LLVM_DUMP_METHOD void PMStack::dump() const { 1767 for (PMDataManager *Manager : S) 1768 dbgs() << Manager->getAsPass()->getPassName() << ' '; 1769 1770 if (!S.empty()) 1771 dbgs() << '\n'; 1772} 1773 1774/// Find appropriate Module Pass Manager in the PM Stack and 1775/// add self into that manager. 1776void ModulePass::assignPassManager(PMStack &PMS, 1777 PassManagerType PreferredType) { 1778 // Find Module Pass Manager 1779 PassManagerType T; 1780 while ((T = PMS.top()->getPassManagerType()) > PMT_ModulePassManager && 1781 T != PreferredType) 1782 PMS.pop(); 1783 PMS.top()->add(this); 1784} 1785 1786/// Find appropriate Function Pass Manager or Call Graph Pass Manager 1787/// in the PM Stack and add self into that manager. 1788void FunctionPass::assignPassManager(PMStack &PMS, 1789 PassManagerType /*PreferredType*/) { 1790 // Find Function Pass Manager 1791 PMDataManager *PM; 1792 while (PM = PMS.top(), PM->getPassManagerType() > PMT_FunctionPassManager) 1793 PMS.pop(); 1794 1795 // Create new Function Pass Manager if needed. 1796 if (PM->getPassManagerType() != PMT_FunctionPassManager) { 1797 // [1] Create new Function Pass Manager 1798 auto *FPP = new FPPassManager; 1799 FPP->populateInheritedAnalysis(PMS); 1800 1801 // [2] Set up new manager's top level manager 1802 PM->getTopLevelManager()->addIndirectPassManager(FPP); 1803 1804 // [3] Assign manager to manage this new manager. This may create 1805 // and push new managers into PMS 1806 FPP->assignPassManager(PMS, PM->getPassManagerType()); 1807 1808 // [4] Push new manager into PMS 1809 PMS.push(FPP); 1810 PM = FPP; 1811 } 1812 1813 // Assign FPP as the manager of this pass. 1814 PM->add(this); 1815} 1816 1817PassManagerBase::~PassManagerBase() {} 1818