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
)));