Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/CGSCCPassManager.h
Line
Count
Source (jump to first uncovered line)
1
//===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
/// \file
9
///
10
/// This header provides classes for managing passes over SCCs of the call
11
/// graph. These passes form an important component of LLVM's interprocedural
12
/// optimizations. Because they operate on the SCCs of the call graph, and they
13
/// traverse the graph in post-order, they can effectively do pair-wise
14
/// interprocedural optimizations for all call edges in the program while
15
/// incrementally refining it and improving the context of these pair-wise
16
/// optimizations. At each call site edge, the callee has already been
17
/// optimized as much as is possible. This in turn allows very accurate
18
/// analysis of it for IPO.
19
///
20
/// A secondary more general goal is to be able to isolate optimization on
21
/// unrelated parts of the IR module. This is useful to ensure our
22
/// optimizations are principled and don't miss oportunities where refinement
23
/// of one part of the module influence transformations in another part of the
24
/// module. But this is also useful if we want to parallelize the optimizations
25
/// across common large module graph shapes which tend to be very wide and have
26
/// large regions of unrelated cliques.
27
///
28
/// To satisfy these goals, we use the LazyCallGraph which provides two graphs
29
/// nested inside each other (and built lazily from the bottom-up): the call
30
/// graph proper, and a reference graph. The reference graph is super set of
31
/// the call graph and is a conservative approximation of what could through
32
/// scalar or CGSCC transforms *become* the call graph. Using this allows us to
33
/// ensure we optimize functions prior to them being introduced into the call
34
/// graph by devirtualization or other technique, and thus ensures that
35
/// subsequent pair-wise interprocedural optimizations observe the optimized
36
/// form of these functions. The (potentially transitive) reference
37
/// reachability used by the reference graph is a conservative approximation
38
/// that still allows us to have independent regions of the graph.
39
///
40
/// FIXME: There is one major drawback of the reference graph: in its naive
41
/// form it is quadratic because it contains a distinct edge for each
42
/// (potentially indirect) reference, even if are all through some common
43
/// global table of function pointers. This can be fixed in a number of ways
44
/// that essentially preserve enough of the normalization. While it isn't
45
/// expected to completely preclude the usability of this, it will need to be
46
/// addressed.
47
///
48
///
49
/// All of these issues are made substantially more complex in the face of
50
/// mutations to the call graph while optimization passes are being run. When
51
/// mutations to the call graph occur we want to achieve two different things:
52
///
53
/// - We need to update the call graph in-flight and invalidate analyses
54
///   cached on entities in the graph. Because of the cache-based analysis
55
///   design of the pass manager, it is essential to have stable identities for
56
///   the elements of the IR that passes traverse, and to invalidate any
57
///   analyses cached on these elements as the mutations take place.
58
///
59
/// - We want to preserve the incremental and post-order traversal of the
60
///   graph even as it is refined and mutated. This means we want optimization
61
///   to observe the most refined form of the call graph and to do so in
62
///   post-order.
63
///
64
/// To address this, the CGSCC manager uses both worklists that can be expanded
65
/// by passes which transform the IR, and provides invalidation tests to skip
66
/// entries that become dead. This extra data is provided to every SCC pass so
67
/// that it can carefully update the manager's traversal as the call graph
68
/// mutates.
69
///
70
/// We also provide support for running function passes within the CGSCC walk,
71
/// and there we provide automatic update of the call graph including of the
72
/// pass manager to reflect call graph changes that fall out naturally as part
73
/// of scalar transformations.
74
///
75
/// The patterns used to ensure the goals of post-order visitation of the fully
76
/// refined graph:
77
///
78
/// 1) Sink toward the "bottom" as the graph is refined. This means that any
79
///    iteration continues in some valid post-order sequence after the mutation
80
///    has altered the structure.
81
///
82
/// 2) Enqueue in post-order, including the current entity. If the current
83
///    entity's shape changes, it and everything after it in post-order needs
84
///    to be visited to observe that shape.
85
///
86
//===----------------------------------------------------------------------===//
87
88
#ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
89
#define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
90
91
#include "llvm/ADT/DenseSet.h"
92
#include "llvm/ADT/PriorityWorklist.h"
93
#include "llvm/ADT/STLExtras.h"
94
#include "llvm/ADT/SmallPtrSet.h"
95
#include "llvm/ADT/SmallVector.h"
96
#include "llvm/Analysis/LazyCallGraph.h"
97
#include "llvm/IR/CallSite.h"
98
#include "llvm/IR/Function.h"
99
#include "llvm/IR/InstIterator.h"
100
#include "llvm/IR/PassManager.h"
101
#include "llvm/IR/ValueHandle.h"
102
#include "llvm/Support/Debug.h"
103
#include "llvm/Support/raw_ostream.h"
104
#include <algorithm>
105
#include <cassert>
106
#include <utility>
107
108
namespace llvm {
109
110
struct CGSCCUpdateResult;
111
class Module;
112
113
// Allow debug logging in this inline function.
114
#define DEBUG_TYPE "cgscc"
115
116
/// Extern template declaration for the analysis set for this IR unit.
117
extern template class AllAnalysesOn<LazyCallGraph::SCC>;
118
119
extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
120
121
/// The CGSCC analysis manager.
122
///
123
/// See the documentation for the AnalysisManager template for detail
124
/// documentation. This type serves as a convenient way to refer to this
125
/// construct in the adaptors and proxies used to integrate this into the larger
126
/// pass manager infrastructure.
127
using CGSCCAnalysisManager =
128
    AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
129
130
// Explicit specialization and instantiation declarations for the pass manager.
131
// See the comments on the definition of the specialization for details on how
132
// it differs from the primary template.
133
template <>
134
PreservedAnalyses
135
PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
136
            CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
137
                                      CGSCCAnalysisManager &AM,
138
                                      LazyCallGraph &G, CGSCCUpdateResult &UR);
139
extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
140
                                  LazyCallGraph &, CGSCCUpdateResult &>;
141
142
/// The CGSCC pass manager.
143
///
144
/// See the documentation for the PassManager template for details. It runs
145
/// a sequence of SCC passes over each SCC that the manager is run over. This
146
/// type serves as a convenient way to refer to this construct.
147
using CGSCCPassManager =
148
    PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
149
                CGSCCUpdateResult &>;
150
151
/// An explicit specialization of the require analysis template pass.
152
template <typename AnalysisT>
153
struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager,
154
                           LazyCallGraph &, CGSCCUpdateResult &>
155
    : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
156
                                        CGSCCAnalysisManager, LazyCallGraph &,
157
                                        CGSCCUpdateResult &>> {
158
  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
159
9
                        LazyCallGraph &CG, CGSCCUpdateResult &) {
160
9
    (void)AM.template getResult<AnalysisT>(C, CG);
161
9
    return PreservedAnalyses::all();
162
9
  }
PassBuilder.cpp:llvm::RequireAnalysisPass<(anonymous namespace)::NoOpCGSCCAnalysis, llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&)
Line
Count
Source
159
9
                        LazyCallGraph &CG, CGSCCUpdateResult &) {
160
9
    (void)AM.template getResult<AnalysisT>(C, CG);
161
9
    return PreservedAnalyses::all();
162
9
  }
Unexecuted instantiation: llvm::RequireAnalysisPass<llvm::FunctionAnalysisManagerCGSCCProxy, llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&)
Unexecuted instantiation: llvm::RequireAnalysisPass<llvm::PassInstrumentationAnalysis, llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&)
163
};
164
165
/// A proxy from a \c CGSCCAnalysisManager to a \c Module.
166
using CGSCCAnalysisManagerModuleProxy =
167
    InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
168
169
/// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
170
/// it can have access to the call graph in order to walk all the SCCs when
171
/// invalidating things.
172
template <> class CGSCCAnalysisManagerModuleProxy::Result {
173
public:
174
  explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
175
423
      : InnerAM(&InnerAM), G(&G) {}
176
177
  /// Accessor for the analysis manager.
178
460
  CGSCCAnalysisManager &getManager() { return *InnerAM; }
179
180
  /// Handler for invalidation of the Module.
181
  ///
182
  /// If the proxy analysis itself is preserved, then we assume that the set of
183
  /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the
184
  /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear
185
  /// on the CGSCCAnalysisManager.
186
  ///
187
  /// Regardless of whether this analysis is marked as preserved, all of the
188
  /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based
189
  /// on the set of preserved analyses.
190
  bool invalidate(Module &M, const PreservedAnalyses &PA,
191
                  ModuleAnalysisManager::Invalidator &Inv);
192
193
private:
194
  CGSCCAnalysisManager *InnerAM;
195
  LazyCallGraph *G;
196
};
197
198
/// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
199
/// so it can pass the lazy call graph to the result.
200
template <>
201
CGSCCAnalysisManagerModuleProxy::Result
202
CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);
203
204
// Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
205
// template.
206
extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
207
208
extern template class OuterAnalysisManagerProxy<
209
    ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
210
211
/// A proxy from a \c ModuleAnalysisManager to an \c SCC.
212
using ModuleAnalysisManagerCGSCCProxy =
213
    OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
214
                              LazyCallGraph &>;
215
216
/// Support structure for SCC passes to communicate updates the call graph back
217
/// to the CGSCC pass manager infrsatructure.
218
///
219
/// The CGSCC pass manager runs SCC passes which are allowed to update the call
220
/// graph and SCC structures. This means the structure the pass manager works
221
/// on is mutating underneath it. In order to support that, there needs to be
222
/// careful communication about the precise nature and ramifications of these
223
/// updates to the pass management infrastructure.
224
///
225
/// All SCC passes will have to accept a reference to the management layer's
226
/// update result struct and use it to reflect the results of any CG updates
227
/// performed.
228
///
229
/// Passes which do not change the call graph structure in any way can just
230
/// ignore this argument to their run method.
231
struct CGSCCUpdateResult {
232
  /// Worklist of the RefSCCs queued for processing.
233
  ///
234
  /// When a pass refines the graph and creates new RefSCCs or causes them to
235
  /// have a different shape or set of component SCCs it should add the RefSCCs
236
  /// to this worklist so that we visit them in the refined form.
237
  ///
238
  /// This worklist is in reverse post-order, as we pop off the back in order
239
  /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
240
  /// them in reverse post-order.
241
  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist;
242
243
  /// Worklist of the SCCs queued for processing.
244
  ///
245
  /// When a pass refines the graph and creates new SCCs or causes them to have
246
  /// a different shape or set of component functions it should add the SCCs to
247
  /// this worklist so that we visit them in the refined form.
248
  ///
249
  /// Note that if the SCCs are part of a RefSCC that is added to the \c
250
  /// RCWorklist, they don't need to be added here as visiting the RefSCC will
251
  /// be sufficient to re-visit the SCCs within it.
252
  ///
253
  /// This worklist is in reverse post-order, as we pop off the back in order
254
  /// to observe SCCs in post-order. When adding SCCs, clients should add them
255
  /// in reverse post-order.
256
  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist;
257
258
  /// The set of invalidated RefSCCs which should be skipped if they are found
259
  /// in \c RCWorklist.
260
  ///
261
  /// This is used to quickly prune out RefSCCs when they get deleted and
262
  /// happen to already be on the worklist. We use this primarily to avoid
263
  /// scanning the list and removing entries from it.
264
  SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;
265
266
  /// The set of invalidated SCCs which should be skipped if they are found
267
  /// in \c CWorklist.
268
  ///
269
  /// This is used to quickly prune out SCCs when they get deleted and happen
270
  /// to already be on the worklist. We use this primarily to avoid scanning
271
  /// the list and removing entries from it.
272
  SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
273
274
  /// If non-null, the updated current \c RefSCC being processed.
275
  ///
276
  /// This is set when a graph refinement takes place an the "current" point in
277
  /// the graph moves "down" or earlier in the post-order walk. This will often
278
  /// cause the "current" RefSCC to be a newly created RefSCC object and the
279
  /// old one to be added to the above worklist. When that happens, this
280
  /// pointer is non-null and can be used to continue processing the "top" of
281
  /// the post-order walk.
282
  LazyCallGraph::RefSCC *UpdatedRC;
283
284
  /// If non-null, the updated current \c SCC being processed.
285
  ///
286
  /// This is set when a graph refinement takes place an the "current" point in
287
  /// the graph moves "down" or earlier in the post-order walk. This will often
288
  /// cause the "current" SCC to be a newly created SCC object and the old one
289
  /// to be added to the above worklist. When that happens, this pointer is
290
  /// non-null and can be used to continue processing the "top" of the
291
  /// post-order walk.
292
  LazyCallGraph::SCC *UpdatedC;
293
294
  /// Preserved analyses across SCCs.
295
  ///
296
  /// We specifically want to allow CGSCC passes to mutate ancestor IR
297
  /// (changing both the CG structure and the function IR itself). However,
298
  /// this means we need to take special care to correctly mark what analyses
299
  /// are preserved *across* SCCs. We have to track this out-of-band here
300
  /// because within the main `PassManeger` infrastructure we need to mark
301
  /// everything within an SCC as preserved in order to avoid repeatedly
302
  /// invalidating the same analyses as we unnest pass managers and adaptors.
303
  /// So we track the cross-SCC version of the preserved analyses here from any
304
  /// code that does direct invalidation of SCC analyses, and then use it
305
  /// whenever we move forward in the post-order walk of SCCs before running
306
  /// passes over the new SCC.
307
  PreservedAnalyses CrossSCCPA;
308
309
  /// A hacky area where the inliner can retain history about inlining
310
  /// decisions that mutated the call graph's SCC structure in order to avoid
311
  /// infinite inlining. See the comments in the inliner's CG update logic.
312
  ///
313
  /// FIXME: Keeping this here seems like a big layering issue, we should look
314
  /// for a better technique.
315
  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
316
      &InlinedInternalEdges;
317
};
318
319
/// The core module pass which does a post-order walk of the SCCs and
320
/// runs a CGSCC pass over each one.
321
///
322
/// Designed to allow composition of a CGSCCPass(Manager) and
323
/// a ModulePassManager. Note that this pass must be run with a module analysis
324
/// manager as it uses the LazyCallGraph analysis. It will also run the
325
/// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
326
/// pass over the module to enable a \c FunctionAnalysisManager to be used
327
/// within this run safely.
328
template <typename CGSCCPassT>
329
class ModuleToPostOrderCGSCCPassAdaptor
330
    : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
331
public:
332
  explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
333
460
      : Pass(std::move(Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >::ModuleToPostOrderCGSCCPassAdaptor(llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>)
Line
Count
Source
333
236
      : Pass(std::move(Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >::ModuleToPostOrderCGSCCPassAdaptor(llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >)
Line
Count
Source
333
160
      : Pass(std::move(Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PostOrderFunctionAttrsPass>::ModuleToPostOrderCGSCCPassAdaptor(llvm::PostOrderFunctionAttrsPass)
Line
Count
Source
333
43
      : Pass(std::move(Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::InlinerPass>::ModuleToPostOrderCGSCCPassAdaptor(llvm::InlinerPass)
Line
Count
Source
333
21
      : Pass(std::move(Pass)) {}
334
335
  // We have to explicitly define all the special member functions because MSVC
336
  // refuses to generate them.
337
  ModuleToPostOrderCGSCCPassAdaptor(
338
      const ModuleToPostOrderCGSCCPassAdaptor &Arg)
339
      : Pass(Arg.Pass) {}
340
341
  ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
342
920
      : Pass(std::move(Arg.Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >::ModuleToPostOrderCGSCCPassAdaptor(llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >&&)
Line
Count
Source
342
472
      : Pass(std::move(Arg.Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >::ModuleToPostOrderCGSCCPassAdaptor(llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >&&)
Line
Count
Source
342
320
      : Pass(std::move(Arg.Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PostOrderFunctionAttrsPass>::ModuleToPostOrderCGSCCPassAdaptor(llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PostOrderFunctionAttrsPass>&&)
Line
Count
Source
342
86
      : Pass(std::move(Arg.Pass)) {}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::InlinerPass>::ModuleToPostOrderCGSCCPassAdaptor(llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::InlinerPass>&&)
Line
Count
Source
342
42
      : Pass(std::move(Arg.Pass)) {}
343
344
  friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
345
                   ModuleToPostOrderCGSCCPassAdaptor &RHS) {
346
    std::swap(LHS.Pass, RHS.Pass);
347
  }
348
349
  ModuleToPostOrderCGSCCPassAdaptor &
350
  operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
351
    swap(*this, RHS);
352
    return *this;
353
  }
354
355
  /// Runs the CGSCC pass across every SCC in the module.
356
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
357
358
private:
359
  CGSCCPassT Pass;
360
};
361
362
/// A function to deduce a function pass type and wrap it in the
363
/// templated adaptor.
364
template <typename CGSCCPassT>
365
ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
366
460
createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
367
460
  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
368
460
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > llvm::createModuleToPostOrderCGSCCPassAdaptor<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >(llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>)
Line
Count
Source
366
236
createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
367
236
  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
368
236
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > > llvm::createModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >(llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >)
Line
Count
Source
366
160
createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
367
160
  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
368
160
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PostOrderFunctionAttrsPass> llvm::createModuleToPostOrderCGSCCPassAdaptor<llvm::PostOrderFunctionAttrsPass>(llvm::PostOrderFunctionAttrsPass)
Line
Count
Source
366
43
createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
367
43
  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
368
43
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::InlinerPass> llvm::createModuleToPostOrderCGSCCPassAdaptor<llvm::InlinerPass>(llvm::InlinerPass)
Line
Count
Source
366
21
createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
367
21
  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
368
21
}
369
370
/// A proxy from a \c FunctionAnalysisManager to an \c SCC.
371
///
372
/// When a module pass runs and triggers invalidation, both the CGSCC and
373
/// Function analysis manager proxies on the module get an invalidation event.
374
/// We don't want to fully duplicate responsibility for most of the
375
/// invalidation logic. Instead, this layer is only responsible for SCC-local
376
/// invalidation events. We work with the module's FunctionAnalysisManager to
377
/// invalidate function analyses.
378
class FunctionAnalysisManagerCGSCCProxy
379
    : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
380
public:
381
  class Result {
382
  public:
383
3.53k
    explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
384
385
    /// Accessor for the analysis manager.
386
5.97k
    FunctionAnalysisManager &getManager() { return *FAM; }
387
388
    bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
389
                    CGSCCAnalysisManager::Invalidator &Inv);
390
391
  private:
392
    FunctionAnalysisManager *FAM;
393
  };
394
395
  /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
396
  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
397
398
private:
399
  friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
400
401
  static AnalysisKey Key;
402
};
403
404
extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
405
406
/// A proxy from a \c CGSCCAnalysisManager to a \c Function.
407
using CGSCCAnalysisManagerFunctionProxy =
408
    OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
409
410
/// Helper to update the call graph after running a function pass.
411
///
412
/// Function passes can only mutate the call graph in specific ways. This
413
/// routine provides a helper that updates the call graph in those ways
414
/// including returning whether any changes were made and populating a CG
415
/// update result struct for the overall CGSCC walk.
416
LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
417
    LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
418
    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
419
420
/// Adaptor that maps from a SCC to its functions.
421
///
422
/// Designed to allow composition of a FunctionPass(Manager) and
423
/// a CGSCCPassManager. Note that if this pass is constructed with a pointer
424
/// to a \c CGSCCAnalysisManager it will run the
425
/// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
426
/// pass over the SCC to enable a \c FunctionAnalysisManager to be used
427
/// within this run safely.
428
template <typename FunctionPassT>
429
class CGSCCToFunctionPassAdaptor
430
    : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
431
public:
432
  explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
433
225
      : Pass(std::move(Pass)) {}
434
435
  // We have to explicitly define all the special member functions because MSVC
436
  // refuses to generate them.
437
  CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
438
      : Pass(Arg.Pass) {}
439
440
  CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
441
450
      : Pass(std::move(Arg.Pass)) {}
442
443
  friend void swap(CGSCCToFunctionPassAdaptor &LHS,
444
                   CGSCCToFunctionPassAdaptor &RHS) {
445
    std::swap(LHS.Pass, RHS.Pass);
446
  }
447
448
  CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
449
    swap(*this, RHS);
450
    return *this;
451
  }
452
453
  /// Runs the function pass across every function in the module.
454
  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
455
1.40k
                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
456
1.40k
    // Setup the function analysis manager from its proxy.
457
1.40k
    FunctionAnalysisManager &FAM =
458
1.40k
        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
459
1.40k
460
1.40k
    SmallVector<LazyCallGraph::Node *, 4> Nodes;
461
1.40k
    for (LazyCallGraph::Node &N : C)
462
1.49k
      Nodes.push_back(&N);
463
1.40k
464
1.40k
    // The SCC may get split while we are optimizing functions due to deleting
465
1.40k
    // edges. If this happens, the current SCC can shift, so keep track of
466
1.40k
    // a pointer we can overwrite.
467
1.40k
    LazyCallGraph::SCC *CurrentC = &C;
468
1.40k
469
1.40k
    LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
470
1.40k
                      << "\n");
471
1.40k
472
1.40k
    PreservedAnalyses PA = PreservedAnalyses::all();
473
1.49k
    for (LazyCallGraph::Node *N : Nodes) {
474
1.49k
      // Skip nodes from other SCCs. These may have been split out during
475
1.49k
      // processing. We'll eventually visit those SCCs and pick up the nodes
476
1.49k
      // there.
477
1.49k
      if (CG.lookupSCC(*N) != CurrentC)
478
40
        continue;
479
1.45k
480
1.45k
      Function &F = N->getFunction();
481
1.45k
482
1.45k
      PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
483
1.45k
      if (!PI.runBeforePass<Function>(Pass, F))
484
0
        continue;
485
1.45k
486
1.45k
      PreservedAnalyses PassPA = Pass.run(F, FAM);
487
1.45k
488
1.45k
      PI.runAfterPass<Function>(Pass, F);
489
1.45k
490
1.45k
      // We know that the function pass couldn't have invalidated any other
491
1.45k
      // function's analyses (that's the contract of a function pass), so
492
1.45k
      // directly handle the function analysis manager's invalidation here.
493
1.45k
      FAM.invalidate(F, PassPA);
494
1.45k
495
1.45k
      // Then intersect the preserved set so that invalidation of module
496
1.45k
      // analyses will eventually occur when the module pass completes.
497
1.45k
      PA.intersect(std::move(PassPA));
498
1.45k
499
1.45k
      // If the call graph hasn't been preserved, update it based on this
500
1.45k
      // function pass. This may also update the current SCC to point to
501
1.45k
      // a smaller, more refined SCC.
502
1.45k
      auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
503
1.45k
      if (!PAC.preserved() && 
!PAC.preservedSet<AllAnalysesOn<Module>>()826
) {
504
826
        CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
505
826
                                                              AM, UR);
506
826
        assert(
507
826
            CG.lookupSCC(*N) == CurrentC &&
508
826
            "Current SCC not updated to the SCC containing the current node!");
509
826
      }
510
1.45k
    }
511
1.40k
512
1.40k
    // By definition we preserve the proxy. And we preserve all analyses on
513
1.40k
    // Functions. This precludes *any* invalidation of function analyses by the
514
1.40k
    // proxy, but that's OK because we've taken care to invalidate analyses in
515
1.40k
    // the function analysis manager incrementally above.
516
1.40k
    PA.preserveSet<AllAnalysesOn<Function>>();
517
1.40k
    PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
518
1.40k
519
1.40k
    // We've also ensured that we updated the call graph along the way.
520
1.40k
    PA.preserve<LazyCallGraphAnalysis>();
521
1.40k
522
1.40k
    return PA;
523
1.40k
  }
524
525
private:
526
  FunctionPassT Pass;
527
};
528
529
/// A function to deduce a function pass type and wrap it in the
530
/// templated adaptor.
531
template <typename FunctionPassT>
532
CGSCCToFunctionPassAdaptor<FunctionPassT>
533
225
createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
534
225
  return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
535
225
}
536
537
/// A helper that repeats an SCC pass each time an indirect call is refined to
538
/// a direct call by that pass.
539
///
540
/// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
541
/// change shape, we may also want to repeat an SCC pass if it simply refines
542
/// an indirect call to a direct call, even if doing so does not alter the
543
/// shape of the graph. Note that this only pertains to direct calls to
544
/// functions where IPO across the SCC may be able to compute more precise
545
/// results. For intrinsics, we assume scalar optimizations already can fully
546
/// reason about them.
547
///
548
/// This repetition has the potential to be very large however, as each one
549
/// might refine a single call site. As a consequence, in practice we use an
550
/// upper bound on the number of repetitions to limit things.
551
template <typename PassT>
552
class DevirtSCCRepeatedPass
553
    : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
554
public:
555
  explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
556
163
      : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
557
558
  /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
559
  /// whenever an indirect call is refined.
560
  PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
561
1.17k
                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
562
1.17k
    PreservedAnalyses PA = PreservedAnalyses::all();
563
1.17k
    PassInstrumentation PI =
564
1.17k
        AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
565
1.17k
566
1.17k
    // The SCC may be refined while we are running passes over it, so set up
567
1.17k
    // a pointer that we can update.
568
1.17k
    LazyCallGraph::SCC *C = &InitialC;
569
1.17k
570
1.17k
    // Collect value handles for all of the indirect call sites.
571
1.17k
    SmallVector<WeakTrackingVH, 8> CallHandles;
572
1.17k
573
1.17k
    // Struct to track the counts of direct and indirect calls in each function
574
1.17k
    // of the SCC.
575
1.17k
    struct CallCount {
576
1.17k
      int Direct;
577
1.17k
      int Indirect;
578
1.17k
    };
579
1.17k
580
1.17k
    // Put value handles on all of the indirect calls and return the number of
581
1.17k
    // direct calls for each function in the SCC.
582
1.17k
    auto ScanSCC = [](LazyCallGraph::SCC &C,
583
2.34k
                      SmallVectorImpl<WeakTrackingVH> &CallHandles) {
584
2.34k
      assert(CallHandles.empty() && "Must start with a clear set of handles.");
585
2.34k
586
2.34k
      SmallVector<CallCount, 4> CallCounts;
587
2.35k
      for (LazyCallGraph::Node &N : C) {
588
2.35k
        CallCounts.push_back({0, 0});
589
2.35k
        CallCount &Count = CallCounts.back();
590
2.35k
        for (Instruction &I : instructions(N.getFunction()))
591
11.5k
          if (auto CS = CallSite(&I)) {
592
4.04k
            if (CS.getCalledFunction()) {
593
3.96k
              ++Count.Direct;
594
3.96k
            } else {
595
86
              ++Count.Indirect;
596
86
              CallHandles.push_back(WeakTrackingVH(&I));
597
86
            }
598
4.04k
          }
599
2.35k
      }
600
2.34k
601
2.34k
      return CallCounts;
602
2.34k
    };
603
1.17k
604
1.17k
    // Populate the initial call handles and get the initial call counts.
605
1.17k
    auto CallCounts = ScanSCC(*C, CallHandles);
606
1.17k
607
1.17k
    for (int Iteration = 0;; 
++Iteration8
) {
608
1.17k
609
1.17k
      if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
610
0
        continue;
611
1.17k
612
1.17k
      PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
613
1.17k
614
1.17k
      if (UR.InvalidatedSCCs.count(C))
615
0
        PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
616
1.17k
      else
617
1.17k
        PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
618
1.17k
619
1.17k
      // If the SCC structure has changed, bail immediately and let the outer
620
1.17k
      // CGSCC layer handle any iteration to reflect the refined structure.
621
1.17k
      if (UR.UpdatedC && 
UR.UpdatedC != C1
) {
622
1
        PA.intersect(std::move(PassPA));
623
1
        break;
624
1
      }
625
1.17k
626
1.17k
      // Check that we didn't miss any update scenario.
627
1.17k
      assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
628
1.17k
      assert(C->begin() != C->end() && "Cannot have an empty SCC!");
629
1.17k
      assert((int)CallCounts.size() == C->size() &&
630
1.17k
             "Cannot have changed the size of the SCC!");
631
1.17k
632
1.17k
      // Check whether any of the handles were devirtualized.
633
1.17k
      auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
634
48
        if (!CallH)
635
2
          return false;
636
46
        auto CS = CallSite(CallH);
637
46
        if (!CS)
638
0
          return false;
639
46
640
46
        // If the call is still indirect, leave it alone.
641
46
        Function *F = CS.getCalledFunction();
642
46
        if (!F)
643
39
          return false;
644
7
645
7
        LLVM_DEBUG(dbgs() << "Found devirutalized call from "
646
7
                          << CS.getParent()->getParent()->getName() << " to "
647
7
                          << F->getName() << "\n");
648
7
649
7
        // We now have a direct call where previously we had an indirect call,
650
7
        // so iterate to process this devirtualization site.
651
7
        return true;
652
7
      };
653
1.17k
      bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
654
1.17k
655
1.17k
      // Rescan to build up a new set of handles and count how many direct
656
1.17k
      // calls remain. If we decide to iterate, this also sets up the input to
657
1.17k
      // the next iteration.
658
1.17k
      CallHandles.clear();
659
1.17k
      auto NewCallCounts = ScanSCC(*C, CallHandles);
660
1.17k
661
1.17k
      // If we haven't found an explicit devirtualization already see if we
662
1.17k
      // have decreased the number of indirect calls and increased the number
663
1.17k
      // of direct calls for any function in the SCC. This can be fooled by all
664
1.17k
      // manner of transformations such as DCE and other things, but seems to
665
1.17k
      // work well in practice.
666
1.17k
      if (!Devirt)
667
2.34k
        
for (int i = 0, Size = C->size(); 1.17k
i < Size;
++i1.17k
)
668
1.17k
          if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
669
1.17k
              
CallCounts[i].Direct < NewCallCounts[i].Direct2
) {
670
2
            Devirt = true;
671
2
            break;
672
2
          }
673
1.17k
674
1.17k
      if (!Devirt) {
675
1.16k
        PA.intersect(std::move(PassPA));
676
1.16k
        break;
677
1.16k
      }
678
9
679
9
      // Otherwise, if we've already hit our max, we're done.
680
9
      if (Iteration >= MaxIterations) {
681
1
        LLVM_DEBUG(
682
1
            dbgs() << "Found another devirtualization after hitting the max "
683
1
                      "number of repetitions ("
684
1
                   << MaxIterations << ") on SCC: " << *C << "\n");
685
1
        PA.intersect(std::move(PassPA));
686
1
        break;
687
1
      }
688
8
689
8
      LLVM_DEBUG(
690
8
          dbgs()
691
8
          << "Repeating an SCC pass after finding a devirtualization in: " << *C
692
8
          << "\n");
693
8
694
8
      // Move over the new call counts in preparation for iterating.
695
8
      CallCounts = std::move(NewCallCounts);
696
8
697
8
      // Update the analysis manager with each run and intersect the total set
698
8
      // of preserved analyses so we're ready to iterate.
699
8
      AM.invalidate(*C, PassPA);
700
8
      PA.intersect(std::move(PassPA));
701
8
    }
702
1.17k
703
1.17k
    // Note that we don't add any preserved entries here unlike a more normal
704
1.17k
    // "pass manager" because we only handle invalidation *between* iterations,
705
1.17k
    // not after the last iteration.
706
1.17k
    return PA;
707
1.17k
  }
708
709
private:
710
  PassT Pass;
711
  int MaxIterations;
712
};
713
714
/// A function to deduce a function pass type and wrap it in the
715
/// templated adaptor.
716
template <typename PassT>
717
DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
718
163
                                                         int MaxIterations) {
719
163
  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
720
163
}
721
722
// Out-of-line implementation details for templates below this point.
723
724
template <typename CGSCCPassT>
725
PreservedAnalyses
726
ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::run(Module &M,
727
460
                                                   ModuleAnalysisManager &AM) {
728
460
  // Setup the CGSCC analysis manager from its proxy.
729
460
  CGSCCAnalysisManager &CGAM =
730
460
      AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
731
460
732
460
  // Get the call graph for this module.
733
460
  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
734
460
735
460
  // We keep worklists to allow us to push more work onto the pass manager as
736
460
  // the passes are run.
737
460
  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
738
460
  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
739
460
740
460
  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
741
460
  // iterating off the worklists.
742
460
  SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
743
460
  SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
744
460
745
460
  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
746
460
      InlinedInternalEdges;
747
460
748
460
  CGSCCUpdateResult UR = {
749
460
      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
750
460
      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};
751
460
752
460
  // Request PassInstrumentation from analysis manager, will use it to run
753
460
  // instrumenting callbacks for the passes later.
754
460
  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
755
460
756
460
  PreservedAnalyses PA = PreservedAnalyses::all();
757
460
  CG.buildRefSCCs();
758
460
  for (auto RCI = CG.postorder_ref_scc_begin(),
759
460
            RCE = CG.postorder_ref_scc_end();
760
2.61k
       RCI != RCE;) {
761
2.15k
    assert(RCWorklist.empty() &&
762
2.15k
           "Should always start with an empty RefSCC worklist");
763
2.15k
    // The postorder_ref_sccs range we are walking is lazily constructed, so
764
2.15k
    // we only push the first one onto the worklist. The worklist allows us
765
2.15k
    // to capture *new* RefSCCs created during transformations.
766
2.15k
    //
767
2.15k
    // We really want to form RefSCCs lazily because that makes them cheaper
768
2.15k
    // to update as the program is simplified and allows us to have greater
769
2.15k
    // cache locality as forming a RefSCC touches all the parts of all the
770
2.15k
    // functions within that RefSCC.
771
2.15k
    //
772
2.15k
    // We also eagerly increment the iterator to the next position because
773
2.15k
    // the CGSCC passes below may delete the current RefSCC.
774
2.15k
    RCWorklist.insert(&*RCI++);
775
2.15k
776
2.18k
    do {
777
2.18k
      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
778
2.18k
      if (InvalidRefSCCSet.count(RC)) {
779
6
        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
780
6
        continue;
781
6
      }
782
2.17k
783
2.17k
      assert(CWorklist.empty() &&
784
2.17k
             "Should always start with an empty SCC worklist");
785
2.17k
786
2.17k
      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
787
2.17k
                        << "\n");
788
2.17k
789
2.17k
      // Push the initial SCCs in reverse post-order as we'll pop off the
790
2.17k
      // back and so see this in post-order.
791
2.17k
      for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
792
2.21k
        CWorklist.insert(&C);
793
2.17k
794
2.25k
      do {
795
2.25k
        LazyCallGraph::SCC *C = CWorklist.pop_back_val();
796
2.25k
        // Due to call graph mutations, we may have invalid SCCs or SCCs from
797
2.25k
        // other RefSCCs in the worklist. The invalid ones are dead and the
798
2.25k
        // other RefSCCs should be queued above, so we just need to skip both
799
2.25k
        // scenarios here.
800
2.25k
        if (InvalidSCCSet.count(C)) {
801
7
          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
802
7
          continue;
803
7
        }
804
2.25k
        if (&C->getOuterRefSCC() != RC) {
805
24
          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
806
24
                               "RefSCC...\n");
807
24
          continue;
808
24
        }
809
2.22k
810
2.22k
        // Ensure we can proxy analysis updates from from the CGSCC analysis
811
2.22k
        // manager into the Function analysis manager by getting a proxy here.
812
2.22k
        // FIXME: This seems like a bit of a hack. We should find a cleaner
813
2.22k
        // or more costructive way to ensure this happens.
814
2.22k
        (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG);
815
2.22k
816
2.22k
        // Each time we visit a new SCC pulled off the worklist,
817
2.22k
        // a transformation of a child SCC may have also modified this parent
818
2.22k
        // and invalidated analyses. So we invalidate using the update record's
819
2.22k
        // cross-SCC preserved set. This preserved set is intersected by any
820
2.22k
        // CGSCC pass that handles invalidation (primarily pass managers) prior
821
2.22k
        // to marking its SCC as preserved. That lets us track everything that
822
2.22k
        // might need invalidation across SCCs without excessive invalidations
823
2.22k
        // on a single SCC.
824
2.22k
        //
825
2.22k
        // This essentially allows SCC passes to freely invalidate analyses
826
2.22k
        // of any ancestor SCC. If this becomes detrimental to successfully
827
2.22k
        // caching analyses, we could force each SCC pass to manually
828
2.22k
        // invalidate the analyses for any SCCs other than themselves which
829
2.22k
        // are mutated. However, that seems to lose the robustness of the
830
2.22k
        // pass-manager driven invalidation scheme.
831
2.22k
        //
832
2.22k
        // FIXME: This is redundant in one case -- the top of the worklist may
833
2.22k
        // *also* be the same SCC we just ran over (and invalidated for). In
834
2.22k
        // that case, we'll end up doing a redundant invalidation here as
835
2.22k
        // a consequence.
836
2.22k
        CGAM.invalidate(*C, UR.CrossSCCPA);
837
2.22k
838
2.26k
        do {
839
2.26k
          // Check that we didn't miss any update scenario.
840
2.26k
          assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
841
2.26k
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
842
2.26k
          assert(&C->getOuterRefSCC() == RC &&
843
2.26k
                 "Processing an SCC in a different RefSCC!");
844
2.26k
845
2.26k
          UR.UpdatedRC = nullptr;
846
2.26k
          UR.UpdatedC = nullptr;
847
2.26k
848
2.26k
          // Check the PassInstrumentation's BeforePass callbacks before
849
2.26k
          // running the pass, skip its execution completely if asked to
850
2.26k
          // (callback returns false).
851
2.26k
          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
852
0
            continue;
853
2.26k
854
2.26k
          PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
855
2.26k
856
2.26k
          if (UR.InvalidatedSCCs.count(C))
857
16
            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
858
2.24k
          else
859
2.24k
            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
860
2.26k
861
2.26k
          // Update the SCC and RefSCC if necessary.
862
2.26k
          C = UR.UpdatedC ? 
UR.UpdatedC34
:
C2.22k
;
863
2.26k
          RC = UR.UpdatedRC ? 
UR.UpdatedRC21
:
RC2.24k
;
864
2.26k
865
2.26k
          // If the CGSCC pass wasn't able to provide a valid updated SCC,
866
2.26k
          // the current SCC may simply need to be skipped if invalid.
867
2.26k
          if (UR.InvalidatedSCCs.count(C)) {
868
3
            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
869
3
            break;
870
3
          }
871
2.25k
          // Check that we didn't miss any update scenario.
872
2.25k
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
873
2.25k
874
2.25k
          // We handle invalidating the CGSCC analysis manager's information
875
2.25k
          // for the (potentially updated) SCC here. Note that any other SCCs
876
2.25k
          // whose structure has changed should have been invalidated by
877
2.25k
          // whatever was updating the call graph. This SCC gets invalidated
878
2.25k
          // late as it contains the nodes that were actively being
879
2.25k
          // processed.
880
2.25k
          CGAM.invalidate(*C, PassPA);
881
2.25k
882
2.25k
          // Then intersect the preserved set so that invalidation of module
883
2.25k
          // analyses will eventually occur when the module pass completes.
884
2.25k
          // Also intersect with the cross-SCC preserved set to capture any
885
2.25k
          // cross-SCC invalidation.
886
2.25k
          UR.CrossSCCPA.intersect(PassPA);
887
2.25k
          PA.intersect(std::move(PassPA));
888
2.25k
889
2.25k
          // The pass may have restructured the call graph and refined the
890
2.25k
          // current SCC and/or RefSCC. We need to update our current SCC and
891
2.25k
          // RefSCC pointers to follow these. Also, when the current SCC is
892
2.25k
          // refined, re-run the SCC pass over the newly refined SCC in order
893
2.25k
          // to observe the most precise SCC model available. This inherently
894
2.25k
          // cannot cycle excessively as it only happens when we split SCCs
895
2.25k
          // apart, at most converging on a DAG of single nodes.
896
2.25k
          // FIXME: If we ever start having RefSCC passes, we'll want to
897
2.25k
          // iterate there too.
898
2.25k
          if (UR.UpdatedC)
899
2.25k
            LLVM_DEBUG(dbgs()
900
2.25k
                       << "Re-running SCC passes after a refinement of the "
901
2.25k
                          "current SCC: "
902
2.25k
                       << *UR.UpdatedC << "\n");
903
2.25k
904
2.25k
          // Note that both `C` and `RC` may at this point refer to deleted,
905
2.25k
          // invalid SCC and RefSCCs respectively. But we will short circuit
906
2.25k
          // the processing when we check them in the loop above.
907
2.25k
        } while (UR.UpdatedC);
908
2.25k
      } while (!CWorklist.empty());
909
2.17k
910
2.17k
      // We only need to keep internal inlined edge information within
911
2.17k
      // a RefSCC, clear it to save on space and let the next time we visit
912
2.17k
      // any of these functions have a fresh start.
913
2.17k
      InlinedInternalEdges.clear();
914
2.18k
    } while (!RCWorklist.empty());
915
2.15k
  }
916
460
917
460
  // By definition we preserve the call garph, all SCC analyses, and the
918
460
  // analysis proxies by handling them above and in any nested pass managers.
919
460
  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
920
460
  PA.preserve<LazyCallGraphAnalysis>();
921
460
  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
922
460
  PA.preserve<FunctionAnalysisManagerModuleProxy>();
923
460
  return PA;
924
460
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
Line
Count
Source
727
236
                                                   ModuleAnalysisManager &AM) {
728
236
  // Setup the CGSCC analysis manager from its proxy.
729
236
  CGSCCAnalysisManager &CGAM =
730
236
      AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
731
236
732
236
  // Get the call graph for this module.
733
236
  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
734
236
735
236
  // We keep worklists to allow us to push more work onto the pass manager as
736
236
  // the passes are run.
737
236
  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
738
236
  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
739
236
740
236
  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
741
236
  // iterating off the worklists.
742
236
  SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
743
236
  SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
744
236
745
236
  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
746
236
      InlinedInternalEdges;
747
236
748
236
  CGSCCUpdateResult UR = {
749
236
      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
750
236
      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};
751
236
752
236
  // Request PassInstrumentation from analysis manager, will use it to run
753
236
  // instrumenting callbacks for the passes later.
754
236
  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
755
236
756
236
  PreservedAnalyses PA = PreservedAnalyses::all();
757
236
  CG.buildRefSCCs();
758
236
  for (auto RCI = CG.postorder_ref_scc_begin(),
759
236
            RCE = CG.postorder_ref_scc_end();
760
1.20k
       RCI != RCE;) {
761
968
    assert(RCWorklist.empty() &&
762
968
           "Should always start with an empty RefSCC worklist");
763
968
    // The postorder_ref_sccs range we are walking is lazily constructed, so
764
968
    // we only push the first one onto the worklist. The worklist allows us
765
968
    // to capture *new* RefSCCs created during transformations.
766
968
    //
767
968
    // We really want to form RefSCCs lazily because that makes them cheaper
768
968
    // to update as the program is simplified and allows us to have greater
769
968
    // cache locality as forming a RefSCC touches all the parts of all the
770
968
    // functions within that RefSCC.
771
968
    //
772
968
    // We also eagerly increment the iterator to the next position because
773
968
    // the CGSCC passes below may delete the current RefSCC.
774
968
    RCWorklist.insert(&*RCI++);
775
968
776
992
    do {
777
992
      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
778
992
      if (InvalidRefSCCSet.count(RC)) {
779
6
        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
780
6
        continue;
781
6
      }
782
986
783
986
      assert(CWorklist.empty() &&
784
986
             "Should always start with an empty SCC worklist");
785
986
786
986
      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
787
986
                        << "\n");
788
986
789
986
      // Push the initial SCCs in reverse post-order as we'll pop off the
790
986
      // back and so see this in post-order.
791
986
      for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
792
1.01k
        CWorklist.insert(&C);
793
986
794
1.05k
      do {
795
1.05k
        LazyCallGraph::SCC *C = CWorklist.pop_back_val();
796
1.05k
        // Due to call graph mutations, we may have invalid SCCs or SCCs from
797
1.05k
        // other RefSCCs in the worklist. The invalid ones are dead and the
798
1.05k
        // other RefSCCs should be queued above, so we just need to skip both
799
1.05k
        // scenarios here.
800
1.05k
        if (InvalidSCCSet.count(C)) {
801
7
          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
802
7
          continue;
803
7
        }
804
1.05k
        if (&C->getOuterRefSCC() != RC) {
805
17
          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
806
17
                               "RefSCC...\n");
807
17
          continue;
808
17
        }
809
1.03k
810
1.03k
        // Ensure we can proxy analysis updates from from the CGSCC analysis
811
1.03k
        // manager into the Function analysis manager by getting a proxy here.
812
1.03k
        // FIXME: This seems like a bit of a hack. We should find a cleaner
813
1.03k
        // or more costructive way to ensure this happens.
814
1.03k
        (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG);
815
1.03k
816
1.03k
        // Each time we visit a new SCC pulled off the worklist,
817
1.03k
        // a transformation of a child SCC may have also modified this parent
818
1.03k
        // and invalidated analyses. So we invalidate using the update record's
819
1.03k
        // cross-SCC preserved set. This preserved set is intersected by any
820
1.03k
        // CGSCC pass that handles invalidation (primarily pass managers) prior
821
1.03k
        // to marking its SCC as preserved. That lets us track everything that
822
1.03k
        // might need invalidation across SCCs without excessive invalidations
823
1.03k
        // on a single SCC.
824
1.03k
        //
825
1.03k
        // This essentially allows SCC passes to freely invalidate analyses
826
1.03k
        // of any ancestor SCC. If this becomes detrimental to successfully
827
1.03k
        // caching analyses, we could force each SCC pass to manually
828
1.03k
        // invalidate the analyses for any SCCs other than themselves which
829
1.03k
        // are mutated. However, that seems to lose the robustness of the
830
1.03k
        // pass-manager driven invalidation scheme.
831
1.03k
        //
832
1.03k
        // FIXME: This is redundant in one case -- the top of the worklist may
833
1.03k
        // *also* be the same SCC we just ran over (and invalidated for). In
834
1.03k
        // that case, we'll end up doing a redundant invalidation here as
835
1.03k
        // a consequence.
836
1.03k
        CGAM.invalidate(*C, UR.CrossSCCPA);
837
1.03k
838
1.06k
        do {
839
1.06k
          // Check that we didn't miss any update scenario.
840
1.06k
          assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
841
1.06k
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
842
1.06k
          assert(&C->getOuterRefSCC() == RC &&
843
1.06k
                 "Processing an SCC in a different RefSCC!");
844
1.06k
845
1.06k
          UR.UpdatedRC = nullptr;
846
1.06k
          UR.UpdatedC = nullptr;
847
1.06k
848
1.06k
          // Check the PassInstrumentation's BeforePass callbacks before
849
1.06k
          // running the pass, skip its execution completely if asked to
850
1.06k
          // (callback returns false).
851
1.06k
          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
852
0
            continue;
853
1.06k
854
1.06k
          PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
855
1.06k
856
1.06k
          if (UR.InvalidatedSCCs.count(C))
857
16
            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
858
1.05k
          else
859
1.05k
            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
860
1.06k
861
1.06k
          // Update the SCC and RefSCC if necessary.
862
1.06k
          C = UR.UpdatedC ? 
UR.UpdatedC33
:
C1.03k
;
863
1.06k
          RC = UR.UpdatedRC ? 
UR.UpdatedRC18
:
RC1.05k
;
864
1.06k
865
1.06k
          // If the CGSCC pass wasn't able to provide a valid updated SCC,
866
1.06k
          // the current SCC may simply need to be skipped if invalid.
867
1.06k
          if (UR.InvalidatedSCCs.count(C)) {
868
3
            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
869
3
            break;
870
3
          }
871
1.06k
          // Check that we didn't miss any update scenario.
872
1.06k
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
873
1.06k
874
1.06k
          // We handle invalidating the CGSCC analysis manager's information
875
1.06k
          // for the (potentially updated) SCC here. Note that any other SCCs
876
1.06k
          // whose structure has changed should have been invalidated by
877
1.06k
          // whatever was updating the call graph. This SCC gets invalidated
878
1.06k
          // late as it contains the nodes that were actively being
879
1.06k
          // processed.
880
1.06k
          CGAM.invalidate(*C, PassPA);
881
1.06k
882
1.06k
          // Then intersect the preserved set so that invalidation of module
883
1.06k
          // analyses will eventually occur when the module pass completes.
884
1.06k
          // Also intersect with the cross-SCC preserved set to capture any
885
1.06k
          // cross-SCC invalidation.
886
1.06k
          UR.CrossSCCPA.intersect(PassPA);
887
1.06k
          PA.intersect(std::move(PassPA));
888
1.06k
889
1.06k
          // The pass may have restructured the call graph and refined the
890
1.06k
          // current SCC and/or RefSCC. We need to update our current SCC and
891
1.06k
          // RefSCC pointers to follow these. Also, when the current SCC is
892
1.06k
          // refined, re-run the SCC pass over the newly refined SCC in order
893
1.06k
          // to observe the most precise SCC model available. This inherently
894
1.06k
          // cannot cycle excessively as it only happens when we split SCCs
895
1.06k
          // apart, at most converging on a DAG of single nodes.
896
1.06k
          // FIXME: If we ever start having RefSCC passes, we'll want to
897
1.06k
          // iterate there too.
898
1.06k
          if (UR.UpdatedC)
899
1.06k
            LLVM_DEBUG(dbgs()
900
1.06k
                       << "Re-running SCC passes after a refinement of the "
901
1.06k
                          "current SCC: "
902
1.06k
                       << *UR.UpdatedC << "\n");
903
1.06k
904
1.06k
          // Note that both `C` and `RC` may at this point refer to deleted,
905
1.06k
          // invalid SCC and RefSCCs respectively. But we will short circuit
906
1.06k
          // the processing when we check them in the loop above.
907
1.06k
        } while (UR.UpdatedC);
908
1.05k
      } while (!CWorklist.empty());
909
986
910
986
      // We only need to keep internal inlined edge information within
911
986
      // a RefSCC, clear it to save on space and let the next time we visit
912
986
      // any of these functions have a fresh start.
913
986
      InlinedInternalEdges.clear();
914
992
    } while (!RCWorklist.empty());
915
968
  }
916
236
917
236
  // By definition we preserve the call garph, all SCC analyses, and the
918
236
  // analysis proxies by handling them above and in any nested pass managers.
919
236
  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
920
236
  PA.preserve<LazyCallGraphAnalysis>();
921
236
  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
922
236
  PA.preserve<FunctionAnalysisManagerModuleProxy>();
923
236
  return PA;
924
236
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
Line
Count
Source
727
160
                                                   ModuleAnalysisManager &AM) {
728
160
  // Setup the CGSCC analysis manager from its proxy.
729
160
  CGSCCAnalysisManager &CGAM =
730
160
      AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
731
160
732
160
  // Get the call graph for this module.
733
160
  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
734
160
735
160
  // We keep worklists to allow us to push more work onto the pass manager as
736
160
  // the passes are run.
737
160
  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
738
160
  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
739
160
740
160
  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
741
160
  // iterating off the worklists.
742
160
  SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
743
160
  SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
744
160
745
160
  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
746
160
      InlinedInternalEdges;
747
160
748
160
  CGSCCUpdateResult UR = {
749
160
      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
750
160
      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};
751
160
752
160
  // Request PassInstrumentation from analysis manager, will use it to run
753
160
  // instrumenting callbacks for the passes later.
754
160
  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
755
160
756
160
  PreservedAnalyses PA = PreservedAnalyses::all();
757
160
  CG.buildRefSCCs();
758
160
  for (auto RCI = CG.postorder_ref_scc_begin(),
759
160
            RCE = CG.postorder_ref_scc_end();
760
1.30k
       RCI != RCE;) {
761
1.14k
    assert(RCWorklist.empty() &&
762
1.14k
           "Should always start with an empty RefSCC worklist");
763
1.14k
    // The postorder_ref_sccs range we are walking is lazily constructed, so
764
1.14k
    // we only push the first one onto the worklist. The worklist allows us
765
1.14k
    // to capture *new* RefSCCs created during transformations.
766
1.14k
    //
767
1.14k
    // We really want to form RefSCCs lazily because that makes them cheaper
768
1.14k
    // to update as the program is simplified and allows us to have greater
769
1.14k
    // cache locality as forming a RefSCC touches all the parts of all the
770
1.14k
    // functions within that RefSCC.
771
1.14k
    //
772
1.14k
    // We also eagerly increment the iterator to the next position because
773
1.14k
    // the CGSCC passes below may delete the current RefSCC.
774
1.14k
    RCWorklist.insert(&*RCI++);
775
1.14k
776
1.15k
    do {
777
1.15k
      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
778
1.15k
      if (InvalidRefSCCSet.count(RC)) {
779
0
        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
780
0
        continue;
781
0
      }
782
1.15k
783
1.15k
      assert(CWorklist.empty() &&
784
1.15k
             "Should always start with an empty SCC worklist");
785
1.15k
786
1.15k
      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
787
1.15k
                        << "\n");
788
1.15k
789
1.15k
      // Push the initial SCCs in reverse post-order as we'll pop off the
790
1.15k
      // back and so see this in post-order.
791
1.15k
      for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
792
1.16k
        CWorklist.insert(&C);
793
1.15k
794
1.16k
      do {
795
1.16k
        LazyCallGraph::SCC *C = CWorklist.pop_back_val();
796
1.16k
        // Due to call graph mutations, we may have invalid SCCs or SCCs from
797
1.16k
        // other RefSCCs in the worklist. The invalid ones are dead and the
798
1.16k
        // other RefSCCs should be queued above, so we just need to skip both
799
1.16k
        // scenarios here.
800
1.16k
        if (InvalidSCCSet.count(C)) {
801
0
          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
802
0
          continue;
803
0
        }
804
1.16k
        if (&C->getOuterRefSCC() != RC) {
805
7
          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
806
7
                               "RefSCC...\n");
807
7
          continue;
808
7
        }
809
1.15k
810
1.15k
        // Ensure we can proxy analysis updates from from the CGSCC analysis
811
1.15k
        // manager into the Function analysis manager by getting a proxy here.
812
1.15k
        // FIXME: This seems like a bit of a hack. We should find a cleaner
813
1.15k
        // or more costructive way to ensure this happens.
814
1.15k
        (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG);
815
1.15k
816
1.15k
        // Each time we visit a new SCC pulled off the worklist,
817
1.15k
        // a transformation of a child SCC may have also modified this parent
818
1.15k
        // and invalidated analyses. So we invalidate using the update record's
819
1.15k
        // cross-SCC preserved set. This preserved set is intersected by any
820
1.15k
        // CGSCC pass that handles invalidation (primarily pass managers) prior
821
1.15k
        // to marking its SCC as preserved. That lets us track everything that
822
1.15k
        // might need invalidation across SCCs without excessive invalidations
823
1.15k
        // on a single SCC.
824
1.15k
        //
825
1.15k
        // This essentially allows SCC passes to freely invalidate analyses
826
1.15k
        // of any ancestor SCC. If this becomes detrimental to successfully
827
1.15k
        // caching analyses, we could force each SCC pass to manually
828
1.15k
        // invalidate the analyses for any SCCs other than themselves which
829
1.15k
        // are mutated. However, that seems to lose the robustness of the
830
1.15k
        // pass-manager driven invalidation scheme.
831
1.15k
        //
832
1.15k
        // FIXME: This is redundant in one case -- the top of the worklist may
833
1.15k
        // *also* be the same SCC we just ran over (and invalidated for). In
834
1.15k
        // that case, we'll end up doing a redundant invalidation here as
835
1.15k
        // a consequence.
836
1.15k
        CGAM.invalidate(*C, UR.CrossSCCPA);
837
1.15k
838
1.15k
        do {
839
1.15k
          // Check that we didn't miss any update scenario.
840
1.15k
          assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
841
1.15k
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
842
1.15k
          assert(&C->getOuterRefSCC() == RC &&
843
1.15k
                 "Processing an SCC in a different RefSCC!");
844
1.15k
845
1.15k
          UR.UpdatedRC = nullptr;
846
1.15k
          UR.UpdatedC = nullptr;
847
1.15k
848
1.15k
          // Check the PassInstrumentation's BeforePass callbacks before
849
1.15k
          // running the pass, skip its execution completely if asked to
850
1.15k
          // (callback returns false).
851
1.15k
          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
852
0
            continue;
853
1.15k
854
1.15k
          PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
855
1.15k
856
1.15k
          if (UR.InvalidatedSCCs.count(C))
857
0
            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
858
1.15k
          else
859
1.15k
            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
860
1.15k
861
1.15k
          // Update the SCC and RefSCC if necessary.
862
1.15k
          C = UR.UpdatedC ? 
UR.UpdatedC1
:
C1.15k
;
863
1.15k
          RC = UR.UpdatedRC ? 
UR.UpdatedRC3
:
RC1.15k
;
864
1.15k
865
1.15k
          // If the CGSCC pass wasn't able to provide a valid updated SCC,
866
1.15k
          // the current SCC may simply need to be skipped if invalid.
867
1.15k
          if (UR.InvalidatedSCCs.count(C)) {
868
0
            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
869
0
            break;
870
0
          }
871
1.15k
          // Check that we didn't miss any update scenario.
872
1.15k
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
873
1.15k
874
1.15k
          // We handle invalidating the CGSCC analysis manager's information
875
1.15k
          // for the (potentially updated) SCC here. Note that any other SCCs
876
1.15k
          // whose structure has changed should have been invalidated by
877
1.15k
          // whatever was updating the call graph. This SCC gets invalidated
878
1.15k
          // late as it contains the nodes that were actively being
879
1.15k
          // processed.
880
1.15k
          CGAM.invalidate(*C, PassPA);
881
1.15k
882
1.15k
          // Then intersect the preserved set so that invalidation of module
883
1.15k
          // analyses will eventually occur when the module pass completes.
884
1.15k
          // Also intersect with the cross-SCC preserved set to capture any
885
1.15k
          // cross-SCC invalidation.
886
1.15k
          UR.CrossSCCPA.intersect(PassPA);
887
1.15k
          PA.intersect(std::move(PassPA));
888
1.15k
889
1.15k
          // The pass may have restructured the call graph and refined the
890
1.15k
          // current SCC and/or RefSCC. We need to update our current SCC and
891
1.15k
          // RefSCC pointers to follow these. Also, when the current SCC is
892
1.15k
          // refined, re-run the SCC pass over the newly refined SCC in order
893
1.15k
          // to observe the most precise SCC model available. This inherently
894
1.15k
          // cannot cycle excessively as it only happens when we split SCCs
895
1.15k
          // apart, at most converging on a DAG of single nodes.
896
1.15k
          // FIXME: If we ever start having RefSCC passes, we'll want to
897
1.15k
          // iterate there too.
898
1.15k
          if (UR.UpdatedC)
899
1.15k
            LLVM_DEBUG(dbgs()
900
1.15k
                       << "Re-running SCC passes after a refinement of the "
901
1.15k
                          "current SCC: "
902
1.15k
                       << *UR.UpdatedC << "\n");
903
1.15k
904
1.15k
          // Note that both `C` and `RC` may at this point refer to deleted,
905
1.15k
          // invalid SCC and RefSCCs respectively. But we will short circuit
906
1.15k
          // the processing when we check them in the loop above.
907
1.15k
        } while (UR.UpdatedC);
908
1.16k
      } while (!CWorklist.empty());
909
1.15k
910
1.15k
      // We only need to keep internal inlined edge information within
911
1.15k
      // a RefSCC, clear it to save on space and let the next time we visit
912
1.15k
      // any of these functions have a fresh start.
913
1.15k
      InlinedInternalEdges.clear();
914
1.15k
    } while (!RCWorklist.empty());
915
1.14k
  }
916
160
917
160
  // By definition we preserve the call garph, all SCC analyses, and the
918
160
  // analysis proxies by handling them above and in any nested pass managers.
919
160
  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
920
160
  PA.preserve<LazyCallGraphAnalysis>();
921
160
  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
922
160
  PA.preserve<FunctionAnalysisManagerModuleProxy>();
923
160
  return PA;
924
160
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::PostOrderFunctionAttrsPass>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
Line
Count
Source
727
43
                                                   ModuleAnalysisManager &AM) {
728
43
  // Setup the CGSCC analysis manager from its proxy.
729
43
  CGSCCAnalysisManager &CGAM =
730
43
      AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
731
43
732
43
  // Get the call graph for this module.
733
43
  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
734
43
735
43
  // We keep worklists to allow us to push more work onto the pass manager as
736
43
  // the passes are run.
737
43
  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
738
43
  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
739
43
740
43
  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
741
43
  // iterating off the worklists.
742
43
  SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
743
43
  SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
744
43
745
43
  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
746
43
      InlinedInternalEdges;
747
43
748
43
  CGSCCUpdateResult UR = {
749
43
      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
750
43
      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};
751
43
752
43
  // Request PassInstrumentation from analysis manager, will use it to run
753
43
  // instrumenting callbacks for the passes later.
754
43
  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
755
43
756
43
  PreservedAnalyses PA = PreservedAnalyses::all();
757
43
  CG.buildRefSCCs();
758
43
  for (auto RCI = CG.postorder_ref_scc_begin(),
759
43
            RCE = CG.postorder_ref_scc_end();
760
67
       RCI != RCE;) {
761
24
    assert(RCWorklist.empty() &&
762
24
           "Should always start with an empty RefSCC worklist");
763
24
    // The postorder_ref_sccs range we are walking is lazily constructed, so
764
24
    // we only push the first one onto the worklist. The worklist allows us
765
24
    // to capture *new* RefSCCs created during transformations.
766
24
    //
767
24
    // We really want to form RefSCCs lazily because that makes them cheaper
768
24
    // to update as the program is simplified and allows us to have greater
769
24
    // cache locality as forming a RefSCC touches all the parts of all the
770
24
    // functions within that RefSCC.
771
24
    //
772
24
    // We also eagerly increment the iterator to the next position because
773
24
    // the CGSCC passes below may delete the current RefSCC.
774
24
    RCWorklist.insert(&*RCI++);
775
24
776
24
    do {
777
24
      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
778
24
      if (InvalidRefSCCSet.count(RC)) {
779
0
        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
780
0
        continue;
781
0
      }
782
24
783
24
      assert(CWorklist.empty() &&
784
24
             "Should always start with an empty SCC worklist");
785
24
786
24
      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
787
24
                        << "\n");
788
24
789
24
      // Push the initial SCCs in reverse post-order as we'll pop off the
790
24
      // back and so see this in post-order.
791
24
      for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
792
24
        CWorklist.insert(&C);
793
24
794
24
      do {
795
24
        LazyCallGraph::SCC *C = CWorklist.pop_back_val();
796
24
        // Due to call graph mutations, we may have invalid SCCs or SCCs from
797
24
        // other RefSCCs in the worklist. The invalid ones are dead and the
798
24
        // other RefSCCs should be queued above, so we just need to skip both
799
24
        // scenarios here.
800
24
        if (InvalidSCCSet.count(C)) {
801
0
          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
802
0
          continue;
803
0
        }
804
24
        if (&C->getOuterRefSCC() != RC) {
805
0
          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
806
0
                               "RefSCC...\n");
807
0
          continue;
808
0
        }
809
24
810
24
        // Ensure we can proxy analysis updates from from the CGSCC analysis
811
24
        // manager into the Function analysis manager by getting a proxy here.
812
24
        // FIXME: This seems like a bit of a hack. We should find a cleaner
813
24
        // or more costructive way to ensure this happens.
814
24
        (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG);
815
24
816
24
        // Each time we visit a new SCC pulled off the worklist,
817
24
        // a transformation of a child SCC may have also modified this parent
818
24
        // and invalidated analyses. So we invalidate using the update record's
819
24
        // cross-SCC preserved set. This preserved set is intersected by any
820
24
        // CGSCC pass that handles invalidation (primarily pass managers) prior
821
24
        // to marking its SCC as preserved. That lets us track everything that
822
24
        // might need invalidation across SCCs without excessive invalidations
823
24
        // on a single SCC.
824
24
        //
825
24
        // This essentially allows SCC passes to freely invalidate analyses
826
24
        // of any ancestor SCC. If this becomes detrimental to successfully
827
24
        // caching analyses, we could force each SCC pass to manually
828
24
        // invalidate the analyses for any SCCs other than themselves which
829
24
        // are mutated. However, that seems to lose the robustness of the
830
24
        // pass-manager driven invalidation scheme.
831
24
        //
832
24
        // FIXME: This is redundant in one case -- the top of the worklist may
833
24
        // *also* be the same SCC we just ran over (and invalidated for). In
834
24
        // that case, we'll end up doing a redundant invalidation here as
835
24
        // a consequence.
836
24
        CGAM.invalidate(*C, UR.CrossSCCPA);
837
24
838
24
        do {
839
24
          // Check that we didn't miss any update scenario.
840
24
          assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
841
24
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
842
24
          assert(&C->getOuterRefSCC() == RC &&
843
24
                 "Processing an SCC in a different RefSCC!");
844
24
845
24
          UR.UpdatedRC = nullptr;
846
24
          UR.UpdatedC = nullptr;
847
24
848
24
          // Check the PassInstrumentation's BeforePass callbacks before
849
24
          // running the pass, skip its execution completely if asked to
850
24
          // (callback returns false).
851
24
          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
852
0
            continue;
853
24
854
24
          PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
855
24
856
24
          if (UR.InvalidatedSCCs.count(C))
857
0
            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
858
24
          else
859
24
            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
860
24
861
24
          // Update the SCC and RefSCC if necessary.
862
24
          C = UR.UpdatedC ? 
UR.UpdatedC0
: C;
863
24
          RC = UR.UpdatedRC ? 
UR.UpdatedRC0
: RC;
864
24
865
24
          // If the CGSCC pass wasn't able to provide a valid updated SCC,
866
24
          // the current SCC may simply need to be skipped if invalid.
867
24
          if (UR.InvalidatedSCCs.count(C)) {
868
0
            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
869
0
            break;
870
0
          }
871
24
          // Check that we didn't miss any update scenario.
872
24
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
873
24
874
24
          // We handle invalidating the CGSCC analysis manager's information
875
24
          // for the (potentially updated) SCC here. Note that any other SCCs
876
24
          // whose structure has changed should have been invalidated by
877
24
          // whatever was updating the call graph. This SCC gets invalidated
878
24
          // late as it contains the nodes that were actively being
879
24
          // processed.
880
24
          CGAM.invalidate(*C, PassPA);
881
24
882
24
          // Then intersect the preserved set so that invalidation of module
883
24
          // analyses will eventually occur when the module pass completes.
884
24
          // Also intersect with the cross-SCC preserved set to capture any
885
24
          // cross-SCC invalidation.
886
24
          UR.CrossSCCPA.intersect(PassPA);
887
24
          PA.intersect(std::move(PassPA));
888
24
889
24
          // The pass may have restructured the call graph and refined the
890
24
          // current SCC and/or RefSCC. We need to update our current SCC and
891
24
          // RefSCC pointers to follow these. Also, when the current SCC is
892
24
          // refined, re-run the SCC pass over the newly refined SCC in order
893
24
          // to observe the most precise SCC model available. This inherently
894
24
          // cannot cycle excessively as it only happens when we split SCCs
895
24
          // apart, at most converging on a DAG of single nodes.
896
24
          // FIXME: If we ever start having RefSCC passes, we'll want to
897
24
          // iterate there too.
898
24
          if (UR.UpdatedC)
899
24
            LLVM_DEBUG(dbgs()
900
24
                       << "Re-running SCC passes after a refinement of the "
901
24
                          "current SCC: "
902
24
                       << *UR.UpdatedC << "\n");
903
24
904
24
          // Note that both `C` and `RC` may at this point refer to deleted,
905
24
          // invalid SCC and RefSCCs respectively. But we will short circuit
906
24
          // the processing when we check them in the loop above.
907
24
        } while (UR.UpdatedC);
908
24
      } while (!CWorklist.empty());
909
24
910
24
      // We only need to keep internal inlined edge information within
911
24
      // a RefSCC, clear it to save on space and let the next time we visit
912
24
      // any of these functions have a fresh start.
913
24
      InlinedInternalEdges.clear();
914
24
    } while (!RCWorklist.empty());
915
24
  }
916
43
917
43
  // By definition we preserve the call garph, all SCC analyses, and the
918
43
  // analysis proxies by handling them above and in any nested pass managers.
919
43
  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
920
43
  PA.preserve<LazyCallGraphAnalysis>();
921
43
  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
922
43
  PA.preserve<FunctionAnalysisManagerModuleProxy>();
923
43
  return PA;
924
43
}
llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::InlinerPass>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
Line
Count
Source
727
21
                                                   ModuleAnalysisManager &AM) {
728
21
  // Setup the CGSCC analysis manager from its proxy.
729
21
  CGSCCAnalysisManager &CGAM =
730
21
      AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
731
21
732
21
  // Get the call graph for this module.
733
21
  LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
734
21
735
21
  // We keep worklists to allow us to push more work onto the pass manager as
736
21
  // the passes are run.
737
21
  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
738
21
  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
739
21
740
21
  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
741
21
  // iterating off the worklists.
742
21
  SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
743
21
  SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
744
21
745
21
  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
746
21
      InlinedInternalEdges;
747
21
748
21
  CGSCCUpdateResult UR = {
749
21
      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
750
21
      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};
751
21
752
21
  // Request PassInstrumentation from analysis manager, will use it to run
753
21
  // instrumenting callbacks for the passes later.
754
21
  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
755
21
756
21
  PreservedAnalyses PA = PreservedAnalyses::all();
757
21
  CG.buildRefSCCs();
758
21
  for (auto RCI = CG.postorder_ref_scc_begin(),
759
21
            RCE = CG.postorder_ref_scc_end();
760
34
       RCI != RCE;) {
761
13
    assert(RCWorklist.empty() &&
762
13
           "Should always start with an empty RefSCC worklist");
763
13
    // The postorder_ref_sccs range we are walking is lazily constructed, so
764
13
    // we only push the first one onto the worklist. The worklist allows us
765
13
    // to capture *new* RefSCCs created during transformations.
766
13
    //
767
13
    // We really want to form RefSCCs lazily because that makes them cheaper
768
13
    // to update as the program is simplified and allows us to have greater
769
13
    // cache locality as forming a RefSCC touches all the parts of all the
770
13
    // functions within that RefSCC.
771
13
    //
772
13
    // We also eagerly increment the iterator to the next position because
773
13
    // the CGSCC passes below may delete the current RefSCC.
774
13
    RCWorklist.insert(&*RCI++);
775
13
776
13
    do {
777
13
      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
778
13
      if (InvalidRefSCCSet.count(RC)) {
779
0
        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
780
0
        continue;
781
0
      }
782
13
783
13
      assert(CWorklist.empty() &&
784
13
             "Should always start with an empty SCC worklist");
785
13
786
13
      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
787
13
                        << "\n");
788
13
789
13
      // Push the initial SCCs in reverse post-order as we'll pop off the
790
13
      // back and so see this in post-order.
791
13
      for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
792
13
        CWorklist.insert(&C);
793
13
794
13
      do {
795
13
        LazyCallGraph::SCC *C = CWorklist.pop_back_val();
796
13
        // Due to call graph mutations, we may have invalid SCCs or SCCs from
797
13
        // other RefSCCs in the worklist. The invalid ones are dead and the
798
13
        // other RefSCCs should be queued above, so we just need to skip both
799
13
        // scenarios here.
800
13
        if (InvalidSCCSet.count(C)) {
801
0
          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
802
0
          continue;
803
0
        }
804
13
        if (&C->getOuterRefSCC() != RC) {
805
0
          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
806
0
                               "RefSCC...\n");
807
0
          continue;
808
0
        }
809
13
810
13
        // Ensure we can proxy analysis updates from from the CGSCC analysis
811
13
        // manager into the Function analysis manager by getting a proxy here.
812
13
        // FIXME: This seems like a bit of a hack. We should find a cleaner
813
13
        // or more costructive way to ensure this happens.
814
13
        (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG);
815
13
816
13
        // Each time we visit a new SCC pulled off the worklist,
817
13
        // a transformation of a child SCC may have also modified this parent
818
13
        // and invalidated analyses. So we invalidate using the update record's
819
13
        // cross-SCC preserved set. This preserved set is intersected by any
820
13
        // CGSCC pass that handles invalidation (primarily pass managers) prior
821
13
        // to marking its SCC as preserved. That lets us track everything that
822
13
        // might need invalidation across SCCs without excessive invalidations
823
13
        // on a single SCC.
824
13
        //
825
13
        // This essentially allows SCC passes to freely invalidate analyses
826
13
        // of any ancestor SCC. If this becomes detrimental to successfully
827
13
        // caching analyses, we could force each SCC pass to manually
828
13
        // invalidate the analyses for any SCCs other than themselves which
829
13
        // are mutated. However, that seems to lose the robustness of the
830
13
        // pass-manager driven invalidation scheme.
831
13
        //
832
13
        // FIXME: This is redundant in one case -- the top of the worklist may
833
13
        // *also* be the same SCC we just ran over (and invalidated for). In
834
13
        // that case, we'll end up doing a redundant invalidation here as
835
13
        // a consequence.
836
13
        CGAM.invalidate(*C, UR.CrossSCCPA);
837
13
838
13
        do {
839
13
          // Check that we didn't miss any update scenario.
840
13
          assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
841
13
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
842
13
          assert(&C->getOuterRefSCC() == RC &&
843
13
                 "Processing an SCC in a different RefSCC!");
844
13
845
13
          UR.UpdatedRC = nullptr;
846
13
          UR.UpdatedC = nullptr;
847
13
848
13
          // Check the PassInstrumentation's BeforePass callbacks before
849
13
          // running the pass, skip its execution completely if asked to
850
13
          // (callback returns false).
851
13
          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
852
0
            continue;
853
13
854
13
          PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
855
13
856
13
          if (UR.InvalidatedSCCs.count(C))
857
0
            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
858
13
          else
859
13
            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
860
13
861
13
          // Update the SCC and RefSCC if necessary.
862
13
          C = UR.UpdatedC ? 
UR.UpdatedC0
: C;
863
13
          RC = UR.UpdatedRC ? 
UR.UpdatedRC0
: RC;
864
13
865
13
          // If the CGSCC pass wasn't able to provide a valid updated SCC,
866
13
          // the current SCC may simply need to be skipped if invalid.
867
13
          if (UR.InvalidatedSCCs.count(C)) {
868
0
            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
869
0
            break;
870
0
          }
871
13
          // Check that we didn't miss any update scenario.
872
13
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
873
13
874
13
          // We handle invalidating the CGSCC analysis manager's information
875
13
          // for the (potentially updated) SCC here. Note that any other SCCs
876
13
          // whose structure has changed should have been invalidated by
877
13
          // whatever was updating the call graph. This SCC gets invalidated
878
13
          // late as it contains the nodes that were actively being
879
13
          // processed.
880
13
          CGAM.invalidate(*C, PassPA);
881
13
882
13
          // Then intersect the preserved set so that invalidation of module
883
13
          // analyses will eventually occur when the module pass completes.
884
13
          // Also intersect with the cross-SCC preserved set to capture any
885
13
          // cross-SCC invalidation.
886
13
          UR.CrossSCCPA.intersect(PassPA);
887
13
          PA.intersect(std::move(PassPA));
888
13
889
13
          // The pass may have restructured the call graph and refined the
890
13
          // current SCC and/or RefSCC. We need to update our current SCC and
891
13
          // RefSCC pointers to follow these. Also, when the current SCC is
892
13
          // refined, re-run the SCC pass over the newly refined SCC in order
893
13
          // to observe the most precise SCC model available. This inherently
894
13
          // cannot cycle excessively as it only happens when we split SCCs
895
13
          // apart, at most converging on a DAG of single nodes.
896
13
          // FIXME: If we ever start having RefSCC passes, we'll want to
897
13
          // iterate there too.
898
13
          if (UR.UpdatedC)
899
13
            LLVM_DEBUG(dbgs()
900
13
                       << "Re-running SCC passes after a refinement of the "
901
13
                          "current SCC: "
902
13
                       << *UR.UpdatedC << "\n");
903
13
904
13
          // Note that both `C` and `RC` may at this point refer to deleted,
905
13
          // invalid SCC and RefSCCs respectively. But we will short circuit
906
13
          // the processing when we check them in the loop above.
907
13
        } while (UR.UpdatedC);
908
13
      } while (!CWorklist.empty());
909
13
910
13
      // We only need to keep internal inlined edge information within
911
13
      // a RefSCC, clear it to save on space and let the next time we visit
912
13
      // any of these functions have a fresh start.
913
13
      InlinedInternalEdges.clear();
914
13
    } while (!RCWorklist.empty());
915
13
  }
916
21
917
21
  // By definition we preserve the call garph, all SCC analyses, and the
918
21
  // analysis proxies by handling them above and in any nested pass managers.
919
21
  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
920
21
  PA.preserve<LazyCallGraphAnalysis>();
921
21
  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
922
21
  PA.preserve<FunctionAnalysisManagerModuleProxy>();
923
21
  return PA;
924
21
}
925
926
// Clear out the debug logging macro.
927
#undef DEBUG_TYPE
928
929
} // end namespace llvm
930
931
#endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H