LLVM  7.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 
368  CG.buildRefSCCs();
369  for (auto RCI = CG.postorder_ref_scc_begin(),
370  RCE = CG.postorder_ref_scc_end();
371  RCI != RCE;) {
372  assert(RCWorklist.empty() &&
373  "Should always start with an empty RefSCC worklist");
374  // The postorder_ref_sccs range we are walking is lazily constructed, so
375  // we only push the first one onto the worklist. The worklist allows us
376  // to capture *new* RefSCCs created during transformations.
377  //
378  // We really want to form RefSCCs lazily because that makes them cheaper
379  // to update as the program is simplified and allows us to have greater
380  // cache locality as forming a RefSCC touches all the parts of all the
381  // functions within that RefSCC.
382  //
383  // We also eagerly increment the iterator to the next position because
384  // the CGSCC passes below may delete the current RefSCC.
385  RCWorklist.insert(&*RCI++);
386 
387  do {
388  LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
389  if (InvalidRefSCCSet.count(RC)) {
390  LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
391  continue;
392  }
393 
394  assert(CWorklist.empty() &&
395  "Should always start with an empty SCC worklist");
396 
397  LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
398  << "\n");
399 
400  // Push the initial SCCs in reverse post-order as we'll pop off the
401  // back and so see this in post-order.
402  for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
403  CWorklist.insert(&C);
404 
405  do {
406  LazyCallGraph::SCC *C = CWorklist.pop_back_val();
407  // Due to call graph mutations, we may have invalid SCCs or SCCs from
408  // other RefSCCs in the worklist. The invalid ones are dead and the
409  // other RefSCCs should be queued above, so we just need to skip both
410  // scenarios here.
411  if (InvalidSCCSet.count(C)) {
412  LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
413  continue;
414  }
415  if (&C->getOuterRefSCC() != RC) {
416  LLVM_DEBUG(dbgs()
417  << "Skipping an SCC that is now part of some other "
418  "RefSCC...\n");
419  continue;
420  }
421 
422  do {
423  // Check that we didn't miss any update scenario.
424  assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
425  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
426  assert(&C->getOuterRefSCC() == RC &&
427  "Processing an SCC in a different RefSCC!");
428 
429  UR.UpdatedRC = nullptr;
430  UR.UpdatedC = nullptr;
431  PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
432 
433  // Update the SCC and RefSCC if necessary.
434  C = UR.UpdatedC ? UR.UpdatedC : C;
435  RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
436 
437  // If the CGSCC pass wasn't able to provide a valid updated SCC,
438  // the current SCC may simply need to be skipped if invalid.
439  if (UR.InvalidatedSCCs.count(C)) {
440  LLVM_DEBUG(dbgs()
441  << "Skipping invalidated root or island SCC!\n");
442  break;
443  }
444  // Check that we didn't miss any update scenario.
445  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
446 
447  // We handle invalidating the CGSCC analysis manager's information
448  // for the (potentially updated) SCC here. Note that any other SCCs
449  // whose structure has changed should have been invalidated by
450  // whatever was updating the call graph. This SCC gets invalidated
451  // late as it contains the nodes that were actively being
452  // processed.
453  CGAM.invalidate(*C, PassPA);
454 
455  // Then intersect the preserved set so that invalidation of module
456  // analyses will eventually occur when the module pass completes.
457  PA.intersect(std::move(PassPA));
458 
459  // The pass may have restructured the call graph and refined the
460  // current SCC and/or RefSCC. We need to update our current SCC and
461  // RefSCC pointers to follow these. Also, when the current SCC is
462  // refined, re-run the SCC pass over the newly refined SCC in order
463  // to observe the most precise SCC model available. This inherently
464  // cannot cycle excessively as it only happens when we split SCCs
465  // apart, at most converging on a DAG of single nodes.
466  // FIXME: If we ever start having RefSCC passes, we'll want to
467  // iterate there too.
468  if (UR.UpdatedC)
469  LLVM_DEBUG(dbgs()
470  << "Re-running SCC passes after a refinement of the "
471  "current SCC: "
472  << *UR.UpdatedC << "\n");
473 
474  // Note that both `C` and `RC` may at this point refer to deleted,
475  // invalid SCC and RefSCCs respectively. But we will short circuit
476  // the processing when we check them in the loop above.
477  } while (UR.UpdatedC);
478  } while (!CWorklist.empty());
479 
480  // We only need to keep internal inlined edge information within
481  // a RefSCC, clear it to save on space and let the next time we visit
482  // any of these functions have a fresh start.
483  InlinedInternalEdges.clear();
484  } while (!RCWorklist.empty());
485  }
486 
487  // By definition we preserve the call garph, all SCC analyses, and the
488  // analysis proxies by handling them above and in any nested pass managers.
493  return PA;
494  }
495 
496 private:
497  CGSCCPassT Pass;
498 };
499 
500 /// A function to deduce a function pass type and wrap it in the
501 /// templated adaptor.
502 template <typename CGSCCPassT>
505  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
506 }
507 
508 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
509 ///
510 /// When a module pass runs and triggers invalidation, both the CGSCC and
511 /// Function analysis manager proxies on the module get an invalidation event.
512 /// We don't want to fully duplicate responsibility for most of the
513 /// invalidation logic. Instead, this layer is only responsible for SCC-local
514 /// invalidation events. We work with the module's FunctionAnalysisManager to
515 /// invalidate function analyses.
517  : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
518 public:
519  class Result {
520  public:
521  explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
522 
523  /// Accessor for the analysis manager.
525 
526  bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
528 
529  private:
531  };
532 
533  /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
534  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
535 
536 private:
538 
539  static AnalysisKey Key;
540 };
541 
543 
544 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
547 
548 /// Helper to update the call graph after running a function pass.
549 ///
550 /// Function passes can only mutate the call graph in specific ways. This
551 /// routine provides a helper that updates the call graph in those ways
552 /// including returning whether any changes were made and populating a CG
553 /// update result struct for the overall CGSCC walk.
555  LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
556  CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
557 
558 /// Adaptor that maps from a SCC to its functions.
559 ///
560 /// Designed to allow composition of a FunctionPass(Manager) and
561 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
562 /// to a \c CGSCCAnalysisManager it will run the
563 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
564 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
565 /// within this run safely.
566 template <typename FunctionPassT>
569 public:
570  explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
571  : Pass(std::move(Pass)) {}
572 
573  // We have to explicitly define all the special member functions because MSVC
574  // refuses to generate them.
576  : Pass(Arg.Pass) {}
577 
579  : Pass(std::move(Arg.Pass)) {}
580 
583  std::swap(LHS.Pass, RHS.Pass);
584  }
585 
587  swap(*this, RHS);
588  return *this;
589  }
590 
591  /// Runs the function pass across every function in the module.
592  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
593  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
594  // Setup the function analysis manager from its proxy.
597 
599  for (LazyCallGraph::Node &N : C)
600  Nodes.push_back(&N);
601 
602  // The SCC may get split while we are optimizing functions due to deleting
603  // edges. If this happens, the current SCC can shift, so keep track of
604  // a pointer we can overwrite.
605  LazyCallGraph::SCC *CurrentC = &C;
606 
607  LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
608  << "\n");
609 
611  for (LazyCallGraph::Node *N : Nodes) {
612  // Skip nodes from other SCCs. These may have been split out during
613  // processing. We'll eventually visit those SCCs and pick up the nodes
614  // there.
615  if (CG.lookupSCC(*N) != CurrentC)
616  continue;
617 
618  PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
619 
620  // We know that the function pass couldn't have invalidated any other
621  // function's analyses (that's the contract of a function pass), so
622  // directly handle the function analysis manager's invalidation here.
623  FAM.invalidate(N->getFunction(), PassPA);
624 
625  // Then intersect the preserved set so that invalidation of module
626  // analyses will eventually occur when the module pass completes.
627  PA.intersect(std::move(PassPA));
628 
629  // If the call graph hasn't been preserved, update it based on this
630  // function pass. This may also update the current SCC to point to
631  // a smaller, more refined SCC.
632  auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
633  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
634  CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
635  AM, UR);
636  assert(
637  CG.lookupSCC(*N) == CurrentC &&
638  "Current SCC not updated to the SCC containing the current node!");
639  }
640  }
641 
642  // By definition we preserve the proxy. And we preserve all analyses on
643  // Functions. This precludes *any* invalidation of function analyses by the
644  // proxy, but that's OK because we've taken care to invalidate analyses in
645  // the function analysis manager incrementally above.
648 
649  // We've also ensured that we updated the call graph along the way.
651 
652  return PA;
653  }
654 
655 private:
656  FunctionPassT Pass;
657 };
658 
659 /// A function to deduce a function pass type and wrap it in the
660 /// templated adaptor.
661 template <typename FunctionPassT>
664  return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
665 }
666 
667 /// A helper that repeats an SCC pass each time an indirect call is refined to
668 /// a direct call by that pass.
669 ///
670 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
671 /// change shape, we may also want to repeat an SCC pass if it simply refines
672 /// an indirect call to a direct call, even if doing so does not alter the
673 /// shape of the graph. Note that this only pertains to direct calls to
674 /// functions where IPO across the SCC may be able to compute more precise
675 /// results. For intrinsics, we assume scalar optimizations already can fully
676 /// reason about them.
677 ///
678 /// This repetition has the potential to be very large however, as each one
679 /// might refine a single call site. As a consequence, in practice we use an
680 /// upper bound on the number of repetitions to limit things.
681 template <typename PassT>
683  : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
684 public:
686  : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
687 
688  /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
689  /// whenever an indirect call is refined.
690  PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
691  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
693 
694  // The SCC may be refined while we are running passes over it, so set up
695  // a pointer that we can update.
696  LazyCallGraph::SCC *C = &InitialC;
697 
698  // Collect value handles for all of the indirect call sites.
699  SmallVector<WeakTrackingVH, 8> CallHandles;
700 
701  // Struct to track the counts of direct and indirect calls in each function
702  // of the SCC.
703  struct CallCount {
704  int Direct;
705  int Indirect;
706  };
707 
708  // Put value handles on all of the indirect calls and return the number of
709  // direct calls for each function in the SCC.
710  auto ScanSCC = [](LazyCallGraph::SCC &C,
711  SmallVectorImpl<WeakTrackingVH> &CallHandles) {
712  assert(CallHandles.empty() && "Must start with a clear set of handles.");
713 
714  SmallVector<CallCount, 4> CallCounts;
715  for (LazyCallGraph::Node &N : C) {
716  CallCounts.push_back({0, 0});
717  CallCount &Count = CallCounts.back();
718  for (Instruction &I : instructions(N.getFunction()))
719  if (auto CS = CallSite(&I)) {
720  if (CS.getCalledFunction()) {
721  ++Count.Direct;
722  } else {
723  ++Count.Indirect;
724  CallHandles.push_back(WeakTrackingVH(&I));
725  }
726  }
727  }
728 
729  return CallCounts;
730  };
731 
732  // Populate the initial call handles and get the initial call counts.
733  auto CallCounts = ScanSCC(*C, CallHandles);
734 
735  for (int Iteration = 0;; ++Iteration) {
736  PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
737 
738  // If the SCC structure has changed, bail immediately and let the outer
739  // CGSCC layer handle any iteration to reflect the refined structure.
740  if (UR.UpdatedC && UR.UpdatedC != C) {
741  PA.intersect(std::move(PassPA));
742  break;
743  }
744 
745  // Check that we didn't miss any update scenario.
746  assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
747  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
748  assert((int)CallCounts.size() == C->size() &&
749  "Cannot have changed the size of the SCC!");
750 
751  // Check whether any of the handles were devirtualized.
752  auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
753  if (!CallH)
754  return false;
755  auto CS = CallSite(CallH);
756  if (!CS)
757  return false;
758 
759  // If the call is still indirect, leave it alone.
760  Function *F = CS.getCalledFunction();
761  if (!F)
762  return false;
763 
764  LLVM_DEBUG(dbgs() << "Found devirutalized call from "
765  << CS.getParent()->getParent()->getName() << " to "
766  << F->getName() << "\n");
767 
768  // We now have a direct call where previously we had an indirect call,
769  // so iterate to process this devirtualization site.
770  return true;
771  };
772  bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
773 
774  // Rescan to build up a new set of handles and count how many direct
775  // calls remain. If we decide to iterate, this also sets up the input to
776  // the next iteration.
777  CallHandles.clear();
778  auto NewCallCounts = ScanSCC(*C, CallHandles);
779 
780  // If we haven't found an explicit devirtualization already see if we
781  // have decreased the number of indirect calls and increased the number
782  // of direct calls for any function in the SCC. This can be fooled by all
783  // manner of transformations such as DCE and other things, but seems to
784  // work well in practice.
785  if (!Devirt)
786  for (int i = 0, Size = C->size(); i < Size; ++i)
787  if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
788  CallCounts[i].Direct < NewCallCounts[i].Direct) {
789  Devirt = true;
790  break;
791  }
792 
793  if (!Devirt) {
794  PA.intersect(std::move(PassPA));
795  break;
796  }
797 
798  // Otherwise, if we've already hit our max, we're done.
799  if (Iteration >= MaxIterations) {
800  LLVM_DEBUG(
801  dbgs() << "Found another devirtualization after hitting the max "
802  "number of repetitions ("
803  << MaxIterations << ") on SCC: " << *C << "\n");
804  PA.intersect(std::move(PassPA));
805  break;
806  }
807 
808  LLVM_DEBUG(
809  dbgs()
810  << "Repeating an SCC pass after finding a devirtualization in: " << *C
811  << "\n");
812 
813  // Move over the new call counts in preparation for iterating.
814  CallCounts = std::move(NewCallCounts);
815 
816  // Update the analysis manager with each run and intersect the total set
817  // of preserved analyses so we're ready to iterate.
818  AM.invalidate(*C, PassPA);
819  PA.intersect(std::move(PassPA));
820  }
821 
822  // Note that we don't add any preserved entries here unlike a more normal
823  // "pass manager" because we only handle invalidation *between* iterations,
824  // not after the last iteration.
825  return PA;
826  }
827 
828 private:
829  PassT Pass;
830  int MaxIterations;
831 };
832 
833 /// A function to deduce a function pass type and wrap it in the
834 /// templated adaptor.
835 template <typename PassT>
837  int MaxIterations) {
838  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
839 }
840 
841 // Clear out the debug logging macro.
842 #undef DEBUG_TYPE
843 
844 } // end namespace llvm
845 
846 #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:687
Compute iterated dominance frontiers using a linear time algorithm.
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:225
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
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:1246
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: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:921
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:981
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:237
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:365
A lazily constructed view of the call graph of a module.
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
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:915
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:159
SmallPriorityWorklist< LazyCallGraph::SCC *, 1 > & CWorklist
Worklist of the SCCs queued for processing.
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:922
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
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1062
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:1009
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
void invalidate(IRUnitT &IR)
Invalidate a specific analysis pass for an IR module.
Definition: PassManager.h:759
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:239
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
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:420
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
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:224
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
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:1255
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:559
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.
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
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 header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:119
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:946