Coverage Report

Created: 2018-11-16 02:38

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