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