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