1 //===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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.
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 influence 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.
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.
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
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:
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.
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
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
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.
75 /// The patterns used to ensure the goals of post-order visitation of the fully
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.
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.
86 //===----------------------------------------------------------------------===//
88 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
89 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
91 #include "llvm/ADT/DenseMap.h"
92 #include "llvm/ADT/DenseSet.h"
93 #include "llvm/ADT/PriorityWorklist.h"
94 #include "llvm/ADT/STLExtras.h"
95 #include "llvm/ADT/SmallPtrSet.h"
96 #include "llvm/ADT/SmallVector.h"
97 #include "llvm/Analysis/LazyCallGraph.h"
98 #include "llvm/IR/Function.h"
99 #include "llvm/IR/InstIterator.h"
100 #include "llvm/IR/PassManager.h"
101 #include "llvm/IR/ValueHandle.h"
102 #include "llvm/Support/Debug.h"
103 #include "llvm/Support/raw_ostream.h"
110 struct CGSCCUpdateResult;
113 // Allow debug logging in this inline function.
114 #define DEBUG_TYPE "cgscc"
116 /// Extern template declaration for the analysis set for this IR unit.
117 extern template class AllAnalysesOn<LazyCallGraph::SCC>;
119 extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
121 /// The CGSCC analysis manager.
123 /// See the documentation for the AnalysisManager template for detail
124 /// documentation. This type serves as a convenient way to refer to this
125 /// construct in the adaptors and proxies used to integrate this into the larger
126 /// pass manager infrastructure.
127 using CGSCCAnalysisManager =
128 AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
130 // Explicit specialization and instantiation declarations for the pass manager.
131 // See the comments on the definition of the specialization for details on how
132 // it differs from the primary template.
135 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
136 CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
137 CGSCCAnalysisManager &AM,
138 LazyCallGraph &G, CGSCCUpdateResult &UR);
139 extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
140 LazyCallGraph &, CGSCCUpdateResult &>;
142 /// The CGSCC pass manager.
144 /// See the documentation for the PassManager template for details. It runs
145 /// a sequence of SCC passes over each SCC that the manager is run over. This
146 /// type serves as a convenient way to refer to this construct.
147 using CGSCCPassManager =
148 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
149 CGSCCUpdateResult &>;
151 /// An explicit specialization of the require analysis template pass.
152 template <typename AnalysisT>
153 struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager,
154 LazyCallGraph &, CGSCCUpdateResult &>
155 : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
156 CGSCCAnalysisManager, LazyCallGraph &,
157 CGSCCUpdateResult &>> {
158 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
159 LazyCallGraph &CG, CGSCCUpdateResult &) {
160 (void)AM.template getResult<AnalysisT>(C, CG);
161 return PreservedAnalyses::all();
165 /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
166 using CGSCCAnalysisManagerModuleProxy =
167 InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
169 /// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
170 /// it can have access to the call graph in order to walk all the SCCs when
171 /// invalidating things.
172 template <> class CGSCCAnalysisManagerModuleProxy::Result {
174 explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
175 : InnerAM(&InnerAM), G(&G) {}
177 /// Accessor for the analysis manager.
178 CGSCCAnalysisManager &getManager() { return *InnerAM; }
180 /// Handler for invalidation of the Module.
182 /// If the proxy analysis itself is preserved, then we assume that the set of
183 /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the
184 /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear
185 /// on the CGSCCAnalysisManager.
187 /// Regardless of whether this analysis is marked as preserved, all of the
188 /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based
189 /// on the set of preserved analyses.
190 bool invalidate(Module &M, const PreservedAnalyses &PA,
191 ModuleAnalysisManager::Invalidator &Inv);
194 CGSCCAnalysisManager *InnerAM;
198 /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
199 /// so it can pass the lazy call graph to the result.
201 CGSCCAnalysisManagerModuleProxy::Result
202 CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);
204 // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
206 extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
208 extern template class OuterAnalysisManagerProxy<
209 ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
211 /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
212 using ModuleAnalysisManagerCGSCCProxy =
213 OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
216 /// Support structure for SCC passes to communicate updates the call graph back
217 /// to the CGSCC pass manager infrsatructure.
219 /// The CGSCC pass manager runs SCC passes which are allowed to update the call
220 /// graph and SCC structures. This means the structure the pass manager works
221 /// on is mutating underneath it. In order to support that, there needs to be
222 /// careful communication about the precise nature and ramifications of these
223 /// updates to the pass management infrastructure.
225 /// All SCC passes will have to accept a reference to the management layer's
226 /// update result struct and use it to reflect the results of any CG updates
229 /// Passes which do not change the call graph structure in any way can just
230 /// ignore this argument to their run method.
231 struct CGSCCUpdateResult {
232 /// Worklist of the RefSCCs queued for processing.
234 /// When a pass refines the graph and creates new RefSCCs or causes them to
235 /// have a different shape or set of component SCCs it should add the RefSCCs
236 /// to this worklist so that we visit them in the refined form.
238 /// This worklist is in reverse post-order, as we pop off the back in order
239 /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
240 /// them in reverse post-order.
241 SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist;
243 /// Worklist of the SCCs queued for processing.
245 /// When a pass refines the graph and creates new SCCs or causes them to have
246 /// a different shape or set of component functions it should add the SCCs to
247 /// this worklist so that we visit them in the refined form.
249 /// Note that if the SCCs are part of a RefSCC that is added to the \c
250 /// RCWorklist, they don't need to be added here as visiting the RefSCC will
251 /// be sufficient to re-visit the SCCs within it.
253 /// This worklist is in reverse post-order, as we pop off the back in order
254 /// to observe SCCs in post-order. When adding SCCs, clients should add them
255 /// in reverse post-order.
256 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist;
258 /// The set of invalidated RefSCCs which should be skipped if they are found
259 /// in \c RCWorklist.
261 /// This is used to quickly prune out RefSCCs when they get deleted and
262 /// happen to already be on the worklist. We use this primarily to avoid
263 /// scanning the list and removing entries from it.
264 SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;
266 /// The set of invalidated SCCs which should be skipped if they are found
269 /// This is used to quickly prune out SCCs when they get deleted and happen
270 /// to already be on the worklist. We use this primarily to avoid scanning
271 /// the list and removing entries from it.
272 SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
274 /// If non-null, the updated current \c RefSCC being processed.
276 /// This is set when a graph refinement takes place an the "current" point in
277 /// the graph moves "down" or earlier in the post-order walk. This will often
278 /// cause the "current" RefSCC to be a newly created RefSCC object and the
279 /// old one to be added to the above worklist. When that happens, this
280 /// pointer is non-null and can be used to continue processing the "top" of
281 /// the post-order walk.
282 LazyCallGraph::RefSCC *UpdatedRC;
284 /// If non-null, the updated current \c SCC being processed.
286 /// This is set when a graph refinement takes place an the "current" point in
287 /// the graph moves "down" or earlier in the post-order walk. This will often
288 /// cause the "current" SCC to be a newly created SCC object and the old one
289 /// to be added to the above worklist. When that happens, this pointer is
290 /// non-null and can be used to continue processing the "top" of the
292 LazyCallGraph::SCC *UpdatedC;
294 /// Preserved analyses across SCCs.
296 /// We specifically want to allow CGSCC passes to mutate ancestor IR
297 /// (changing both the CG structure and the function IR itself). However,
298 /// this means we need to take special care to correctly mark what analyses
299 /// are preserved *across* SCCs. We have to track this out-of-band here
300 /// because within the main `PassManeger` infrastructure we need to mark
301 /// everything within an SCC as preserved in order to avoid repeatedly
302 /// invalidating the same analyses as we unnest pass managers and adaptors.
303 /// So we track the cross-SCC version of the preserved analyses here from any
304 /// code that does direct invalidation of SCC analyses, and then use it
305 /// whenever we move forward in the post-order walk of SCCs before running
306 /// passes over the new SCC.
307 PreservedAnalyses CrossSCCPA;
309 /// A hacky area where the inliner can retain history about inlining
310 /// decisions that mutated the call graph's SCC structure in order to avoid
311 /// infinite inlining. See the comments in the inliner's CG update logic.
313 /// FIXME: Keeping this here seems like a big layering issue, we should look
314 /// for a better technique.
315 SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
316 &InlinedInternalEdges;
319 /// The core module pass which does a post-order walk of the SCCs and
320 /// runs a CGSCC pass over each one.
322 /// Designed to allow composition of a CGSCCPass(Manager) and
323 /// a ModulePassManager. Note that this pass must be run with a module analysis
324 /// manager as it uses the LazyCallGraph analysis. It will also run the
325 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
326 /// pass over the module to enable a \c FunctionAnalysisManager to be used
327 /// within this run safely.
328 template <typename CGSCCPassT>
329 class ModuleToPostOrderCGSCCPassAdaptor
330 : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
332 explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
333 : Pass(std::move(Pass)) {}
335 // We have to explicitly define all the special member functions because MSVC
336 // refuses to generate them.
337 ModuleToPostOrderCGSCCPassAdaptor(
338 const ModuleToPostOrderCGSCCPassAdaptor &Arg)
341 ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
342 : Pass(std::move(Arg.Pass)) {}
344 friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
345 ModuleToPostOrderCGSCCPassAdaptor &RHS) {
346 std::swap(LHS.Pass, RHS.Pass);
349 ModuleToPostOrderCGSCCPassAdaptor &
350 operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
355 /// Runs the CGSCC pass across every SCC in the module.
356 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
362 /// A function to deduce a function pass type and wrap it in the
363 /// templated adaptor.
364 template <typename CGSCCPassT>
365 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
366 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
367 return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
370 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
372 /// When a module pass runs and triggers invalidation, both the CGSCC and
373 /// Function analysis manager proxies on the module get an invalidation event.
374 /// We don't want to fully duplicate responsibility for most of the
375 /// invalidation logic. Instead, this layer is only responsible for SCC-local
376 /// invalidation events. We work with the module's FunctionAnalysisManager to
377 /// invalidate function analyses.
378 class FunctionAnalysisManagerCGSCCProxy
379 : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
383 explicit Result() : FAM(nullptr) {}
384 explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
386 void updateFAM(FunctionAnalysisManager &FAM) { this->FAM = &FAM; }
387 /// Accessor for the analysis manager.
388 FunctionAnalysisManager &getManager() {
393 bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
394 CGSCCAnalysisManager::Invalidator &Inv);
397 FunctionAnalysisManager *FAM;
400 /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
401 Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
404 friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
406 static AnalysisKey Key;
409 extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
411 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
412 using CGSCCAnalysisManagerFunctionProxy =
413 OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
415 /// Helper to update the call graph after running a function pass.
417 /// Function passes can only mutate the call graph in specific ways. This
418 /// routine provides a helper that updates the call graph in those ways
419 /// including returning whether any changes were made and populating a CG
420 /// update result struct for the overall CGSCC walk.
421 LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
422 LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
423 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
424 FunctionAnalysisManager &FAM);
426 /// Helper to update the call graph after running a CGSCC pass.
428 /// CGSCC passes can only mutate the call graph in specific ways. This
429 /// routine provides a helper that updates the call graph in those ways
430 /// including returning whether any changes were made and populating a CG
431 /// update result struct for the overall CGSCC walk.
432 LazyCallGraph::SCC &updateCGAndAnalysisManagerForCGSCCPass(
433 LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
434 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
435 FunctionAnalysisManager &FAM);
437 /// Adaptor that maps from a SCC to its functions.
439 /// Designed to allow composition of a FunctionPass(Manager) and
440 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
441 /// to a \c CGSCCAnalysisManager it will run the
442 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
443 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
444 /// within this run safely.
445 template <typename FunctionPassT>
446 class CGSCCToFunctionPassAdaptor
447 : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
449 explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
450 : Pass(std::move(Pass)) {}
452 // We have to explicitly define all the special member functions because MSVC
453 // refuses to generate them.
454 CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
457 CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
458 : Pass(std::move(Arg.Pass)) {}
460 friend void swap(CGSCCToFunctionPassAdaptor &LHS,
461 CGSCCToFunctionPassAdaptor &RHS) {
462 std::swap(LHS.Pass, RHS.Pass);
465 CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
470 /// Runs the function pass across every function in the module.
471 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
472 LazyCallGraph &CG, CGSCCUpdateResult &UR) {
473 // Setup the function analysis manager from its proxy.
474 FunctionAnalysisManager &FAM =
475 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
477 SmallVector<LazyCallGraph::Node *, 4> Nodes;
478 for (LazyCallGraph::Node &N : C)
481 // The SCC may get split while we are optimizing functions due to deleting
482 // edges. If this happens, the current SCC can shift, so keep track of
483 // a pointer we can overwrite.
484 LazyCallGraph::SCC *CurrentC = &C;
486 LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
489 PreservedAnalyses PA = PreservedAnalyses::all();
490 for (LazyCallGraph::Node *N : Nodes) {
491 // Skip nodes from other SCCs. These may have been split out during
492 // processing. We'll eventually visit those SCCs and pick up the nodes
494 if (CG.lookupSCC(*N) != CurrentC)
497 Function &F = N->getFunction();
499 PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
500 if (!PI.runBeforePass<Function>(Pass, F))
503 PreservedAnalyses PassPA;
505 TimeTraceScope TimeScope(Pass.name());
506 PassPA = Pass.run(F, FAM);
509 PI.runAfterPass<Function>(Pass, F);
511 // We know that the function pass couldn't have invalidated any other
512 // function's analyses (that's the contract of a function pass), so
513 // directly handle the function analysis manager's invalidation here.
514 FAM.invalidate(F, PassPA);
516 // Then intersect the preserved set so that invalidation of module
517 // analyses will eventually occur when the module pass completes.
518 PA.intersect(std::move(PassPA));
520 // If the call graph hasn't been preserved, update it based on this
521 // function pass. This may also update the current SCC to point to
522 // a smaller, more refined SCC.
523 auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
524 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
525 CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
528 CG.lookupSCC(*N) == CurrentC &&
529 "Current SCC not updated to the SCC containing the current node!");
533 // By definition we preserve the proxy. And we preserve all analyses on
534 // Functions. This precludes *any* invalidation of function analyses by the
535 // proxy, but that's OK because we've taken care to invalidate analyses in
536 // the function analysis manager incrementally above.
537 PA.preserveSet<AllAnalysesOn<Function>>();
538 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
540 // We've also ensured that we updated the call graph along the way.
541 PA.preserve<LazyCallGraphAnalysis>();
550 /// A function to deduce a function pass type and wrap it in the
551 /// templated adaptor.
552 template <typename FunctionPassT>
553 CGSCCToFunctionPassAdaptor<FunctionPassT>
554 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
555 return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
558 /// A helper that repeats an SCC pass each time an indirect call is refined to
559 /// a direct call by that pass.
561 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
562 /// change shape, we may also want to repeat an SCC pass if it simply refines
563 /// an indirect call to a direct call, even if doing so does not alter the
564 /// shape of the graph. Note that this only pertains to direct calls to
565 /// functions where IPO across the SCC may be able to compute more precise
566 /// results. For intrinsics, we assume scalar optimizations already can fully
567 /// reason about them.
569 /// This repetition has the potential to be very large however, as each one
570 /// might refine a single call site. As a consequence, in practice we use an
571 /// upper bound on the number of repetitions to limit things.
572 template <typename PassT>
573 class DevirtSCCRepeatedPass
574 : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
576 explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
577 : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
579 /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
580 /// whenever an indirect call is refined.
581 PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
582 LazyCallGraph &CG, CGSCCUpdateResult &UR) {
583 PreservedAnalyses PA = PreservedAnalyses::all();
584 PassInstrumentation PI =
585 AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
587 // The SCC may be refined while we are running passes over it, so set up
588 // a pointer that we can update.
589 LazyCallGraph::SCC *C = &InitialC;
591 // Collect value handles for all of the indirect call sites.
592 SmallVector<WeakTrackingVH, 8> CallHandles;
594 // Struct to track the counts of direct and indirect calls in each function
601 // Put value handles on all of the indirect calls and return the number of
602 // direct calls for each function in the SCC.
603 auto ScanSCC = [](LazyCallGraph::SCC &C,
604 SmallVectorImpl<WeakTrackingVH> &CallHandles) {
605 assert(CallHandles.empty() && "Must start with a clear set of handles.");
607 SmallDenseMap<Function *, CallCount> CallCounts;
608 CallCount CountLocal = {0, 0};
609 for (LazyCallGraph::Node &N : C) {
611 CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
613 for (Instruction &I : instructions(N.getFunction()))
614 if (auto *CB = dyn_cast<CallBase>(&I)) {
615 if (CB->getCalledFunction()) {
619 CallHandles.push_back(WeakTrackingVH(&I));
627 // Populate the initial call handles and get the initial call counts.
628 auto CallCounts = ScanSCC(*C, CallHandles);
630 for (int Iteration = 0;; ++Iteration) {
632 if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
635 PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
637 if (UR.InvalidatedSCCs.count(C))
638 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
640 PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
642 // If the SCC structure has changed, bail immediately and let the outer
643 // CGSCC layer handle any iteration to reflect the refined structure.
644 if (UR.UpdatedC && UR.UpdatedC != C) {
645 PA.intersect(std::move(PassPA));
649 // Check that we didn't miss any update scenario.
650 assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
651 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
653 // Check whether any of the handles were devirtualized.
654 auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
657 auto *CB = dyn_cast<CallBase>(CallH);
661 // If the call is still indirect, leave it alone.
662 Function *F = CB->getCalledFunction();
666 LLVM_DEBUG(dbgs() << "Found devirtualized call from "
667 << CB->getParent()->getParent()->getName() << " to "
668 << F->getName() << "\n");
670 // We now have a direct call where previously we had an indirect call,
671 // so iterate to process this devirtualization site.
674 bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
676 // Rescan to build up a new set of handles and count how many direct
677 // calls remain. If we decide to iterate, this also sets up the input to
678 // the next iteration.
680 auto NewCallCounts = ScanSCC(*C, CallHandles);
682 // If we haven't found an explicit devirtualization already see if we
683 // have decreased the number of indirect calls and increased the number
684 // of direct calls for any function in the SCC. This can be fooled by all
685 // manner of transformations such as DCE and other things, but seems to
686 // work well in practice.
688 // Iterate over the keys in NewCallCounts, if Function also exists in
689 // CallCounts, make the check below.
690 for (auto &Pair : NewCallCounts) {
691 auto &CallCountNew = Pair.second;
692 auto CountIt = CallCounts.find(Pair.first);
693 if (CountIt != CallCounts.end()) {
694 const auto &CallCountOld = CountIt->second;
695 if (CallCountOld.Indirect > CallCountNew.Indirect &&
696 CallCountOld.Direct < CallCountNew.Direct) {
704 PA.intersect(std::move(PassPA));
708 // Otherwise, if we've already hit our max, we're done.
709 if (Iteration >= MaxIterations) {
711 dbgs() << "Found another devirtualization after hitting the max "
712 "number of repetitions ("
713 << MaxIterations << ") on SCC: " << *C << "\n");
714 PA.intersect(std::move(PassPA));
720 << "Repeating an SCC pass after finding a devirtualization in: " << *C
723 // Move over the new call counts in preparation for iterating.
724 CallCounts = std::move(NewCallCounts);
726 // Update the analysis manager with each run and intersect the total set
727 // of preserved analyses so we're ready to iterate.
728 AM.invalidate(*C, PassPA);
730 PA.intersect(std::move(PassPA));
733 // Note that we don't add any preserved entries here unlike a more normal
734 // "pass manager" because we only handle invalidation *between* iterations,
735 // not after the last iteration.
744 /// A function to deduce a function pass type and wrap it in the
745 /// templated adaptor.
746 template <typename PassT>
747 DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
749 return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
752 // Out-of-line implementation details for templates below this point.
754 template <typename CGSCCPassT>
756 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::run(Module &M,
757 ModuleAnalysisManager &AM) {
758 // Setup the CGSCC analysis manager from its proxy.
759 CGSCCAnalysisManager &CGAM =
760 AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
762 // Get the call graph for this module.
763 LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
765 // Get Function analysis manager from its proxy.
766 FunctionAnalysisManager &FAM =
767 AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M)->getManager();
769 // We keep worklists to allow us to push more work onto the pass manager as
770 // the passes are run.
771 SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
772 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
774 // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
775 // iterating off the worklists.
776 SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
777 SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
779 SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
780 InlinedInternalEdges;
782 CGSCCUpdateResult UR = {
783 RCWorklist, CWorklist, InvalidRefSCCSet, InvalidSCCSet,
784 nullptr, nullptr, PreservedAnalyses::all(), InlinedInternalEdges};
786 // Request PassInstrumentation from analysis manager, will use it to run
787 // instrumenting callbacks for the passes later.
788 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
790 PreservedAnalyses PA = PreservedAnalyses::all();
792 for (auto RCI = CG.postorder_ref_scc_begin(),
793 RCE = CG.postorder_ref_scc_end();
795 assert(RCWorklist.empty() &&
796 "Should always start with an empty RefSCC worklist");
797 // The postorder_ref_sccs range we are walking is lazily constructed, so
798 // we only push the first one onto the worklist. The worklist allows us
799 // to capture *new* RefSCCs created during transformations.
801 // We really want to form RefSCCs lazily because that makes them cheaper
802 // to update as the program is simplified and allows us to have greater
803 // cache locality as forming a RefSCC touches all the parts of all the
804 // functions within that RefSCC.
806 // We also eagerly increment the iterator to the next position because
807 // the CGSCC passes below may delete the current RefSCC.
808 RCWorklist.insert(&*RCI++);
811 LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
812 if (InvalidRefSCCSet.count(RC)) {
813 LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
817 assert(CWorklist.empty() &&
818 "Should always start with an empty SCC worklist");
820 LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
823 // The top of the worklist may *also* be the same SCC we just ran over
824 // (and invalidated for). Keep track of that last SCC we processed due
825 // to SCC update to avoid redundant processing when an SCC is both just
826 // updated itself and at the top of the worklist.
827 LazyCallGraph::SCC *LastUpdatedC = nullptr;
829 // Push the initial SCCs in reverse post-order as we'll pop off the
830 // back and so see this in post-order.
831 for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
832 CWorklist.insert(&C);
835 LazyCallGraph::SCC *C = CWorklist.pop_back_val();
836 // Due to call graph mutations, we may have invalid SCCs or SCCs from
837 // other RefSCCs in the worklist. The invalid ones are dead and the
838 // other RefSCCs should be queued above, so we just need to skip both
840 if (InvalidSCCSet.count(C)) {
841 LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
844 if (LastUpdatedC == C) {
845 LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
848 if (&C->getOuterRefSCC() != RC) {
849 LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
854 // Ensure we can proxy analysis updates from the CGSCC analysis manager
855 // into the the Function analysis manager by getting a proxy here.
856 // This also needs to update the FunctionAnalysisManager, as this may be
857 // the first time we see this SCC.
858 CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
861 // Each time we visit a new SCC pulled off the worklist,
862 // a transformation of a child SCC may have also modified this parent
863 // and invalidated analyses. So we invalidate using the update record's
864 // cross-SCC preserved set. This preserved set is intersected by any
865 // CGSCC pass that handles invalidation (primarily pass managers) prior
866 // to marking its SCC as preserved. That lets us track everything that
867 // might need invalidation across SCCs without excessive invalidations
870 // This essentially allows SCC passes to freely invalidate analyses
871 // of any ancestor SCC. If this becomes detrimental to successfully
872 // caching analyses, we could force each SCC pass to manually
873 // invalidate the analyses for any SCCs other than themselves which
874 // are mutated. However, that seems to lose the robustness of the
875 // pass-manager driven invalidation scheme.
876 CGAM.invalidate(*C, UR.CrossSCCPA);
879 // Check that we didn't miss any update scenario.
880 assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
881 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
882 assert(&C->getOuterRefSCC() == RC &&
883 "Processing an SCC in a different RefSCC!");
885 LastUpdatedC = UR.UpdatedC;
886 UR.UpdatedRC = nullptr;
887 UR.UpdatedC = nullptr;
889 // Check the PassInstrumentation's BeforePass callbacks before
890 // running the pass, skip its execution completely if asked to
891 // (callback returns false).
892 if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
895 PreservedAnalyses PassPA;
897 TimeTraceScope TimeScope(Pass.name());
898 PassPA = Pass.run(*C, CGAM, CG, UR);
901 if (UR.InvalidatedSCCs.count(C))
902 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
904 PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
906 // Update the SCC and RefSCC if necessary.
907 C = UR.UpdatedC ? UR.UpdatedC : C;
908 RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
911 // If we're updating the SCC, also update the FAM inside the proxy's
913 CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
917 // If the CGSCC pass wasn't able to provide a valid updated SCC,
918 // the current SCC may simply need to be skipped if invalid.
919 if (UR.InvalidatedSCCs.count(C)) {
920 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
923 // Check that we didn't miss any update scenario.
924 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
926 // We handle invalidating the CGSCC analysis manager's information
927 // for the (potentially updated) SCC here. Note that any other SCCs
928 // whose structure has changed should have been invalidated by
929 // whatever was updating the call graph. This SCC gets invalidated
930 // late as it contains the nodes that were actively being
932 CGAM.invalidate(*C, PassPA);
934 // Then intersect the preserved set so that invalidation of module
935 // analyses will eventually occur when the module pass completes.
936 // Also intersect with the cross-SCC preserved set to capture any
937 // cross-SCC invalidation.
938 UR.CrossSCCPA.intersect(PassPA);
939 PA.intersect(std::move(PassPA));
941 // The pass may have restructured the call graph and refined the
942 // current SCC and/or RefSCC. We need to update our current SCC and
943 // RefSCC pointers to follow these. Also, when the current SCC is
944 // refined, re-run the SCC pass over the newly refined SCC in order
945 // to observe the most precise SCC model available. This inherently
946 // cannot cycle excessively as it only happens when we split SCCs
947 // apart, at most converging on a DAG of single nodes.
948 // FIXME: If we ever start having RefSCC passes, we'll want to
949 // iterate there too.
952 << "Re-running SCC passes after a refinement of the "
954 << *UR.UpdatedC << "\n");
956 // Note that both `C` and `RC` may at this point refer to deleted,
957 // invalid SCC and RefSCCs respectively. But we will short circuit
958 // the processing when we check them in the loop above.
959 } while (UR.UpdatedC);
960 } while (!CWorklist.empty());
962 // We only need to keep internal inlined edge information within
963 // a RefSCC, clear it to save on space and let the next time we visit
964 // any of these functions have a fresh start.
965 InlinedInternalEdges.clear();
966 } while (!RCWorklist.empty());
969 // By definition we preserve the call garph, all SCC analyses, and the
970 // analysis proxies by handling them above and in any nested pass managers.
971 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
972 PA.preserve<LazyCallGraphAnalysis>();
973 PA.preserve<CGSCCAnalysisManagerModuleProxy>();
974 PA.preserve<FunctionAnalysisManagerModuleProxy>();
978 // Clear out the debug logging macro.
981 } // end namespace llvm
983 #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H