LLVM  8.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  PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
445 
446  // Update the SCC and RefSCC if necessary.
447  C = UR.UpdatedC ? UR.UpdatedC : C;
448  RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
449 
450  // If the CGSCC pass wasn't able to provide a valid updated SCC,
451  // the current SCC may simply need to be skipped if invalid.
452  if (UR.InvalidatedSCCs.count(C)) {
453  LLVM_DEBUG(dbgs()
454  << "Skipping invalidated root or island SCC!\n");
455  break;
456  }
457  // Check that we didn't miss any update scenario.
458  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
459 
460  // We handle invalidating the CGSCC analysis manager's information
461  // for the (potentially updated) SCC here. Note that any other SCCs
462  // whose structure has changed should have been invalidated by
463  // whatever was updating the call graph. This SCC gets invalidated
464  // late as it contains the nodes that were actively being
465  // processed.
466  CGAM.invalidate(*C, PassPA);
467 
468  // Then intersect the preserved set so that invalidation of module
469  // analyses will eventually occur when the module pass completes.
470  PA.intersect(std::move(PassPA));
471 
472  // The pass may have restructured the call graph and refined the
473  // current SCC and/or RefSCC. We need to update our current SCC and
474  // RefSCC pointers to follow these. Also, when the current SCC is
475  // refined, re-run the SCC pass over the newly refined SCC in order
476  // to observe the most precise SCC model available. This inherently
477  // cannot cycle excessively as it only happens when we split SCCs
478  // apart, at most converging on a DAG of single nodes.
479  // FIXME: If we ever start having RefSCC passes, we'll want to
480  // iterate there too.
481  if (UR.UpdatedC)
482  LLVM_DEBUG(dbgs()
483  << "Re-running SCC passes after a refinement of the "
484  "current SCC: "
485  << *UR.UpdatedC << "\n");
486 
487  // Note that both `C` and `RC` may at this point refer to deleted,
488  // invalid SCC and RefSCCs respectively. But we will short circuit
489  // the processing when we check them in the loop above.
490  } while (UR.UpdatedC);
491  } while (!CWorklist.empty());
492 
493  // We only need to keep internal inlined edge information within
494  // a RefSCC, clear it to save on space and let the next time we visit
495  // any of these functions have a fresh start.
496  InlinedInternalEdges.clear();
497  } while (!RCWorklist.empty());
498  }
499 
500  // By definition we preserve the call garph, all SCC analyses, and the
501  // analysis proxies by handling them above and in any nested pass managers.
502  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
503  PA.preserve<LazyCallGraphAnalysis>();
504  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
505  PA.preserve<FunctionAnalysisManagerModuleProxy>();
506  return PA;
507  }
508 
509 private:
510  CGSCCPassT Pass;
511 };
512 
513 /// A function to deduce a function pass type and wrap it in the
514 /// templated adaptor.
515 template <typename CGSCCPassT>
518  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
519 }
520 
521 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
522 ///
523 /// When a module pass runs and triggers invalidation, both the CGSCC and
524 /// Function analysis manager proxies on the module get an invalidation event.
525 /// We don't want to fully duplicate responsibility for most of the
526 /// invalidation logic. Instead, this layer is only responsible for SCC-local
527 /// invalidation events. We work with the module's FunctionAnalysisManager to
528 /// invalidate function analyses.
530  : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
531 public:
532  class Result {
533  public:
534  explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
535 
536  /// Accessor for the analysis manager.
538 
539  bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
541 
542  private:
544  };
545 
546  /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
547  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
548 
549 private:
551 
552  static AnalysisKey Key;
553 };
554 
556 
557 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
560 
561 /// Helper to update the call graph after running a function pass.
562 ///
563 /// Function passes can only mutate the call graph in specific ways. This
564 /// routine provides a helper that updates the call graph in those ways
565 /// including returning whether any changes were made and populating a CG
566 /// update result struct for the overall CGSCC walk.
568  LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
569  CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
570 
571 /// Adaptor that maps from a SCC to its functions.
572 ///
573 /// Designed to allow composition of a FunctionPass(Manager) and
574 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
575 /// to a \c CGSCCAnalysisManager it will run the
576 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
577 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
578 /// within this run safely.
579 template <typename FunctionPassT>
582 public:
583  explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
584  : Pass(std::move(Pass)) {}
585 
586  // We have to explicitly define all the special member functions because MSVC
587  // refuses to generate them.
589  : Pass(Arg.Pass) {}
590 
592  : Pass(std::move(Arg.Pass)) {}
593 
596  std::swap(LHS.Pass, RHS.Pass);
597  }
598 
600  swap(*this, RHS);
601  return *this;
602  }
603 
604  /// Runs the function pass across every function in the module.
605  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
606  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
607  // Setup the function analysis manager from its proxy.
610 
612  for (LazyCallGraph::Node &N : C)
613  Nodes.push_back(&N);
614 
615  // The SCC may get split while we are optimizing functions due to deleting
616  // edges. If this happens, the current SCC can shift, so keep track of
617  // a pointer we can overwrite.
618  LazyCallGraph::SCC *CurrentC = &C;
619 
620  LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
621  << "\n");
622 
624  for (LazyCallGraph::Node *N : Nodes) {
625  // Skip nodes from other SCCs. These may have been split out during
626  // processing. We'll eventually visit those SCCs and pick up the nodes
627  // there.
628  if (CG.lookupSCC(*N) != CurrentC)
629  continue;
630 
631  Function &F = N->getFunction();
632 
634  if (!PI.runBeforePass<Function>(Pass, F))
635  continue;
636 
637  PreservedAnalyses PassPA = Pass.run(F, FAM);
638 
639  PI.runAfterPass<Function>(Pass, F);
640 
641  // We know that the function pass couldn't have invalidated any other
642  // function's analyses (that's the contract of a function pass), so
643  // directly handle the function analysis manager's invalidation here.
644  FAM.invalidate(F, PassPA);
645 
646  // Then intersect the preserved set so that invalidation of module
647  // analyses will eventually occur when the module pass completes.
648  PA.intersect(std::move(PassPA));
649 
650  // If the call graph hasn't been preserved, update it based on this
651  // function pass. This may also update the current SCC to point to
652  // a smaller, more refined SCC.
653  auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
654  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
655  CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
656  AM, UR);
657  assert(
658  CG.lookupSCC(*N) == CurrentC &&
659  "Current SCC not updated to the SCC containing the current node!");
660  }
661  }
662 
663  // By definition we preserve the proxy. And we preserve all analyses on
664  // Functions. This precludes *any* invalidation of function analyses by the
665  // proxy, but that's OK because we've taken care to invalidate analyses in
666  // the function analysis manager incrementally above.
669 
670  // We've also ensured that we updated the call graph along the way.
672 
673  return PA;
674  }
675 
676 private:
677  FunctionPassT Pass;
678 };
679 
680 /// A function to deduce a function pass type and wrap it in the
681 /// templated adaptor.
682 template <typename FunctionPassT>
685  return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
686 }
687 
688 /// A helper that repeats an SCC pass each time an indirect call is refined to
689 /// a direct call by that pass.
690 ///
691 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
692 /// change shape, we may also want to repeat an SCC pass if it simply refines
693 /// an indirect call to a direct call, even if doing so does not alter the
694 /// shape of the graph. Note that this only pertains to direct calls to
695 /// functions where IPO across the SCC may be able to compute more precise
696 /// results. For intrinsics, we assume scalar optimizations already can fully
697 /// reason about them.
698 ///
699 /// This repetition has the potential to be very large however, as each one
700 /// might refine a single call site. As a consequence, in practice we use an
701 /// upper bound on the number of repetitions to limit things.
702 template <typename PassT>
704  : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
705 public:
707  : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
708 
709  /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
710  /// whenever an indirect call is refined.
711  PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
712  LazyCallGraph &CG, CGSCCUpdateResult &UR) {
715  AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
716 
717  // The SCC may be refined while we are running passes over it, so set up
718  // a pointer that we can update.
719  LazyCallGraph::SCC *C = &InitialC;
720 
721  // Collect value handles for all of the indirect call sites.
722  SmallVector<WeakTrackingVH, 8> CallHandles;
723 
724  // Struct to track the counts of direct and indirect calls in each function
725  // of the SCC.
726  struct CallCount {
727  int Direct;
728  int Indirect;
729  };
730 
731  // Put value handles on all of the indirect calls and return the number of
732  // direct calls for each function in the SCC.
733  auto ScanSCC = [](LazyCallGraph::SCC &C,
734  SmallVectorImpl<WeakTrackingVH> &CallHandles) {
735  assert(CallHandles.empty() && "Must start with a clear set of handles.");
736 
737  SmallVector<CallCount, 4> CallCounts;
738  for (LazyCallGraph::Node &N : C) {
739  CallCounts.push_back({0, 0});
740  CallCount &Count = CallCounts.back();
741  for (Instruction &I : instructions(N.getFunction()))
742  if (auto CS = CallSite(&I)) {
743  if (CS.getCalledFunction()) {
744  ++Count.Direct;
745  } else {
746  ++Count.Indirect;
747  CallHandles.push_back(WeakTrackingVH(&I));
748  }
749  }
750  }
751 
752  return CallCounts;
753  };
754 
755  // Populate the initial call handles and get the initial call counts.
756  auto CallCounts = ScanSCC(*C, CallHandles);
757 
758  for (int Iteration = 0;; ++Iteration) {
759 
760  if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
761  continue;
762 
763  PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
764 
765  PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
766 
767  // If the SCC structure has changed, bail immediately and let the outer
768  // CGSCC layer handle any iteration to reflect the refined structure.
769  if (UR.UpdatedC && UR.UpdatedC != C) {
770  PA.intersect(std::move(PassPA));
771  break;
772  }
773 
774  // Check that we didn't miss any update scenario.
775  assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
776  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
777  assert((int)CallCounts.size() == C->size() &&
778  "Cannot have changed the size of the SCC!");
779 
780  // Check whether any of the handles were devirtualized.
781  auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
782  if (!CallH)
783  return false;
784  auto CS = CallSite(CallH);
785  if (!CS)
786  return false;
787 
788  // If the call is still indirect, leave it alone.
789  Function *F = CS.getCalledFunction();
790  if (!F)
791  return false;
792 
793  LLVM_DEBUG(dbgs() << "Found devirutalized call from "
794  << CS.getParent()->getParent()->getName() << " to "
795  << F->getName() << "\n");
796 
797  // We now have a direct call where previously we had an indirect call,
798  // so iterate to process this devirtualization site.
799  return true;
800  };
801  bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
802 
803  // Rescan to build up a new set of handles and count how many direct
804  // calls remain. If we decide to iterate, this also sets up the input to
805  // the next iteration.
806  CallHandles.clear();
807  auto NewCallCounts = ScanSCC(*C, CallHandles);
808 
809  // If we haven't found an explicit devirtualization already see if we
810  // have decreased the number of indirect calls and increased the number
811  // of direct calls for any function in the SCC. This can be fooled by all
812  // manner of transformations such as DCE and other things, but seems to
813  // work well in practice.
814  if (!Devirt)
815  for (int i = 0, Size = C->size(); i < Size; ++i)
816  if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
817  CallCounts[i].Direct < NewCallCounts[i].Direct) {
818  Devirt = true;
819  break;
820  }
821 
822  if (!Devirt) {
823  PA.intersect(std::move(PassPA));
824  break;
825  }
826 
827  // Otherwise, if we've already hit our max, we're done.
828  if (Iteration >= MaxIterations) {
829  LLVM_DEBUG(
830  dbgs() << "Found another devirtualization after hitting the max "
831  "number of repetitions ("
832  << MaxIterations << ") on SCC: " << *C << "\n");
833  PA.intersect(std::move(PassPA));
834  break;
835  }
836 
837  LLVM_DEBUG(
838  dbgs()
839  << "Repeating an SCC pass after finding a devirtualization in: " << *C
840  << "\n");
841 
842  // Move over the new call counts in preparation for iterating.
843  CallCounts = std::move(NewCallCounts);
844 
845  // Update the analysis manager with each run and intersect the total set
846  // of preserved analyses so we're ready to iterate.
847  AM.invalidate(*C, PassPA);
848  PA.intersect(std::move(PassPA));
849  }
850 
851  // Note that we don't add any preserved entries here unlike a more normal
852  // "pass manager" because we only handle invalidation *between* iterations,
853  // not after the last iteration.
854  return PA;
855  }
856 
857 private:
858  PassT Pass;
859  int MaxIterations;
860 };
861 
862 /// A function to deduce a function pass type and wrap it in the
863 /// templated adaptor.
864 template <typename PassT>
866  int MaxIterations) {
867  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
868 }
869 
870 // Clear out the debug logging macro.
871 #undef DEBUG_TYPE
872 
873 } // end namespace llvm
874 
875 #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
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:226
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.
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:251
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:1049
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
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:224
#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