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