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

source code of llvm/lib/IR/LegacyPassManager.cpp