LLVM  9.0.0svn
CGSCCPassManager.h
Go to the documentation of this file.
1 //===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
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.
19 ///
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.
27 ///
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.
39 ///
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
47 ///
48 ///
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:
52 ///
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.
58 ///
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
62 /// post-order.
63 ///
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
68 /// mutates.
69 ///
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.
74 ///
75 /// The patterns used to ensure the goals of post-order visitation of the fully
76 /// refined graph:
77 ///
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.
81 ///
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.
85 ///
86 //===----------------------------------------------------------------------===//
87
88 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
89 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
90
97 #include "llvm/IR/CallSite.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"
104 #include <algorithm>
105 #include <cassert>
106 #include <utility>
107
108 namespace llvm {
109
110 struct CGSCCUpdateResult;
111 class Module;
112
113 // Allow debug logging in this inline function.
114 #define DEBUG_TYPE "cgscc"
115
116 /// Extern template declaration for the analysis set for this IR unit.
117 extern template class AllAnalysesOn<LazyCallGraph::SCC>;
118
119 extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
120
121 /// The CGSCC analysis manager.
122 ///
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 =
129
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.
133 template <>
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 &>;
141
142 /// The CGSCC pass manager.
143 ///
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 &>;
150
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();
162  }
163 };
164
165 /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
168
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.
173 public:
174  explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
175  : InnerAM(&InnerAM), G(&G) {}
176
177  /// Accessor for the analysis manager.
178  CGSCCAnalysisManager &getManager() { return *InnerAM; }
179
180  /// Handler for invalidation of the Module.
181  ///
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.
186  ///
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,
192
193 private:
194  CGSCCAnalysisManager *InnerAM;
195  LazyCallGraph *G;
196 };
197
198 /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
199 /// so it can pass the lazy call graph to the result.
200 template <>
203
204 // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
205 // template.
207
208 extern template class OuterAnalysisManagerProxy<
209  ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
210
211 /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
214  LazyCallGraph &>;
215
216 /// Support structure for SCC passes to communicate updates the call graph back
217 /// to the CGSCC pass manager infrsatructure.
218 ///
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.
224 ///
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
227 /// performed.
228 ///
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.
233  ///
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.
237  ///
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.
242
243  /// Worklist of the SCCs queued for processing.
244  ///
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.
248  ///
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.
252  ///
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.
257
258  /// The set of invalidated RefSCCs which should be skipped if they are found
259  /// in \c RCWorklist.
260  ///
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.
265
266  /// The set of invalidated SCCs which should be skipped if they are found
267  /// in \c CWorklist.
268  ///
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.
273
274  /// If non-null, the updated current \c RefSCC being processed.
275  ///
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.
283
284  /// If non-null, the updated current \c SCC being processed.
285  ///
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
291  /// post-order walk.
292  LazyCallGraph::SCC *UpdatedC;
293
294  /// A hacky area where the inliner can retain history about inlining
295  /// decisions that mutated the call graph's SCC structure in order to avoid
296  /// infinite inlining. See the comments in the inliner's CG update logic.
297  ///
298  /// FIXME: Keeping this here seems like a big layering issue, we should look
299  /// for a better technique.
302 };
303
304 /// The core module pass which does a post-order walk of the SCCs and
305 /// runs a CGSCC pass over each one.
306 ///
307 /// Designed to allow composition of a CGSCCPass(Manager) and
308 /// a ModulePassManager. Note that this pass must be run with a module analysis
309 /// manager as it uses the LazyCallGraph analysis. It will also run the
310 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
311 /// pass over the module to enable a \c FunctionAnalysisManager to be used
312 /// within this run safely.
313 template <typename CGSCCPassT>
316 public:
318  : Pass(std::move(Pass)) {}
319
320  // We have to explicitly define all the special member functions because MSVC
321  // refuses to generate them.
324  : Pass(Arg.Pass) {}
325
327  : Pass(std::move(Arg.Pass)) {}
328
331  std::swap(LHS.Pass, RHS.Pass);
332  }
333
336  swap(*this, RHS);
337  return *this;
338  }
339
340  /// Runs the CGSCC pass across every SCC in the module.
341  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
342  // Setup the CGSCC analysis manager from its proxy.
343  CGSCCAnalysisManager &CGAM =
345
346  // Get the call graph for this module.
347  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
348
349  // We keep worklists to allow us to push more work onto the pass manager as
350  // the passes are run.
353
354  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
355  // iterating off the worklists.
358
360  InlinedInternalEdges;
361
362  CGSCCUpdateResult UR = {RCWorklist, CWorklist, InvalidRefSCCSet,
363  InvalidSCCSet, nullptr, nullptr,
364  InlinedInternalEdges};
365
366  // Request PassInstrumentation from analysis manager, will use it to run
367  // instrumenting callbacks for the passes later.
369
371  CG.buildRefSCCs();
372  for (auto RCI = CG.postorder_ref_scc_begin(),
373  RCE = CG.postorder_ref_scc_end();
374  RCI != RCE;) {
375  assert(RCWorklist.empty() &&
377  // The postorder_ref_sccs range we are walking is lazily constructed, so
378  // we only push the first one onto the worklist. The worklist allows us
379  // to capture *new* RefSCCs created during transformations.
380  //
381  // We really want to form RefSCCs lazily because that makes them cheaper
382  // to update as the program is simplified and allows us to have greater
383  // cache locality as forming a RefSCC touches all the parts of all the
384  // functions within that RefSCC.
385  //
386  // We also eagerly increment the iterator to the next position because
387  // the CGSCC passes below may delete the current RefSCC.
388  RCWorklist.insert(&*RCI++);
389
390  do {
391  LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
392  if (InvalidRefSCCSet.count(RC)) {
393  LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
394  continue;
395  }
396
397  assert(CWorklist.empty() &&
399
400  LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
401  << "\n");
402
403  // Push the initial SCCs in reverse post-order as we'll pop off the
404  // back and so see this in post-order.
405  for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
406  CWorklist.insert(&C);
407
408  do {
409  LazyCallGraph::SCC *C = CWorklist.pop_back_val();
410  // Due to call graph mutations, we may have invalid SCCs or SCCs from
411  // other RefSCCs in the worklist. The invalid ones are dead and the
412  // other RefSCCs should be queued above, so we just need to skip both
413  // scenarios here.
414  if (InvalidSCCSet.count(C)) {
415  LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
416  continue;
417  }
418  if (&C->getOuterRefSCC() != RC) {
419  LLVM_DEBUG(dbgs()
420  << "Skipping an SCC that is now part of some other "
421  "RefSCC...\n");
422  continue;
423  }
424
425  do {
426  // Check that we didn't miss any update scenario.
427  assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
428  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
429  assert(&C->getOuterRefSCC() == RC &&
430  "Processing an SCC in a different RefSCC!");
431
432  UR.UpdatedRC = nullptr;
433  UR.UpdatedC = nullptr;
434
435  // Check the PassInstrumentation's BeforePass callbacks before
436  // running the pass, skip its execution completely if asked to
437  // (callback returns false).
438  if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
439  continue;
440
441  PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
442
443  if (UR.InvalidatedSCCs.count(C))
444  PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
445  else
446  PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
447
448  // Update the SCC and RefSCC if necessary.
449  C = UR.UpdatedC ? UR.UpdatedC : C;
450  RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
451
452  // If the CGSCC pass wasn't able to provide a valid updated SCC,
453  // the current SCC may simply need to be skipped if invalid.
454  if (UR.InvalidatedSCCs.count(C)) {
455  LLVM_DEBUG(dbgs()
456  << "Skipping invalidated root or island SCC!\n");
457  break;
458  }
459  // Check that we didn't miss any update scenario.
460  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
461
462  // We handle invalidating the CGSCC analysis manager's information
463  // for the (potentially updated) SCC here. Note that any other SCCs
464  // whose structure has changed should have been invalidated by
465  // whatever was updating the call graph. This SCC gets invalidated
466  // late as it contains the nodes that were actively being
467  // processed.
468  CGAM.invalidate(*C, PassPA);
469
470  // Then intersect the preserved set so that invalidation of module
471  // analyses will eventually occur when the module pass completes.
472  PA.intersect(std::move(PassPA));
473
474  // The pass may have restructured the call graph and refined the
475  // current SCC and/or RefSCC. We need to update our current SCC and
476  // RefSCC pointers to follow these. Also, when the current SCC is
477  // refined, re-run the SCC pass over the newly refined SCC in order
478  // to observe the most precise SCC model available. This inherently
479  // cannot cycle excessively as it only happens when we split SCCs
480  // apart, at most converging on a DAG of single nodes.
481  // FIXME: If we ever start having RefSCC passes, we'll want to
482  // iterate there too.
483  if (UR.UpdatedC)
484  LLVM_DEBUG(dbgs()
485  << "Re-running SCC passes after a refinement of the "
486  "current SCC: "
487  << *UR.UpdatedC << "\n");
488
489  // Note that both C and RC may at this point refer to deleted,
490  // invalid SCC and RefSCCs respectively. But we will short circuit
491  // the processing when we check them in the loop above.
492  } while (UR.UpdatedC);
493  } while (!CWorklist.empty());
494
495  // We only need to keep internal inlined edge information within
496  // a RefSCC, clear it to save on space and let the next time we visit
497  // any of these functions have a fresh start.
498  InlinedInternalEdges.clear();
499  } while (!RCWorklist.empty());
500  }
501
502  // By definition we preserve the call garph, all SCC analyses, and the
503  // analysis proxies by handling them above and in any nested pass managers.
504  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
505  PA.preserve<LazyCallGraphAnalysis>();
506  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
507  PA.preserve<FunctionAnalysisManagerModuleProxy>();
508  return PA;
509  }
510
511 private:
512  CGSCCPassT Pass;
513 };
514
515 /// A function to deduce a function pass type and wrap it in the
517 template <typename CGSCCPassT>
521 }
522
523 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
524 ///
525 /// When a module pass runs and triggers invalidation, both the CGSCC and
526 /// Function analysis manager proxies on the module get an invalidation event.
527 /// We don't want to fully duplicate responsibility for most of the
528 /// invalidation logic. Instead, this layer is only responsible for SCC-local
529 /// invalidation events. We work with the module's FunctionAnalysisManager to
530 /// invalidate function analyses.
532  : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
533 public:
534  class Result {
535  public:
536  explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
537
538  /// Accessor for the analysis manager.
540
541  bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
543
544  private:
546  };
547
548  /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
549  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
550
551 private:
553
554  static AnalysisKey Key;
555 };
556
558
559 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
562
563 /// Helper to update the call graph after running a function pass.
564 ///
565 /// Function passes can only mutate the call graph in specific ways. This
566 /// routine provides a helper that updates the call graph in those ways
567 /// including returning whether any changes were made and populating a CG
568 /// update result struct for the overall CGSCC walk.
570  LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
571  CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
572
573 /// Adaptor that maps from a SCC to its functions.
574 ///
575 /// Designed to allow composition of a FunctionPass(Manager) and
576 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
577 /// to a \c CGSCCAnalysisManager it will run the
578 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
579 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
580 /// within this run safely.
581 template <typename FunctionPassT>
584 public:
586  : Pass(std::move(Pass)) {}
587
588  // We have to explicitly define all the special member functions because MSVC
589  // refuses to generate them.
591  : Pass(Arg.Pass) {}
592
594  : Pass(std::move(Arg.Pass)) {}
595
598  std::swap(LHS.Pass, RHS.Pass);
599  }
600
602  swap(*this, RHS);
603  return *this;
604  }
605
606  /// Runs the function pass across every function in the module.
607  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
608  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
609  // Setup the function analysis manager from its proxy.
612
614  for (LazyCallGraph::Node &N : C)
615  Nodes.push_back(&N);
616
617  // The SCC may get split while we are optimizing functions due to deleting
618  // edges. If this happens, the current SCC can shift, so keep track of
619  // a pointer we can overwrite.
620  LazyCallGraph::SCC *CurrentC = &C;
621
622  LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
623  << "\n");
624
626  for (LazyCallGraph::Node *N : Nodes) {
627  // Skip nodes from other SCCs. These may have been split out during
628  // processing. We'll eventually visit those SCCs and pick up the nodes
629  // there.
630  if (CG.lookupSCC(*N) != CurrentC)
631  continue;
632
633  Function &F = N->getFunction();
634
636  if (!PI.runBeforePass<Function>(Pass, F))
637  continue;
638
639  PreservedAnalyses PassPA = Pass.run(F, FAM);
640
641  PI.runAfterPass<Function>(Pass, F);
642
643  // We know that the function pass couldn't have invalidated any other
644  // function's analyses (that's the contract of a function pass), so
645  // directly handle the function analysis manager's invalidation here.
646  FAM.invalidate(F, PassPA);
647
648  // Then intersect the preserved set so that invalidation of module
649  // analyses will eventually occur when the module pass completes.
650  PA.intersect(std::move(PassPA));
651
652  // If the call graph hasn't been preserved, update it based on this
653  // function pass. This may also update the current SCC to point to
654  // a smaller, more refined SCC.
655  auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
656  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
657  CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
658  AM, UR);
659  assert(
660  CG.lookupSCC(*N) == CurrentC &&
661  "Current SCC not updated to the SCC containing the current node!");
662  }
663  }
664
665  // By definition we preserve the proxy. And we preserve all analyses on
666  // Functions. This precludes *any* invalidation of function analyses by the
667  // proxy, but that's OK because we've taken care to invalidate analyses in
668  // the function analysis manager incrementally above.
671
672  // We've also ensured that we updated the call graph along the way.
674
675  return PA;
676  }
677
678 private:
679  FunctionPassT Pass;
680 };
681
682 /// A function to deduce a function pass type and wrap it in the
684 template <typename FunctionPassT>
688 }
689
690 /// A helper that repeats an SCC pass each time an indirect call is refined to
691 /// a direct call by that pass.
692 ///
693 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
694 /// change shape, we may also want to repeat an SCC pass if it simply refines
695 /// an indirect call to a direct call, even if doing so does not alter the
696 /// shape of the graph. Note that this only pertains to direct calls to
697 /// functions where IPO across the SCC may be able to compute more precise
698 /// results. For intrinsics, we assume scalar optimizations already can fully
700 ///
701 /// This repetition has the potential to be very large however, as each one
702 /// might refine a single call site. As a consequence, in practice we use an
703 /// upper bound on the number of repetitions to limit things.
704 template <typename PassT>
706  : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
707 public:
709  : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
710
711  /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
712  /// whenever an indirect call is refined.
713  PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
714  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
717  AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
718
719  // The SCC may be refined while we are running passes over it, so set up
720  // a pointer that we can update.
721  LazyCallGraph::SCC *C = &InitialC;
722
723  // Collect value handles for all of the indirect call sites.
724  SmallVector<WeakTrackingVH, 8> CallHandles;
725
726  // Struct to track the counts of direct and indirect calls in each function
727  // of the SCC.
728  struct CallCount {
729  int Direct;
730  int Indirect;
731  };
732
733  // Put value handles on all of the indirect calls and return the number of
734  // direct calls for each function in the SCC.
735  auto ScanSCC = [](LazyCallGraph::SCC &C,
736  SmallVectorImpl<WeakTrackingVH> &CallHandles) {
738
739  SmallVector<CallCount, 4> CallCounts;
740  for (LazyCallGraph::Node &N : C) {
741  CallCounts.push_back({0, 0});
742  CallCount &Count = CallCounts.back();
743  for (Instruction &I : instructions(N.getFunction()))
744  if (auto CS = CallSite(&I)) {
745  if (CS.getCalledFunction()) {
746  ++Count.Direct;
747  } else {
748  ++Count.Indirect;
749  CallHandles.push_back(WeakTrackingVH(&I));
750  }
751  }
752  }
753
754  return CallCounts;
755  };
756
757  // Populate the initial call handles and get the initial call counts.
758  auto CallCounts = ScanSCC(*C, CallHandles);
759
760  for (int Iteration = 0;; ++Iteration) {
761
762  if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
763  continue;
764
765  PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
766
767  if (UR.InvalidatedSCCs.count(C))
768  PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
769  else
770  PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
771
772  // If the SCC structure has changed, bail immediately and let the outer
773  // CGSCC layer handle any iteration to reflect the refined structure.
774  if (UR.UpdatedC && UR.UpdatedC != C) {
775  PA.intersect(std::move(PassPA));
776  break;
777  }
778
779  // Check that we didn't miss any update scenario.
780  assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
781  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
782  assert((int)CallCounts.size() == C->size() &&
783  "Cannot have changed the size of the SCC!");
784
785  // Check whether any of the handles were devirtualized.
786  auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
787  if (!CallH)
788  return false;
789  auto CS = CallSite(CallH);
790  if (!CS)
791  return false;
792
793  // If the call is still indirect, leave it alone.
794  Function *F = CS.getCalledFunction();
795  if (!F)
796  return false;
797
798  LLVM_DEBUG(dbgs() << "Found devirutalized call from "
799  << CS.getParent()->getParent()->getName() << " to "
800  << F->getName() << "\n");
801
802  // We now have a direct call where previously we had an indirect call,
803  // so iterate to process this devirtualization site.
804  return true;
805  };
806  bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
807
808  // Rescan to build up a new set of handles and count how many direct
809  // calls remain. If we decide to iterate, this also sets up the input to
810  // the next iteration.
811  CallHandles.clear();
812  auto NewCallCounts = ScanSCC(*C, CallHandles);
813
814  // If we haven't found an explicit devirtualization already see if we
815  // have decreased the number of indirect calls and increased the number
816  // of direct calls for any function in the SCC. This can be fooled by all
817  // manner of transformations such as DCE and other things, but seems to
818  // work well in practice.
819  if (!Devirt)
820  for (int i = 0, Size = C->size(); i < Size; ++i)
821  if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
822  CallCounts[i].Direct < NewCallCounts[i].Direct) {
823  Devirt = true;
824  break;
825  }
826
827  if (!Devirt) {
828  PA.intersect(std::move(PassPA));
829  break;
830  }
831
832  // Otherwise, if we've already hit our max, we're done.
833  if (Iteration >= MaxIterations) {
834  LLVM_DEBUG(
835  dbgs() << "Found another devirtualization after hitting the max "
836  "number of repetitions ("
837  << MaxIterations << ") on SCC: " << *C << "\n");
838  PA.intersect(std::move(PassPA));
839  break;
840  }
841
842  LLVM_DEBUG(
843  dbgs()
844  << "Repeating an SCC pass after finding a devirtualization in: " << *C
845  << "\n");
846
847  // Move over the new call counts in preparation for iterating.
848  CallCounts = std::move(NewCallCounts);
849
850  // Update the analysis manager with each run and intersect the total set
851  // of preserved analyses so we're ready to iterate.
852  AM.invalidate(*C, PassPA);
853  PA.intersect(std::move(PassPA));
854  }
855
856  // Note that we don't add any preserved entries here unlike a more normal
857  // "pass manager" because we only handle invalidation *between* iterations,
858  // not after the last iteration.
859  return PA;
860  }
861
862 private:
863  PassT Pass;
864  int MaxIterations;
865 };
866
867 /// A function to deduce a function pass type and wrap it in the
869 template <typename PassT>
871  int MaxIterations) {
872  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
873 }
874
875 // Clear out the debug logging macro.
876 #undef DEBUG_TYPE
877
878 } // end namespace llvm
879
880 #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
uint64_t CallInst * C
This file provides a priority worklist.
PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Runs the wrapped pass up to MaxIterations on the SCC, iterating whenever an indirect call is refined...
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SmallPriorityWorklist< LazyCallGraph::RefSCC *, 1 > & RCWorklist
Worklist of the RefSCCs queued for processing.
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
Definition: PassManager.h:225
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
LazyCallGraph::SCC & updateCGAndAnalysisManagerForFunctionPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR)
Helper to update the call graph after running a function pass.
SCC * lookupSCC(Node &N) const
Lookup a function&#39;s SCC in the graph.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, typename AnalysisManager< IRUnitT, ExtraArgTs... >::Invalidator &Inv)
Handler for invalidation of the outer IR unit, IRUnitT.
Implements a lazy call graph analysis and related passes for the new pass manager.
A function to deduce a function pass type and wrap it in the templated adaptor.
A function to deduce a function pass type and wrap it in the templated adaptor.
bool empty() const
Determine if the PriorityWorklist is empty or not.
F(f)
A utility pass template to force an analysis result to be available.
Definition: PassManager.h:1348
Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
A proxy from a FunctionAnalysisManager to an SCC.
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
RefSCC & getOuterRefSCC() const
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Runs the function pass across every function in the module.
Definition: BitVector.h:937
LazyCallGraph::SCC * UpdatedC
If non-null, the updated current SCC being processed.
iterator begin() const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
postorder_ref_scc_iterator postorder_ref_scc_begin()
AnalysisManagerT & getManager()
Accessor for the analysis manager.
Definition: PassManager.h:1072
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:266
Key
A RefSCC of the call graph.
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:181
AnalysisManager< LazyCallGraph::SCC, LazyCallGraph & > CGSCCAnalysisManager
The CGSCC analysis manager.
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:365
A lazily constructed view of the call graph of a module.
bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const
BeforePass instrumentation point - takes Pass instance to be executed and constant reference to IR it...
static cl::opt< unsigned > MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4))
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
The core module pass which does a post-order walk of the SCCs and runs a CGSCC pass over each one...
SmallPtrSetImpl< LazyCallGraph::RefSCC * > & InvalidatedRefSCCs
The set of invalidated RefSCCs which should be skipped if they are found in RCWorklist.
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:382
LazyCallGraph::RefSCC * UpdatedRC
If non-null, the updated current RefSCC being processed.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
FunctionAnalysisManager & getManager()
Accessor for the analysis manager.
iterator end() const
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
A node in the call graph.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
DevirtSCCRepeatedPass< PassT > createDevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
A function to deduce a function pass type and wrap it in the templated adaptor.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
SmallPriorityWorklist< LazyCallGraph::SCC *, 1 > & CWorklist
Worklist of the SCCs queued for processing.
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:574
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Runs the CGSCC pass across every SCC in the module.
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition: PassManager.h:1013
print lazy value Lazy Value Info Printer Pass
CGSCCAnalysisManager & getManager()
Accessor for the analysis manager.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void runAfterPass(const PassT &Pass, const IRUnitT &IR) const
AfterPass instrumentation point - takes Pass instance that has just been executed and constant refere...
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1153
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
void runAfterPassInvalidated(const PassT &Pass) const
AfterPassInvalidated instrumentation point - takes Pass instance that has just been executed...
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:1100
const DataFlowGraph & G
Definition: RDFGraph.cpp:210
void invalidate(IRUnitT &IR)
Invalidate a specific analysis pass for an IR module.
Definition: PassManager.h:841
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:267
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
A helper that repeats an SCC pass each time an indirect call is refined to a direct call by that pass...
Adaptor that maps from a SCC to its functions.
Manages a sequence of passes over a particular unit of IR.
Definition: PassManager.h:457
Definition: SmallVector.h:55
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
uint32_t Size
Definition: Profile.cpp:46
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&... Args)
Run this pass over some unit of IR.
Definition: PassManager.h:1357
An analysis pass which computes the call graph for a module.
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &)
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:641
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
An SCC of the call graph.
DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
inst_range instructions(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
This class provides instrumentation entry points for the Pass Manager, doing calls to callbacks regis...
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
postorder_ref_scc_iterator postorder_ref_scc_end()
SmallDenseSet< std::pair< LazyCallGraph::Node *, LazyCallGraph::SCC * >, 4 > & InlinedInternalEdges
A hacky area where the inliner can retain history about inlining decisions that mutated the call grap...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1037