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