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