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
99namespace llvm {
100
101class Function;
102class Value;
103template <typename T, unsigned int N> class SmallPriorityWorklist;
104struct CGSCCUpdateResult;
105
106class 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.
112extern template class AllAnalysesOn<LazyCallGraph::SCC>;
113
114extern 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.
122using 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.
128template <>
129PreservedAnalyses
130PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
131 CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
132 CGSCCAnalysisManager &AM,
133 LazyCallGraph &G, CGSCCUpdateResult &UR);
134extern 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.
142using CGSCCPassManager =
143 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
144 CGSCCUpdateResult &>;
145
146/// An explicit specialization of the require analysis template pass.
147template <typename AnalysisT>
148struct 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.
167using 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.
173template <> class CGSCCAnalysisManagerModuleProxy::Result {
174public:
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
194private:
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.
201template <>
202CGSCCAnalysisManagerModuleProxy::Result
203CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);
204
205// Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
206// template.
207extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
208
209extern template class OuterAnalysisManagerProxy<
210 ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
211
212/// A proxy from a \c ModuleAnalysisManager to an \c SCC.
213using 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.
232struct 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.
329class ModuleToPostOrderCGSCCPassAdaptor
330 : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor> {
331public:
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(LHS.Pass, RHS.Pass);
345 }
346
347 ModuleToPostOrderCGSCCPassAdaptor &
348 operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
349 swap(*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
365private:
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.
371template <typename CGSCCPassT>
372ModuleToPostOrderCGSCCPassAdaptor
373createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT &&Pass) {
374 using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
375 PreservedAnalyses, 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.
392class FunctionAnalysisManagerCGSCCProxy
393 : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
394public:
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
417private:
418 friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
419
420 static AnalysisKey Key;
421};
422
423extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
424
425/// A proxy from a \c CGSCCAnalysisManager to a \c Function.
426using 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.
435LazyCallGraph::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.
446LazyCallGraph::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.
459class CGSCCToFunctionPassAdaptor
460 : public PassInfoMixin<CGSCCToFunctionPassAdaptor> {
461public:
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(LHS.Pass, RHS.Pass);
476 }
477
478 CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
479 swap(*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)
491 OS << "<eager-inv>";
492 OS << "(";
493 Pass->printPipeline(OS, MapClassName2PassName);
494 OS << ")";
495 }
496
497 static bool isRequired() { return true; }
498
499private:
500 std::unique_ptr<PassConceptT> Pass;
501 bool EagerlyInvalidate;
502 bool NoRerun;
503};
504
505/// A function to deduce a function pass type and wrap it in the
506/// templated adaptor.
507template <typename FunctionPassT>
508CGSCCToFunctionPassAdaptor
509createCGSCCToFunctionPassAdaptor(FunctionPassT &&Pass,
510 bool EagerlyInvalidate = false,
511 bool NoRerun = false) {
512 using PassModelT =
513 detail::PassModel<Function, FunctionPassT, PreservedAnalyses,
514 FunctionAnalysisManager>;
515 // Do not use make_unique, it causes too many template instantiations,
516 // causing terrible compile times.
517 return CGSCCToFunctionPassAdaptor(
518 std::unique_ptr<CGSCCToFunctionPassAdaptor::PassConceptT>(
519 new PassModelT(std::forward<FunctionPassT>(Pass))),
520 EagerlyInvalidate, NoRerun);
521}
522
523// A marker to determine if function passes should be run on a function within a
524// CGSCCToFunctionPassAdaptor. This is used to prevent running an expensive
525// function pass (manager) on a function multiple times if SCC mutations cause a
526// function to be visited multiple times and the function is not modified by
527// other SCC passes.
528class ShouldNotRunFunctionPassesAnalysis
529 : public AnalysisInfoMixin<ShouldNotRunFunctionPassesAnalysis> {
530public:
531 static AnalysisKey Key;
532 struct Result {};
533
534 Result run(Function &F, FunctionAnalysisManager &FAM) { return Result(); }
535};
536
537/// A helper that repeats an SCC pass each time an indirect call is refined to
538/// a direct call by that pass.
539///
540/// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
541/// change shape, we may also want to repeat an SCC pass if it simply refines
542/// an indirect call to a direct call, even if doing so does not alter the
543/// shape of the graph. Note that this only pertains to direct calls to
544/// functions where IPO across the SCC may be able to compute more precise
545/// results. For intrinsics, we assume scalar optimizations already can fully
546/// reason about them.
547///
548/// This repetition has the potential to be very large however, as each one
549/// might refine a single call site. As a consequence, in practice we use an
550/// upper bound on the number of repetitions to limit things.
551class DevirtSCCRepeatedPass : public PassInfoMixin<DevirtSCCRepeatedPass> {
552public:
553 using PassConceptT =
554 detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager,
555 LazyCallGraph &, CGSCCUpdateResult &>;
556
557 explicit DevirtSCCRepeatedPass(std::unique_ptr<PassConceptT> Pass,
558 int MaxIterations)
559 : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
560
561 /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
562 /// whenever an indirect call is refined.
563 PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
564 LazyCallGraph &CG, CGSCCUpdateResult &UR);
565
566 void printPipeline(raw_ostream &OS,
567 function_ref<StringRef(StringRef)> MapClassName2PassName) {
568 OS << "devirt<" << MaxIterations << ">(";
569 Pass->printPipeline(OS, MapClassName2PassName);
570 OS << ")";
571 }
572
573private:
574 std::unique_ptr<PassConceptT> Pass;
575 int MaxIterations;
576};
577
578/// A function to deduce a function pass type and wrap it in the
579/// templated adaptor.
580template <typename CGSCCPassT>
581DevirtSCCRepeatedPass createDevirtSCCRepeatedPass(CGSCCPassT &&Pass,
582 int MaxIterations) {
583 using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT,
584 PreservedAnalyses, CGSCCAnalysisManager,
585 LazyCallGraph &, CGSCCUpdateResult &>;
586 // Do not use make_unique, it causes too many template instantiations,
587 // causing terrible compile times.
588 return DevirtSCCRepeatedPass(
589 std::unique_ptr<DevirtSCCRepeatedPass::PassConceptT>(
590 new PassModelT(std::forward<CGSCCPassT>(Pass))),
591 MaxIterations);
592}
593
594// Clear out the debug logging macro.
595#undef DEBUG_TYPE
596
597} // end namespace llvm
598
599#endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H
600

source code of llvm/include/llvm/Analysis/CGSCCPassManager.h