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 /// traverse the graph in post-order, they can effectively do pair-wise
15 /// interprocedural optimizations for all call edges in the program while
16 /// incrementally refining it and improving the context of these pair-wise
17 /// optimizations. At each call site edge, the callee has already been
18 /// optimized as much as is possible. This in turn allows very accurate
19 /// analysis of it for IPO.
21 /// A secondary more general goal is to be able to isolate optimization on
22 /// unrelated parts of the IR module. This is useful to ensure our
23 /// optimizations are principled and don't miss oportunities where refinement
24 /// of one part of the module influence transformations in another part of the
25 /// module. But this is also useful if we want to parallelize the optimizations
26 /// across common large module graph shapes which tend to be very wide and have
27 /// large regions of unrelated cliques.
29 /// To satisfy these goals, we use the LazyCallGraph which provides two graphs
30 /// nested inside each other (and built lazily from the bottom-up): the call
31 /// graph proper, and a reference graph. The reference graph is super set of
32 /// the call graph and is a conservative approximation of what could through
33 /// scalar or CGSCC transforms *become* the call graph. Using this allows us to
34 /// ensure we optimize functions prior to them being introduced into the call
35 /// graph by devirtualization or other technique, and thus ensures that
36 /// subsequent pair-wise interprocedural optimizations observe the optimized
37 /// form of these functions. The (potentially transitive) reference
38 /// reachability used by the reference graph is a conservative approximation
39 /// that still allows us to have independent regions of the graph.
41 /// FIXME: There is one major drawback of the reference graph: in its naive
42 /// form it is quadratic because it contains a distinct edge for each
43 /// (potentially indirect) reference, even if are all through some common
44 /// global table of function pointers. This can be fixed in a number of ways
45 /// that essentially preserve enough of the normalization. While it isn't
46 /// expected to completely preclude the usability of this, it will need to be
50 /// All of these issues are made substantially more complex in the face of
51 /// mutations to the call graph while optimization passes are being run. When
52 /// mutations to the call graph occur we want to achieve two different things:
54 /// - We need to update the call graph in-flight and invalidate analyses
55 /// cached on entities in the graph. Because of the cache-based analysis
56 /// design of the pass manager, it is essential to have stable identities for
57 /// the elements of the IR that passes traverse, and to invalidate any
58 /// analyses cached on these elements as the mutations take place.
60 /// - We want to preserve the incremental and post-order traversal of the
61 /// graph even as it is refined and mutated. This means we want optimization
62 /// to observe the most refined form of the call graph and to do so in
65 /// To address this, the CGSCC manager uses both worklists that can be expanded
66 /// by passes which transform the IR, and provides invalidation tests to skip
67 /// entries that become dead. This extra data is provided to every SCC pass so
68 /// that it can carefully update the manager's traversal as the call graph
71 /// We also provide support for running function passes within the CGSCC walk,
72 /// and there we provide automatic update of the call graph including of the
73 /// pass manager to reflect call graph changes that fall out naturally as part
74 /// of scalar transformations.
76 /// The patterns used to ensure the goals of post-order visitation of the fully
79 /// 1) Sink toward the "bottom" as the graph is refined. This means that any
80 /// iteration continues in some valid post-order sequence after the mutation
81 /// has altered the structure.
83 /// 2) Enqueue in post-order, including the current entity. If the current
84 /// entity's shape changes, it and everything after it in post-order needs
85 /// to be visited to observe that shape.
87 //===----------------------------------------------------------------------===//
89 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
90 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
92 #include "llvm/ADT/PriorityWorklist.h"
93 #include "llvm/Analysis/LazyCallGraph.h"
94 #include "llvm/IR/CallSite.h"
95 #include "llvm/IR/InstIterator.h"
96 #include "llvm/IR/PassManager.h"
97 #include "llvm/IR/ValueHandle.h"
101 struct CGSCCUpdateResult;
103 /// Extern template declaration for the analysis set for this IR unit.
104 extern template class AllAnalysesOn<LazyCallGraph::SCC>;
106 extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
107 /// \brief The CGSCC analysis manager.
109 /// See the documentation for the AnalysisManager template for detail
110 /// documentation. This typedef serves as a convenient way to refer to this
111 /// construct in the adaptors and proxies used to integrate this into the larger
112 /// pass manager infrastructure.
113 typedef AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>
114 CGSCCAnalysisManager;
116 // Explicit specialization and instantiation declarations for the pass manager.
117 // See the comments on the definition of the specialization for details on how
118 // it differs from the primary template.
121 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
122 CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
123 CGSCCAnalysisManager &AM,
124 LazyCallGraph &G, CGSCCUpdateResult &UR);
125 extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
126 LazyCallGraph &, CGSCCUpdateResult &>;
128 /// \brief The CGSCC pass manager.
130 /// See the documentation for the PassManager template for details. It runs
131 /// a sequence of SCC passes over each SCC that the manager is run over. This
132 /// typedef serves as a convenient way to refer to this construct.
133 typedef PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
137 /// An explicit specialization of the require analysis template pass.
138 template <typename AnalysisT>
139 struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager,
140 LazyCallGraph &, CGSCCUpdateResult &>
141 : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
142 CGSCCAnalysisManager, LazyCallGraph &,
143 CGSCCUpdateResult &>> {
144 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
145 LazyCallGraph &CG, CGSCCUpdateResult &) {
146 (void)AM.template getResult<AnalysisT>(C, CG);
147 return PreservedAnalyses::all();
151 /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
152 typedef InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>
153 CGSCCAnalysisManagerModuleProxy;
155 /// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
156 /// it can have access to the call graph in order to walk all the SCCs when
157 /// invalidating things.
158 template <> class CGSCCAnalysisManagerModuleProxy::Result {
160 explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
161 : InnerAM(&InnerAM), G(&G) {}
163 /// \brief Accessor for the analysis manager.
164 CGSCCAnalysisManager &getManager() { return *InnerAM; }
166 /// \brief Handler for invalidation of the Module.
168 /// If the proxy analysis itself is preserved, then we assume that the set of
169 /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the
170 /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear
171 /// on the CGSCCAnalysisManager.
173 /// Regardless of whether this analysis is marked as preserved, all of the
174 /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based
175 /// on the set of preserved analyses.
176 bool invalidate(Module &M, const PreservedAnalyses &PA,
177 ModuleAnalysisManager::Invalidator &Inv);
180 CGSCCAnalysisManager *InnerAM;
184 /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
185 /// so it can pass the lazy call graph to the result.
187 CGSCCAnalysisManagerModuleProxy::Result
188 CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);
190 // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
192 extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
194 extern template class OuterAnalysisManagerProxy<
195 ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
196 /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
197 typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
199 ModuleAnalysisManagerCGSCCProxy;
201 /// Support structure for SCC passes to communicate updates the call graph back
202 /// to the CGSCC pass manager infrsatructure.
204 /// The CGSCC pass manager runs SCC passes which are allowed to update the call
205 /// graph and SCC structures. This means the structure the pass manager works
206 /// on is mutating underneath it. In order to support that, there needs to be
207 /// careful communication about the precise nature and ramifications of these
208 /// updates to the pass management infrastructure.
210 /// All SCC passes will have to accept a reference to the management layer's
211 /// update result struct and use it to reflect the results of any CG updates
214 /// Passes which do not change the call graph structure in any way can just
215 /// ignore this argument to their run method.
216 struct CGSCCUpdateResult {
217 /// Worklist of the RefSCCs queued for processing.
219 /// When a pass refines the graph and creates new RefSCCs or causes them to
220 /// have a different shape or set of component SCCs it should add the RefSCCs
221 /// to this worklist so that we visit them in the refined form.
223 /// This worklist is in reverse post-order, as we pop off the back in order
224 /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
225 /// them in reverse post-order.
226 SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist;
228 /// Worklist of the SCCs queued for processing.
230 /// When a pass refines the graph and creates new SCCs or causes them to have
231 /// a different shape or set of component functions it should add the SCCs to
232 /// this worklist so that we visit them in the refined form.
234 /// Note that if the SCCs are part of a RefSCC that is added to the \c
235 /// RCWorklist, they don't need to be added here as visiting the RefSCC will
236 /// be sufficient to re-visit the SCCs within it.
238 /// This worklist is in reverse post-order, as we pop off the back in order
239 /// to observe SCCs in post-order. When adding SCCs, clients should add them
240 /// in reverse post-order.
241 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist;
243 /// The set of invalidated RefSCCs which should be skipped if they are found
244 /// in \c RCWorklist.
246 /// This is used to quickly prune out RefSCCs when they get deleted and
247 /// happen to already be on the worklist. We use this primarily to avoid
248 /// scanning the list and removing entries from it.
249 SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;
251 /// The set of invalidated SCCs which should be skipped if they are found
254 /// This is used to quickly prune out SCCs when they get deleted and happen
255 /// to already be on the worklist. We use this primarily to avoid scanning
256 /// the list and removing entries from it.
257 SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
259 /// If non-null, the updated current \c RefSCC being processed.
261 /// This is set when a graph refinement takes place an the "current" point in
262 /// the graph moves "down" or earlier in the post-order walk. This will often
263 /// cause the "current" RefSCC to be a newly created RefSCC object and the
264 /// old one to be added to the above worklist. When that happens, this
265 /// pointer is non-null and can be used to continue processing the "top" of
266 /// the post-order walk.
267 LazyCallGraph::RefSCC *UpdatedRC;
269 /// If non-null, the updated current \c SCC being processed.
271 /// This is set when a graph refinement takes place an the "current" point in
272 /// the graph moves "down" or earlier in the post-order walk. This will often
273 /// cause the "current" SCC to be a newly created SCC object and the old one
274 /// to be added to the above worklist. When that happens, this pointer is
275 /// non-null and can be used to continue processing the "top" of the
277 LazyCallGraph::SCC *UpdatedC;
280 /// \brief The core module pass which does a post-order walk of the SCCs and
281 /// runs a CGSCC pass over each one.
283 /// Designed to allow composition of a CGSCCPass(Manager) and
284 /// a ModulePassManager. Note that this pass must be run with a module analysis
285 /// manager as it uses the LazyCallGraph analysis. It will also run the
286 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
287 /// pass over the module to enable a \c FunctionAnalysisManager to be used
288 /// within this run safely.
289 template <typename CGSCCPassT>
290 class ModuleToPostOrderCGSCCPassAdaptor
291 : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
293 explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false)
294 : Pass(std::move(Pass)), DebugLogging(DebugLogging) {}
295 // We have to explicitly define all the special member functions because MSVC
296 // refuses to generate them.
297 ModuleToPostOrderCGSCCPassAdaptor(
298 const ModuleToPostOrderCGSCCPassAdaptor &Arg)
299 : Pass(Arg.Pass), DebugLogging(Arg.DebugLogging) {}
300 ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
301 : Pass(std::move(Arg.Pass)), DebugLogging(Arg.DebugLogging) {}
302 friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
303 ModuleToPostOrderCGSCCPassAdaptor &RHS) {
305 swap(LHS.Pass, RHS.Pass);
306 swap(LHS.DebugLogging, RHS.DebugLogging);
308 ModuleToPostOrderCGSCCPassAdaptor &
309 operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
314 /// \brief Runs the CGSCC pass across every SCC in the module.
315 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
316 // Setup the CGSCC analysis manager from its proxy.
317 CGSCCAnalysisManager &CGAM =
318 AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
320 // Get the call graph for this module.
321 LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
323 // We keep worklists to allow us to push more work onto the pass manager as
324 // the passes are run.
325 SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
326 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
328 // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
329 // iterating off the worklists.
330 SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
331 SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
333 CGSCCUpdateResult UR = {RCWorklist, CWorklist, InvalidRefSCCSet,
334 InvalidSCCSet, nullptr, nullptr};
336 PreservedAnalyses PA = PreservedAnalyses::all();
338 for (auto RCI = CG.postorder_ref_scc_begin(),
339 RCE = CG.postorder_ref_scc_end();
341 assert(RCWorklist.empty() &&
342 "Should always start with an empty RefSCC worklist");
343 // The postorder_ref_sccs range we are walking is lazily constructed, so
344 // we only push the first one onto the worklist. The worklist allows us
345 // to capture *new* RefSCCs created during transformations.
347 // We really want to form RefSCCs lazily because that makes them cheaper
348 // to update as the program is simplified and allows us to have greater
349 // cache locality as forming a RefSCC touches all the parts of all the
350 // functions within that RefSCC.
352 // We also eagerly increment the iterator to the next position because
353 // the CGSCC passes below may delete the current RefSCC.
354 RCWorklist.insert(&*RCI++);
357 LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
358 if (InvalidRefSCCSet.count(RC)) {
360 dbgs() << "Skipping an invalid RefSCC...\n";
364 assert(CWorklist.empty() &&
365 "Should always start with an empty SCC worklist");
368 dbgs() << "Running an SCC pass across the RefSCC: " << *RC << "\n";
370 // Push the initial SCCs in reverse post-order as we'll pop off the the
371 // back and so see this in post-order.
372 for (LazyCallGraph::SCC &C : reverse(*RC))
373 CWorklist.insert(&C);
376 LazyCallGraph::SCC *C = CWorklist.pop_back_val();
377 // Due to call graph mutations, we may have invalid SCCs or SCCs from
378 // other RefSCCs in the worklist. The invalid ones are dead and the
379 // other RefSCCs should be queued above, so we just need to skip both
381 if (InvalidSCCSet.count(C)) {
383 dbgs() << "Skipping an invalid SCC...\n";
386 if (&C->getOuterRefSCC() != RC) {
388 dbgs() << "Skipping an SCC that is now part of some other "
394 // Check that we didn't miss any update scenario.
395 assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
396 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
397 assert(&C->getOuterRefSCC() == RC &&
398 "Processing an SCC in a different RefSCC!");
400 UR.UpdatedRC = nullptr;
401 UR.UpdatedC = nullptr;
402 PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
404 // We handle invalidating the CGSCC analysis manager's information
405 // for the (potentially updated) SCC here. Note that any other SCCs
406 // whose structure has changed should have been invalidated by
407 // whatever was updating the call graph. This SCC gets invalidated
408 // late as it contains the nodes that were actively being
410 CGAM.invalidate(*(UR.UpdatedC ? UR.UpdatedC : C), PassPA);
412 // Then intersect the preserved set so that invalidation of module
413 // analyses will eventually occur when the module pass completes.
414 PA.intersect(std::move(PassPA));
416 // The pass may have restructured the call graph and refined the
417 // current SCC and/or RefSCC. We need to update our current SCC and
418 // RefSCC pointers to follow these. Also, when the current SCC is
419 // refined, re-run the SCC pass over the newly refined SCC in order
420 // to observe the most precise SCC model available. This inherently
421 // cannot cycle excessively as it only happens when we split SCCs
422 // apart, at most converging on a DAG of single nodes.
423 // FIXME: If we ever start having RefSCC passes, we'll want to
424 // iterate there too.
425 RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
426 C = UR.UpdatedC ? UR.UpdatedC : C;
427 if (DebugLogging && UR.UpdatedC)
428 dbgs() << "Re-running SCC passes after a refinement of the "
430 << *UR.UpdatedC << "\n";
432 // Note that both `C` and `RC` may at this point refer to deleted,
433 // invalid SCC and RefSCCs respectively. But we will short circuit
434 // the processing when we check them in the loop above.
435 } while (UR.UpdatedC);
437 } while (!CWorklist.empty());
438 } while (!RCWorklist.empty());
441 // By definition we preserve the call garph, all SCC analyses, and the
442 // analysis proxies by handling them above and in any nested pass managers.
443 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
444 PA.preserve<LazyCallGraphAnalysis>();
445 PA.preserve<CGSCCAnalysisManagerModuleProxy>();
446 PA.preserve<FunctionAnalysisManagerModuleProxy>();
455 /// \brief A function to deduce a function pass type and wrap it in the
456 /// templated adaptor.
457 template <typename CGSCCPassT>
458 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
459 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false) {
460 return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass), DebugLogging);
463 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
465 /// When a module pass runs and triggers invalidation, both the CGSCC and
466 /// Function analysis manager proxies on the module get an invalidation event.
467 /// We don't want to fully duplicate responsibility for most of the
468 /// invalidation logic. Instead, this layer is only responsible for SCC-local
469 /// invalidation events. We work with the module's FunctionAnalysisManager to
470 /// invalidate function analyses.
471 class FunctionAnalysisManagerCGSCCProxy
472 : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
476 explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
478 /// \brief Accessor for the analysis manager.
479 FunctionAnalysisManager &getManager() { return *FAM; }
481 bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
482 CGSCCAnalysisManager::Invalidator &Inv);
485 FunctionAnalysisManager *FAM;
488 /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
489 Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
492 friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
493 static AnalysisKey Key;
496 extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
497 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
498 typedef OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>
499 CGSCCAnalysisManagerFunctionProxy;
501 /// Helper to update the call graph after running a function pass.
503 /// Function passes can only mutate the call graph in specific ways. This
504 /// routine provides a helper that updates the call graph in those ways
505 /// including returning whether any changes were made and populating a CG
506 /// update result struct for the overall CGSCC walk.
507 LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
508 LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
509 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, bool DebugLogging = false);
511 /// \brief Adaptor that maps from a SCC to its functions.
513 /// Designed to allow composition of a FunctionPass(Manager) and
514 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
515 /// to a \c CGSCCAnalysisManager it will run the
516 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
517 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
518 /// within this run safely.
519 template <typename FunctionPassT>
520 class CGSCCToFunctionPassAdaptor
521 : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
523 explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass, bool DebugLogging = false)
524 : Pass(std::move(Pass)), DebugLogging(DebugLogging) {}
525 // We have to explicitly define all the special member functions because MSVC
526 // refuses to generate them.
527 CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
528 : Pass(Arg.Pass), DebugLogging(Arg.DebugLogging) {}
529 CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
530 : Pass(std::move(Arg.Pass)), DebugLogging(Arg.DebugLogging) {}
531 friend void swap(CGSCCToFunctionPassAdaptor &LHS,
532 CGSCCToFunctionPassAdaptor &RHS) {
534 swap(LHS.Pass, RHS.Pass);
535 swap(LHS.DebugLogging, RHS.DebugLogging);
537 CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
542 /// \brief Runs the function pass across every function in the module.
543 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
544 LazyCallGraph &CG, CGSCCUpdateResult &UR) {
545 // Setup the function analysis manager from its proxy.
546 FunctionAnalysisManager &FAM =
547 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
549 SmallVector<LazyCallGraph::Node *, 4> Nodes;
550 for (LazyCallGraph::Node &N : C)
553 // The SCC may get split while we are optimizing functions due to deleting
554 // edges. If this happens, the current SCC can shift, so keep track of
555 // a pointer we can overwrite.
556 LazyCallGraph::SCC *CurrentC = &C;
559 dbgs() << "Running function passes across an SCC: " << C << "\n";
561 PreservedAnalyses PA = PreservedAnalyses::all();
562 for (LazyCallGraph::Node *N : Nodes) {
563 // Skip nodes from other SCCs. These may have been split out during
564 // processing. We'll eventually visit those SCCs and pick up the nodes
566 if (CG.lookupSCC(*N) != CurrentC)
569 PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
571 // We know that the function pass couldn't have invalidated any other
572 // function's analyses (that's the contract of a function pass), so
573 // directly handle the function analysis manager's invalidation here.
574 FAM.invalidate(N->getFunction(), PassPA);
576 // Then intersect the preserved set so that invalidation of module
577 // analyses will eventually occur when the module pass completes.
578 PA.intersect(std::move(PassPA));
580 // If the call graph hasn't been preserved, update it based on this
581 // function pass. This may also update the current SCC to point to
582 // a smaller, more refined SCC.
583 auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
584 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
585 CurrentC = &updateCGAndAnalysisManagerForFunctionPass(
586 CG, *CurrentC, *N, AM, UR, DebugLogging);
588 CG.lookupSCC(*N) == CurrentC &&
589 "Current SCC not updated to the SCC containing the current node!");
593 // By definition we preserve the proxy. And we preserve all analyses on
594 // Functions. This precludes *any* invalidation of function analyses by the
595 // proxy, but that's OK because we've taken care to invalidate analyses in
596 // the function analysis manager incrementally above.
597 PA.preserveSet<AllAnalysesOn<Function>>();
598 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
600 // We've also ensured that we updated the call graph along the way.
601 PA.preserve<LazyCallGraphAnalysis>();
611 /// \brief A function to deduce a function pass type and wrap it in the
612 /// templated adaptor.
613 template <typename FunctionPassT>
614 CGSCCToFunctionPassAdaptor<FunctionPassT>
615 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass, bool DebugLogging = false) {
616 return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass),
620 /// A helper that repeats an SCC pass each time an indirect call is refined to
621 /// a direct call by that pass.
623 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
624 /// change shape, we may also want to repeat an SCC pass if it simply refines
625 /// an indirect call to a direct call, even if doing so does not alter the
626 /// shape of the graph. Note that this only pertains to direct calls to
627 /// functions where IPO across the SCC may be able to compute more precise
628 /// results. For intrinsics, we assume scalar optimizations already can fully
629 /// reason about them.
631 /// This repetition has the potential to be very large however, as each one
632 /// might refine a single call site. As a consequence, in practice we use an
633 /// upper bound on the number of repetitions to limit things.
634 template <typename PassT>
635 class DevirtSCCRepeatedPass
636 : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
638 explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations,
639 bool DebugLogging = false)
640 : Pass(std::move(Pass)), MaxIterations(MaxIterations),
641 DebugLogging(DebugLogging) {}
643 /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
644 /// whenever an indirect call is refined.
645 PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
646 LazyCallGraph &CG, CGSCCUpdateResult &UR) {
647 PreservedAnalyses PA = PreservedAnalyses::all();
649 // The SCC may be refined while we are running passes over it, so set up
650 // a pointer that we can update.
651 LazyCallGraph::SCC *C = &InitialC;
653 // Collect value handles for all of the indirect call sites.
654 SmallVector<WeakTrackingVH, 8> CallHandles;
656 // Struct to track the counts of direct and indirect calls in each function
663 // Put value handles on all of the indirect calls and return the number of
664 // direct calls for each function in the SCC.
665 auto ScanSCC = [](LazyCallGraph::SCC &C,
666 SmallVectorImpl<WeakTrackingVH> &CallHandles) {
667 assert(CallHandles.empty() && "Must start with a clear set of handles.");
669 SmallVector<CallCount, 4> CallCounts;
670 for (LazyCallGraph::Node &N : C) {
671 CallCounts.push_back({0, 0});
672 CallCount &Count = CallCounts.back();
673 for (Instruction &I : instructions(N.getFunction()))
674 if (auto CS = CallSite(&I)) {
675 if (CS.getCalledFunction()) {
679 CallHandles.push_back(WeakTrackingVH(&I));
687 // Populate the initial call handles and get the initial call counts.
688 auto CallCounts = ScanSCC(*C, CallHandles);
690 for (int Iteration = 0;; ++Iteration) {
691 PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
693 // If the SCC structure has changed, bail immediately and let the outer
694 // CGSCC layer handle any iteration to reflect the refined structure.
695 if (UR.UpdatedC && UR.UpdatedC != C) {
696 PA.intersect(std::move(PassPA));
700 // Check that we didn't miss any update scenario.
701 assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
702 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
703 assert((int)CallCounts.size() == C->size() &&
704 "Cannot have changed the size of the SCC!");
706 // Check whether any of the handles were devirtualized.
707 auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
710 auto CS = CallSite(CallH);
714 // If the call is still indirect, leave it alone.
715 Function *F = CS.getCalledFunction();
720 dbgs() << "Found devirutalized call from "
721 << CS.getParent()->getParent()->getName() << " to "
722 << F->getName() << "\n";
724 // We now have a direct call where previously we had an indirect call,
725 // so iterate to process this devirtualization site.
728 bool Devirt = any_of(CallHandles, IsDevirtualizedHandle);
730 // Rescan to build up a new set of handles and count how many direct
731 // calls remain. If we decide to iterate, this also sets up the input to
732 // the next iteration.
734 auto NewCallCounts = ScanSCC(*C, CallHandles);
736 // If we haven't found an explicit devirtualization already see if we
737 // have decreased the number of indirect calls and increased the number
738 // of direct calls for any function in the SCC. This can be fooled by all
739 // manner of transformations such as DCE and other things, but seems to
740 // work well in practice.
742 for (int i = 0, Size = C->size(); i < Size; ++i)
743 if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
744 CallCounts[i].Direct < NewCallCounts[i].Direct) {
750 PA.intersect(std::move(PassPA));
754 // Otherwise, if we've already hit our max, we're done.
755 if (Iteration >= MaxIterations) {
757 dbgs() << "Found another devirtualization after hitting the max "
758 "number of repetitions ("
759 << MaxIterations << ") on SCC: " << *C << "\n";
760 PA.intersect(std::move(PassPA));
765 dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
768 // Move over the new call counts in preparation for iterating.
769 CallCounts = std::move(NewCallCounts);
771 // Update the analysis manager with each run and intersect the total set
772 // of preserved analyses so we're ready to iterate.
773 AM.invalidate(*C, PassPA);
774 PA.intersect(std::move(PassPA));
777 // Note that we don't add any preserved entries here unlike a more normal
778 // "pass manager" because we only handle invalidation *between* iterations,
779 // not after the last iteration.
789 /// \brief A function to deduce a function pass type and wrap it in the
790 /// templated adaptor.
791 template <typename PassT>
792 DevirtSCCRepeatedPass<PassT>
793 createDevirtSCCRepeatedPass(PassT Pass, int MaxIterations,
794 bool DebugLogging = false) {
795 return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations,