xref: /freebsd/contrib/llvm-project/llvm/lib/IR/LegacyPassManager.cpp (revision 6966ac055c3b7a39266fb982493330df7a097997)
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>
35 using namespace llvm;
36 using 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 
47 namespace {
48 // Different debug levels that can be enabled...
49 enum PassDebugLevel {
50   Disabled, Arguments, Structure, Executions, Details
51 };
52 }
53 
54 static cl::opt<enum PassDebugLevel>
55 PassDebugging("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 
64 namespace {
65 typedef llvm::cl::list<const llvm::PassInfo *, bool, PassNameParser>
66 PassOptionList;
67 }
68 
69 // Print IR out before/after specified passes.
70 static PassOptionList
71 PrintBefore("print-before",
72             llvm::cl::desc("Print IR before specified passes"),
73             cl::Hidden);
74 
75 static PassOptionList
76 PrintAfter("print-after",
77            llvm::cl::desc("Print IR after specified passes"),
78            cl::Hidden);
79 
80 static cl::opt<bool> PrintBeforeAll("print-before-all",
81                                     llvm::cl::desc("Print IR before each pass"),
82                                     cl::init(false), cl::Hidden);
83 static cl::opt<bool> PrintAfterAll("print-after-all",
84                                    llvm::cl::desc("Print IR after each pass"),
85                                    cl::init(false), cl::Hidden);
86 
87 static 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 
93 static 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 
103 bool llvm::shouldPrintBeforePass() {
104   return PrintBeforeAll || !PrintBefore.empty();
105 }
106 
107 bool llvm::shouldPrintAfterPass() {
108   return PrintAfterAll || !PrintAfter.empty();
109 }
110 
111 static 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 
122 bool llvm::shouldPrintBeforePass(StringRef PassID) {
123   return PrintBeforeAll || ShouldPrintBeforeOrAfterPass(PassID, PrintBefore);
124 }
125 
126 bool llvm::shouldPrintAfterPass(StringRef PassID) {
127   return PrintAfterAll || ShouldPrintBeforeOrAfterPass(PassID, PrintAfter);
128 }
129 
130 bool llvm::forcePrintModuleIR() { return PrintModuleScope; }
131 
132 bool 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.
139 bool PMDataManager::isPassDebuggingExecutionsOrMore() const {
140   return PassDebugging >= Executions;
141 }
142 
143 unsigned 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 
165 void 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 
287 void 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 
317 
318 namespace {
319 //===----------------------------------------------------------------------===//
320 // BBPassManager
321 //
322 /// BBPassManager manages BasicBlockPass. It batches all the
323 /// pass together and sequence them to process one basic block before
324 /// processing next basic block.
325 class BBPassManager : public PMDataManager, public FunctionPass {
326 
327 public:
328   static char ID;
329   explicit BBPassManager()
330     : PMDataManager(), FunctionPass(ID) {}
331 
332   /// Execute all of the passes scheduled for execution.  Keep track of
333   /// whether any of the passes modifies the function, and if so, return true.
334   bool runOnFunction(Function &F) override;
335 
336   /// Pass Manager itself does not invalidate any analysis info.
337   void getAnalysisUsage(AnalysisUsage &Info) const override {
338     Info.setPreservesAll();
339   }
340 
341   bool doInitialization(Module &M) override;
342   bool doInitialization(Function &F);
343   bool doFinalization(Module &M) override;
344   bool doFinalization(Function &F);
345 
346   PMDataManager *getAsPMDataManager() override { return this; }
347   Pass *getAsPass() override { return this; }
348 
349   StringRef getPassName() const override { return "BasicBlock Pass Manager"; }
350 
351   // Print passes managed by this manager
352   void dumpPassStructure(unsigned Offset) override {
353     dbgs().indent(Offset*2) << "BasicBlockPass Manager\n";
354     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
355       BasicBlockPass *BP = getContainedPass(Index);
356       BP->dumpPassStructure(Offset + 1);
357       dumpLastUses(BP, Offset+1);
358     }
359   }
360 
361   BasicBlockPass *getContainedPass(unsigned N) {
362     assert(N < PassVector.size() && "Pass number out of range!");
363     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
364     return BP;
365   }
366 
367   PassManagerType getPassManagerType() const override {
368     return PMT_BasicBlockPassManager;
369   }
370 };
371 
372 char BBPassManager::ID = 0;
373 } // End anonymous namespace
374 
375 namespace llvm {
376 namespace legacy {
377 //===----------------------------------------------------------------------===//
378 // FunctionPassManagerImpl
379 //
380 /// FunctionPassManagerImpl manages FPPassManagers
381 class FunctionPassManagerImpl : public Pass,
382                                 public PMDataManager,
383                                 public PMTopLevelManager {
384   virtual void anchor();
385 private:
386   bool wasRun;
387 public:
388   static char ID;
389   explicit FunctionPassManagerImpl() :
390     Pass(PT_PassManager, ID), PMDataManager(),
391     PMTopLevelManager(new FPPassManager()), wasRun(false) {}
392 
393   /// \copydoc FunctionPassManager::add()
394   void add(Pass *P) {
395     schedulePass(P);
396   }
397 
398   /// createPrinterPass - Get a function printer pass.
399   Pass *createPrinterPass(raw_ostream &O,
400                           const std::string &Banner) const override {
401     return createPrintFunctionPass(O, Banner);
402   }
403 
404   // Prepare for running an on the fly pass, freeing memory if needed
405   // from a previous run.
406   void releaseMemoryOnTheFly();
407 
408   /// run - Execute all of the passes scheduled for execution.  Keep track of
409   /// whether any of the passes modifies the module, and if so, return true.
410   bool run(Function &F);
411 
412   /// doInitialization - Run all of the initializers for the function passes.
413   ///
414   bool doInitialization(Module &M) override;
415 
416   /// doFinalization - Run all of the finalizers for the function passes.
417   ///
418   bool doFinalization(Module &M) override;
419 
420 
421   PMDataManager *getAsPMDataManager() override { return this; }
422   Pass *getAsPass() override { return this; }
423   PassManagerType getTopLevelPassManagerType() override {
424     return PMT_FunctionPassManager;
425   }
426 
427   /// Pass Manager itself does not invalidate any analysis info.
428   void getAnalysisUsage(AnalysisUsage &Info) const override {
429     Info.setPreservesAll();
430   }
431 
432   FPPassManager *getContainedManager(unsigned N) {
433     assert(N < PassManagers.size() && "Pass number out of range!");
434     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
435     return FP;
436   }
437 };
438 
439 void FunctionPassManagerImpl::anchor() {}
440 
441 char FunctionPassManagerImpl::ID = 0;
442 } // End of legacy namespace
443 } // End of llvm namespace
444 
445 namespace {
446 //===----------------------------------------------------------------------===//
447 // MPPassManager
448 //
449 /// MPPassManager manages ModulePasses and function pass managers.
450 /// It batches all Module passes and function pass managers together and
451 /// sequences them to process one module.
452 class MPPassManager : public Pass, public PMDataManager {
453 public:
454   static char ID;
455   explicit MPPassManager() :
456     Pass(PT_PassManager, ID), PMDataManager() { }
457 
458   // Delete on the fly managers.
459   ~MPPassManager() override {
460     for (auto &OnTheFlyManager : OnTheFlyManagers) {
461       FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
462       delete FPP;
463     }
464   }
465 
466   /// createPrinterPass - Get a module printer pass.
467   Pass *createPrinterPass(raw_ostream &O,
468                           const std::string &Banner) const override {
469     return createPrintModulePass(O, Banner);
470   }
471 
472   /// run - Execute all of the passes scheduled for execution.  Keep track of
473   /// whether any of the passes modifies the module, and if so, return true.
474   bool runOnModule(Module &M);
475 
476   using llvm::Pass::doInitialization;
477   using llvm::Pass::doFinalization;
478 
479   /// Pass Manager itself does not invalidate any analysis info.
480   void getAnalysisUsage(AnalysisUsage &Info) const override {
481     Info.setPreservesAll();
482   }
483 
484   /// Add RequiredPass into list of lower level passes required by pass P.
485   /// RequiredPass is run on the fly by Pass Manager when P requests it
486   /// through getAnalysis interface.
487   void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override;
488 
489   /// Return function pass corresponding to PassInfo PI, that is
490   /// required by module pass MP. Instantiate analysis pass, by using
491   /// its runOnFunction() for function F.
492   Pass* getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F) override;
493 
494   StringRef getPassName() const override { return "Module Pass Manager"; }
495 
496   PMDataManager *getAsPMDataManager() override { return this; }
497   Pass *getAsPass() override { return this; }
498 
499   // Print passes managed by this manager
500   void dumpPassStructure(unsigned Offset) override {
501     dbgs().indent(Offset*2) << "ModulePass Manager\n";
502     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
503       ModulePass *MP = getContainedPass(Index);
504       MP->dumpPassStructure(Offset + 1);
505       MapVector<Pass *, FunctionPassManagerImpl *>::const_iterator I =
506           OnTheFlyManagers.find(MP);
507       if (I != OnTheFlyManagers.end())
508         I->second->dumpPassStructure(Offset + 2);
509       dumpLastUses(MP, Offset+1);
510     }
511   }
512 
513   ModulePass *getContainedPass(unsigned N) {
514     assert(N < PassVector.size() && "Pass number out of range!");
515     return static_cast<ModulePass *>(PassVector[N]);
516   }
517 
518   PassManagerType getPassManagerType() const override {
519     return PMT_ModulePassManager;
520   }
521 
522  private:
523   /// Collection of on the fly FPPassManagers. These managers manage
524   /// function passes that are required by module passes.
525    MapVector<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
526 };
527 
528 char MPPassManager::ID = 0;
529 } // End anonymous namespace
530 
531 namespace llvm {
532 namespace legacy {
533 //===----------------------------------------------------------------------===//
534 // PassManagerImpl
535 //
536 
537 /// PassManagerImpl manages MPPassManagers
538 class PassManagerImpl : public Pass,
539                         public PMDataManager,
540                         public PMTopLevelManager {
541   virtual void anchor();
542 
543 public:
544   static char ID;
545   explicit PassManagerImpl() :
546     Pass(PT_PassManager, ID), PMDataManager(),
547                               PMTopLevelManager(new MPPassManager()) {}
548 
549   /// \copydoc PassManager::add()
550   void add(Pass *P) {
551     schedulePass(P);
552   }
553 
554   /// createPrinterPass - Get a module printer pass.
555   Pass *createPrinterPass(raw_ostream &O,
556                           const std::string &Banner) const override {
557     return createPrintModulePass(O, Banner);
558   }
559 
560   /// run - Execute all of the passes scheduled for execution.  Keep track of
561   /// whether any of the passes modifies the module, and if so, return true.
562   bool run(Module &M);
563 
564   using llvm::Pass::doInitialization;
565   using llvm::Pass::doFinalization;
566 
567   /// Pass Manager itself does not invalidate any analysis info.
568   void getAnalysisUsage(AnalysisUsage &Info) const override {
569     Info.setPreservesAll();
570   }
571 
572   PMDataManager *getAsPMDataManager() override { return this; }
573   Pass *getAsPass() override { return this; }
574   PassManagerType getTopLevelPassManagerType() override {
575     return PMT_ModulePassManager;
576   }
577 
578   MPPassManager *getContainedManager(unsigned N) {
579     assert(N < PassManagers.size() && "Pass number out of range!");
580     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
581     return MP;
582   }
583 };
584 
585 void PassManagerImpl::anchor() {}
586 
587 char PassManagerImpl::ID = 0;
588 } // End of legacy namespace
589 } // End of llvm namespace
590 
591 //===----------------------------------------------------------------------===//
592 // PMTopLevelManager implementation
593 
594 /// Initialize top level manager. Create first pass manager.
595 PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
596   PMDM->setTopLevelManager(this);
597   addPassManager(PMDM);
598   activeStack.push(PMDM);
599 }
600 
601 /// Set pass P as the last user of the given analysis passes.
602 void
603 PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
604   unsigned PDepth = 0;
605   if (P->getResolver())
606     PDepth = P->getResolver()->getPMDataManager().getDepth();
607 
608   for (Pass *AP : AnalysisPasses) {
609     LastUser[AP] = P;
610 
611     if (P == AP)
612       continue;
613 
614     // Update the last users of passes that are required transitive by AP.
615     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
616     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
617     SmallVector<Pass *, 12> LastUses;
618     SmallVector<Pass *, 12> LastPMUses;
619     for (AnalysisID ID : IDs) {
620       Pass *AnalysisPass = findAnalysisPass(ID);
621       assert(AnalysisPass && "Expected analysis pass to exist.");
622       AnalysisResolver *AR = AnalysisPass->getResolver();
623       assert(AR && "Expected analysis resolver to exist.");
624       unsigned APDepth = AR->getPMDataManager().getDepth();
625 
626       if (PDepth == APDepth)
627         LastUses.push_back(AnalysisPass);
628       else if (PDepth > APDepth)
629         LastPMUses.push_back(AnalysisPass);
630     }
631 
632     setLastUser(LastUses, P);
633 
634     // If this pass has a corresponding pass manager, push higher level
635     // analysis to this pass manager.
636     if (P->getResolver())
637       setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
638 
639 
640     // If AP is the last user of other passes then make P last user of
641     // such passes.
642     for (auto LU : LastUser) {
643       if (LU.second == AP)
644         // DenseMap iterator is not invalidated here because
645         // this is just updating existing entries.
646         LastUser[LU.first] = P;
647     }
648   }
649 }
650 
651 /// Collect passes whose last user is P
652 void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
653                                         Pass *P) {
654   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
655     InversedLastUser.find(P);
656   if (DMI == InversedLastUser.end())
657     return;
658 
659   SmallPtrSet<Pass *, 8> &LU = DMI->second;
660   for (Pass *LUP : LU) {
661     LastUses.push_back(LUP);
662   }
663 
664 }
665 
666 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
667   AnalysisUsage *AnUsage = nullptr;
668   auto DMI = AnUsageMap.find(P);
669   if (DMI != AnUsageMap.end())
670     AnUsage = DMI->second;
671   else {
672     // Look up the analysis usage from the pass instance (different instances
673     // of the same pass can produce different results), but unique the
674     // resulting object to reduce memory usage.  This helps to greatly reduce
675     // memory usage when we have many instances of only a few pass types
676     // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set
677     // of dependencies.
678     AnalysisUsage AU;
679     P->getAnalysisUsage(AU);
680 
681     AUFoldingSetNode* Node = nullptr;
682     FoldingSetNodeID ID;
683     AUFoldingSetNode::Profile(ID, AU);
684     void *IP = nullptr;
685     if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP))
686       Node = N;
687     else {
688       Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU);
689       UniqueAnalysisUsages.InsertNode(Node, IP);
690     }
691     assert(Node && "cached analysis usage must be non null");
692 
693     AnUsageMap[P] = &Node->AU;
694     AnUsage = &Node->AU;
695   }
696   return AnUsage;
697 }
698 
699 /// Schedule pass P for execution. Make sure that passes required by
700 /// P are run before P is run. Update analysis info maintained by
701 /// the manager. Remove dead passes. This is a recursive function.
702 void PMTopLevelManager::schedulePass(Pass *P) {
703 
704   // TODO : Allocate function manager for this pass, other wise required set
705   // may be inserted into previous function manager
706 
707   // Give pass a chance to prepare the stage.
708   P->preparePassManager(activeStack);
709 
710   // If P is an analysis pass and it is available then do not
711   // generate the analysis again. Stale analysis info should not be
712   // available at this point.
713   const PassInfo *PI = findAnalysisPassInfo(P->getPassID());
714   if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) {
715     // Remove any cached AnalysisUsage information.
716     AnUsageMap.erase(P);
717     delete P;
718     return;
719   }
720 
721   AnalysisUsage *AnUsage = findAnalysisUsage(P);
722 
723   bool checkAnalysis = true;
724   while (checkAnalysis) {
725     checkAnalysis = false;
726 
727     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
728     for (const AnalysisID ID : RequiredSet) {
729 
730       Pass *AnalysisPass = findAnalysisPass(ID);
731       if (!AnalysisPass) {
732         const PassInfo *PI = findAnalysisPassInfo(ID);
733 
734         if (!PI) {
735           // Pass P is not in the global PassRegistry
736           dbgs() << "Pass '"  << P->getPassName() << "' is not initialized." << "\n";
737           dbgs() << "Verify if there is a pass dependency cycle." << "\n";
738           dbgs() << "Required Passes:" << "\n";
739           for (const AnalysisID ID2 : RequiredSet) {
740             if (ID == ID2)
741               break;
742             Pass *AnalysisPass2 = findAnalysisPass(ID2);
743             if (AnalysisPass2) {
744               dbgs() << "\t" << AnalysisPass2->getPassName() << "\n";
745             } else {
746               dbgs() << "\t"   << "Error: Required pass not found! Possible causes:"  << "\n";
747               dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)"    << "\n";
748               dbgs() << "\t\t" << "- Corruption of the global PassRegistry"           << "\n";
749             }
750           }
751         }
752 
753         assert(PI && "Expected required passes to be initialized");
754         AnalysisPass = PI->createPass();
755         if (P->getPotentialPassManagerType () ==
756             AnalysisPass->getPotentialPassManagerType())
757           // Schedule analysis pass that is managed by the same pass manager.
758           schedulePass(AnalysisPass);
759         else if (P->getPotentialPassManagerType () >
760                  AnalysisPass->getPotentialPassManagerType()) {
761           // Schedule analysis pass that is managed by a new manager.
762           schedulePass(AnalysisPass);
763           // Recheck analysis passes to ensure that required analyses that
764           // are already checked are still available.
765           checkAnalysis = true;
766         } else
767           // Do not schedule this analysis. Lower level analysis
768           // passes are run on the fly.
769           delete AnalysisPass;
770       }
771     }
772   }
773 
774   // Now all required passes are available.
775   if (ImmutablePass *IP = P->getAsImmutablePass()) {
776     // P is a immutable pass and it will be managed by this
777     // top level manager. Set up analysis resolver to connect them.
778     PMDataManager *DM = getAsPMDataManager();
779     AnalysisResolver *AR = new AnalysisResolver(*DM);
780     P->setResolver(AR);
781     DM->initializeAnalysisImpl(P);
782     addImmutablePass(IP);
783     DM->recordAvailableAnalysis(IP);
784     return;
785   }
786 
787   if (PI && !PI->isAnalysis() && shouldPrintBeforePass(PI->getPassArgument())) {
788     Pass *PP = P->createPrinterPass(
789         dbgs(), ("*** IR Dump Before " + P->getPassName() + " ***").str());
790     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
791   }
792 
793   // Add the requested pass to the best available pass manager.
794   P->assignPassManager(activeStack, getTopLevelPassManagerType());
795 
796   if (PI && !PI->isAnalysis() && shouldPrintAfterPass(PI->getPassArgument())) {
797     Pass *PP = P->createPrinterPass(
798         dbgs(), ("*** IR Dump After " + P->getPassName() + " ***").str());
799     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
800   }
801 }
802 
803 /// Find the pass that implements Analysis AID. Search immutable
804 /// passes and all pass managers. If desired pass is not found
805 /// then return NULL.
806 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
807   // For immutable passes we have a direct mapping from ID to pass, so check
808   // that first.
809   if (Pass *P = ImmutablePassMap.lookup(AID))
810     return P;
811 
812   // Check pass managers
813   for (PMDataManager *PassManager : PassManagers)
814     if (Pass *P = PassManager->findAnalysisPass(AID, false))
815       return P;
816 
817   // Check other pass managers
818   for (PMDataManager *IndirectPassManager : IndirectPassManagers)
819     if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false))
820       return P;
821 
822   return nullptr;
823 }
824 
825 const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const {
826   const PassInfo *&PI = AnalysisPassInfos[AID];
827   if (!PI)
828     PI = PassRegistry::getPassRegistry()->getPassInfo(AID);
829   else
830     assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) &&
831            "The pass info pointer changed for an analysis ID!");
832 
833   return PI;
834 }
835 
836 void PMTopLevelManager::addImmutablePass(ImmutablePass *P) {
837   P->initializePass();
838   ImmutablePasses.push_back(P);
839 
840   // Add this pass to the map from its analysis ID. We clobber any prior runs
841   // of the pass in the map so that the last one added is the one found when
842   // doing lookups.
843   AnalysisID AID = P->getPassID();
844   ImmutablePassMap[AID] = P;
845 
846   // Also add any interfaces implemented by the immutable pass to the map for
847   // fast lookup.
848   const PassInfo *PassInf = findAnalysisPassInfo(AID);
849   assert(PassInf && "Expected all immutable passes to be initialized");
850   for (const PassInfo *ImmPI : PassInf->getInterfacesImplemented())
851     ImmutablePassMap[ImmPI->getTypeInfo()] = P;
852 }
853 
854 // Print passes managed by this top level manager.
855 void PMTopLevelManager::dumpPasses() const {
856 
857   if (PassDebugging < Structure)
858     return;
859 
860   // Print out the immutable passes
861   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
862     ImmutablePasses[i]->dumpPassStructure(0);
863   }
864 
865   // Every class that derives from PMDataManager also derives from Pass
866   // (sometimes indirectly), but there's no inheritance relationship
867   // between PMDataManager and Pass, so we have to getAsPass to get
868   // from a PMDataManager* to a Pass*.
869   for (PMDataManager *Manager : PassManagers)
870     Manager->getAsPass()->dumpPassStructure(1);
871 }
872 
873 void PMTopLevelManager::dumpArguments() const {
874 
875   if (PassDebugging < Arguments)
876     return;
877 
878   dbgs() << "Pass Arguments: ";
879   for (ImmutablePass *P : ImmutablePasses)
880     if (const PassInfo *PI = findAnalysisPassInfo(P->getPassID())) {
881       assert(PI && "Expected all immutable passes to be initialized");
882       if (!PI->isAnalysisGroup())
883         dbgs() << " -" << PI->getPassArgument();
884     }
885   for (PMDataManager *PM : PassManagers)
886     PM->dumpPassArguments();
887   dbgs() << "\n";
888 }
889 
890 void PMTopLevelManager::initializeAllAnalysisInfo() {
891   for (PMDataManager *PM : PassManagers)
892     PM->initializeAnalysisInfo();
893 
894   // Initailize other pass managers
895   for (PMDataManager *IPM : IndirectPassManagers)
896     IPM->initializeAnalysisInfo();
897 
898   for (auto LU : LastUser) {
899     SmallPtrSet<Pass *, 8> &L = InversedLastUser[LU.second];
900     L.insert(LU.first);
901   }
902 }
903 
904 /// Destructor
905 PMTopLevelManager::~PMTopLevelManager() {
906   for (PMDataManager *PM : PassManagers)
907     delete PM;
908 
909   for (ImmutablePass *P : ImmutablePasses)
910     delete P;
911 }
912 
913 //===----------------------------------------------------------------------===//
914 // PMDataManager implementation
915 
916 /// Augement AvailableAnalysis by adding analysis made available by pass P.
917 void PMDataManager::recordAvailableAnalysis(Pass *P) {
918   AnalysisID PI = P->getPassID();
919 
920   AvailableAnalysis[PI] = P;
921 
922   assert(!AvailableAnalysis.empty());
923 
924   // This pass is the current implementation of all of the interfaces it
925   // implements as well.
926   const PassInfo *PInf = TPM->findAnalysisPassInfo(PI);
927   if (!PInf) return;
928   const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
929   for (unsigned i = 0, e = II.size(); i != e; ++i)
930     AvailableAnalysis[II[i]->getTypeInfo()] = P;
931 }
932 
933 // Return true if P preserves high level analysis used by other
934 // passes managed by this manager
935 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
936   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
937   if (AnUsage->getPreservesAll())
938     return true;
939 
940   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
941   for (Pass *P1 : HigherLevelAnalysis) {
942     if (P1->getAsImmutablePass() == nullptr &&
943         !is_contained(PreservedSet, P1->getPassID()))
944       return false;
945   }
946 
947   return true;
948 }
949 
950 /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
951 void PMDataManager::verifyPreservedAnalysis(Pass *P) {
952   // Don't do this unless assertions are enabled.
953 #ifdef NDEBUG
954   return;
955 #endif
956   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
957   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
958 
959   // Verify preserved analysis
960   for (AnalysisID AID : PreservedSet) {
961     if (Pass *AP = findAnalysisPass(AID, true)) {
962       TimeRegion PassTimer(getPassTimer(AP));
963       AP->verifyAnalysis();
964     }
965   }
966 }
967 
968 /// Remove Analysis not preserved by Pass P
969 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
970   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
971   if (AnUsage->getPreservesAll())
972     return;
973 
974   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
975   for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
976          E = AvailableAnalysis.end(); I != E; ) {
977     DenseMap<AnalysisID, Pass*>::iterator Info = I++;
978     if (Info->second->getAsImmutablePass() == nullptr &&
979         !is_contained(PreservedSet, Info->first)) {
980       // Remove this analysis
981       if (PassDebugging >= Details) {
982         Pass *S = Info->second;
983         dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
984         dbgs() << S->getPassName() << "'\n";
985       }
986       AvailableAnalysis.erase(Info);
987     }
988   }
989 
990   // Check inherited analysis also. If P is not preserving analysis
991   // provided by parent manager then remove it here.
992   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
993 
994     if (!InheritedAnalysis[Index])
995       continue;
996 
997     for (DenseMap<AnalysisID, Pass*>::iterator
998            I = InheritedAnalysis[Index]->begin(),
999            E = InheritedAnalysis[Index]->end(); I != E; ) {
1000       DenseMap<AnalysisID, Pass *>::iterator Info = I++;
1001       if (Info->second->getAsImmutablePass() == nullptr &&
1002           !is_contained(PreservedSet, Info->first)) {
1003         // Remove this analysis
1004         if (PassDebugging >= Details) {
1005           Pass *S = Info->second;
1006           dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
1007           dbgs() << S->getPassName() << "'\n";
1008         }
1009         InheritedAnalysis[Index]->erase(Info);
1010       }
1011     }
1012   }
1013 }
1014 
1015 /// Remove analysis passes that are not used any longer
1016 void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg,
1017                                      enum PassDebuggingString DBG_STR) {
1018 
1019   SmallVector<Pass *, 12> DeadPasses;
1020 
1021   // If this is a on the fly manager then it does not have TPM.
1022   if (!TPM)
1023     return;
1024 
1025   TPM->collectLastUses(DeadPasses, P);
1026 
1027   if (PassDebugging >= Details && !DeadPasses.empty()) {
1028     dbgs() << " -*- '" <<  P->getPassName();
1029     dbgs() << "' is the last user of following pass instances.";
1030     dbgs() << " Free these instances\n";
1031   }
1032 
1033   for (Pass *P : DeadPasses)
1034     freePass(P, Msg, DBG_STR);
1035 }
1036 
1037 void PMDataManager::freePass(Pass *P, StringRef Msg,
1038                              enum PassDebuggingString DBG_STR) {
1039   dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg);
1040 
1041   {
1042     // If the pass crashes releasing memory, remember this.
1043     PassManagerPrettyStackEntry X(P);
1044     TimeRegion PassTimer(getPassTimer(P));
1045 
1046     P->releaseMemory();
1047   }
1048 
1049   AnalysisID PI = P->getPassID();
1050   if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) {
1051     // Remove the pass itself (if it is not already removed).
1052     AvailableAnalysis.erase(PI);
1053 
1054     // Remove all interfaces this pass implements, for which it is also
1055     // listed as the available implementation.
1056     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
1057     for (unsigned i = 0, e = II.size(); i != e; ++i) {
1058       DenseMap<AnalysisID, Pass*>::iterator Pos =
1059         AvailableAnalysis.find(II[i]->getTypeInfo());
1060       if (Pos != AvailableAnalysis.end() && Pos->second == P)
1061         AvailableAnalysis.erase(Pos);
1062     }
1063   }
1064 }
1065 
1066 /// Add pass P into the PassVector. Update
1067 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
1068 void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
1069   // This manager is going to manage pass P. Set up analysis resolver
1070   // to connect them.
1071   AnalysisResolver *AR = new AnalysisResolver(*this);
1072   P->setResolver(AR);
1073 
1074   // If a FunctionPass F is the last user of ModulePass info M
1075   // then the F's manager, not F, records itself as a last user of M.
1076   SmallVector<Pass *, 12> TransferLastUses;
1077 
1078   if (!ProcessAnalysis) {
1079     // Add pass
1080     PassVector.push_back(P);
1081     return;
1082   }
1083 
1084   // At the moment, this pass is the last user of all required passes.
1085   SmallVector<Pass *, 12> LastUses;
1086   SmallVector<Pass *, 8> UsedPasses;
1087   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
1088 
1089   unsigned PDepth = this->getDepth();
1090 
1091   collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P);
1092   for (Pass *PUsed : UsedPasses) {
1093     unsigned RDepth = 0;
1094 
1095     assert(PUsed->getResolver() && "Analysis Resolver is not set");
1096     PMDataManager &DM = PUsed->getResolver()->getPMDataManager();
1097     RDepth = DM.getDepth();
1098 
1099     if (PDepth == RDepth)
1100       LastUses.push_back(PUsed);
1101     else if (PDepth > RDepth) {
1102       // Let the parent claim responsibility of last use
1103       TransferLastUses.push_back(PUsed);
1104       // Keep track of higher level analysis used by this manager.
1105       HigherLevelAnalysis.push_back(PUsed);
1106     } else
1107       llvm_unreachable("Unable to accommodate Used Pass");
1108   }
1109 
1110   // Set P as P's last user until someone starts using P.
1111   // However, if P is a Pass Manager then it does not need
1112   // to record its last user.
1113   if (!P->getAsPMDataManager())
1114     LastUses.push_back(P);
1115   TPM->setLastUser(LastUses, P);
1116 
1117   if (!TransferLastUses.empty()) {
1118     Pass *My_PM = getAsPass();
1119     TPM->setLastUser(TransferLastUses, My_PM);
1120     TransferLastUses.clear();
1121   }
1122 
1123   // Now, take care of required analyses that are not available.
1124   for (AnalysisID ID : ReqAnalysisNotAvailable) {
1125     const PassInfo *PI = TPM->findAnalysisPassInfo(ID);
1126     Pass *AnalysisPass = PI->createPass();
1127     this->addLowerLevelRequiredPass(P, AnalysisPass);
1128   }
1129 
1130   // Take a note of analysis required and made available by this pass.
1131   // Remove the analysis not preserved by this pass
1132   removeNotPreservedAnalysis(P);
1133   recordAvailableAnalysis(P);
1134 
1135   // Add pass
1136   PassVector.push_back(P);
1137 }
1138 
1139 
1140 /// Populate UP with analysis pass that are used or required by
1141 /// pass P and are available. Populate RP_NotAvail with analysis
1142 /// pass that are required by pass P but are not available.
1143 void PMDataManager::collectRequiredAndUsedAnalyses(
1144     SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail,
1145     Pass *P) {
1146   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
1147 
1148   for (const auto &UsedID : AnUsage->getUsedSet())
1149     if (Pass *AnalysisPass = findAnalysisPass(UsedID, true))
1150       UP.push_back(AnalysisPass);
1151 
1152   for (const auto &RequiredID : AnUsage->getRequiredSet())
1153     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
1154       UP.push_back(AnalysisPass);
1155     else
1156       RP_NotAvail.push_back(RequiredID);
1157 
1158   for (const auto &RequiredID : AnUsage->getRequiredTransitiveSet())
1159     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
1160       UP.push_back(AnalysisPass);
1161     else
1162       RP_NotAvail.push_back(RequiredID);
1163 }
1164 
1165 // All Required analyses should be available to the pass as it runs!  Here
1166 // we fill in the AnalysisImpls member of the pass so that it can
1167 // successfully use the getAnalysis() method to retrieve the
1168 // implementations it needs.
1169 //
1170 void PMDataManager::initializeAnalysisImpl(Pass *P) {
1171   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
1172 
1173   for (const AnalysisID ID : AnUsage->getRequiredSet()) {
1174     Pass *Impl = findAnalysisPass(ID, true);
1175     if (!Impl)
1176       // This may be analysis pass that is initialized on the fly.
1177       // If that is not the case then it will raise an assert when it is used.
1178       continue;
1179     AnalysisResolver *AR = P->getResolver();
1180     assert(AR && "Analysis Resolver is not set");
1181     AR->addAnalysisImplsPair(ID, Impl);
1182   }
1183 }
1184 
1185 /// Find the pass that implements Analysis AID. If desired pass is not found
1186 /// then return NULL.
1187 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
1188 
1189   // Check if AvailableAnalysis map has one entry.
1190   DenseMap<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
1191 
1192   if (I != AvailableAnalysis.end())
1193     return I->second;
1194 
1195   // Search Parents through TopLevelManager
1196   if (SearchParent)
1197     return TPM->findAnalysisPass(AID);
1198 
1199   return nullptr;
1200 }
1201 
1202 // Print list of passes that are last used by P.
1203 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
1204 
1205   SmallVector<Pass *, 12> LUses;
1206 
1207   // If this is a on the fly manager then it does not have TPM.
1208   if (!TPM)
1209     return;
1210 
1211   TPM->collectLastUses(LUses, P);
1212 
1213   for (Pass *P : LUses) {
1214     dbgs() << "--" << std::string(Offset*2, ' ');
1215     P->dumpPassStructure(0);
1216   }
1217 }
1218 
1219 void PMDataManager::dumpPassArguments() const {
1220   for (Pass *P : PassVector) {
1221     if (PMDataManager *PMD = P->getAsPMDataManager())
1222       PMD->dumpPassArguments();
1223     else
1224       if (const PassInfo *PI =
1225             TPM->findAnalysisPassInfo(P->getPassID()))
1226         if (!PI->isAnalysisGroup())
1227           dbgs() << " -" << PI->getPassArgument();
1228   }
1229 }
1230 
1231 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
1232                                  enum PassDebuggingString S2,
1233                                  StringRef Msg) {
1234   if (PassDebugging < Executions)
1235     return;
1236   dbgs() << "[" << std::chrono::system_clock::now() << "] " << (void *)this
1237          << std::string(getDepth() * 2 + 1, ' ');
1238   switch (S1) {
1239   case EXECUTION_MSG:
1240     dbgs() << "Executing Pass '" << P->getPassName();
1241     break;
1242   case MODIFICATION_MSG:
1243     dbgs() << "Made Modification '" << P->getPassName();
1244     break;
1245   case FREEING_MSG:
1246     dbgs() << " Freeing Pass '" << P->getPassName();
1247     break;
1248   default:
1249     break;
1250   }
1251   switch (S2) {
1252   case ON_BASICBLOCK_MSG:
1253     dbgs() << "' on BasicBlock '" << Msg << "'...\n";
1254     break;
1255   case ON_FUNCTION_MSG:
1256     dbgs() << "' on Function '" << Msg << "'...\n";
1257     break;
1258   case ON_MODULE_MSG:
1259     dbgs() << "' on Module '"  << Msg << "'...\n";
1260     break;
1261   case ON_REGION_MSG:
1262     dbgs() << "' on Region '"  << Msg << "'...\n";
1263     break;
1264   case ON_LOOP_MSG:
1265     dbgs() << "' on Loop '" << Msg << "'...\n";
1266     break;
1267   case ON_CG_MSG:
1268     dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n";
1269     break;
1270   default:
1271     break;
1272   }
1273 }
1274 
1275 void PMDataManager::dumpRequiredSet(const Pass *P) const {
1276   if (PassDebugging < Details)
1277     return;
1278 
1279   AnalysisUsage analysisUsage;
1280   P->getAnalysisUsage(analysisUsage);
1281   dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
1282 }
1283 
1284 void PMDataManager::dumpPreservedSet(const Pass *P) const {
1285   if (PassDebugging < Details)
1286     return;
1287 
1288   AnalysisUsage analysisUsage;
1289   P->getAnalysisUsage(analysisUsage);
1290   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
1291 }
1292 
1293 void PMDataManager::dumpUsedSet(const Pass *P) const {
1294   if (PassDebugging < Details)
1295     return;
1296 
1297   AnalysisUsage analysisUsage;
1298   P->getAnalysisUsage(analysisUsage);
1299   dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet());
1300 }
1301 
1302 void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
1303                                    const AnalysisUsage::VectorType &Set) const {
1304   assert(PassDebugging >= Details);
1305   if (Set.empty())
1306     return;
1307   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
1308   for (unsigned i = 0; i != Set.size(); ++i) {
1309     if (i) dbgs() << ',';
1310     const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]);
1311     if (!PInf) {
1312       // Some preserved passes, such as AliasAnalysis, may not be initialized by
1313       // all drivers.
1314       dbgs() << " Uninitialized Pass";
1315       continue;
1316     }
1317     dbgs() << ' ' << PInf->getPassName();
1318   }
1319   dbgs() << '\n';
1320 }
1321 
1322 /// Add RequiredPass into list of lower level passes required by pass P.
1323 /// RequiredPass is run on the fly by Pass Manager when P requests it
1324 /// through getAnalysis interface.
1325 /// This should be handled by specific pass manager.
1326 void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1327   if (TPM) {
1328     TPM->dumpArguments();
1329     TPM->dumpPasses();
1330   }
1331 
1332   // Module Level pass may required Function Level analysis info
1333   // (e.g. dominator info). Pass manager uses on the fly function pass manager
1334   // to provide this on demand. In that case, in Pass manager terminology,
1335   // module level pass is requiring lower level analysis info managed by
1336   // lower level pass manager.
1337 
1338   // When Pass manager is not able to order required analysis info, Pass manager
1339   // checks whether any lower level manager will be able to provide this
1340   // analysis info on demand or not.
1341 #ifndef NDEBUG
1342   dbgs() << "Unable to schedule '" << RequiredPass->getPassName();
1343   dbgs() << "' required by '" << P->getPassName() << "'\n";
1344 #endif
1345   llvm_unreachable("Unable to schedule pass");
1346 }
1347 
1348 Pass *PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F) {
1349   llvm_unreachable("Unable to find on the fly pass");
1350 }
1351 
1352 // Destructor
1353 PMDataManager::~PMDataManager() {
1354   for (Pass *P : PassVector)
1355     delete P;
1356 }
1357 
1358 //===----------------------------------------------------------------------===//
1359 // NOTE: Is this the right place to define this method ?
1360 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
1361 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
1362   return PM.findAnalysisPass(ID, dir);
1363 }
1364 
1365 Pass *AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI,
1366                                      Function &F) {
1367   return PM.getOnTheFlyPass(P, AnalysisPI, F);
1368 }
1369 
1370 //===----------------------------------------------------------------------===//
1371 // BBPassManager implementation
1372 
1373 /// Execute all of the passes scheduled for execution by invoking
1374 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
1375 /// the function, and if so, return true.
1376 bool BBPassManager::runOnFunction(Function &F) {
1377   if (F.isDeclaration())
1378     return false;
1379 
1380   bool Changed = doInitialization(F);
1381   Module &M = *F.getParent();
1382 
1383   unsigned InstrCount, BBSize = 0;
1384   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
1385   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
1386   if (EmitICRemark)
1387     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
1388 
1389   for (BasicBlock &BB : F) {
1390     // Collect the initial size of the basic block.
1391     if (EmitICRemark)
1392       BBSize = BB.size();
1393     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1394       BasicBlockPass *BP = getContainedPass(Index);
1395       bool LocalChanged = false;
1396 
1397       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, BB.getName());
1398       dumpRequiredSet(BP);
1399 
1400       initializeAnalysisImpl(BP);
1401 
1402       {
1403         // If the pass crashes, remember this.
1404         PassManagerPrettyStackEntry X(BP, BB);
1405         TimeRegion PassTimer(getPassTimer(BP));
1406         LocalChanged |= BP->runOnBasicBlock(BB);
1407         if (EmitICRemark) {
1408           unsigned NewSize = BB.size();
1409           // Update the size of the basic block, emit a remark, and update the
1410           // size of the module.
1411           if (NewSize != BBSize) {
1412             int64_t Delta =
1413                 static_cast<int64_t>(NewSize) - static_cast<int64_t>(BBSize);
1414             emitInstrCountChangedRemark(BP, M, Delta, InstrCount,
1415                                         FunctionToInstrCount, &F);
1416             InstrCount = static_cast<int64_t>(InstrCount) + Delta;
1417             BBSize = NewSize;
1418           }
1419         }
1420       }
1421 
1422       Changed |= LocalChanged;
1423       if (LocalChanged)
1424         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
1425                      BB.getName());
1426       dumpPreservedSet(BP);
1427       dumpUsedSet(BP);
1428 
1429       verifyPreservedAnalysis(BP);
1430       removeNotPreservedAnalysis(BP);
1431       recordAvailableAnalysis(BP);
1432       removeDeadPasses(BP, BB.getName(), ON_BASICBLOCK_MSG);
1433     }
1434   }
1435 
1436   return doFinalization(F) || Changed;
1437 }
1438 
1439 // Implement doInitialization and doFinalization
1440 bool BBPassManager::doInitialization(Module &M) {
1441   bool Changed = false;
1442 
1443   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1444     Changed |= getContainedPass(Index)->doInitialization(M);
1445 
1446   return Changed;
1447 }
1448 
1449 bool BBPassManager::doFinalization(Module &M) {
1450   bool Changed = false;
1451 
1452   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1453     Changed |= getContainedPass(Index)->doFinalization(M);
1454 
1455   return Changed;
1456 }
1457 
1458 bool BBPassManager::doInitialization(Function &F) {
1459   bool Changed = false;
1460 
1461   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1462     BasicBlockPass *BP = getContainedPass(Index);
1463     Changed |= BP->doInitialization(F);
1464   }
1465 
1466   return Changed;
1467 }
1468 
1469 bool BBPassManager::doFinalization(Function &F) {
1470   bool Changed = false;
1471 
1472   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1473     BasicBlockPass *BP = getContainedPass(Index);
1474     Changed |= BP->doFinalization(F);
1475   }
1476 
1477   return Changed;
1478 }
1479 
1480 
1481 //===----------------------------------------------------------------------===//
1482 // FunctionPassManager implementation
1483 
1484 /// Create new Function pass manager
1485 FunctionPassManager::FunctionPassManager(Module *m) : M(m) {
1486   FPM = new FunctionPassManagerImpl();
1487   // FPM is the top level manager.
1488   FPM->setTopLevelManager(FPM);
1489 
1490   AnalysisResolver *AR = new AnalysisResolver(*FPM);
1491   FPM->setResolver(AR);
1492 }
1493 
1494 FunctionPassManager::~FunctionPassManager() {
1495   delete FPM;
1496 }
1497 
1498 void FunctionPassManager::add(Pass *P) {
1499   FPM->add(P);
1500 }
1501 
1502 /// run - Execute all of the passes scheduled for execution.  Keep
1503 /// track of whether any of the passes modifies the function, and if
1504 /// so, return true.
1505 ///
1506 bool FunctionPassManager::run(Function &F) {
1507   handleAllErrors(F.materialize(), [&](ErrorInfoBase &EIB) {
1508     report_fatal_error("Error reading bitcode file: " + EIB.message());
1509   });
1510   return FPM->run(F);
1511 }
1512 
1513 
1514 /// doInitialization - Run all of the initializers for the function passes.
1515 ///
1516 bool FunctionPassManager::doInitialization() {
1517   return FPM->doInitialization(*M);
1518 }
1519 
1520 /// doFinalization - Run all of the finalizers for the function passes.
1521 ///
1522 bool FunctionPassManager::doFinalization() {
1523   return FPM->doFinalization(*M);
1524 }
1525 
1526 //===----------------------------------------------------------------------===//
1527 // FunctionPassManagerImpl implementation
1528 //
1529 bool FunctionPassManagerImpl::doInitialization(Module &M) {
1530   bool Changed = false;
1531 
1532   dumpArguments();
1533   dumpPasses();
1534 
1535   for (ImmutablePass *ImPass : getImmutablePasses())
1536     Changed |= ImPass->doInitialization(M);
1537 
1538   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1539     Changed |= getContainedManager(Index)->doInitialization(M);
1540 
1541   return Changed;
1542 }
1543 
1544 bool FunctionPassManagerImpl::doFinalization(Module &M) {
1545   bool Changed = false;
1546 
1547   for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index)
1548     Changed |= getContainedManager(Index)->doFinalization(M);
1549 
1550   for (ImmutablePass *ImPass : getImmutablePasses())
1551     Changed |= ImPass->doFinalization(M);
1552 
1553   return Changed;
1554 }
1555 
1556 /// cleanup - After running all passes, clean up pass manager cache.
1557 void FPPassManager::cleanup() {
1558  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1559     FunctionPass *FP = getContainedPass(Index);
1560     AnalysisResolver *AR = FP->getResolver();
1561     assert(AR && "Analysis Resolver is not set");
1562     AR->clearAnalysisImpls();
1563  }
1564 }
1565 
1566 void FunctionPassManagerImpl::releaseMemoryOnTheFly() {
1567   if (!wasRun)
1568     return;
1569   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1570     FPPassManager *FPPM = getContainedManager(Index);
1571     for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) {
1572       FPPM->getContainedPass(Index)->releaseMemory();
1573     }
1574   }
1575   wasRun = false;
1576 }
1577 
1578 // Execute all the passes managed by this top level manager.
1579 // Return true if any function is modified by a pass.
1580 bool FunctionPassManagerImpl::run(Function &F) {
1581   bool Changed = false;
1582 
1583   initializeAllAnalysisInfo();
1584   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1585     Changed |= getContainedManager(Index)->runOnFunction(F);
1586     F.getContext().yield();
1587   }
1588 
1589   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1590     getContainedManager(Index)->cleanup();
1591 
1592   wasRun = true;
1593   return Changed;
1594 }
1595 
1596 //===----------------------------------------------------------------------===//
1597 // FPPassManager implementation
1598 
1599 char FPPassManager::ID = 0;
1600 /// Print passes managed by this manager
1601 void FPPassManager::dumpPassStructure(unsigned Offset) {
1602   dbgs().indent(Offset*2) << "FunctionPass Manager\n";
1603   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1604     FunctionPass *FP = getContainedPass(Index);
1605     FP->dumpPassStructure(Offset + 1);
1606     dumpLastUses(FP, Offset+1);
1607   }
1608 }
1609 
1610 
1611 /// Execute all of the passes scheduled for execution by invoking
1612 /// runOnFunction method.  Keep track of whether any of the passes modifies
1613 /// the function, and if so, return true.
1614 bool FPPassManager::runOnFunction(Function &F) {
1615   if (F.isDeclaration())
1616     return false;
1617 
1618   bool Changed = false;
1619   Module &M = *F.getParent();
1620   // Collect inherited analysis from Module level pass manager.
1621   populateInheritedAnalysis(TPM->activeStack);
1622 
1623   unsigned InstrCount, FunctionSize = 0;
1624   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
1625   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
1626   // Collect the initial size of the module.
1627   if (EmitICRemark) {
1628     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
1629     FunctionSize = F.getInstructionCount();
1630   }
1631 
1632   llvm::TimeTraceScope FunctionScope("OptFunction", F.getName());
1633 
1634   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1635     FunctionPass *FP = getContainedPass(Index);
1636     bool LocalChanged = false;
1637 
1638     llvm::TimeTraceScope PassScope("RunPass", FP->getPassName());
1639 
1640     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
1641     dumpRequiredSet(FP);
1642 
1643     initializeAnalysisImpl(FP);
1644 
1645     {
1646       PassManagerPrettyStackEntry X(FP, F);
1647       TimeRegion PassTimer(getPassTimer(FP));
1648       LocalChanged |= FP->runOnFunction(F);
1649       if (EmitICRemark) {
1650         unsigned NewSize = F.getInstructionCount();
1651 
1652         // Update the size of the function, emit a remark, and update the size
1653         // of the module.
1654         if (NewSize != FunctionSize) {
1655           int64_t Delta = static_cast<int64_t>(NewSize) -
1656                           static_cast<int64_t>(FunctionSize);
1657           emitInstrCountChangedRemark(FP, M, Delta, InstrCount,
1658                                       FunctionToInstrCount, &F);
1659           InstrCount = static_cast<int64_t>(InstrCount) + Delta;
1660           FunctionSize = NewSize;
1661         }
1662       }
1663     }
1664 
1665     Changed |= LocalChanged;
1666     if (LocalChanged)
1667       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
1668     dumpPreservedSet(FP);
1669     dumpUsedSet(FP);
1670 
1671     verifyPreservedAnalysis(FP);
1672     removeNotPreservedAnalysis(FP);
1673     recordAvailableAnalysis(FP);
1674     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
1675   }
1676 
1677   return Changed;
1678 }
1679 
1680 bool FPPassManager::runOnModule(Module &M) {
1681   bool Changed = false;
1682 
1683   llvm::TimeTraceScope TimeScope("OptModule", M.getName());
1684   for (Function &F : M)
1685     Changed |= runOnFunction(F);
1686 
1687   return Changed;
1688 }
1689 
1690 bool FPPassManager::doInitialization(Module &M) {
1691   bool Changed = false;
1692 
1693   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1694     Changed |= getContainedPass(Index)->doInitialization(M);
1695 
1696   return Changed;
1697 }
1698 
1699 bool FPPassManager::doFinalization(Module &M) {
1700   bool Changed = false;
1701 
1702   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1703     Changed |= getContainedPass(Index)->doFinalization(M);
1704 
1705   return Changed;
1706 }
1707 
1708 //===----------------------------------------------------------------------===//
1709 // MPPassManager implementation
1710 
1711 /// Execute all of the passes scheduled for execution by invoking
1712 /// runOnModule method.  Keep track of whether any of the passes modifies
1713 /// the module, and if so, return true.
1714 bool
1715 MPPassManager::runOnModule(Module &M) {
1716   llvm::TimeTraceScope TimeScope("OptModule", M.getName());
1717 
1718   bool Changed = false;
1719 
1720   // Initialize on-the-fly passes
1721   for (auto &OnTheFlyManager : OnTheFlyManagers) {
1722     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
1723     Changed |= FPP->doInitialization(M);
1724   }
1725 
1726   // Initialize module passes
1727   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1728     Changed |= getContainedPass(Index)->doInitialization(M);
1729 
1730   unsigned InstrCount;
1731   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
1732   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
1733   // Collect the initial size of the module.
1734   if (EmitICRemark)
1735     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
1736 
1737   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1738     ModulePass *MP = getContainedPass(Index);
1739     bool LocalChanged = false;
1740 
1741     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
1742     dumpRequiredSet(MP);
1743 
1744     initializeAnalysisImpl(MP);
1745 
1746     {
1747       PassManagerPrettyStackEntry X(MP, M);
1748       TimeRegion PassTimer(getPassTimer(MP));
1749 
1750       LocalChanged |= MP->runOnModule(M);
1751       if (EmitICRemark) {
1752         // Update the size of the module.
1753         unsigned ModuleCount = M.getInstructionCount();
1754         if (ModuleCount != InstrCount) {
1755           int64_t Delta = static_cast<int64_t>(ModuleCount) -
1756                           static_cast<int64_t>(InstrCount);
1757           emitInstrCountChangedRemark(MP, M, Delta, InstrCount,
1758                                       FunctionToInstrCount);
1759           InstrCount = ModuleCount;
1760         }
1761       }
1762     }
1763 
1764     Changed |= LocalChanged;
1765     if (LocalChanged)
1766       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
1767                    M.getModuleIdentifier());
1768     dumpPreservedSet(MP);
1769     dumpUsedSet(MP);
1770 
1771     verifyPreservedAnalysis(MP);
1772     removeNotPreservedAnalysis(MP);
1773     recordAvailableAnalysis(MP);
1774     removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
1775   }
1776 
1777   // Finalize module passes
1778   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1779     Changed |= getContainedPass(Index)->doFinalization(M);
1780 
1781   // Finalize on-the-fly passes
1782   for (auto &OnTheFlyManager : OnTheFlyManagers) {
1783     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
1784     // We don't know when is the last time an on-the-fly pass is run,
1785     // so we need to releaseMemory / finalize here
1786     FPP->releaseMemoryOnTheFly();
1787     Changed |= FPP->doFinalization(M);
1788   }
1789 
1790   return Changed;
1791 }
1792 
1793 /// Add RequiredPass into list of lower level passes required by pass P.
1794 /// RequiredPass is run on the fly by Pass Manager when P requests it
1795 /// through getAnalysis interface.
1796 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1797   assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
1798          "Unable to handle Pass that requires lower level Analysis pass");
1799   assert((P->getPotentialPassManagerType() <
1800           RequiredPass->getPotentialPassManagerType()) &&
1801          "Unable to handle Pass that requires lower level Analysis pass");
1802   if (!RequiredPass)
1803     return;
1804 
1805   FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
1806   if (!FPP) {
1807     FPP = new FunctionPassManagerImpl();
1808     // FPP is the top level manager.
1809     FPP->setTopLevelManager(FPP);
1810 
1811     OnTheFlyManagers[P] = FPP;
1812   }
1813   const PassInfo *RequiredPassPI =
1814       TPM->findAnalysisPassInfo(RequiredPass->getPassID());
1815 
1816   Pass *FoundPass = nullptr;
1817   if (RequiredPassPI && RequiredPassPI->isAnalysis()) {
1818     FoundPass =
1819       ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID());
1820   }
1821   if (!FoundPass) {
1822     FoundPass = RequiredPass;
1823     // This should be guaranteed to add RequiredPass to the passmanager given
1824     // that we checked for an available analysis above.
1825     FPP->add(RequiredPass);
1826   }
1827   // Register P as the last user of FoundPass or RequiredPass.
1828   SmallVector<Pass *, 1> LU;
1829   LU.push_back(FoundPass);
1830   FPP->setLastUser(LU,  P);
1831 }
1832 
1833 /// Return function pass corresponding to PassInfo PI, that is
1834 /// required by module pass MP. Instantiate analysis pass, by using
1835 /// its runOnFunction() for function F.
1836 Pass* MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F){
1837   FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
1838   assert(FPP && "Unable to find on the fly pass");
1839 
1840   FPP->releaseMemoryOnTheFly();
1841   FPP->run(F);
1842   return ((PMTopLevelManager*)FPP)->findAnalysisPass(PI);
1843 }
1844 
1845 
1846 //===----------------------------------------------------------------------===//
1847 // PassManagerImpl implementation
1848 
1849 //
1850 /// run - Execute all of the passes scheduled for execution.  Keep track of
1851 /// whether any of the passes modifies the module, and if so, return true.
1852 bool PassManagerImpl::run(Module &M) {
1853   bool Changed = false;
1854 
1855   dumpArguments();
1856   dumpPasses();
1857 
1858   for (ImmutablePass *ImPass : getImmutablePasses())
1859     Changed |= ImPass->doInitialization(M);
1860 
1861   initializeAllAnalysisInfo();
1862   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1863     Changed |= getContainedManager(Index)->runOnModule(M);
1864     M.getContext().yield();
1865   }
1866 
1867   for (ImmutablePass *ImPass : getImmutablePasses())
1868     Changed |= ImPass->doFinalization(M);
1869 
1870   return Changed;
1871 }
1872 
1873 //===----------------------------------------------------------------------===//
1874 // PassManager implementation
1875 
1876 /// Create new pass manager
1877 PassManager::PassManager() {
1878   PM = new PassManagerImpl();
1879   // PM is the top level manager
1880   PM->setTopLevelManager(PM);
1881 }
1882 
1883 PassManager::~PassManager() {
1884   delete PM;
1885 }
1886 
1887 void PassManager::add(Pass *P) {
1888   PM->add(P);
1889 }
1890 
1891 /// run - Execute all of the passes scheduled for execution.  Keep track of
1892 /// whether any of the passes modifies the module, and if so, return true.
1893 bool PassManager::run(Module &M) {
1894   return PM->run(M);
1895 }
1896 
1897 //===----------------------------------------------------------------------===//
1898 // PMStack implementation
1899 //
1900 
1901 // Pop Pass Manager from the stack and clear its analysis info.
1902 void PMStack::pop() {
1903 
1904   PMDataManager *Top = this->top();
1905   Top->initializeAnalysisInfo();
1906 
1907   S.pop_back();
1908 }
1909 
1910 // Push PM on the stack and set its top level manager.
1911 void PMStack::push(PMDataManager *PM) {
1912   assert(PM && "Unable to push. Pass Manager expected");
1913   assert(PM->getDepth()==0 && "Pass Manager depth set too early");
1914 
1915   if (!this->empty()) {
1916     assert(PM->getPassManagerType() > this->top()->getPassManagerType()
1917            && "pushing bad pass manager to PMStack");
1918     PMTopLevelManager *TPM = this->top()->getTopLevelManager();
1919 
1920     assert(TPM && "Unable to find top level manager");
1921     TPM->addIndirectPassManager(PM);
1922     PM->setTopLevelManager(TPM);
1923     PM->setDepth(this->top()->getDepth()+1);
1924   } else {
1925     assert((PM->getPassManagerType() == PMT_ModulePassManager
1926            || PM->getPassManagerType() == PMT_FunctionPassManager)
1927            && "pushing bad pass manager to PMStack");
1928     PM->setDepth(1);
1929   }
1930 
1931   S.push_back(PM);
1932 }
1933 
1934 // Dump content of the pass manager stack.
1935 LLVM_DUMP_METHOD void PMStack::dump() const {
1936   for (PMDataManager *Manager : S)
1937     dbgs() << Manager->getAsPass()->getPassName() << ' ';
1938 
1939   if (!S.empty())
1940     dbgs() << '\n';
1941 }
1942 
1943 /// Find appropriate Module Pass Manager in the PM Stack and
1944 /// add self into that manager.
1945 void ModulePass::assignPassManager(PMStack &PMS,
1946                                    PassManagerType PreferredType) {
1947   // Find Module Pass Manager
1948   while (!PMS.empty()) {
1949     PassManagerType TopPMType = PMS.top()->getPassManagerType();
1950     if (TopPMType == PreferredType)
1951       break; // We found desired pass manager
1952     else if (TopPMType > PMT_ModulePassManager)
1953       PMS.pop();    // Pop children pass managers
1954     else
1955       break;
1956   }
1957   assert(!PMS.empty() && "Unable to find appropriate Pass Manager");
1958   PMS.top()->add(this);
1959 }
1960 
1961 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1962 /// in the PM Stack and add self into that manager.
1963 void FunctionPass::assignPassManager(PMStack &PMS,
1964                                      PassManagerType PreferredType) {
1965 
1966   // Find Function Pass Manager
1967   while (!PMS.empty()) {
1968     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1969       PMS.pop();
1970     else
1971       break;
1972   }
1973 
1974   // Create new Function Pass Manager if needed.
1975   FPPassManager *FPP;
1976   if (PMS.top()->getPassManagerType() == PMT_FunctionPassManager) {
1977     FPP = (FPPassManager *)PMS.top();
1978   } else {
1979     assert(!PMS.empty() && "Unable to create Function Pass Manager");
1980     PMDataManager *PMD = PMS.top();
1981 
1982     // [1] Create new Function Pass Manager
1983     FPP = new FPPassManager();
1984     FPP->populateInheritedAnalysis(PMS);
1985 
1986     // [2] Set up new manager's top level manager
1987     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1988     TPM->addIndirectPassManager(FPP);
1989 
1990     // [3] Assign manager to manage this new manager. This may create
1991     // and push new managers into PMS
1992     FPP->assignPassManager(PMS, PMD->getPassManagerType());
1993 
1994     // [4] Push new manager into PMS
1995     PMS.push(FPP);
1996   }
1997 
1998   // Assign FPP as the manager of this pass.
1999   FPP->add(this);
2000 }
2001 
2002 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
2003 /// in the PM Stack and add self into that manager.
2004 void BasicBlockPass::assignPassManager(PMStack &PMS,
2005                                        PassManagerType PreferredType) {
2006   BBPassManager *BBP;
2007 
2008   // Basic Pass Manager is a leaf pass manager. It does not handle
2009   // any other pass manager.
2010   if (!PMS.empty() &&
2011       PMS.top()->getPassManagerType() == PMT_BasicBlockPassManager) {
2012     BBP = (BBPassManager *)PMS.top();
2013   } else {
2014     // If leaf manager is not Basic Block Pass manager then create new
2015     // basic Block Pass manager.
2016     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
2017     PMDataManager *PMD = PMS.top();
2018 
2019     // [1] Create new Basic Block Manager
2020     BBP = new BBPassManager();
2021 
2022     // [2] Set up new manager's top level manager
2023     // Basic Block Pass Manager does not live by itself
2024     PMTopLevelManager *TPM = PMD->getTopLevelManager();
2025     TPM->addIndirectPassManager(BBP);
2026 
2027     // [3] Assign manager to manage this new manager. This may create
2028     // and push new managers into PMS
2029     BBP->assignPassManager(PMS, PreferredType);
2030 
2031     // [4] Push new manager into PMS
2032     PMS.push(BBP);
2033   }
2034 
2035   // Assign BBP as the manager of this pass.
2036   BBP->add(this);
2037 }
2038 
2039 PassManagerBase::~PassManagerBase() {}
2040