1 | //===- CGSCCPassManager.h - Call graph pass management ----------*- 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 | /// \file |
9 | /// |
10 | /// This header provides classes for managing passes over SCCs of the call |
11 | /// graph. These passes form an important component of LLVM's interprocedural |
12 | /// optimizations. Because they operate on the SCCs of the call graph, and they |
13 | /// traverse the graph in post-order, they can effectively do pair-wise |
14 | /// interprocedural optimizations for all call edges in the program while |
15 | /// incrementally refining it and improving the context of these pair-wise |
16 | /// optimizations. At each call site edge, the callee has already been |
17 | /// optimized as much as is possible. This in turn allows very accurate |
18 | /// analysis of it for IPO. |
19 | /// |
20 | /// A secondary more general goal is to be able to isolate optimization on |
21 | /// unrelated parts of the IR module. This is useful to ensure our |
22 | /// optimizations are principled and don't miss oportunities where refinement |
23 | /// of one part of the module influences transformations in another part of the |
24 | /// module. But this is also useful if we want to parallelize the optimizations |
25 | /// across common large module graph shapes which tend to be very wide and have |
26 | /// large regions of unrelated cliques. |
27 | /// |
28 | /// To satisfy these goals, we use the LazyCallGraph which provides two graphs |
29 | /// nested inside each other (and built lazily from the bottom-up): the call |
30 | /// graph proper, and a reference graph. The reference graph is super set of |
31 | /// the call graph and is a conservative approximation of what could through |
32 | /// scalar or CGSCC transforms *become* the call graph. Using this allows us to |
33 | /// ensure we optimize functions prior to them being introduced into the call |
34 | /// graph by devirtualization or other technique, and thus ensures that |
35 | /// subsequent pair-wise interprocedural optimizations observe the optimized |
36 | /// form of these functions. The (potentially transitive) reference |
37 | /// reachability used by the reference graph is a conservative approximation |
38 | /// that still allows us to have independent regions of the graph. |
39 | /// |
40 | /// FIXME: There is one major drawback of the reference graph: in its naive |
41 | /// form it is quadratic because it contains a distinct edge for each |
42 | /// (potentially indirect) reference, even if are all through some common |
43 | /// global table of function pointers. This can be fixed in a number of ways |
44 | /// that essentially preserve enough of the normalization. While it isn't |
45 | /// expected to completely preclude the usability of this, it will need to be |
46 | /// addressed. |
47 | /// |
48 | /// |
49 | /// All of these issues are made substantially more complex in the face of |
50 | /// mutations to the call graph while optimization passes are being run. When |
51 | /// mutations to the call graph occur we want to achieve two different things: |
52 | /// |
53 | /// - We need to update the call graph in-flight and invalidate analyses |
54 | /// cached on entities in the graph. Because of the cache-based analysis |
55 | /// design of the pass manager, it is essential to have stable identities for |
56 | /// the elements of the IR that passes traverse, and to invalidate any |
57 | /// analyses cached on these elements as the mutations take place. |
58 | /// |
59 | /// - We want to preserve the incremental and post-order traversal of the |
60 | /// graph even as it is refined and mutated. This means we want optimization |
61 | /// to observe the most refined form of the call graph and to do so in |
62 | /// post-order. |
63 | /// |
64 | /// To address this, the CGSCC manager uses both worklists that can be expanded |
65 | /// by passes which transform the IR, and provides invalidation tests to skip |
66 | /// entries that become dead. This extra data is provided to every SCC pass so |
67 | /// that it can carefully update the manager's traversal as the call graph |
68 | /// mutates. |
69 | /// |
70 | /// We also provide support for running function passes within the CGSCC walk, |
71 | /// and there we provide automatic update of the call graph including of the |
72 | /// pass manager to reflect call graph changes that fall out naturally as part |
73 | /// of scalar transformations. |
74 | /// |
75 | /// The patterns used to ensure the goals of post-order visitation of the fully |
76 | /// refined graph: |
77 | /// |
78 | /// 1) Sink toward the "bottom" as the graph is refined. This means that any |
79 | /// iteration continues in some valid post-order sequence after the mutation |
80 | /// has altered the structure. |
81 | /// |
82 | /// 2) Enqueue in post-order, including the current entity. If the current |
83 | /// entity's shape changes, it and everything after it in post-order needs |
84 | /// to be visited to observe that shape. |
85 | /// |
86 | //===----------------------------------------------------------------------===// |
87 | |
88 | #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H |
89 | #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H |
90 | |
91 | #include "llvm/ADT/MapVector.h" |
92 | #include "llvm/Analysis/LazyCallGraph.h" |
93 | #include "llvm/IR/PassManager.h" |
94 | #include "llvm/IR/ValueHandle.h" |
95 | #include "llvm/Support/raw_ostream.h" |
96 | #include <cassert> |
97 | #include <utility> |
98 | |
99 | namespace llvm { |
100 | |
101 | class Function; |
102 | class Value; |
103 | template <typename T, unsigned int N> class SmallPriorityWorklist; |
104 | struct CGSCCUpdateResult; |
105 | |
106 | class Module; |
107 | |
108 | // Allow debug logging in this inline function. |
109 | #define DEBUG_TYPE "cgscc" |
110 | |
111 | /// Extern template declaration for the analysis set for this IR unit. |
112 | extern template class AllAnalysesOn<LazyCallGraph::SCC>; |
113 | |
114 | extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>; |
115 | |
116 | /// The CGSCC analysis manager. |
117 | /// |
118 | /// See the documentation for the AnalysisManager template for detail |
119 | /// documentation. This type serves as a convenient way to refer to this |
120 | /// construct in the adaptors and proxies used to integrate this into the larger |
121 | /// pass manager infrastructure. |
122 | using CGSCCAnalysisManager = |
123 | AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>; |
124 | |
125 | // Explicit specialization and instantiation declarations for the pass manager. |
126 | // See the comments on the definition of the specialization for details on how |
127 | // it differs from the primary template. |
128 | template <> |
129 | PreservedAnalyses |
130 | PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, |
131 | CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC, |
132 | CGSCCAnalysisManager &AM, |
133 | LazyCallGraph &G, CGSCCUpdateResult &UR); |
134 | extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, |
135 | LazyCallGraph &, CGSCCUpdateResult &>; |
136 | |
137 | /// The CGSCC pass manager. |
138 | /// |
139 | /// See the documentation for the PassManager template for details. It runs |
140 | /// a sequence of SCC passes over each SCC that the manager is run over. This |
141 | /// type serves as a convenient way to refer to this construct. |
142 | using CGSCCPassManager = |
143 | PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, |
144 | CGSCCUpdateResult &>; |
145 | |
146 | /// An explicit specialization of the require analysis template pass. |
147 | template <typename AnalysisT> |
148 | struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager, |
149 | LazyCallGraph &, CGSCCUpdateResult &> |
150 | : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, |
151 | CGSCCAnalysisManager, LazyCallGraph &, |
152 | CGSCCUpdateResult &>> { |
153 | PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, |
154 | LazyCallGraph &CG, CGSCCUpdateResult &) { |
155 | (void)AM.template getResult<AnalysisT>(C, CG); |
156 | return PreservedAnalyses::all(); |
157 | } |
158 | void printPipeline(raw_ostream &OS, |
159 | function_ref<StringRef(StringRef)> MapClassName2PassName) { |
160 | auto ClassName = AnalysisT::name(); |
161 | auto PassName = MapClassName2PassName(ClassName); |
162 | OS << "require<" << PassName << '>'; |
163 | } |
164 | }; |
165 | |
166 | /// A proxy from a \c CGSCCAnalysisManager to a \c Module. |
167 | using CGSCCAnalysisManagerModuleProxy = |
168 | InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>; |
169 | |
170 | /// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so |
171 | /// it can have access to the call graph in order to walk all the SCCs when |
172 | /// invalidating things. |
173 | template <> class CGSCCAnalysisManagerModuleProxy::Result { |
174 | public: |
175 | explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G) |
176 | : InnerAM(&InnerAM), G(&G) {} |
177 | |
178 | /// Accessor for the analysis manager. |
179 | CGSCCAnalysisManager &getManager() { return *InnerAM; } |
180 | |
181 | /// Handler for invalidation of the Module. |
182 | /// |
183 | /// If the proxy analysis itself is preserved, then we assume that the set of |
184 | /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the |
185 | /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear |
186 | /// on the CGSCCAnalysisManager. |
187 | /// |
188 | /// Regardless of whether this analysis is marked as preserved, all of the |
189 | /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based |
190 | /// on the set of preserved analyses. |
191 | bool invalidate(Module &M, const PreservedAnalyses &PA, |
192 | ModuleAnalysisManager::Invalidator &Inv); |
193 | |
194 | private: |
195 | CGSCCAnalysisManager *InnerAM; |
196 | LazyCallGraph *G; |
197 | }; |
198 | |
199 | /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy |
200 | /// so it can pass the lazy call graph to the result. |
201 | template <> |
202 | CGSCCAnalysisManagerModuleProxy::Result |
203 | CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM); |
204 | |
205 | // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern |
206 | // template. |
207 | extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>; |
208 | |
209 | extern template class OuterAnalysisManagerProxy< |
210 | ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>; |
211 | |
212 | /// A proxy from a \c ModuleAnalysisManager to an \c SCC. |
213 | using ModuleAnalysisManagerCGSCCProxy = |
214 | OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC, |
215 | LazyCallGraph &>; |
216 | |
217 | /// Support structure for SCC passes to communicate updates the call graph back |
218 | /// to the CGSCC pass manager infrastructure. |
219 | /// |
220 | /// The CGSCC pass manager runs SCC passes which are allowed to update the call |
221 | /// graph and SCC structures. This means the structure the pass manager works |
222 | /// on is mutating underneath it. In order to support that, there needs to be |
223 | /// careful communication about the precise nature and ramifications of these |
224 | /// updates to the pass management infrastructure. |
225 | /// |
226 | /// All SCC passes will have to accept a reference to the management layer's |
227 | /// update result struct and use it to reflect the results of any CG updates |
228 | /// performed. |
229 | /// |
230 | /// Passes which do not change the call graph structure in any way can just |
231 | /// ignore this argument to their run method. |
232 | struct CGSCCUpdateResult { |
233 | /// Worklist of the RefSCCs queued for processing. |
234 | /// |
235 | /// When a pass refines the graph and creates new RefSCCs or causes them to |
236 | /// have a different shape or set of component SCCs it should add the RefSCCs |
237 | /// to this worklist so that we visit them in the refined form. |
238 | /// |
239 | /// This worklist is in reverse post-order, as we pop off the back in order |
240 | /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add |
241 | /// them in reverse post-order. |
242 | SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist; |
243 | |
244 | /// Worklist of the SCCs queued for processing. |
245 | /// |
246 | /// When a pass refines the graph and creates new SCCs or causes them to have |
247 | /// a different shape or set of component functions it should add the SCCs to |
248 | /// this worklist so that we visit them in the refined form. |
249 | /// |
250 | /// Note that if the SCCs are part of a RefSCC that is added to the \c |
251 | /// RCWorklist, they don't need to be added here as visiting the RefSCC will |
252 | /// be sufficient to re-visit the SCCs within it. |
253 | /// |
254 | /// This worklist is in reverse post-order, as we pop off the back in order |
255 | /// to observe SCCs in post-order. When adding SCCs, clients should add them |
256 | /// in reverse post-order. |
257 | SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist; |
258 | |
259 | /// The set of invalidated RefSCCs which should be skipped if they are found |
260 | /// in \c RCWorklist. |
261 | /// |
262 | /// This is used to quickly prune out RefSCCs when they get deleted and |
263 | /// happen to already be on the worklist. We use this primarily to avoid |
264 | /// scanning the list and removing entries from it. |
265 | SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs; |
266 | |
267 | /// The set of invalidated SCCs which should be skipped if they are found |
268 | /// in \c CWorklist. |
269 | /// |
270 | /// This is used to quickly prune out SCCs when they get deleted and happen |
271 | /// to already be on the worklist. We use this primarily to avoid scanning |
272 | /// the list and removing entries from it. |
273 | SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs; |
274 | |
275 | /// If non-null, the updated current \c SCC being processed. |
276 | /// |
277 | /// This is set when a graph refinement takes place and the "current" point |
278 | /// in the graph moves "down" or earlier in the post-order walk. This will |
279 | /// often cause the "current" SCC to be a newly created SCC object and the |
280 | /// old one to be added to the above worklist. When that happens, this |
281 | /// pointer is non-null and can be used to continue processing the "top" of |
282 | /// the post-order walk. |
283 | LazyCallGraph::SCC *UpdatedC; |
284 | |
285 | /// Preserved analyses across SCCs. |
286 | /// |
287 | /// We specifically want to allow CGSCC passes to mutate ancestor IR |
288 | /// (changing both the CG structure and the function IR itself). However, |
289 | /// this means we need to take special care to correctly mark what analyses |
290 | /// are preserved *across* SCCs. We have to track this out-of-band here |
291 | /// because within the main `PassManager` infrastructure we need to mark |
292 | /// everything within an SCC as preserved in order to avoid repeatedly |
293 | /// invalidating the same analyses as we unnest pass managers and adaptors. |
294 | /// So we track the cross-SCC version of the preserved analyses here from any |
295 | /// code that does direct invalidation of SCC analyses, and then use it |
296 | /// whenever we move forward in the post-order walk of SCCs before running |
297 | /// passes over the new SCC. |
298 | PreservedAnalyses CrossSCCPA; |
299 | |
300 | /// A hacky area where the inliner can retain history about inlining |
301 | /// decisions that mutated the call graph's SCC structure in order to avoid |
302 | /// infinite inlining. See the comments in the inliner's CG update logic. |
303 | /// |
304 | /// FIXME: Keeping this here seems like a big layering issue, we should look |
305 | /// for a better technique. |
306 | SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4> |
307 | &InlinedInternalEdges; |
308 | |
309 | /// Weak VHs to keep track of indirect calls for the purposes of detecting |
310 | /// devirtualization. |
311 | /// |
312 | /// This is a map to avoid having duplicate entries. If a Value is |
313 | /// deallocated, its corresponding WeakTrackingVH will be nulled out. When |
314 | /// checking if a Value is in the map or not, also check if the corresponding |
315 | /// WeakTrackingVH is null to avoid issues with a new Value sharing the same |
316 | /// address as a deallocated one. |
317 | SmallMapVector<Value *, WeakTrackingVH, 16> IndirectVHs; |
318 | }; |
319 | |
320 | /// The core module pass which does a post-order walk of the SCCs and |
321 | /// runs a CGSCC pass over each one. |
322 | /// |
323 | /// Designed to allow composition of a CGSCCPass(Manager) and |
324 | /// a ModulePassManager. Note that this pass must be run with a module analysis |
325 | /// manager as it uses the LazyCallGraph analysis. It will also run the |
326 | /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC |
327 | /// pass over the module to enable a \c FunctionAnalysisManager to be used |
328 | /// within this run safely. |
329 | class ModuleToPostOrderCGSCCPassAdaptor |
330 | : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor> { |
331 | public: |
332 | using PassConceptT = |
333 | detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager, |
334 | LazyCallGraph &, CGSCCUpdateResult &>; |
335 | |
336 | explicit ModuleToPostOrderCGSCCPassAdaptor(std::unique_ptr<PassConceptT> Pass) |
337 | : Pass(std::move(Pass)) {} |
338 | |
339 | ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg) |
340 | : Pass(std::move(Arg.Pass)) {} |
341 | |
342 | friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS, |
343 | ModuleToPostOrderCGSCCPassAdaptor &RHS) { |
344 | std::swap(x&: LHS.Pass, y&: RHS.Pass); |
345 | } |
346 | |
347 | ModuleToPostOrderCGSCCPassAdaptor & |
348 | operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) { |
349 | swap(LHS&: *this, RHS); |
350 | return *this; |
351 | } |
352 | |
353 | /// Runs the CGSCC pass across every SCC in the module. |
354 | PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); |
355 | |
356 | void printPipeline(raw_ostream &OS, |
357 | function_ref<StringRef(StringRef)> MapClassName2PassName) { |
358 | OS << "cgscc(" ; |
359 | Pass->printPipeline(OS, MapClassName2PassName); |
360 | OS << ')'; |
361 | } |
362 | |
363 | static bool isRequired() { return true; } |
364 | |
365 | private: |
366 | std::unique_ptr<PassConceptT> Pass; |
367 | }; |
368 | |
369 | /// A function to deduce a function pass type and wrap it in the |
370 | /// templated adaptor. |
371 | template <typename CGSCCPassT> |
372 | ModuleToPostOrderCGSCCPassAdaptor |
373 | createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT &&Pass) { |
374 | using PassModelT = |
375 | detail::PassModel<LazyCallGraph::SCC, CGSCCPassT, CGSCCAnalysisManager, |
376 | LazyCallGraph &, CGSCCUpdateResult &>; |
377 | // Do not use make_unique, it causes too many template instantiations, |
378 | // causing terrible compile times. |
379 | return ModuleToPostOrderCGSCCPassAdaptor( |
380 | std::unique_ptr<ModuleToPostOrderCGSCCPassAdaptor::PassConceptT>( |
381 | new PassModelT(std::forward<CGSCCPassT>(Pass)))); |
382 | } |
383 | |
384 | /// A proxy from a \c FunctionAnalysisManager to an \c SCC. |
385 | /// |
386 | /// When a module pass runs and triggers invalidation, both the CGSCC and |
387 | /// Function analysis manager proxies on the module get an invalidation event. |
388 | /// We don't want to fully duplicate responsibility for most of the |
389 | /// invalidation logic. Instead, this layer is only responsible for SCC-local |
390 | /// invalidation events. We work with the module's FunctionAnalysisManager to |
391 | /// invalidate function analyses. |
392 | class FunctionAnalysisManagerCGSCCProxy |
393 | : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> { |
394 | public: |
395 | class Result { |
396 | public: |
397 | explicit Result() : FAM(nullptr) {} |
398 | explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {} |
399 | |
400 | void updateFAM(FunctionAnalysisManager &FAM) { this->FAM = &FAM; } |
401 | /// Accessor for the analysis manager. |
402 | FunctionAnalysisManager &getManager() { |
403 | assert(FAM); |
404 | return *FAM; |
405 | } |
406 | |
407 | bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, |
408 | CGSCCAnalysisManager::Invalidator &Inv); |
409 | |
410 | private: |
411 | FunctionAnalysisManager *FAM; |
412 | }; |
413 | |
414 | /// Computes the \c FunctionAnalysisManager and stores it in the result proxy. |
415 | Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &); |
416 | |
417 | private: |
418 | friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>; |
419 | |
420 | static AnalysisKey Key; |
421 | }; |
422 | |
423 | extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>; |
424 | |
425 | /// A proxy from a \c CGSCCAnalysisManager to a \c Function. |
426 | using CGSCCAnalysisManagerFunctionProxy = |
427 | OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>; |
428 | |
429 | /// Helper to update the call graph after running a function pass. |
430 | /// |
431 | /// Function passes can only mutate the call graph in specific ways. This |
432 | /// routine provides a helper that updates the call graph in those ways |
433 | /// including returning whether any changes were made and populating a CG |
434 | /// update result struct for the overall CGSCC walk. |
435 | LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass( |
436 | LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, |
437 | CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, |
438 | FunctionAnalysisManager &FAM); |
439 | |
440 | /// Helper to update the call graph after running a CGSCC pass. |
441 | /// |
442 | /// CGSCC passes can only mutate the call graph in specific ways. This |
443 | /// routine provides a helper that updates the call graph in those ways |
444 | /// including returning whether any changes were made and populating a CG |
445 | /// update result struct for the overall CGSCC walk. |
446 | LazyCallGraph::SCC &updateCGAndAnalysisManagerForCGSCCPass( |
447 | LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, |
448 | CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, |
449 | FunctionAnalysisManager &FAM); |
450 | |
451 | /// Adaptor that maps from a SCC to its functions. |
452 | /// |
453 | /// Designed to allow composition of a FunctionPass(Manager) and |
454 | /// a CGSCCPassManager. Note that if this pass is constructed with a pointer |
455 | /// to a \c CGSCCAnalysisManager it will run the |
456 | /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function |
457 | /// pass over the SCC to enable a \c FunctionAnalysisManager to be used |
458 | /// within this run safely. |
459 | class CGSCCToFunctionPassAdaptor |
460 | : public PassInfoMixin<CGSCCToFunctionPassAdaptor> { |
461 | public: |
462 | using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>; |
463 | |
464 | explicit CGSCCToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass, |
465 | bool EagerlyInvalidate, bool NoRerun) |
466 | : Pass(std::move(Pass)), EagerlyInvalidate(EagerlyInvalidate), |
467 | NoRerun(NoRerun) {} |
468 | |
469 | CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg) |
470 | : Pass(std::move(Arg.Pass)), EagerlyInvalidate(Arg.EagerlyInvalidate), |
471 | NoRerun(Arg.NoRerun) {} |
472 | |
473 | friend void swap(CGSCCToFunctionPassAdaptor &LHS, |
474 | CGSCCToFunctionPassAdaptor &RHS) { |
475 | std::swap(x&: LHS.Pass, y&: RHS.Pass); |
476 | } |
477 | |
478 | CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) { |
479 | swap(LHS&: *this, RHS); |
480 | return *this; |
481 | } |
482 | |
483 | /// Runs the function pass across every function in the module. |
484 | PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, |
485 | LazyCallGraph &CG, CGSCCUpdateResult &UR); |
486 | |
487 | void printPipeline(raw_ostream &OS, |
488 | function_ref<StringRef(StringRef)> MapClassName2PassName) { |
489 | OS << "function" ; |
490 | if (EagerlyInvalidate || NoRerun) { |
491 | OS << "<" ; |
492 | if (EagerlyInvalidate) |
493 | OS << "eager-inv" ; |
494 | if (EagerlyInvalidate && NoRerun) |
495 | OS << ";" ; |
496 | if (NoRerun) |
497 | OS << "no-rerun" ; |
498 | OS << ">" ; |
499 | } |
500 | OS << '('; |
501 | Pass->printPipeline(OS, MapClassName2PassName); |
502 | OS << ')'; |
503 | } |
504 | |
505 | static bool isRequired() { return true; } |
506 | |
507 | private: |
508 | std::unique_ptr<PassConceptT> Pass; |
509 | bool EagerlyInvalidate; |
510 | bool NoRerun; |
511 | }; |
512 | |
513 | /// A function to deduce a function pass type and wrap it in the |
514 | /// templated adaptor. |
515 | template <typename FunctionPassT> |
516 | CGSCCToFunctionPassAdaptor |
517 | createCGSCCToFunctionPassAdaptor(FunctionPassT &&Pass, |
518 | bool EagerlyInvalidate = false, |
519 | bool NoRerun = false) { |
520 | using PassModelT = |
521 | detail::PassModel<Function, FunctionPassT, FunctionAnalysisManager>; |
522 | // Do not use make_unique, it causes too many template instantiations, |
523 | // causing terrible compile times. |
524 | return CGSCCToFunctionPassAdaptor( |
525 | std::unique_ptr<CGSCCToFunctionPassAdaptor::PassConceptT>( |
526 | new PassModelT(std::forward<FunctionPassT>(Pass))), |
527 | EagerlyInvalidate, NoRerun); |
528 | } |
529 | |
530 | // A marker to determine if function passes should be run on a function within a |
531 | // CGSCCToFunctionPassAdaptor. This is used to prevent running an expensive |
532 | // function pass (manager) on a function multiple times if SCC mutations cause a |
533 | // function to be visited multiple times and the function is not modified by |
534 | // other SCC passes. |
535 | class ShouldNotRunFunctionPassesAnalysis |
536 | : public AnalysisInfoMixin<ShouldNotRunFunctionPassesAnalysis> { |
537 | public: |
538 | static AnalysisKey Key; |
539 | struct Result {}; |
540 | |
541 | Result run(Function &F, FunctionAnalysisManager &FAM) { return Result(); } |
542 | }; |
543 | |
544 | /// A helper that repeats an SCC pass each time an indirect call is refined to |
545 | /// a direct call by that pass. |
546 | /// |
547 | /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they |
548 | /// change shape, we may also want to repeat an SCC pass if it simply refines |
549 | /// an indirect call to a direct call, even if doing so does not alter the |
550 | /// shape of the graph. Note that this only pertains to direct calls to |
551 | /// functions where IPO across the SCC may be able to compute more precise |
552 | /// results. For intrinsics, we assume scalar optimizations already can fully |
553 | /// reason about them. |
554 | /// |
555 | /// This repetition has the potential to be very large however, as each one |
556 | /// might refine a single call site. As a consequence, in practice we use an |
557 | /// upper bound on the number of repetitions to limit things. |
558 | class DevirtSCCRepeatedPass : public PassInfoMixin<DevirtSCCRepeatedPass> { |
559 | public: |
560 | using PassConceptT = |
561 | detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager, |
562 | LazyCallGraph &, CGSCCUpdateResult &>; |
563 | |
564 | explicit DevirtSCCRepeatedPass(std::unique_ptr<PassConceptT> Pass, |
565 | int MaxIterations) |
566 | : Pass(std::move(Pass)), MaxIterations(MaxIterations) {} |
567 | |
568 | /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating |
569 | /// whenever an indirect call is refined. |
570 | PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM, |
571 | LazyCallGraph &CG, CGSCCUpdateResult &UR); |
572 | |
573 | void printPipeline(raw_ostream &OS, |
574 | function_ref<StringRef(StringRef)> MapClassName2PassName) { |
575 | OS << "devirt<" << MaxIterations << ">(" ; |
576 | Pass->printPipeline(OS, MapClassName2PassName); |
577 | OS << ')'; |
578 | } |
579 | |
580 | private: |
581 | std::unique_ptr<PassConceptT> Pass; |
582 | int MaxIterations; |
583 | }; |
584 | |
585 | /// A function to deduce a function pass type and wrap it in the |
586 | /// templated adaptor. |
587 | template <typename CGSCCPassT> |
588 | DevirtSCCRepeatedPass createDevirtSCCRepeatedPass(CGSCCPassT &&Pass, |
589 | int MaxIterations) { |
590 | using PassModelT = |
591 | detail::PassModel<LazyCallGraph::SCC, CGSCCPassT, CGSCCAnalysisManager, |
592 | LazyCallGraph &, CGSCCUpdateResult &>; |
593 | // Do not use make_unique, it causes too many template instantiations, |
594 | // causing terrible compile times. |
595 | return DevirtSCCRepeatedPass( |
596 | std::unique_ptr<DevirtSCCRepeatedPass::PassConceptT>( |
597 | new PassModelT(std::forward<CGSCCPassT>(Pass))), |
598 | MaxIterations); |
599 | } |
600 | |
601 | // Clear out the debug logging macro. |
602 | #undef DEBUG_TYPE |
603 | |
604 | } // end namespace llvm |
605 | |
606 | #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H |
607 | |