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 void *IP = nullptr;
638 if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, InsertPos&: IP))
639 Node = N;
640 else {
641 Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU);
642 UniqueAnalysisUsages.InsertNode(N: Node, InsertPos: IP);
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, ShouldPrintChanged = false;
1392 if (ReportChanged) {
1393 const PassInfo *PI = Pass::lookupPassInfo(TI: FP->getPassID());
1394 if (PI && !PI->isAnalysis()) {
1395 PassID = PI->getPassArgument();
1396 IsInteresting = isPassInPrintList(PassName: PassID);
1397 ShouldPrintChanged = IsInteresting && isFunctionInPrintList(FunctionName: Name);
1398 } else {
1399 ReportChanged = false;
1400 }
1401 }
1402 if (ShouldPrintChanged) {
1403 BeforeStr.clear();
1404 AfterStr.clear();
1405 raw_svector_ostream OS(BeforeStr);
1406 // printIRUnit returns false if there is nothing to report.
1407 ShouldPrintChanged = FP->printIRUnit(OS, F);
1408 }
1409
1410 {
1411 PassManagerPrettyStackEntry X(FP, F);
1412 TimeRegion PassTimer(getPassTimer(FP));
1413#ifdef EXPENSIVE_CHECKS
1414 uint64_t RefHash = FP->structuralHash(F);
1415#endif
1416 LocalChanged |= FP->runOnFunction(F);
1417
1418#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
1419 if (!LocalChanged && (RefHash != FP->structuralHash(F))) {
1420 llvm::errs() << "Pass modifies its input and doesn't report it: "
1421 << FP->getPassName() << "\n";
1422 llvm_unreachable("Pass modifies its input and doesn't report it");
1423 }
1424#endif
1425
1426 if (EmitICRemark) {
1427 unsigned NewSize = F.getInstructionCount();
1428
1429 // Update the size of the function, emit a remark, and update the size
1430 // of the module.
1431 if (NewSize != FunctionSize) {
1432 int64_t Delta = static_cast<int64_t>(NewSize) -
1433 static_cast<int64_t>(FunctionSize);
1434 emitInstrCountChangedRemark(P: FP, M, Delta, CountBefore: InstrCount,
1435 FunctionToInstrCount, F: &F);
1436 InstrCount = static_cast<int64_t>(InstrCount) + Delta;
1437 FunctionSize = NewSize;
1438 }
1439 }
1440 }
1441
1442 if (ShouldPrintChanged) {
1443 raw_svector_ostream OS(AfterStr);
1444 FP->printIRUnit(OS, F);
1445 }
1446 if (ReportChanged)
1447 reportChangedIR(Before: BeforeStr, After: AfterStr, PassName: FP->getPassName(), PassID, IRName: Name,
1448 IsInteresting, ShouldReport: ShouldPrintChanged);
1449
1450 Changed |= LocalChanged;
1451 if (LocalChanged)
1452 dumpPassInfo(P: FP, S1: MODIFICATION_MSG, S2: ON_FUNCTION_MSG, Msg: Name);
1453 dumpPreservedSet(P: FP);
1454 dumpUsedSet(P: FP);
1455
1456 verifyPreservedAnalysis(P: FP);
1457 if (LocalChanged)
1458 removeNotPreservedAnalysis(P: FP);
1459 recordAvailableAnalysis(P: FP);
1460 removeDeadPasses(P: FP, Msg: Name, DBG_STR: ON_FUNCTION_MSG);
1461 }
1462
1463 return Changed;
1464}
1465
1466bool FPPassManager::runOnModule(Module &M) {
1467 bool Changed = false;
1468
1469 for (Function &F : M)
1470 Changed |= runOnFunction(F);
1471
1472 return Changed;
1473}
1474
1475bool FPPassManager::doInitialization(Module &M) {
1476 bool Changed = false;
1477
1478 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1479 Changed |= getContainedPass(N: Index)->doInitialization(M);
1480
1481 return Changed;
1482}
1483
1484bool FPPassManager::doFinalization(Module &M) {
1485 bool Changed = false;
1486
1487 for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1488 Changed |= getContainedPass(N: Index)->doFinalization(M);
1489
1490 return Changed;
1491}
1492
1493//===----------------------------------------------------------------------===//
1494// MPPassManager implementation
1495
1496/// Execute all of the passes scheduled for execution by invoking
1497/// runOnModule method. Keep track of whether any of the passes modifies
1498/// the module, and if so, return true.
1499bool
1500MPPassManager::runOnModule(Module &M) {
1501 llvm::TimeTraceScope TimeScope("OptModule", M.getName());
1502
1503 bool Changed = false;
1504
1505 // Initialize on-the-fly passes
1506 for (auto &OnTheFlyManager : OnTheFlyManagers) {
1507 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
1508 Changed |= FPP->doInitialization(M);
1509 }
1510
1511 // Initialize module passes
1512 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1513 Changed |= getContainedPass(N: Index)->doInitialization(M);
1514
1515 unsigned InstrCount;
1516 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
1517 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
1518 // Collect the initial size of the module.
1519 if (EmitICRemark)
1520 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
1521
1522 SmallString<0> BeforeStr, AfterStr;
1523 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1524 ModulePass *MP = getContainedPass(N: Index);
1525 bool LocalChanged = false;
1526
1527 dumpPassInfo(P: MP, S1: EXECUTION_MSG, S2: ON_MODULE_MSG, Msg: M.getModuleIdentifier());
1528 dumpRequiredSet(P: MP);
1529
1530 initializeAnalysisImpl(P: MP);
1531
1532 // As in FPPassManager, but for module passes. Not subject to
1533 // -filter-print-funcs.
1534 StringRef PassID;
1535 bool ReportChanged = PrintChanged != ChangePrinter::None;
1536 bool IsInteresting = false, ShouldPrintChanged = false;
1537 if (ReportChanged) {
1538 const PassInfo *PI = Pass::lookupPassInfo(TI: MP->getPassID());
1539 if (PI && !PI->isAnalysis()) {
1540 PassID = PI->getPassArgument();
1541 IsInteresting = ShouldPrintChanged = isPassInPrintList(PassName: PassID);
1542 } else {
1543 ReportChanged = false;
1544 }
1545 }
1546 if (ShouldPrintChanged) {
1547 BeforeStr.clear();
1548 AfterStr.clear();
1549 raw_svector_ostream OS(BeforeStr);
1550 M.print(OS, /*AAW=*/nullptr);
1551 }
1552
1553 {
1554 PassManagerPrettyStackEntry X(MP, M);
1555 TimeRegion PassTimer(getPassTimer(MP));
1556
1557#ifdef EXPENSIVE_CHECKS
1558 uint64_t RefHash = MP->structuralHash(M);
1559#endif
1560
1561 LocalChanged |= MP->runOnModule(M);
1562
1563#ifdef EXPENSIVE_CHECKS
1564 assert((LocalChanged || (RefHash == MP->structuralHash(M))) &&
1565 "Pass modifies its input and doesn't report it.");
1566#endif
1567
1568 if (EmitICRemark) {
1569 // Update the size of the module.
1570 unsigned ModuleCount = M.getInstructionCount();
1571 if (ModuleCount != InstrCount) {
1572 int64_t Delta = static_cast<int64_t>(ModuleCount) -
1573 static_cast<int64_t>(InstrCount);
1574 emitInstrCountChangedRemark(P: MP, M, Delta, CountBefore: InstrCount,
1575 FunctionToInstrCount);
1576 InstrCount = ModuleCount;
1577 }
1578 }
1579 }
1580
1581 if (ShouldPrintChanged) {
1582 raw_svector_ostream OS(AfterStr);
1583 M.print(OS, /*AAW=*/nullptr);
1584 }
1585 if (ReportChanged)
1586 reportChangedIR(Before: BeforeStr, After: AfterStr, PassName: MP->getPassName(), PassID,
1587 IRName: M.getModuleIdentifier(), IsInteresting,
1588 ShouldReport: ShouldPrintChanged);
1589
1590 Changed |= LocalChanged;
1591 if (LocalChanged)
1592 dumpPassInfo(P: MP, S1: MODIFICATION_MSG, S2: ON_MODULE_MSG,
1593 Msg: M.getModuleIdentifier());
1594 dumpPreservedSet(P: MP);
1595 dumpUsedSet(P: MP);
1596
1597 verifyPreservedAnalysis(P: MP);
1598 if (LocalChanged)
1599 removeNotPreservedAnalysis(P: MP);
1600 recordAvailableAnalysis(P: MP);
1601 removeDeadPasses(P: MP, Msg: M.getModuleIdentifier(), DBG_STR: ON_MODULE_MSG);
1602 }
1603
1604 // Finalize module passes
1605 for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1606 Changed |= getContainedPass(N: Index)->doFinalization(M);
1607
1608 // Finalize on-the-fly passes
1609 for (auto &OnTheFlyManager : OnTheFlyManagers) {
1610 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
1611 // We don't know when is the last time an on-the-fly pass is run,
1612 // so we need to releaseMemory / finalize here
1613 FPP->releaseMemoryOnTheFly();
1614 Changed |= FPP->doFinalization(M);
1615 }
1616
1617 return Changed;
1618}
1619
1620/// Add RequiredPass into list of lower level passes required by pass P.
1621/// RequiredPass is run on the fly by Pass Manager when P requests it
1622/// through getAnalysis interface.
1623void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1624 assert(RequiredPass && "No required pass?");
1625 assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
1626 "Unable to handle Pass that requires lower level Analysis pass");
1627 assert((P->getPotentialPassManagerType() <
1628 RequiredPass->getPotentialPassManagerType()) &&
1629 "Unable to handle Pass that requires lower level Analysis pass");
1630
1631 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
1632 if (!FPP) {
1633 FPP = new legacy::FunctionPassManagerImpl();
1634 // FPP is the top level manager.
1635 FPP->setTopLevelManager(FPP);
1636
1637 OnTheFlyManagers[P] = FPP;
1638 }
1639 const PassInfo *RequiredPassPI =
1640 TPM->findAnalysisPassInfo(AID: RequiredPass->getPassID());
1641
1642 Pass *FoundPass = nullptr;
1643 if (RequiredPassPI && RequiredPassPI->isAnalysis()) {
1644 FoundPass =
1645 ((PMTopLevelManager*)FPP)->findAnalysisPass(AID: RequiredPass->getPassID());
1646 }
1647 if (!FoundPass) {
1648 FoundPass = RequiredPass;
1649 // This should be guaranteed to add RequiredPass to the passmanager given
1650 // that we checked for an available analysis above.
1651 FPP->add(P: RequiredPass);
1652 }
1653 // Register P as the last user of FoundPass or RequiredPass.
1654 SmallVector<Pass *, 1> LU;
1655 LU.push_back(Elt: FoundPass);
1656 FPP->setLastUser(AnalysisPasses: LU, P);
1657}
1658
1659/// Return function pass corresponding to PassInfo PI, that is
1660/// required by module pass MP. Instantiate analysis pass, by using
1661/// its runOnFunction() for function F.
1662std::tuple<Pass *, bool> MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI,
1663 Function &F) {
1664 legacy::FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
1665 assert(FPP && "Unable to find on the fly pass");
1666
1667 FPP->releaseMemoryOnTheFly();
1668 bool Changed = FPP->run(F);
1669 return std::make_tuple(args: ((PMTopLevelManager *)FPP)->findAnalysisPass(AID: PI),
1670 args&: Changed);
1671}
1672
1673namespace llvm {
1674namespace legacy {
1675
1676//===----------------------------------------------------------------------===//
1677// PassManager implementation
1678
1679/// Create new pass manager
1680PassManager::PassManager() {
1681 PM = new PassManagerImpl();
1682 // PM is the top level manager
1683 PM->setTopLevelManager(PM);
1684}
1685
1686PassManager::~PassManager() {
1687 delete PM;
1688}
1689
1690void PassManager::add(Pass *P) {
1691 PM->add(P);
1692}
1693
1694/// run - Execute all of the passes scheduled for execution. Keep track of
1695/// whether any of the passes modifies the module, and if so, return true.
1696bool PassManager::run(Module &M) {
1697 return PM->run(M);
1698}
1699} // namespace legacy
1700} // namespace llvm
1701
1702//===----------------------------------------------------------------------===//
1703// PMStack implementation
1704//
1705
1706// Pop Pass Manager from the stack and clear its analysis info.
1707void PMStack::pop() {
1708
1709 PMDataManager *Top = this->top();
1710 Top->initializeAnalysisInfo();
1711
1712 S.pop_back();
1713}
1714
1715// Push PM on the stack and set its top level manager.
1716void PMStack::push(PMDataManager *PM) {
1717 assert(PM && "Unable to push. Pass Manager expected");
1718 assert(PM->getDepth()==0 && "Pass Manager depth set too early");
1719
1720 if (!this->empty()) {
1721 assert(PM->getPassManagerType() > this->top()->getPassManagerType()
1722 && "pushing bad pass manager to PMStack");
1723 PMTopLevelManager *TPM = this->top()->getTopLevelManager();
1724
1725 assert(TPM && "Unable to find top level manager");
1726 TPM->addIndirectPassManager(Manager: PM);
1727 PM->setTopLevelManager(TPM);
1728 PM->setDepth(this->top()->getDepth()+1);
1729 } else {
1730 assert((PM->getPassManagerType() == PMT_ModulePassManager
1731 || PM->getPassManagerType() == PMT_FunctionPassManager)
1732 && "pushing bad pass manager to PMStack");
1733 PM->setDepth(1);
1734 }
1735
1736 S.push_back(x: PM);
1737}
1738
1739// Dump content of the pass manager stack.
1740LLVM_DUMP_METHOD void PMStack::dump() const {
1741 for (PMDataManager *Manager : S)
1742 dbgs() << Manager->getAsPass()->getPassName() << ' ';
1743
1744 if (!S.empty())
1745 dbgs() << '\n';
1746}
1747
1748/// Find appropriate Module Pass Manager in the PM Stack and
1749/// add self into that manager.
1750void ModulePass::assignPassManager(PMStack &PMS,
1751 PassManagerType PreferredType) {
1752 // Find Module Pass Manager
1753 PassManagerType T;
1754 while ((T = PMS.top()->getPassManagerType()) > PMT_ModulePassManager &&
1755 T != PreferredType)
1756 PMS.pop();
1757 PMS.top()->add(P: this);
1758}
1759
1760/// Find appropriate Function Pass Manager or Call Graph Pass Manager
1761/// in the PM Stack and add self into that manager.
1762void FunctionPass::assignPassManager(PMStack &PMS,
1763 PassManagerType /*PreferredType*/) {
1764 // Find Function Pass Manager
1765 PMDataManager *PM;
1766 while (PM = PMS.top(), PM->getPassManagerType() > PMT_FunctionPassManager)
1767 PMS.pop();
1768
1769 // Create new Function Pass Manager if needed.
1770 if (PM->getPassManagerType() != PMT_FunctionPassManager) {
1771 // [1] Create new Function Pass Manager
1772 auto *FPP = new FPPassManager;
1773 FPP->populateInheritedAnalysis(PMS);
1774
1775 // [2] Set up new manager's top level manager
1776 PM->getTopLevelManager()->addIndirectPassManager(Manager: FPP);
1777
1778 // [3] Assign manager to manage this new manager. This may create
1779 // and push new managers into PMS
1780 FPP->assignPassManager(PMS, PreferredType: PM->getPassManagerType());
1781
1782 // [4] Push new manager into PMS
1783 PMS.push(PM: FPP);
1784 PM = FPP;
1785 }
1786
1787 // Assign FPP as the manager of this pass.
1788 PM->add(P: this);
1789}
1790
1791legacy::PassManagerBase::~PassManagerBase() = default;
1792