1 | //===- LegacyPassManagers.h - Legacy Pass Infrastructure --------*- C++ -*-===// |
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 declares the LLVM Pass Manager infrastructure. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_IR_LEGACYPASSMANAGERS_H |
14 | #define LLVM_IR_LEGACYPASSMANAGERS_H |
15 | |
16 | #include "llvm/ADT/DenseMap.h" |
17 | #include "llvm/ADT/FoldingSet.h" |
18 | #include "llvm/ADT/SmallPtrSet.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/Pass.h" |
21 | #include <vector> |
22 | |
23 | //===----------------------------------------------------------------------===// |
24 | // Overview: |
25 | // The Pass Manager Infrastructure manages passes. It's responsibilities are: |
26 | // |
27 | // o Manage optimization pass execution order |
28 | // o Make required Analysis information available before pass P is run |
29 | // o Release memory occupied by dead passes |
30 | // o If Analysis information is dirtied by a pass then regenerate Analysis |
31 | // information before it is consumed by another pass. |
32 | // |
33 | // Pass Manager Infrastructure uses multiple pass managers. They are |
34 | // PassManager, FunctionPassManager, MPPassManager, FPPassManager, BBPassManager. |
35 | // This class hierarchy uses multiple inheritance but pass managers do not |
36 | // derive from another pass manager. |
37 | // |
38 | // PassManager and FunctionPassManager are two top-level pass manager that |
39 | // represents the external interface of this entire pass manager infrastucture. |
40 | // |
41 | // Important classes : |
42 | // |
43 | // [o] class PMTopLevelManager; |
44 | // |
45 | // Two top level managers, PassManager and FunctionPassManager, derive from |
46 | // PMTopLevelManager. PMTopLevelManager manages information used by top level |
47 | // managers such as last user info. |
48 | // |
49 | // [o] class PMDataManager; |
50 | // |
51 | // PMDataManager manages information, e.g. list of available analysis info, |
52 | // used by a pass manager to manage execution order of passes. It also provides |
53 | // a place to implement common pass manager APIs. All pass managers derive from |
54 | // PMDataManager. |
55 | // |
56 | // [o] class FunctionPassManager; |
57 | // |
58 | // This is a external interface used to manage FunctionPasses. This |
59 | // interface relies on FunctionPassManagerImpl to do all the tasks. |
60 | // |
61 | // [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager, |
62 | // public PMTopLevelManager; |
63 | // |
64 | // FunctionPassManagerImpl is a top level manager. It manages FPPassManagers |
65 | // |
66 | // [o] class FPPassManager : public ModulePass, public PMDataManager; |
67 | // |
68 | // FPPassManager manages FunctionPasses and BBPassManagers |
69 | // |
70 | // [o] class MPPassManager : public Pass, public PMDataManager; |
71 | // |
72 | // MPPassManager manages ModulePasses and FPPassManagers |
73 | // |
74 | // [o] class PassManager; |
75 | // |
76 | // This is a external interface used by various tools to manages passes. It |
77 | // relies on PassManagerImpl to do all the tasks. |
78 | // |
79 | // [o] class PassManagerImpl : public Pass, public PMDataManager, |
80 | // public PMTopLevelManager |
81 | // |
82 | // PassManagerImpl is a top level pass manager responsible for managing |
83 | // MPPassManagers. |
84 | //===----------------------------------------------------------------------===// |
85 | |
86 | #include "llvm/Support/PrettyStackTrace.h" |
87 | |
88 | namespace llvm { |
89 | template <typename T> class ArrayRef; |
90 | class Module; |
91 | class StringRef; |
92 | class Value; |
93 | class PMDataManager; |
94 | |
95 | // enums for debugging strings |
96 | enum PassDebuggingString { |
97 | EXECUTION_MSG, // "Executing Pass '" + PassName |
98 | MODIFICATION_MSG, // "Made Modification '" + PassName |
99 | FREEING_MSG, // " Freeing Pass '" + PassName |
100 | ON_FUNCTION_MSG, // "' on Function '" + FunctionName + "'...\n" |
101 | ON_MODULE_MSG, // "' on Module '" + ModuleName + "'...\n" |
102 | ON_REGION_MSG, // "' on Region '" + Msg + "'...\n'" |
103 | ON_LOOP_MSG, // "' on Loop '" + Msg + "'...\n'" |
104 | ON_CG_MSG // "' on Call Graph Nodes '" + Msg + "'...\n'" |
105 | }; |
106 | |
107 | /// PassManagerPrettyStackEntry - This is used to print informative information |
108 | /// about what pass is running when/if a stack trace is generated. |
109 | class PassManagerPrettyStackEntry : public PrettyStackTraceEntry { |
110 | Pass *P; |
111 | Value *V; |
112 | Module *M; |
113 | |
114 | public: |
115 | explicit PassManagerPrettyStackEntry(Pass *p) |
116 | : P(p), V(nullptr), M(nullptr) {} // When P is releaseMemory'd. |
117 | PassManagerPrettyStackEntry(Pass *p, Value &v) |
118 | : P(p), V(&v), M(nullptr) {} // When P is run on V |
119 | PassManagerPrettyStackEntry(Pass *p, Module &m) |
120 | : P(p), V(nullptr), M(&m) {} // When P is run on M |
121 | |
122 | /// print - Emit information about this stack frame to OS. |
123 | void print(raw_ostream &OS) const override; |
124 | }; |
125 | |
126 | //===----------------------------------------------------------------------===// |
127 | // PMStack |
128 | // |
129 | /// PMStack - This class implements a stack data structure of PMDataManager |
130 | /// pointers. |
131 | /// |
132 | /// Top level pass managers (see PassManager.cpp) maintain active Pass Managers |
133 | /// using PMStack. Each Pass implements assignPassManager() to connect itself |
134 | /// with appropriate manager. assignPassManager() walks PMStack to find |
135 | /// suitable manager. |
136 | class PMStack { |
137 | public: |
138 | typedef std::vector<PMDataManager *>::const_reverse_iterator iterator; |
139 | iterator begin() const { return S.rbegin(); } |
140 | iterator end() const { return S.rend(); } |
141 | |
142 | void pop(); |
143 | PMDataManager *top() const { return S.back(); } |
144 | void push(PMDataManager *PM); |
145 | bool empty() const { return S.empty(); } |
146 | |
147 | void dump() const; |
148 | |
149 | private: |
150 | std::vector<PMDataManager *> S; |
151 | }; |
152 | |
153 | //===----------------------------------------------------------------------===// |
154 | // PMTopLevelManager |
155 | // |
156 | /// PMTopLevelManager manages LastUser info and collects common APIs used by |
157 | /// top level pass managers. |
158 | class PMTopLevelManager { |
159 | protected: |
160 | explicit PMTopLevelManager(PMDataManager *PMDM); |
161 | |
162 | unsigned getNumContainedManagers() const { |
163 | return (unsigned)PassManagers.size(); |
164 | } |
165 | |
166 | void initializeAllAnalysisInfo(); |
167 | |
168 | private: |
169 | virtual PMDataManager *getAsPMDataManager() = 0; |
170 | virtual PassManagerType getTopLevelPassManagerType() = 0; |
171 | |
172 | public: |
173 | /// Schedule pass P for execution. Make sure that passes required by |
174 | /// P are run before P is run. Update analysis info maintained by |
175 | /// the manager. Remove dead passes. This is a recursive function. |
176 | void schedulePass(Pass *P); |
177 | |
178 | /// Set pass P as the last user of the given analysis passes. |
179 | void setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P); |
180 | |
181 | /// Collect passes whose last user is P |
182 | void collectLastUses(SmallVectorImpl<Pass *> &LastUses, Pass *P); |
183 | |
184 | /// Find the pass that implements Analysis AID. Search immutable |
185 | /// passes and all pass managers. If desired pass is not found |
186 | /// then return NULL. |
187 | Pass *findAnalysisPass(AnalysisID AID); |
188 | |
189 | /// Retrieve the PassInfo for an analysis. |
190 | const PassInfo *findAnalysisPassInfo(AnalysisID AID) const; |
191 | |
192 | /// Find analysis usage information for the pass P. |
193 | AnalysisUsage *findAnalysisUsage(Pass *P); |
194 | |
195 | virtual ~PMTopLevelManager(); |
196 | |
197 | /// Add immutable pass and initialize it. |
198 | void addImmutablePass(ImmutablePass *P); |
199 | |
200 | inline SmallVectorImpl<ImmutablePass *>& getImmutablePasses() { |
201 | return ImmutablePasses; |
202 | } |
203 | |
204 | void addPassManager(PMDataManager *Manager) { |
205 | PassManagers.push_back(Elt: Manager); |
206 | } |
207 | |
208 | // Add Manager into the list of managers that are not directly |
209 | // maintained by this top level pass manager |
210 | inline void addIndirectPassManager(PMDataManager *Manager) { |
211 | IndirectPassManagers.push_back(Elt: Manager); |
212 | } |
213 | |
214 | // Print passes managed by this top level manager. |
215 | void dumpPasses() const; |
216 | void dumpArguments() const; |
217 | |
218 | // Active Pass Managers |
219 | PMStack activeStack; |
220 | |
221 | protected: |
222 | /// Collection of pass managers |
223 | SmallVector<PMDataManager *, 8> PassManagers; |
224 | |
225 | private: |
226 | /// Collection of pass managers that are not directly maintained |
227 | /// by this pass manager |
228 | SmallVector<PMDataManager *, 8> IndirectPassManagers; |
229 | |
230 | // Map to keep track of last user of the analysis pass. |
231 | // LastUser->second is the last user of Lastuser->first. |
232 | // This is kept in sync with InversedLastUser. |
233 | DenseMap<Pass *, Pass *> LastUser; |
234 | |
235 | // Map to keep track of passes that are last used by a pass. |
236 | // This is kept in sync with LastUser. |
237 | DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser; |
238 | |
239 | /// Immutable passes are managed by top level manager. |
240 | SmallVector<ImmutablePass *, 16> ImmutablePasses; |
241 | |
242 | /// Map from ID to immutable passes. |
243 | SmallDenseMap<AnalysisID, ImmutablePass *, 8> ImmutablePassMap; |
244 | |
245 | |
246 | /// A wrapper around AnalysisUsage for the purpose of uniqueing. The wrapper |
247 | /// is used to avoid needing to make AnalysisUsage itself a folding set node. |
248 | struct AUFoldingSetNode : public FoldingSetNode { |
249 | AnalysisUsage AU; |
250 | AUFoldingSetNode(const AnalysisUsage &AU) : AU(AU) {} |
251 | void Profile(FoldingSetNodeID &ID) const { |
252 | Profile(ID, AU); |
253 | } |
254 | static void Profile(FoldingSetNodeID &ID, const AnalysisUsage &AU) { |
255 | // TODO: We could consider sorting the dependency arrays within the |
256 | // AnalysisUsage (since they are conceptually unordered). |
257 | ID.AddBoolean(B: AU.getPreservesAll()); |
258 | auto ProfileVec = [&](const SmallVectorImpl<AnalysisID>& Vec) { |
259 | ID.AddInteger(I: Vec.size()); |
260 | for(AnalysisID AID : Vec) |
261 | ID.AddPointer(Ptr: AID); |
262 | }; |
263 | ProfileVec(AU.getRequiredSet()); |
264 | ProfileVec(AU.getRequiredTransitiveSet()); |
265 | ProfileVec(AU.getPreservedSet()); |
266 | ProfileVec(AU.getUsedSet()); |
267 | } |
268 | }; |
269 | |
270 | // Contains all of the unique combinations of AnalysisUsage. This is helpful |
271 | // when we have multiple instances of the same pass since they'll usually |
272 | // have the same analysis usage and can share storage. |
273 | FoldingSet<AUFoldingSetNode> UniqueAnalysisUsages; |
274 | |
275 | // Allocator used for allocating UAFoldingSetNodes. This handles deletion of |
276 | // all allocated nodes in one fell swoop. |
277 | SpecificBumpPtrAllocator<AUFoldingSetNode> AUFoldingSetNodeAllocator; |
278 | |
279 | // Maps from a pass to it's associated entry in UniqueAnalysisUsages. Does |
280 | // not own the storage associated with either key or value.. |
281 | DenseMap<Pass *, AnalysisUsage*> AnUsageMap; |
282 | |
283 | /// Collection of PassInfo objects found via analysis IDs and in this top |
284 | /// level manager. This is used to memoize queries to the pass registry. |
285 | /// FIXME: This is an egregious hack because querying the pass registry is |
286 | /// either slow or racy. |
287 | mutable DenseMap<AnalysisID, const PassInfo *> AnalysisPassInfos; |
288 | }; |
289 | |
290 | //===----------------------------------------------------------------------===// |
291 | // PMDataManager |
292 | |
293 | /// PMDataManager provides the common place to manage the analysis data |
294 | /// used by pass managers. |
295 | class PMDataManager { |
296 | public: |
297 | explicit PMDataManager() { initializeAnalysisInfo(); } |
298 | |
299 | virtual ~PMDataManager(); |
300 | |
301 | virtual Pass *getAsPass() = 0; |
302 | |
303 | /// Augment AvailableAnalysis by adding analysis made available by pass P. |
304 | void recordAvailableAnalysis(Pass *P); |
305 | |
306 | /// verifyPreservedAnalysis -- Verify analysis presreved by pass P. |
307 | void verifyPreservedAnalysis(Pass *P); |
308 | |
309 | /// Remove Analysis that is not preserved by the pass |
310 | void removeNotPreservedAnalysis(Pass *P); |
311 | |
312 | /// Remove dead passes used by P. |
313 | void removeDeadPasses(Pass *P, StringRef Msg, |
314 | enum PassDebuggingString); |
315 | |
316 | /// Remove P. |
317 | void freePass(Pass *P, StringRef Msg, |
318 | enum PassDebuggingString); |
319 | |
320 | /// Add pass P into the PassVector. Update |
321 | /// AvailableAnalysis appropriately if ProcessAnalysis is true. |
322 | void add(Pass *P, bool ProcessAnalysis = true); |
323 | |
324 | /// Add RequiredPass into list of lower level passes required by pass P. |
325 | /// RequiredPass is run on the fly by Pass Manager when P requests it |
326 | /// through getAnalysis interface. |
327 | virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass); |
328 | |
329 | virtual std::tuple<Pass *, bool> getOnTheFlyPass(Pass *P, AnalysisID PI, |
330 | Function &F); |
331 | |
332 | /// Initialize available analysis information. |
333 | void initializeAnalysisInfo() { |
334 | AvailableAnalysis.clear(); |
335 | for (auto &IA : InheritedAnalysis) |
336 | IA = nullptr; |
337 | } |
338 | |
339 | // Return true if P preserves high level analysis used by other |
340 | // passes that are managed by this manager. |
341 | bool preserveHigherLevelAnalysis(Pass *P); |
342 | |
343 | /// Populate UsedPasses with analysis pass that are used or required by pass |
344 | /// P and are available. Populate ReqPassNotAvailable with analysis pass that |
345 | /// are required by pass P but are not available. |
346 | void collectRequiredAndUsedAnalyses( |
347 | SmallVectorImpl<Pass *> &UsedPasses, |
348 | SmallVectorImpl<AnalysisID> &ReqPassNotAvailable, Pass *P); |
349 | |
350 | /// All Required analyses should be available to the pass as it runs! Here |
351 | /// we fill in the AnalysisImpls member of the pass so that it can |
352 | /// successfully use the getAnalysis() method to retrieve the |
353 | /// implementations it needs. |
354 | void initializeAnalysisImpl(Pass *P); |
355 | |
356 | /// Find the pass that implements Analysis AID. If desired pass is not found |
357 | /// then return NULL. |
358 | Pass *findAnalysisPass(AnalysisID AID, bool Direction); |
359 | |
360 | // Access toplevel manager |
361 | PMTopLevelManager *getTopLevelManager() { return TPM; } |
362 | void setTopLevelManager(PMTopLevelManager *T) { TPM = T; } |
363 | |
364 | unsigned getDepth() const { return Depth; } |
365 | void setDepth(unsigned newDepth) { Depth = newDepth; } |
366 | |
367 | // Print routines used by debug-pass |
368 | void dumpLastUses(Pass *P, unsigned Offset) const; |
369 | void dumpPassArguments() const; |
370 | void dumpPassInfo(Pass *P, enum PassDebuggingString S1, |
371 | enum PassDebuggingString S2, StringRef Msg); |
372 | void dumpRequiredSet(const Pass *P) const; |
373 | void dumpPreservedSet(const Pass *P) const; |
374 | void dumpUsedSet(const Pass *P) const; |
375 | |
376 | unsigned getNumContainedPasses() const { |
377 | return (unsigned)PassVector.size(); |
378 | } |
379 | |
380 | virtual PassManagerType getPassManagerType() const { |
381 | assert ( 0 && "Invalid use of getPassManagerType" ); |
382 | return PMT_Unknown; |
383 | } |
384 | |
385 | DenseMap<AnalysisID, Pass*> *getAvailableAnalysis() { |
386 | return &AvailableAnalysis; |
387 | } |
388 | |
389 | // Collect AvailableAnalysis from all the active Pass Managers. |
390 | void populateInheritedAnalysis(PMStack &PMS) { |
391 | unsigned Index = 0; |
392 | for (PMDataManager *PMDM : PMS) |
393 | InheritedAnalysis[Index++] = PMDM->getAvailableAnalysis(); |
394 | } |
395 | |
396 | /// Set the initial size of the module if the user has specified that they |
397 | /// want remarks for size. |
398 | /// Returns 0 if the remark was not requested. |
399 | unsigned ( |
400 | Module &M, |
401 | StringMap<std::pair<unsigned, unsigned>> &FunctionToInstrCount); |
402 | |
403 | /// Emit a remark signifying that the number of IR instructions in the module |
404 | /// changed. |
405 | /// \p F is optionally passed by passes which run on Functions, and thus |
406 | /// always know whether or not a non-empty function is available. |
407 | /// |
408 | /// \p FunctionToInstrCount maps the name of a \p Function to a pair. The |
409 | /// first member of the pair is the IR count of the \p Function before running |
410 | /// \p P, and the second member is the IR count of the \p Function after |
411 | /// running \p P. |
412 | void ( |
413 | Pass *P, Module &M, int64_t Delta, unsigned CountBefore, |
414 | StringMap<std::pair<unsigned, unsigned>> &FunctionToInstrCount, |
415 | Function *F = nullptr); |
416 | |
417 | protected: |
418 | // Top level manager. |
419 | PMTopLevelManager *TPM = nullptr; |
420 | |
421 | // Collection of pass that are managed by this manager |
422 | SmallVector<Pass *, 16> PassVector; |
423 | |
424 | // Collection of Analysis provided by Parent pass manager and |
425 | // used by current pass manager. At any time there can not be more |
426 | // then PMT_Last active pass managers. |
427 | DenseMap<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last]; |
428 | |
429 | /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions |
430 | /// or higher is specified. |
431 | bool isPassDebuggingExecutionsOrMore() const; |
432 | |
433 | private: |
434 | void dumpAnalysisUsage(StringRef Msg, const Pass *P, |
435 | const AnalysisUsage::VectorType &Set) const; |
436 | |
437 | // Set of available Analysis. This information is used while scheduling |
438 | // pass. If a pass requires an analysis which is not available then |
439 | // the required analysis pass is scheduled to run before the pass itself is |
440 | // scheduled to run. |
441 | DenseMap<AnalysisID, Pass*> AvailableAnalysis; |
442 | |
443 | // Collection of higher level analysis used by the pass managed by |
444 | // this manager. |
445 | SmallVector<Pass *, 16> HigherLevelAnalysis; |
446 | |
447 | unsigned Depth = 0; |
448 | }; |
449 | |
450 | //===----------------------------------------------------------------------===// |
451 | // FPPassManager |
452 | // |
453 | /// FPPassManager manages BBPassManagers and FunctionPasses. |
454 | /// It batches all function passes and basic block pass managers together and |
455 | /// sequence them to process one function at a time before processing next |
456 | /// function. |
457 | class FPPassManager : public ModulePass, public PMDataManager { |
458 | public: |
459 | static char ID; |
460 | explicit FPPassManager() : ModulePass(ID) {} |
461 | |
462 | /// run - Execute all of the passes scheduled for execution. Keep track of |
463 | /// whether any of the passes modifies the module, and if so, return true. |
464 | bool runOnFunction(Function &F); |
465 | bool runOnModule(Module &M) override; |
466 | |
467 | /// cleanup - After running all passes, clean up pass manager cache. |
468 | void cleanup(); |
469 | |
470 | /// doInitialization - Overrides ModulePass doInitialization for global |
471 | /// initialization tasks |
472 | /// |
473 | using ModulePass::doInitialization; |
474 | |
475 | /// doInitialization - Run all of the initializers for the function passes. |
476 | /// |
477 | bool doInitialization(Module &M) override; |
478 | |
479 | /// doFinalization - Overrides ModulePass doFinalization for global |
480 | /// finalization tasks |
481 | /// |
482 | using ModulePass::doFinalization; |
483 | |
484 | /// doFinalization - Run all of the finalizers for the function passes. |
485 | /// |
486 | bool doFinalization(Module &M) override; |
487 | |
488 | PMDataManager *getAsPMDataManager() override { return this; } |
489 | Pass *getAsPass() override { return this; } |
490 | |
491 | /// Pass Manager itself does not invalidate any analysis info. |
492 | void getAnalysisUsage(AnalysisUsage &Info) const override { |
493 | Info.setPreservesAll(); |
494 | } |
495 | |
496 | // Print passes managed by this manager |
497 | void dumpPassStructure(unsigned Offset) override; |
498 | |
499 | StringRef getPassName() const override { return "Function Pass Manager" ; } |
500 | |
501 | FunctionPass *getContainedPass(unsigned N) { |
502 | assert ( N < PassVector.size() && "Pass number out of range!" ); |
503 | FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]); |
504 | return FP; |
505 | } |
506 | |
507 | PassManagerType getPassManagerType() const override { |
508 | return PMT_FunctionPassManager; |
509 | } |
510 | }; |
511 | |
512 | } |
513 | |
514 | #endif |
515 | |