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