1 //===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This header provides classes for managing passes over SCCs of the call
12 /// graph. These passes form an important component of LLVM's interprocedural
13 /// optimizations. Because they operate on the SCCs of the call graph, and they
14 /// wtraverse the graph in post order, they can effectively do pair-wise
15 /// interprocedural optimizations for all call edges in the program. At each
16 /// call site edge, the callee has already been optimized as much as is
17 /// possible. This in turn allows very accurate analysis of it for IPO.
19 //===----------------------------------------------------------------------===//
21 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
22 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/Analysis/LazyCallGraph.h"
29 class CGSCCAnalysisManager;
31 class CGSCCPassManager {
33 // We have to explicitly define all the special member functions because MSVC
34 // refuses to generate them.
36 CGSCCPassManager(CGSCCPassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
37 CGSCCPassManager &operator=(CGSCCPassManager &&RHS) {
38 Passes = std::move(RHS.Passes);
42 /// \brief Run all of the CGSCC passes in this pass manager over a SCC.
43 PreservedAnalyses run(LazyCallGraph::SCC &C,
44 CGSCCAnalysisManager *AM = nullptr);
46 template <typename CGSCCPassT> void addPass(CGSCCPassT Pass) {
47 Passes.emplace_back(new CGSCCPassModel<CGSCCPassT>(std::move(Pass)));
50 static StringRef name() { return "CGSCCPassManager"; }
53 // Pull in the concept type and model template specialized for SCCs.
54 typedef detail::PassConcept<LazyCallGraph::SCC &, CGSCCAnalysisManager>
56 template <typename PassT>
58 : detail::PassModel<LazyCallGraph::SCC &, CGSCCAnalysisManager, PassT> {
59 CGSCCPassModel(PassT Pass)
60 : detail::PassModel<LazyCallGraph::SCC &, CGSCCAnalysisManager, PassT>(
64 CGSCCPassManager(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
65 CGSCCPassManager &operator=(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
67 std::vector<std::unique_ptr<CGSCCPassConcept>> Passes;
70 /// \brief A function analysis manager to coordinate and cache analyses run over
72 class CGSCCAnalysisManager : public detail::AnalysisManagerBase<
73 CGSCCAnalysisManager, LazyCallGraph::SCC &> {
74 friend class detail::AnalysisManagerBase<CGSCCAnalysisManager,
75 LazyCallGraph::SCC &>;
76 typedef detail::AnalysisManagerBase<CGSCCAnalysisManager,
77 LazyCallGraph::SCC &> BaseT;
78 typedef BaseT::ResultConceptT ResultConceptT;
79 typedef BaseT::PassConceptT PassConceptT;
82 // Most public APIs are inherited from the CRTP base class.
84 // We have to explicitly define all the special member functions because MSVC
85 // refuses to generate them.
86 CGSCCAnalysisManager() {}
87 CGSCCAnalysisManager(CGSCCAnalysisManager &&Arg)
88 : BaseT(std::move(static_cast<BaseT &>(Arg))),
89 CGSCCAnalysisResults(std::move(Arg.CGSCCAnalysisResults)) {}
90 CGSCCAnalysisManager &operator=(CGSCCAnalysisManager &&RHS) {
91 BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
92 CGSCCAnalysisResults = std::move(RHS.CGSCCAnalysisResults);
96 /// \brief Returns true if the analysis manager has an empty results cache.
99 /// \brief Clear the function analysis result cache.
101 /// This routine allows cleaning up when the set of functions itself has
102 /// potentially changed, and thus we can't even look up a a result and
103 /// invalidate it directly. Notably, this does *not* call invalidate
104 /// functions as there is nothing to be done for them.
108 CGSCCAnalysisManager(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION;
109 CGSCCAnalysisManager &
110 operator=(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION;
112 /// \brief Get a function pass result, running the pass if necessary.
113 ResultConceptT &getResultImpl(void *PassID, LazyCallGraph::SCC &C);
115 /// \brief Get a cached function pass result or return null.
116 ResultConceptT *getCachedResultImpl(void *PassID,
117 LazyCallGraph::SCC &C) const;
119 /// \brief Invalidate a function pass result.
120 void invalidateImpl(void *PassID, LazyCallGraph::SCC &C);
122 /// \brief Invalidate the results for a function..
123 PreservedAnalyses invalidateImpl(LazyCallGraph::SCC &C, PreservedAnalyses PA);
125 /// \brief List of function analysis pass IDs and associated concept pointers.
127 /// Requires iterators to be valid across appending new entries and arbitrary
128 /// erases. Provides both the pass ID and concept pointer such that it is
129 /// half of a bijection and provides storage for the actual result concept.
131 std::pair<void *, std::unique_ptr<detail::AnalysisResultConcept<
132 LazyCallGraph::SCC &>>>> CGSCCAnalysisResultListT;
134 /// \brief Map type from function pointer to our custom list type.
135 typedef DenseMap<LazyCallGraph::SCC *, CGSCCAnalysisResultListT>
136 CGSCCAnalysisResultListMapT;
138 /// \brief Map from function to a list of function analysis results.
140 /// Provides linear time removal of all analysis results for a function and
141 /// the ultimate storage for a particular cached analysis result.
142 CGSCCAnalysisResultListMapT CGSCCAnalysisResultLists;
144 /// \brief Map type from a pair of analysis ID and function pointer to an
145 /// iterator into a particular result list.
146 typedef DenseMap<std::pair<void *, LazyCallGraph::SCC *>,
147 CGSCCAnalysisResultListT::iterator> CGSCCAnalysisResultMapT;
149 /// \brief Map from an analysis ID and function to a particular cached
151 CGSCCAnalysisResultMapT CGSCCAnalysisResults;
154 /// \brief A module analysis which acts as a proxy for a CGSCC analysis
157 /// This primarily proxies invalidation information from the module analysis
158 /// manager and module pass manager to a CGSCC analysis manager. You should
159 /// never use a CGSCC analysis manager from within (transitively) a module
160 /// pass manager unless your parent module pass has received a proxy result
162 class CGSCCAnalysisManagerModuleProxy {
166 explicit Result(CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
167 // We have to explicitly define all the special member functions because
168 // MSVC refuses to generate them.
169 Result(const Result &Arg) : CGAM(Arg.CGAM) {}
170 Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
171 Result &operator=(Result RHS) {
172 std::swap(CGAM, RHS.CGAM);
177 /// \brief Accessor for the \c CGSCCAnalysisManager.
178 CGSCCAnalysisManager &getManager() { return *CGAM; }
180 /// \brief Handler for invalidation of the module.
182 /// If this analysis itself is preserved, then we assume that the call
183 /// graph of the module hasn't changed and thus we don't need to invalidate
184 /// *all* cached data associated with a \c SCC* in the \c
185 /// CGSCCAnalysisManager.
187 /// Regardless of whether this analysis is marked as preserved, all of the
188 /// analyses in the \c CGSCCAnalysisManager are potentially invalidated
189 /// based on the set of preserved analyses.
190 bool invalidate(Module &M, const PreservedAnalyses &PA);
193 CGSCCAnalysisManager *CGAM;
196 static void *ID() { return (void *)&PassID; }
198 static StringRef name() { return "CGSCCAnalysisManagerModuleProxy"; }
200 explicit CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManager &CGAM)
202 // We have to explicitly define all the special member functions because MSVC
203 // refuses to generate them.
204 CGSCCAnalysisManagerModuleProxy(
205 const CGSCCAnalysisManagerModuleProxy &Arg)
207 CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManagerModuleProxy &&Arg)
208 : CGAM(std::move(Arg.CGAM)) {}
209 CGSCCAnalysisManagerModuleProxy &
210 operator=(CGSCCAnalysisManagerModuleProxy RHS) {
211 std::swap(CGAM, RHS.CGAM);
215 /// \brief Run the analysis pass and create our proxy result object.
217 /// This doesn't do any interesting work, it is primarily used to insert our
218 /// proxy result object into the module analysis cache so that we can proxy
219 /// invalidation to the CGSCC analysis manager.
221 /// In debug builds, it will also assert that the analysis manager is empty
222 /// as no queries should arrive at the CGSCC analysis manager prior to
223 /// this analysis being requested.
224 Result run(Module &M);
229 CGSCCAnalysisManager *CGAM;
232 /// \brief A CGSCC analysis which acts as a proxy for a module analysis
235 /// This primarily provides an accessor to a parent module analysis manager to
236 /// CGSCC passes. Only the const interface of the module analysis manager is
237 /// provided to indicate that once inside of a CGSCC analysis pass you
238 /// cannot request a module analysis to actually run. Instead, the user must
239 /// rely on the \c getCachedResult API.
241 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
242 /// the recursive return path of each layer of the pass manager and the
243 /// returned PreservedAnalysis set.
244 class ModuleAnalysisManagerCGSCCProxy {
246 /// \brief Result proxy object for \c ModuleAnalysisManagerCGSCCProxy.
249 explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {}
250 // We have to explicitly define all the special member functions because
251 // MSVC refuses to generate them.
252 Result(const Result &Arg) : MAM(Arg.MAM) {}
253 Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {}
254 Result &operator=(Result RHS) {
255 std::swap(MAM, RHS.MAM);
259 const ModuleAnalysisManager &getManager() const { return *MAM; }
261 /// \brief Handle invalidation by ignoring it, this pass is immutable.
262 bool invalidate(LazyCallGraph::SCC &) { return false; }
265 const ModuleAnalysisManager *MAM;
268 static void *ID() { return (void *)&PassID; }
270 static StringRef name() { return "ModuleAnalysisManagerCGSCCProxy"; }
272 ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManager &MAM)
274 // We have to explicitly define all the special member functions because MSVC
275 // refuses to generate them.
276 ModuleAnalysisManagerCGSCCProxy(
277 const ModuleAnalysisManagerCGSCCProxy &Arg)
279 ModuleAnalysisManagerCGSCCProxy(ModuleAnalysisManagerCGSCCProxy &&Arg)
280 : MAM(std::move(Arg.MAM)) {}
281 ModuleAnalysisManagerCGSCCProxy &
282 operator=(ModuleAnalysisManagerCGSCCProxy RHS) {
283 std::swap(MAM, RHS.MAM);
287 /// \brief Run the analysis pass and create our proxy result object.
288 /// Nothing to see here, it just forwards the \c MAM reference into the
290 Result run(LazyCallGraph::SCC &) { return Result(*MAM); }
295 const ModuleAnalysisManager *MAM;
298 /// \brief The core module pass which does a post-order walk of the SCCs and
299 /// runs a CGSCC pass over each one.
301 /// Designed to allow composition of a CGSCCPass(Manager) and
302 /// a ModulePassManager. Note that this pass must be run with a module analysis
303 /// manager as it uses the LazyCallGraph analysis. It will also run the
304 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
305 /// pass over the module to enable a \c FunctionAnalysisManager to be used
306 /// within this run safely.
307 template <typename CGSCCPassT> class ModuleToPostOrderCGSCCPassAdaptor {
309 explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
310 : Pass(std::move(Pass)) {}
311 // We have to explicitly define all the special member functions because MSVC
312 // refuses to generate them.
313 ModuleToPostOrderCGSCCPassAdaptor(
314 const ModuleToPostOrderCGSCCPassAdaptor &Arg)
316 ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
317 : Pass(std::move(Arg.Pass)) {}
318 friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
319 ModuleToPostOrderCGSCCPassAdaptor &RHS) {
321 swap(LHS.Pass, RHS.Pass);
323 ModuleToPostOrderCGSCCPassAdaptor &
324 operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
329 /// \brief Runs the CGSCC pass across every SCC in the module.
330 PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) {
331 assert(AM && "We need analyses to compute the call graph!");
333 // Setup the CGSCC analysis manager from its proxy.
334 CGSCCAnalysisManager &CGAM =
335 AM->getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
337 // Get the call graph for this module.
338 LazyCallGraph &CG = AM->getResult<LazyCallGraphAnalysis>(M);
340 PreservedAnalyses PA = PreservedAnalyses::all();
341 for (LazyCallGraph::SCC &C : CG.postorder_sccs()) {
342 PreservedAnalyses PassPA = Pass.run(C, &CGAM);
344 // We know that the CGSCC pass couldn't have invalidated any other
345 // SCC's analyses (that's the contract of a CGSCC pass), so
346 // directly handle the CGSCC analysis manager's invalidation here. We
347 // also update the preserved set of analyses to reflect that invalidated
348 // analyses are now safe to preserve.
349 // FIXME: This isn't quite correct. We need to handle the case where the
350 // pass updated the CG, particularly some child of the current SCC, and
351 // invalidate its analyses.
352 PassPA = CGAM.invalidate(C, std::move(PassPA));
354 // Then intersect the preserved set so that invalidation of module
355 // analyses will eventually occur when the module pass completes.
356 PA.intersect(std::move(PassPA));
359 // By definition we preserve the proxy. This precludes *any* invalidation
360 // of CGSCC analyses by the proxy, but that's OK because we've taken
361 // care to invalidate analyses in the CGSCC analysis manager
362 // incrementally above.
363 PA.preserve<CGSCCAnalysisManagerModuleProxy>();
367 static StringRef name() { return "ModuleToPostOrderCGSCCPassAdaptor"; }
373 /// \brief A function to deduce a function pass type and wrap it in the
374 /// templated adaptor.
375 template <typename CGSCCPassT>
376 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
377 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
379 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass)));
382 /// \brief A CGSCC analysis which acts as a proxy for a function analysis
385 /// This primarily proxies invalidation information from the CGSCC analysis
386 /// manager and CGSCC pass manager to a function analysis manager. You should
387 /// never use a function analysis manager from within (transitively) a CGSCC
388 /// pass manager unless your parent CGSCC pass has received a proxy result
390 class FunctionAnalysisManagerCGSCCProxy {
394 explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
395 // We have to explicitly define all the special member functions because
396 // MSVC refuses to generate them.
397 Result(const Result &Arg) : FAM(Arg.FAM) {}
398 Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
399 Result &operator=(Result RHS) {
400 std::swap(FAM, RHS.FAM);
405 /// \brief Accessor for the \c FunctionAnalysisManager.
406 FunctionAnalysisManager &getManager() { return *FAM; }
408 /// \brief Handler for invalidation of the SCC.
410 /// If this analysis itself is preserved, then we assume that the set of \c
411 /// Function objects in the \c SCC hasn't changed and thus we don't need
412 /// to invalidate *all* cached data associated with a \c Function* in the \c
413 /// FunctionAnalysisManager.
415 /// Regardless of whether this analysis is marked as preserved, all of the
416 /// analyses in the \c FunctionAnalysisManager are potentially invalidated
417 /// based on the set of preserved analyses.
418 bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA);
421 FunctionAnalysisManager *FAM;
424 static void *ID() { return (void *)&PassID; }
426 static StringRef name() { return "FunctionAnalysisManagerCGSCCProxy"; }
428 explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM)
430 // We have to explicitly define all the special member functions because MSVC
431 // refuses to generate them.
432 FunctionAnalysisManagerCGSCCProxy(
433 const FunctionAnalysisManagerCGSCCProxy &Arg)
435 FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManagerCGSCCProxy &&Arg)
436 : FAM(std::move(Arg.FAM)) {}
437 FunctionAnalysisManagerCGSCCProxy &
438 operator=(FunctionAnalysisManagerCGSCCProxy RHS) {
439 std::swap(FAM, RHS.FAM);
443 /// \brief Run the analysis pass and create our proxy result object.
445 /// This doesn't do any interesting work, it is primarily used to insert our
446 /// proxy result object into the module analysis cache so that we can proxy
447 /// invalidation to the function analysis manager.
449 /// In debug builds, it will also assert that the analysis manager is empty
450 /// as no queries should arrive at the function analysis manager prior to
451 /// this analysis being requested.
452 Result run(LazyCallGraph::SCC &C);
457 FunctionAnalysisManager *FAM;
460 /// \brief A function analysis which acts as a proxy for a CGSCC analysis
463 /// This primarily provides an accessor to a parent CGSCC analysis manager to
464 /// function passes. Only the const interface of the CGSCC analysis manager is
465 /// provided to indicate that once inside of a function analysis pass you
466 /// cannot request a CGSCC analysis to actually run. Instead, the user must
467 /// rely on the \c getCachedResult API.
469 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
470 /// the recursive return path of each layer of the pass manager and the
471 /// returned PreservedAnalysis set.
472 class CGSCCAnalysisManagerFunctionProxy {
474 /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
477 explicit Result(const CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
478 // We have to explicitly define all the special member functions because
479 // MSVC refuses to generate them.
480 Result(const Result &Arg) : CGAM(Arg.CGAM) {}
481 Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
482 Result &operator=(Result RHS) {
483 std::swap(CGAM, RHS.CGAM);
487 const CGSCCAnalysisManager &getManager() const { return *CGAM; }
489 /// \brief Handle invalidation by ignoring it, this pass is immutable.
490 bool invalidate(Function &) { return false; }
493 const CGSCCAnalysisManager *CGAM;
496 static void *ID() { return (void *)&PassID; }
498 static StringRef name() { return "CGSCCAnalysisManagerFunctionProxy"; }
500 CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM)
502 // We have to explicitly define all the special member functions because MSVC
503 // refuses to generate them.
504 CGSCCAnalysisManagerFunctionProxy(
505 const CGSCCAnalysisManagerFunctionProxy &Arg)
507 CGSCCAnalysisManagerFunctionProxy(CGSCCAnalysisManagerFunctionProxy &&Arg)
508 : CGAM(std::move(Arg.CGAM)) {}
509 CGSCCAnalysisManagerFunctionProxy &
510 operator=(CGSCCAnalysisManagerFunctionProxy RHS) {
511 std::swap(CGAM, RHS.CGAM);
515 /// \brief Run the analysis pass and create our proxy result object.
516 /// Nothing to see here, it just forwards the \c CGAM reference into the
518 Result run(Function &) { return Result(*CGAM); }
523 const CGSCCAnalysisManager *CGAM;
526 /// \brief Adaptor that maps from a SCC to its functions.
528 /// Designed to allow composition of a FunctionPass(Manager) and
529 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
530 /// to a \c CGSCCAnalysisManager it will run the
531 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
532 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
533 /// within this run safely.
534 template <typename FunctionPassT> class CGSCCToFunctionPassAdaptor {
536 explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
537 : Pass(std::move(Pass)) {}
538 // We have to explicitly define all the special member functions because MSVC
539 // refuses to generate them.
540 CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
542 CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
543 : Pass(std::move(Arg.Pass)) {}
544 friend void swap(CGSCCToFunctionPassAdaptor &LHS, CGSCCToFunctionPassAdaptor &RHS) {
546 swap(LHS.Pass, RHS.Pass);
548 CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
553 /// \brief Runs the function pass across every function in the module.
554 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager *AM) {
555 FunctionAnalysisManager *FAM = nullptr;
557 // Setup the function analysis manager from its proxy.
558 FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
560 PreservedAnalyses PA = PreservedAnalyses::all();
561 for (LazyCallGraph::Node *N : C) {
562 PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
564 // We know that the function pass couldn't have invalidated any other
565 // function's analyses (that's the contract of a function pass), so
566 // directly handle the function analysis manager's invalidation here.
567 // Also, update the preserved analyses to reflect that once invalidated
568 // these can again be preserved.
570 PassPA = FAM->invalidate(N->getFunction(), std::move(PassPA));
572 // Then intersect the preserved set so that invalidation of module
573 // analyses will eventually occur when the module pass completes.
574 PA.intersect(std::move(PassPA));
577 // By definition we preserve the proxy. This precludes *any* invalidation
578 // of function analyses by the proxy, but that's OK because we've taken
579 // care to invalidate analyses in the function analysis manager
580 // incrementally above.
581 // FIXME: We need to update the call graph here to account for any deleted
583 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
587 static StringRef name() { return "CGSCCToFunctionPassAdaptor"; }
593 /// \brief A function to deduce a function pass type and wrap it in the
594 /// templated adaptor.
595 template <typename FunctionPassT>
596 CGSCCToFunctionPassAdaptor<FunctionPassT>
597 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
598 return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));