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