LLVM  9.0.0svn
CGSCCPassManager.h
Go to the documentation of this file.
1 //===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
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.
20 ///
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.
28 ///
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.
40 ///
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
47 /// addressed.
48 ///
49 ///
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:
53 ///
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.
59 ///
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
63 /// post-order.
64 ///
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
69 /// mutates.
70 ///
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.
75 ///
76 /// The patterns used to ensure the goals of post-order visitation of the fully
77 /// refined graph:
78 ///
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.
82 ///
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.
86 ///
87 //===----------------------------------------------------------------------===//
88 
89 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
90 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
91 
92 #include "llvm/ADT/DenseSet.h"
94 #include "llvm/ADT/STLExtras.h"
95 #include "llvm/ADT/SmallPtrSet.h"
96 #include "llvm/ADT/SmallVector.h"
98 #include "llvm/IR/CallSite.h"
99 #include "llvm/IR/Function.h"
100 #include "llvm/IR/InstIterator.h"
101 #include "llvm/IR/PassManager.h"
102 #include "llvm/IR/ValueHandle.h"
103 #include "llvm/Support/Debug.h"
105 #include <algorithm>
106 #include <cassert>
107 #include <utility>
108 
109 namespace llvm {
110 
111 struct CGSCCUpdateResult;
112 class Module;
113 
114 // Allow debug logging in this inline function.
115 #define DEBUG_TYPE "cgscc"
116 
117 /// Extern template declaration for the analysis set for this IR unit.
118 extern template class AllAnalysesOn<LazyCallGraph::SCC>;
119 
120 extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
121 
122 /// The CGSCC analysis manager.
123 ///
124 /// See the documentation for the AnalysisManager template for detail
125 /// documentation. This type serves as a convenient way to refer to this
126 /// construct in the adaptors and proxies used to integrate this into the larger
127 /// pass manager infrastructure.
128 using CGSCCAnalysisManager =
130 
131 // Explicit specialization and instantiation declarations for the pass manager.
132 // See the comments on the definition of the specialization for details on how
133 // it differs from the primary template.
134 template <>
137  CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
138  CGSCCAnalysisManager &AM,
139  LazyCallGraph &G, CGSCCUpdateResult &UR);
140 extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
141  LazyCallGraph &, CGSCCUpdateResult &>;
142 
143 /// The CGSCC pass manager.
144 ///
145 /// See the documentation for the PassManager template for details. It runs
146 /// a sequence of SCC passes over each SCC that the manager is run over. This
147 /// type serves as a convenient way to refer to this construct.
148 using CGSCCPassManager =
149  PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
150  CGSCCUpdateResult &>;
151 
152 /// An explicit specialization of the require analysis template pass.
153 template <typename AnalysisT>
154 struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager,
155  LazyCallGraph &, CGSCCUpdateResult &>
156  : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
157  CGSCCAnalysisManager, LazyCallGraph &,
158  CGSCCUpdateResult &>> {
159  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
160  LazyCallGraph &CG, CGSCCUpdateResult &) {
161  (void)AM.template getResult<AnalysisT>(C, CG);
162  return PreservedAnalyses::all();
163  }
164 };
165 
166 /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
169 
170 /// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
171 /// it can have access to the call graph in order to walk all the SCCs when
172 /// invalidating things.
174 public:
175  explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
176  : InnerAM(&InnerAM), G(&G) {}
177 
178  /// Accessor for the analysis manager.
179  CGSCCAnalysisManager &getManager() { return *InnerAM; }
180 
181  /// Handler for invalidation of the Module.
182  ///
183  /// If the proxy analysis itself is preserved, then we assume that the set of
184  /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the
185  /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear
186  /// on the CGSCCAnalysisManager.
187  ///
188  /// Regardless of whether this analysis is marked as preserved, all of the
189  /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based
190  /// on the set of preserved analyses.
191  bool invalidate(Module &M, const PreservedAnalyses &PA,
193 
194 private:
195  CGSCCAnalysisManager *InnerAM;
196  LazyCallGraph *G;
197 };
198 
199 /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
200 /// so it can pass the lazy call graph to the result.
201 template <>
204 
205 // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
206 // template.
208 
209 extern template class OuterAnalysisManagerProxy<
210  ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
211 
212 /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
215  LazyCallGraph &>;
216 
217 /// Support structure for SCC passes to communicate updates the call graph back
218 /// to the CGSCC pass manager infrsatructure.
219 ///
220 /// The CGSCC pass manager runs SCC passes which are allowed to update the call
221 /// graph and SCC structures. This means the structure the pass manager works
222 /// on is mutating underneath it. In order to support that, there needs to be
223 /// careful communication about the precise nature and ramifications of these
224 /// updates to the pass management infrastructure.
225 ///
226 /// All SCC passes will have to accept a reference to the management layer's
227 /// update result struct and use it to reflect the results of any CG updates
228 /// performed.
229 ///
230 /// Passes which do not change the call graph structure in any way can just
231 /// ignore this argument to their run method.
232 struct CGSCCUpdateResult {
233  /// Worklist of the RefSCCs queued for processing.
234  ///
235  /// When a pass refines the graph and creates new RefSCCs or causes them to
236  /// have a different shape or set of component SCCs it should add the RefSCCs
237  /// to this worklist so that we visit them in the refined form.
238  ///
239  /// This worklist is in reverse post-order, as we pop off the back in order
240  /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
241  /// them in reverse post-order.
243 
244  /// Worklist of the SCCs queued for processing.
245  ///
246  /// When a pass refines the graph and creates new SCCs or causes them to have
247  /// a different shape or set of component functions it should add the SCCs to
248  /// this worklist so that we visit them in the refined form.
249  ///
250  /// Note that if the SCCs are part of a RefSCC that is added to the \c
251  /// RCWorklist, they don't need to be added here as visiting the RefSCC will
252  /// be sufficient to re-visit the SCCs within it.
253  ///
254  /// This worklist is in reverse post-order, as we pop off the back in order
255  /// to observe SCCs in post-order. When adding SCCs, clients should add them
256  /// in reverse post-order.
258 
259  /// The set of invalidated RefSCCs which should be skipped if they are found
260  /// in \c RCWorklist.
261  ///
262  /// This is used to quickly prune out RefSCCs when they get deleted and
263  /// happen to already be on the worklist. We use this primarily to avoid
264  /// scanning the list and removing entries from it.
266 
267  /// The set of invalidated SCCs which should be skipped if they are found
268  /// in \c CWorklist.
269  ///
270  /// This is used to quickly prune out SCCs when they get deleted and happen
271  /// to already be on the worklist. We use this primarily to avoid scanning
272  /// the list and removing entries from it.
274 
275  /// If non-null, the updated current \c RefSCC being processed.
276  ///
277  /// This is set when a graph refinement takes place an the "current" point in
278  /// the graph moves "down" or earlier in the post-order walk. This will often
279  /// cause the "current" RefSCC to be a newly created RefSCC object and the
280  /// old one to be added to the above worklist. When that happens, this
281  /// pointer is non-null and can be used to continue processing the "top" of
282  /// the post-order walk.
284 
285  /// If non-null, the updated current \c SCC being processed.
286  ///
287  /// This is set when a graph refinement takes place an the "current" point in
288  /// the graph moves "down" or earlier in the post-order walk. This will often
289  /// cause the "current" SCC to be a newly created SCC object and the old one
290  /// to be added to the above worklist. When that happens, this pointer is
291  /// non-null and can be used to continue processing the "top" of the
292  /// post-order walk.
293  LazyCallGraph::SCC *UpdatedC;
294 
295  /// A hacky area where the inliner can retain history about inlining
296  /// decisions that mutated the call graph's SCC structure in order to avoid
297  /// infinite inlining. See the comments in the inliner's CG update logic.
298  ///
299  /// FIXME: Keeping this here seems like a big layering issue, we should look
300  /// for a better technique.
303 };
304 
305 /// The core module pass which does a post-order walk of the SCCs and
306 /// runs a CGSCC pass over each one.
307 ///
308 /// Designed to allow composition of a CGSCCPass(Manager) and
309 /// a ModulePassManager. Note that this pass must be run with a module analysis
310 /// manager as it uses the LazyCallGraph analysis. It will also run the
311 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
312 /// pass over the module to enable a \c FunctionAnalysisManager to be used
313 /// within this run safely.
314 template <typename CGSCCPassT>
316  : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
317 public:
319  : Pass(std::move(Pass)) {}
320 
321  // We have to explicitly define all the special member functions because MSVC
322  // refuses to generate them.
325  : Pass(Arg.Pass) {}
326 
328  : Pass(std::move(Arg.Pass)) {}
329 
332  std::swap(LHS.Pass, RHS.Pass);
333  }
334 
337  swap(*this, RHS);
338  return *this;
339  }
340 
341  /// Runs the CGSCC pass across every SCC in the module.
342  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
343  // Setup the CGSCC analysis manager from its proxy.
344  CGSCCAnalysisManager &CGAM =
346 
347  // Get the call graph for this module.
348  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
349 
350  // We keep worklists to allow us to push more work onto the pass manager as
351  // the passes are run.
354 
355  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
356  // iterating off the worklists.
359 
361  InlinedInternalEdges;
362 
363  CGSCCUpdateResult UR = {RCWorklist, CWorklist, InvalidRefSCCSet,
364  InvalidSCCSet, nullptr, nullptr,
365  InlinedInternalEdges};
366 
367  // Request PassInstrumentation from analysis manager, will use it to run
368  // instrumenting callbacks for the passes later.
370 
372  CG.buildRefSCCs();
373  for (auto RCI = CG.postorder_ref_scc_begin(),
374  RCE = CG.postorder_ref_scc_end();
375  RCI != RCE;) {
376  assert(RCWorklist.empty() &&
377  "Should always start with an empty RefSCC worklist");
378  // The postorder_ref_sccs range we are walking is lazily constructed, so
379  // we only push the first one onto the worklist. The worklist allows us
380  // to capture *new* RefSCCs created during transformations.
381  //
382  // We really want to form RefSCCs lazily because that makes them cheaper
383  // to update as the program is simplified and allows us to have greater
384  // cache locality as forming a RefSCC touches all the parts of all the
385  // functions within that RefSCC.
386  //
387  // We also eagerly increment the iterator to the next position because
388  // the CGSCC passes below may delete the current RefSCC.
389  RCWorklist.insert(&*RCI++);
390 
391  do {
392  LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
393  if (InvalidRefSCCSet.count(RC)) {
394  LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
395  continue;
396  }
397 
398  assert(CWorklist.empty() &&
399  "Should always start with an empty SCC worklist");
400 
401  LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
402  << "\n");
403 
404  // Push the initial SCCs in reverse post-order as we'll pop off the
405  // back and so see this in post-order.
406  for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
407  CWorklist.insert(&C);
408 
409  do {
410  LazyCallGraph::SCC *C = CWorklist.pop_back_val();
411  // Due to call graph mutations, we may have invalid SCCs or SCCs from
412  // other RefSCCs in the worklist. The invalid ones are dead and the
413  // other RefSCCs should be queued above, so we just need to skip both
414  // scenarios here.
415  if (InvalidSCCSet.count(C)) {
416  LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
417  continue;
418  }
419  if (&C->getOuterRefSCC() != RC) {
420  LLVM_DEBUG(dbgs()
421  << "Skipping an SCC that is now part of some other "
422  "RefSCC...\n");
423  continue;
424  }
425 
426  do {
427  // Check that we didn't miss any update scenario.
428  assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
429  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
430  assert(&C->getOuterRefSCC() == RC &&
431  "Processing an SCC in a different RefSCC!");
432 
433  UR.UpdatedRC = nullptr;
434  UR.UpdatedC = nullptr;
435 
436  // Check the PassInstrumentation's BeforePass callbacks before
437  // running the pass, skip its execution completely if asked to
438  // (callback returns false).
439  if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
440  continue;
441 
442  PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
443 
444  if (UR.InvalidatedSCCs.count(C))
445  PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
446  else
447  PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
448 
449  // Update the SCC and RefSCC if necessary.
450  C = UR.UpdatedC ? UR.UpdatedC : C;
451  RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
452 
453  // If the CGSCC pass wasn't able to provide a valid updated SCC,
454  // the current SCC may simply need to be skipped if invalid.
455  if (UR.InvalidatedSCCs.count(C)) {
456  LLVM_DEBUG(dbgs()
457  << "Skipping invalidated root or island SCC!\n");
458  break;
459  }
460  // Check that we didn't miss any update scenario.
461  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
462 
463  // We handle invalidating the CGSCC analysis manager's information
464  // for the (potentially updated) SCC here. Note that any other SCCs
465  // whose structure has changed should have been invalidated by
466  // whatever was updating the call graph. This SCC gets invalidated
467  // late as it contains the nodes that were actively being
468  // processed.
469  CGAM.invalidate(*C, PassPA);
470 
471  // Then intersect the preserved set so that invalidation of module
472  // analyses will eventually occur when the module pass completes.
473  PA.intersect(std::move(PassPA));
474 
475  // The pass may have restructured the call graph and refined the
476  // current SCC and/or RefSCC. We need to update our current SCC and
477  // RefSCC pointers to follow these. Also, when the current SCC is
478  // refined, re-run the SCC pass over the newly refined SCC in order
479  // to observe the most precise SCC model available. This inherently
480  // cannot cycle excessively as it only happens when we split SCCs
481  // apart, at most converging on a DAG of single nodes.
482  // FIXME: If we ever start having RefSCC passes, we'll want to
483  // iterate there too.
484  if (UR.UpdatedC)
485  LLVM_DEBUG(dbgs()
486  << "Re-running SCC passes after a refinement of the "
487  "current SCC: "
488  << *UR.UpdatedC << "\n");
489 
490  // Note that both `C` and `RC` may at this point refer to deleted,
491  // invalid SCC and RefSCCs respectively. But we will short circuit
492  // the processing when we check them in the loop above.
493  } while (UR.UpdatedC);
494  } while (!CWorklist.empty());
495 
496  // We only need to keep internal inlined edge information within
497  // a RefSCC, clear it to save on space and let the next time we visit
498  // any of these functions have a fresh start.
499  InlinedInternalEdges.clear();
500  } while (!RCWorklist.empty());
501  }
502 
503  // By definition we preserve the call garph, all SCC analyses, and the
504  // analysis proxies by handling them above and in any nested pass managers.
505  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
506  PA.preserve<LazyCallGraphAnalysis>();
507  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
508  PA.preserve<FunctionAnalysisManagerModuleProxy>();
509  return PA;
510  }
511 
512 private:
513  CGSCCPassT Pass;
514 };
515 
516 /// A function to deduce a function pass type and wrap it in the
517 /// templated adaptor.
518 template <typename CGSCCPassT>
521  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
522 }
523 
524 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
525 ///
526 /// When a module pass runs and triggers invalidation, both the CGSCC and
527 /// Function analysis manager proxies on the module get an invalidation event.
528 /// We don't want to fully duplicate responsibility for most of the
529 /// invalidation logic. Instead, this layer is only responsible for SCC-local
530 /// invalidation events. We work with the module's FunctionAnalysisManager to
531 /// invalidate function analyses.
533  : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
534 public:
535  class Result {
536  public:
537  explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
538 
539  /// Accessor for the analysis manager.
541 
542  bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
544 
545  private:
547  };
548 
549  /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
550  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
551 
552 private:
554 
555  static AnalysisKey Key;
556 };
557 
559 
560 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
563 
564 /// Helper to update the call graph after running a function pass.
565 ///
566 /// Function passes can only mutate the call graph in specific ways. This
567 /// routine provides a helper that updates the call graph in those ways
568 /// including returning whether any changes were made and populating a CG
569 /// update result struct for the overall CGSCC walk.
571  LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
572  CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
573 
574 /// Adaptor that maps from a SCC to its functions.
575 ///
576 /// Designed to allow composition of a FunctionPass(Manager) and
577 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
578 /// to a \c CGSCCAnalysisManager it will run the
579 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
580 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
581 /// within this run safely.
582 template <typename FunctionPassT>
585 public:
586  explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
587  : Pass(std::move(Pass)) {}
588 
589  // We have to explicitly define all the special member functions because MSVC
590  // refuses to generate them.
592  : Pass(Arg.Pass) {}
593 
595  : Pass(std::move(Arg.Pass)) {}
596 
599  std::swap(LHS.Pass, RHS.Pass);
600  }
601 
603  swap(*this, RHS);
604  return *this;
605  }
606 
607  /// Runs the function pass across every function in the module.
608  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
609  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
610  // Setup the function analysis manager from its proxy.
613 
615  for (LazyCallGraph::Node &N : C)
616  Nodes.push_back(&N);
617 
618  // The SCC may get split while we are optimizing functions due to deleting
619  // edges. If this happens, the current SCC can shift, so keep track of
620  // a pointer we can overwrite.
621  LazyCallGraph::SCC *CurrentC = &C;
622 
623  LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
624  << "\n");
625 
627  for (LazyCallGraph::Node *N : Nodes) {
628  // Skip nodes from other SCCs. These may have been split out during
629  // processing. We'll eventually visit those SCCs and pick up the nodes
630  // there.
631  if (CG.lookupSCC(*N) != CurrentC)
632  continue;
633 
634  Function &F = N->getFunction();
635 
637  if (!PI.runBeforePass<Function>(Pass, F))
638  continue;
639 
640  PreservedAnalyses PassPA = Pass.run(F, FAM);
641 
642  PI.runAfterPass<Function>(Pass, F);
643 
644  // We know that the function pass couldn't have invalidated any other
645  // function's analyses (that's the contract of a function pass), so
646  // directly handle the function analysis manager's invalidation here.
647  FAM.invalidate(F, PassPA);
648 
649  // Then intersect the preserved set so that invalidation of module
650  // analyses will eventually occur when the module pass completes.
651  PA.intersect(std::move(PassPA));
652 
653  // If the call graph hasn't been preserved, update it based on this
654  // function pass. This may also update the current SCC to point to
655  // a smaller, more refined SCC.
656  auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
657  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
658  CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
659  AM, UR);
660  assert(
661  CG.lookupSCC(*N) == CurrentC &&
662  "Current SCC not updated to the SCC containing the current node!");
663  }
664  }
665 
666  // By definition we preserve the proxy. And we preserve all analyses on
667  // Functions. This precludes *any* invalidation of function analyses by the
668  // proxy, but that's OK because we've taken care to invalidate analyses in
669  // the function analysis manager incrementally above.
672 
673  // We've also ensured that we updated the call graph along the way.
675 
676  return PA;
677  }
678 
679 private:
680  FunctionPassT Pass;
681 };
682 
683 /// A function to deduce a function pass type and wrap it in the
684 /// templated adaptor.
685 template <typename FunctionPassT>
688  return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
689 }
690 
691 /// A helper that repeats an SCC pass each time an indirect call is refined to
692 /// a direct call by that pass.
693 ///
694 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
695 /// change shape, we may also want to repeat an SCC pass if it simply refines
696 /// an indirect call to a direct call, even if doing so does not alter the
697 /// shape of the graph. Note that this only pertains to direct calls to
698 /// functions where IPO across the SCC may be able to compute more precise
699 /// results. For intrinsics, we assume scalar optimizations already can fully
700 /// reason about them.
701 ///
702 /// This repetition has the potential to be very large however, as each one
703 /// might refine a single call site. As a consequence, in practice we use an
704 /// upper bound on the number of repetitions to limit things.
705 template <typename PassT>
707  : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
708 public:
710  : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
711 
712  /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
713  /// whenever an indirect call is refined.
714  PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
715  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
718  AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
719 
720  // The SCC may be refined while we are running passes over it, so set up
721  // a pointer that we can update.
722  LazyCallGraph::SCC *C = &InitialC;
723 
724  // Collect value handles for all of the indirect call sites.
725  SmallVector<WeakTrackingVH, 8> CallHandles;
726 
727  // Struct to track the counts of direct and indirect calls in each function
728  // of the SCC.
729  struct CallCount {
730  int Direct;
731  int Indirect;
732  };
733 
734  // Put value handles on all of the indirect calls and return the number of
735  // direct calls for each function in the SCC.
736  auto ScanSCC = [](LazyCallGraph::SCC &C,
737  SmallVectorImpl<WeakTrackingVH> &CallHandles) {
738  assert(CallHandles.empty() && "Must start with a clear set of handles.");
739 
740  SmallVector<CallCount, 4> CallCounts;
741  for (LazyCallGraph::Node &N : C) {
742  CallCounts.push_back({0, 0});
743  CallCount &Count = CallCounts.back();
744  for (Instruction &I : instructions(N.getFunction()))
745  if (auto CS = CallSite(&I)) {
746  if (CS.getCalledFunction()) {
747  ++Count.Direct;
748  } else {
749  ++Count.Indirect;
750  CallHandles.push_back(WeakTrackingVH(&I));
751  }
752  }
753  }
754 
755  return CallCounts;
756  };
757 
758  // Populate the initial call handles and get the initial call counts.
759  auto CallCounts = ScanSCC(*C, CallHandles);
760 
761  for (int Iteration = 0;; ++Iteration) {
762 
763  if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
764  continue;
765 
766  PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
767 
768  if (UR.InvalidatedSCCs.count(C))
769  PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
770  else
771  PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
772 
773  // If the SCC structure has changed, bail immediately and let the outer
774  // CGSCC layer handle any iteration to reflect the refined structure.
775  if (UR.UpdatedC && UR.UpdatedC != C) {
776  PA.intersect(std::move(PassPA));
777  break;
778  }
779 
780  // Check that we didn't miss any update scenario.
781  assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
782  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
783  assert((int)CallCounts.size() == C->size() &&
784  "Cannot have changed the size of the SCC!");
785 
786  // Check whether any of the handles were devirtualized.
787  auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
788  if (!CallH)
789  return false;
790  auto CS = CallSite(CallH);
791  if (!CS)
792  return false;
793 
794  // If the call is still indirect, leave it alone.
795  Function *F = CS.getCalledFunction();
796  if (!F)
797  return false;
798 
799  LLVM_DEBUG(dbgs() << "Found devirutalized call from "
800  << CS.getParent()->getParent()->getName() << " to "
801  << F->getName() << "\n");
802 
803  // We now have a direct call where previously we had an indirect call,
804  // so iterate to process this devirtualization site.
805  return true;
806  };
807  bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
808 
809  // Rescan to build up a new set of handles and count how many direct
810  // calls remain. If we decide to iterate, this also sets up the input to
811  // the next iteration.
812  CallHandles.clear();
813  auto NewCallCounts = ScanSCC(*C, CallHandles);
814 
815  // If we haven't found an explicit devirtualization already see if we
816  // have decreased the number of indirect calls and increased the number
817  // of direct calls for any function in the SCC. This can be fooled by all
818  // manner of transformations such as DCE and other things, but seems to
819  // work well in practice.
820  if (!Devirt)
821  for (int i = 0, Size = C->size(); i < Size; ++i)
822  if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
823  CallCounts[i].Direct < NewCallCounts[i].Direct) {
824  Devirt = true;
825  break;
826  }
827 
828  if (!Devirt) {
829  PA.intersect(std::move(PassPA));
830  break;
831  }
832 
833  // Otherwise, if we've already hit our max, we're done.
834  if (Iteration >= MaxIterations) {
835  LLVM_DEBUG(
836  dbgs() << "Found another devirtualization after hitting the max "
837  "number of repetitions ("
838  << MaxIterations << ") on SCC: " << *C << "\n");
839  PA.intersect(std::move(PassPA));
840  break;
841  }
842 
843  LLVM_DEBUG(
844  dbgs()
845  << "Repeating an SCC pass after finding a devirtualization in: " << *C
846  << "\n");
847 
848  // Move over the new call counts in preparation for iterating.
849  CallCounts = std::move(NewCallCounts);
850 
851  // Update the analysis manager with each run and intersect the total set
852  // of preserved analyses so we're ready to iterate.
853  AM.invalidate(*C, PassPA);
854  PA.intersect(std::move(PassPA));
855  }
856 
857  // Note that we don't add any preserved entries here unlike a more normal
858  // "pass manager" because we only handle invalidation *between* iterations,
859  // not after the last iteration.
860  return PA;
861  }
862 
863 private:
864  PassT Pass;
865  int MaxIterations;
866 };
867 
868 /// A function to deduce a function pass type and wrap it in the
869 /// templated adaptor.
870 template <typename PassT>
872  int MaxIterations) {
873  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
874 }
875 
876 // Clear out the debug logging macro.
877 #undef DEBUG_TYPE
878 
879 } // end namespace llvm
880 
881 #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
uint64_t CallInst * C
This file provides a priority worklist.
ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
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:770
This class represents lattice values for constants.
Definition: AllocatorList.h:24
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:226
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
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.
CGSCCToFunctionPassAdaptor & operator=(CGSCCToFunctionPassAdaptor RHS)
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.
ModuleToPostOrderCGSCCPassAdaptor< CGSCCPassT > createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
A function to deduce a function pass type and wrap it in the templated adaptor.
CGSCCToFunctionPassAdaptor< FunctionPassT > createCGSCCToFunctionPassAdaptor(FunctionPassT Pass)
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)
ModuleToPostOrderCGSCCPassAdaptor & operator=(ModuleToPostOrderCGSCCPassAdaptor RHS)
A utility pass template to force an analysis result to be available.
Definition: PassManager.h:1349
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:344
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:305
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:938
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:42
postorder_ref_scc_iterator postorder_ref_scc_begin()
ModuleToPostOrderCGSCCPassAdaptor(const ModuleToPostOrderCGSCCPassAdaptor &Arg)
AnalysisManagerT & getManager()
Accessor for the analysis manager.
Definition: PassManager.h:1073
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:267
Key
PAL metadata keys.
CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
A RefSCC of the call graph.
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:182
AnalysisManager< LazyCallGraph::SCC, LazyCallGraph & > CGSCCAnalysisManager
The CGSCC analysis manager.
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:366
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:154
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:383
friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS, ModuleToPostOrderCGSCCPassAdaptor &RHS)
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:1193
friend void swap(CGSCCToFunctionPassAdaptor &LHS, CGSCCToFunctionPassAdaptor &RHS)
FunctionAnalysisManager & getManager()
Accessor for the analysis manager.
iterator end() const
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:382
CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
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:160
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:575
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:1014
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:418
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:1154
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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:1101
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
void invalidate(IRUnitT &IR)
Invalidate a specific analysis pass for an IR module.
Definition: PassManager.h:842
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
Implements a dense probed hash-table based set with some number of buckets stored inline...
Definition: DenseSet.h:268
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
A helper that repeats an SCC pass each time an indirect call is refined to a direct call by that pass...
CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
Adaptor that maps from a SCC to its functions.
amdgpu Simplify well known AMD library false Value Value * Arg
Manages a sequence of passes over a particular unit of IR.
Definition: PassManager.h:458
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:190
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:47
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&... Args)
Run this pass over some unit of IR.
Definition: PassManager.h:1358
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:642
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:92
An SCC of the call graph.
DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
inst_range instructions(Function *F)
Definition: InstIterator.h:134
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:123
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:71
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1038