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/Analysis/LazyCallGraph.h"
25 #include "llvm/IR/PassManager.h"
29 /// \brief The CGSCC pass manager.
31 /// See the documentation for the PassManager template for details. It runs
32 /// a sequency of SCC passes over each SCC that the manager is run over. This
33 /// typedef serves as a convenient way to refer to this construct.
34 typedef PassManager<LazyCallGraph::SCC> CGSCCPassManager;
36 /// \brief The CGSCC analysis manager.
38 /// See the documentation for the AnalysisManager template for detail
39 /// documentation. This typedef serves as a convenient way to refer to this
40 /// construct in the adaptors and proxies used to integrate this into the larger
41 /// pass manager infrastructure.
42 typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager;
44 /// \brief A module analysis which acts as a proxy for a CGSCC analysis
47 /// This primarily proxies invalidation information from the module analysis
48 /// manager and module pass manager to a CGSCC analysis manager. You should
49 /// never use a CGSCC analysis manager from within (transitively) a module
50 /// pass manager unless your parent module pass has received a proxy result
52 class CGSCCAnalysisManagerModuleProxy {
56 explicit Result(CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
57 // We have to explicitly define all the special member functions because
58 // MSVC refuses to generate them.
59 Result(const Result &Arg) : CGAM(Arg.CGAM) {}
60 Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
61 Result &operator=(Result RHS) {
62 std::swap(CGAM, RHS.CGAM);
67 /// \brief Accessor for the \c CGSCCAnalysisManager.
68 CGSCCAnalysisManager &getManager() { return *CGAM; }
70 /// \brief Handler for invalidation of the module.
72 /// If this analysis itself is preserved, then we assume that the call
73 /// graph of the module hasn't changed and thus we don't need to invalidate
74 /// *all* cached data associated with a \c SCC* in the \c
75 /// CGSCCAnalysisManager.
77 /// Regardless of whether this analysis is marked as preserved, all of the
78 /// analyses in the \c CGSCCAnalysisManager are potentially invalidated
79 /// based on the set of preserved analyses.
80 bool invalidate(Module &M, const PreservedAnalyses &PA);
83 CGSCCAnalysisManager *CGAM;
86 static void *ID() { return (void *)&PassID; }
88 static StringRef name() { return "CGSCCAnalysisManagerModuleProxy"; }
90 explicit CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManager &CGAM)
92 // We have to explicitly define all the special member functions because MSVC
93 // refuses to generate them.
94 CGSCCAnalysisManagerModuleProxy(const CGSCCAnalysisManagerModuleProxy &Arg)
96 CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManagerModuleProxy &&Arg)
97 : CGAM(std::move(Arg.CGAM)) {}
98 CGSCCAnalysisManagerModuleProxy &
99 operator=(CGSCCAnalysisManagerModuleProxy RHS) {
100 std::swap(CGAM, RHS.CGAM);
104 /// \brief Run the analysis pass and create our proxy result object.
106 /// This doesn't do any interesting work, it is primarily used to insert our
107 /// proxy result object into the module analysis cache so that we can proxy
108 /// invalidation to the CGSCC analysis manager.
110 /// In debug builds, it will also assert that the analysis manager is empty
111 /// as no queries should arrive at the CGSCC analysis manager prior to
112 /// this analysis being requested.
113 Result run(Module &M);
118 CGSCCAnalysisManager *CGAM;
121 /// \brief A CGSCC analysis which acts as a proxy for a module analysis
124 /// This primarily provides an accessor to a parent module analysis manager to
125 /// CGSCC passes. Only the const interface of the module analysis manager is
126 /// provided to indicate that once inside of a CGSCC analysis pass you
127 /// cannot request a module analysis to actually run. Instead, the user must
128 /// rely on the \c getCachedResult API.
130 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
131 /// the recursive return path of each layer of the pass manager and the
132 /// returned PreservedAnalysis set.
133 class ModuleAnalysisManagerCGSCCProxy {
135 /// \brief Result proxy object for \c ModuleAnalysisManagerCGSCCProxy.
138 explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {}
139 // We have to explicitly define all the special member functions because
140 // MSVC refuses to generate them.
141 Result(const Result &Arg) : MAM(Arg.MAM) {}
142 Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {}
143 Result &operator=(Result RHS) {
144 std::swap(MAM, RHS.MAM);
148 const ModuleAnalysisManager &getManager() const { return *MAM; }
150 /// \brief Handle invalidation by ignoring it, this pass is immutable.
151 bool invalidate(LazyCallGraph::SCC &) { return false; }
154 const ModuleAnalysisManager *MAM;
157 static void *ID() { return (void *)&PassID; }
159 static StringRef name() { return "ModuleAnalysisManagerCGSCCProxy"; }
161 ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManager &MAM)
163 // We have to explicitly define all the special member functions because MSVC
164 // refuses to generate them.
165 ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManagerCGSCCProxy &Arg)
167 ModuleAnalysisManagerCGSCCProxy(ModuleAnalysisManagerCGSCCProxy &&Arg)
168 : MAM(std::move(Arg.MAM)) {}
169 ModuleAnalysisManagerCGSCCProxy &
170 operator=(ModuleAnalysisManagerCGSCCProxy RHS) {
171 std::swap(MAM, RHS.MAM);
175 /// \brief Run the analysis pass and create our proxy result object.
176 /// Nothing to see here, it just forwards the \c MAM reference into the
178 Result run(LazyCallGraph::SCC &) { return Result(*MAM); }
183 const ModuleAnalysisManager *MAM;
186 /// \brief The core module pass which does a post-order walk of the SCCs and
187 /// runs a CGSCC pass over each one.
189 /// Designed to allow composition of a CGSCCPass(Manager) and
190 /// a ModulePassManager. Note that this pass must be run with a module analysis
191 /// manager as it uses the LazyCallGraph analysis. It will also run the
192 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
193 /// pass over the module to enable a \c FunctionAnalysisManager to be used
194 /// within this run safely.
195 template <typename CGSCCPassT> class ModuleToPostOrderCGSCCPassAdaptor {
197 explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
198 : Pass(std::move(Pass)) {}
199 // We have to explicitly define all the special member functions because MSVC
200 // refuses to generate them.
201 ModuleToPostOrderCGSCCPassAdaptor(
202 const ModuleToPostOrderCGSCCPassAdaptor &Arg)
204 ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
205 : Pass(std::move(Arg.Pass)) {}
206 friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
207 ModuleToPostOrderCGSCCPassAdaptor &RHS) {
209 swap(LHS.Pass, RHS.Pass);
211 ModuleToPostOrderCGSCCPassAdaptor &
212 operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
217 /// \brief Runs the CGSCC pass across every SCC in the module.
218 PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) {
219 assert(AM && "We need analyses to compute the call graph!");
221 // Setup the CGSCC analysis manager from its proxy.
222 CGSCCAnalysisManager &CGAM =
223 AM->getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
225 // Get the call graph for this module.
226 LazyCallGraph &CG = AM->getResult<LazyCallGraphAnalysis>(M);
228 PreservedAnalyses PA = PreservedAnalyses::all();
229 for (LazyCallGraph::SCC &C : CG.postorder_sccs()) {
230 PreservedAnalyses PassPA = Pass.run(C, &CGAM);
232 // We know that the CGSCC pass couldn't have invalidated any other
233 // SCC's analyses (that's the contract of a CGSCC pass), so
234 // directly handle the CGSCC analysis manager's invalidation here. We
235 // also update the preserved set of analyses to reflect that invalidated
236 // analyses are now safe to preserve.
237 // FIXME: This isn't quite correct. We need to handle the case where the
238 // pass updated the CG, particularly some child of the current SCC, and
239 // invalidate its analyses.
240 PassPA = CGAM.invalidate(C, std::move(PassPA));
242 // Then intersect the preserved set so that invalidation of module
243 // analyses will eventually occur when the module pass completes.
244 PA.intersect(std::move(PassPA));
247 // By definition we preserve the proxy. This precludes *any* invalidation
248 // of CGSCC analyses by the proxy, but that's OK because we've taken
249 // care to invalidate analyses in the CGSCC analysis manager
250 // incrementally above.
251 PA.preserve<CGSCCAnalysisManagerModuleProxy>();
255 static StringRef name() { return "ModuleToPostOrderCGSCCPassAdaptor"; }
261 /// \brief A function to deduce a function pass type and wrap it in the
262 /// templated adaptor.
263 template <typename CGSCCPassT>
264 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
265 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
267 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass)));
270 /// \brief A CGSCC analysis which acts as a proxy for a function analysis
273 /// This primarily proxies invalidation information from the CGSCC analysis
274 /// manager and CGSCC pass manager to a function analysis manager. You should
275 /// never use a function analysis manager from within (transitively) a CGSCC
276 /// pass manager unless your parent CGSCC pass has received a proxy result
278 class FunctionAnalysisManagerCGSCCProxy {
282 explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
283 // We have to explicitly define all the special member functions because
284 // MSVC refuses to generate them.
285 Result(const Result &Arg) : FAM(Arg.FAM) {}
286 Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
287 Result &operator=(Result RHS) {
288 std::swap(FAM, RHS.FAM);
293 /// \brief Accessor for the \c FunctionAnalysisManager.
294 FunctionAnalysisManager &getManager() { return *FAM; }
296 /// \brief Handler for invalidation of the SCC.
298 /// If this analysis itself is preserved, then we assume that the set of \c
299 /// Function objects in the \c SCC hasn't changed and thus we don't need
300 /// to invalidate *all* cached data associated with a \c Function* in the \c
301 /// FunctionAnalysisManager.
303 /// Regardless of whether this analysis is marked as preserved, all of the
304 /// analyses in the \c FunctionAnalysisManager are potentially invalidated
305 /// based on the set of preserved analyses.
306 bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA);
309 FunctionAnalysisManager *FAM;
312 static void *ID() { return (void *)&PassID; }
314 static StringRef name() { return "FunctionAnalysisManagerCGSCCProxy"; }
316 explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM)
318 // We have to explicitly define all the special member functions because MSVC
319 // refuses to generate them.
320 FunctionAnalysisManagerCGSCCProxy(
321 const FunctionAnalysisManagerCGSCCProxy &Arg)
323 FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManagerCGSCCProxy &&Arg)
324 : FAM(std::move(Arg.FAM)) {}
325 FunctionAnalysisManagerCGSCCProxy &
326 operator=(FunctionAnalysisManagerCGSCCProxy RHS) {
327 std::swap(FAM, RHS.FAM);
331 /// \brief Run the analysis pass and create our proxy result object.
333 /// This doesn't do any interesting work, it is primarily used to insert our
334 /// proxy result object into the module analysis cache so that we can proxy
335 /// invalidation to the function analysis manager.
337 /// In debug builds, it will also assert that the analysis manager is empty
338 /// as no queries should arrive at the function analysis manager prior to
339 /// this analysis being requested.
340 Result run(LazyCallGraph::SCC &C);
345 FunctionAnalysisManager *FAM;
348 /// \brief A function analysis which acts as a proxy for a CGSCC analysis
351 /// This primarily provides an accessor to a parent CGSCC analysis manager to
352 /// function passes. Only the const interface of the CGSCC analysis manager is
353 /// provided to indicate that once inside of a function analysis pass you
354 /// cannot request a CGSCC analysis to actually run. Instead, the user must
355 /// rely on the \c getCachedResult API.
357 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
358 /// the recursive return path of each layer of the pass manager and the
359 /// returned PreservedAnalysis set.
360 class CGSCCAnalysisManagerFunctionProxy {
362 /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
365 explicit Result(const CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
366 // We have to explicitly define all the special member functions because
367 // MSVC refuses to generate them.
368 Result(const Result &Arg) : CGAM(Arg.CGAM) {}
369 Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
370 Result &operator=(Result RHS) {
371 std::swap(CGAM, RHS.CGAM);
375 const CGSCCAnalysisManager &getManager() const { return *CGAM; }
377 /// \brief Handle invalidation by ignoring it, this pass is immutable.
378 bool invalidate(Function &) { return false; }
381 const CGSCCAnalysisManager *CGAM;
384 static void *ID() { return (void *)&PassID; }
386 static StringRef name() { return "CGSCCAnalysisManagerFunctionProxy"; }
388 CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM)
390 // We have to explicitly define all the special member functions because MSVC
391 // refuses to generate them.
392 CGSCCAnalysisManagerFunctionProxy(
393 const CGSCCAnalysisManagerFunctionProxy &Arg)
395 CGSCCAnalysisManagerFunctionProxy(CGSCCAnalysisManagerFunctionProxy &&Arg)
396 : CGAM(std::move(Arg.CGAM)) {}
397 CGSCCAnalysisManagerFunctionProxy &
398 operator=(CGSCCAnalysisManagerFunctionProxy RHS) {
399 std::swap(CGAM, RHS.CGAM);
403 /// \brief Run the analysis pass and create our proxy result object.
404 /// Nothing to see here, it just forwards the \c CGAM reference into the
406 Result run(Function &) { return Result(*CGAM); }
411 const CGSCCAnalysisManager *CGAM;
414 /// \brief Adaptor that maps from a SCC to its functions.
416 /// Designed to allow composition of a FunctionPass(Manager) and
417 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
418 /// to a \c CGSCCAnalysisManager it will run the
419 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
420 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
421 /// within this run safely.
422 template <typename FunctionPassT> class CGSCCToFunctionPassAdaptor {
424 explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
425 : Pass(std::move(Pass)) {}
426 // We have to explicitly define all the special member functions because MSVC
427 // refuses to generate them.
428 CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
430 CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
431 : Pass(std::move(Arg.Pass)) {}
432 friend void swap(CGSCCToFunctionPassAdaptor &LHS,
433 CGSCCToFunctionPassAdaptor &RHS) {
435 swap(LHS.Pass, RHS.Pass);
437 CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
442 /// \brief Runs the function pass across every function in the module.
443 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager *AM) {
444 FunctionAnalysisManager *FAM = nullptr;
446 // Setup the function analysis manager from its proxy.
447 FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
449 PreservedAnalyses PA = PreservedAnalyses::all();
450 for (LazyCallGraph::Node *N : C) {
451 PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
453 // We know that the function pass couldn't have invalidated any other
454 // function's analyses (that's the contract of a function pass), so
455 // directly handle the function analysis manager's invalidation here.
456 // Also, update the preserved analyses to reflect that once invalidated
457 // these can again be preserved.
459 PassPA = FAM->invalidate(N->getFunction(), std::move(PassPA));
461 // Then intersect the preserved set so that invalidation of module
462 // analyses will eventually occur when the module pass completes.
463 PA.intersect(std::move(PassPA));
466 // By definition we preserve the proxy. This precludes *any* invalidation
467 // of function analyses by the proxy, but that's OK because we've taken
468 // care to invalidate analyses in the function analysis manager
469 // incrementally above.
470 // FIXME: We need to update the call graph here to account for any deleted
472 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
476 static StringRef name() { return "CGSCCToFunctionPassAdaptor"; }
482 /// \brief A function to deduce a function pass type and wrap it in the
483 /// templated adaptor.
484 template <typename FunctionPassT>
485 CGSCCToFunctionPassAdaptor<FunctionPassT>
486 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
487 return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));