llvm.org GIT mirror llvm / 8bf2780 include / llvm / Analysis / CGSCCPassManager.h
8bf2780

Tree @8bf2780 (Download .tar.gz)

CGSCCPassManager.h @8bf2780raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
//===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
///
/// This header provides classes for managing passes over SCCs of the call
/// graph. These passes form an important component of LLVM's interprocedural
/// optimizations. Because they operate on the SCCs of the call graph, and they
/// traverse the graph in post-order, they can effectively do pair-wise
/// interprocedural optimizations for all call edges in the program while
/// incrementally refining it and improving the context of these pair-wise
/// optimizations. At each call site edge, the callee has already been
/// optimized as much as is possible. This in turn allows very accurate
/// analysis of it for IPO.
///
/// A secondary more general goal is to be able to isolate optimization on
/// unrelated parts of the IR module. This is useful to ensure our
/// optimizations are principled and don't miss oportunities where refinement
/// of one part of the module influence transformations in another part of the
/// module. But this is also useful if we want to parallelize the optimizations
/// across common large module graph shapes which tend to be very wide and have
/// large regions of unrelated cliques.
///
/// To satisfy these goals, we use the LazyCallGraph which provides two graphs
/// nested inside each other (and built lazily from the bottom-up): the call
/// graph proper, and a reference graph. The reference graph is super set of
/// the call graph and is a conservative approximation of what could through
/// scalar or CGSCC transforms *become* the call graph. Using this allows us to
/// ensure we optimize functions prior to them being introduced into the call
/// graph by devirtualization or other technique, and thus ensures that
/// subsequent pair-wise interprocedural optimizations observe the optimized
/// form of these functions. The (potentially transitive) reference
/// reachability used by the reference graph is a conservative approximation
/// that still allows us to have independent regions of the graph.
///
/// FIXME: There is one major drawback of the reference graph: in its naive
/// form it is quadratic because it contains a distinct edge for each
/// (potentially indirect) reference, even if are all through some common
/// global table of function pointers. This can be fixed in a number of ways
/// that essentially preserve enough of the normalization. While it isn't
/// expected to completely preclude the usability of this, it will need to be
/// addressed.
///
///
/// All of these issues are made substantially more complex in the face of
/// mutations to the call graph while optimization passes are being run. When
/// mutations to the call graph occur we want to achieve two different things:
///
/// - We need to update the call graph in-flight and invalidate analyses
///   cached on entities in the graph. Because of the cache-based analysis
///   design of the pass manager, it is essential to have stable identities for
///   the elements of the IR that passes traverse, and to invalidate any
///   analyses cached on these elements as the mutations take place.
///
/// - We want to preserve the incremental and post-order traversal of the
///   graph even as it is refined and mutated. This means we want optimization
///   to observe the most refined form of the call graph and to do so in
///   post-order.
///
/// To address this, the CGSCC manager uses both worklists that can be expanded
/// by passes which transform the IR, and provides invalidation tests to skip
/// entries that become dead. This extra data is provided to every SCC pass so
/// that it can carefully update the manager's traversal as the call graph
/// mutates.
///
/// We also provide support for running function passes within the CGSCC walk,
/// and there we provide automatic update of the call graph including of the
/// pass manager to reflect call graph changes that fall out naturally as part
/// of scalar transformations.
///
/// The patterns used to ensure the goals of post-order visitation of the fully
/// refined graph:
///
/// 1) Sink toward the "bottom" as the graph is refined. This means that any
///    iteration continues in some valid post-order sequence after the mutation
///    has altered the structure.
///
/// 2) Enqueue in post-order, including the current entity. If the current
///    entity's shape changes, it and everything after it in post-order needs
///    to be visited to observe that shape.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
#define LLVM_ANALYSIS_CGSCCPASSMANAGER_H

#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/IR/PassManager.h"

namespace llvm {

struct CGSCCUpdateResult;

/// Extern template declaration for the analysis set for this IR unit.
extern template class AllAnalysesOn<LazyCallGraph::SCC>;

extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
/// \brief The CGSCC analysis manager.
///
/// See the documentation for the AnalysisManager template for detail
/// documentation. This typedef serves as a convenient way to refer to this
/// construct in the adaptors and proxies used to integrate this into the larger
/// pass manager infrastructure.
typedef AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>
    CGSCCAnalysisManager;

// Explicit specialization and instantiation declarations for the pass manager.
// See the comments on the definition of the specialization for details on how
// it differs from the primary template.
template <>
PreservedAnalyses
PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
            CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
                                      CGSCCAnalysisManager &AM,
                                      LazyCallGraph &G, CGSCCUpdateResult &UR);
extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
                                  LazyCallGraph &, CGSCCUpdateResult &>;

/// \brief The CGSCC pass manager.
///
/// See the documentation for the PassManager template for details. It runs
/// a sequency of SCC passes over each SCC that the manager is run over. This
/// typedef serves as a convenient way to refer to this construct.
typedef PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
                    CGSCCUpdateResult &>
    CGSCCPassManager;

/// An explicit specialization of the require analysis template pass.
template <typename AnalysisT>
struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager,
                           LazyCallGraph &, CGSCCUpdateResult &>
    : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
                                        CGSCCAnalysisManager, LazyCallGraph &,
                                        CGSCCUpdateResult &>> {
  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                        LazyCallGraph &CG, CGSCCUpdateResult &) {
    (void)AM.template getResult<AnalysisT>(C, CG);
    return PreservedAnalyses::all();
  }
};

/// A proxy from a \c CGSCCAnalysisManager to a \c Module.
typedef InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>
    CGSCCAnalysisManagerModuleProxy;

/// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
/// it can have access to the call graph in order to walk all the SCCs when
/// invalidating things.
template <> class CGSCCAnalysisManagerModuleProxy::Result {
public:
  explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
      : InnerAM(&InnerAM), G(&G) {}

  /// \brief Accessor for the analysis manager.
  CGSCCAnalysisManager &getManager() { return *InnerAM; }

  /// \brief Handler for invalidation of the Module.
  ///
  /// If the proxy analysis itself is preserved, then we assume that the set of
  /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the
  /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear
  /// on the CGSCCAnalysisManager.
  ///
  /// Regardless of whether this analysis is marked as preserved, all of the
  /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based
  /// on the set of preserved analyses.
  bool invalidate(Module &M, const PreservedAnalyses &PA,
                  ModuleAnalysisManager::Invalidator &Inv);

private:
  CGSCCAnalysisManager *InnerAM;
  LazyCallGraph *G;
};

/// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
/// so it can pass the lazy call graph to the result.
template <>
CGSCCAnalysisManagerModuleProxy::Result
CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);

// Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
// template.
extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;

extern template class OuterAnalysisManagerProxy<
    ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
/// A proxy from a \c ModuleAnalysisManager to an \c SCC.
typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
                                  LazyCallGraph &>
    ModuleAnalysisManagerCGSCCProxy;

/// Support structure for SCC passes to communicate updates the call graph back
/// to the CGSCC pass manager infrsatructure.
///
/// The CGSCC pass manager runs SCC passes which are allowed to update the call
/// graph and SCC structures. This means the structure the pass manager works
/// on is mutating underneath it. In order to support that, there needs to be
/// careful communication about the precise nature and ramifications of these
/// updates to the pass management infrastructure.
///
/// All SCC passes will have to accept a reference to the management layer's
/// update result struct and use it to reflect the results of any CG updates
/// performed.
///
/// Passes which do not change the call graph structure in any way can just
/// ignore this argument to their run method.
struct CGSCCUpdateResult {
  /// Worklist of the RefSCCs queued for processing.
  ///
  /// When a pass refines the graph and creates new RefSCCs or causes them to
  /// have a different shape or set of component SCCs it should add the RefSCCs
  /// to this worklist so that we visit them in the refined form.
  ///
  /// This worklist is in reverse post-order, as we pop off the back in order
  /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
  /// them in reverse post-order.
  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist;

  /// Worklist of the SCCs queued for processing.
  ///
  /// When a pass refines the graph and creates new SCCs or causes them to have
  /// a different shape or set of component functions it should add the SCCs to
  /// this worklist so that we visit them in the refined form.
  ///
  /// Note that if the SCCs are part of a RefSCC that is added to the \c
  /// RCWorklist, they don't need to be added here as visiting the RefSCC will
  /// be sufficient to re-visit the SCCs within it.
  ///
  /// This worklist is in reverse post-order, as we pop off the back in order
  /// to observe SCCs in post-order. When adding SCCs, clients should add them
  /// in reverse post-order.
  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist;

  /// The set of invalidated RefSCCs which should be skipped if they are found
  /// in \c RCWorklist.
  ///
  /// This is used to quickly prune out RefSCCs when they get deleted and
  /// happen to already be on the worklist. We use this primarily to avoid
  /// scanning the list and removing entries from it.
  SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;

  /// The set of invalidated SCCs which should be skipped if they are found
  /// in \c CWorklist.
  ///
  /// This is used to quickly prune out SCCs when they get deleted and happen
  /// to already be on the worklist. We use this primarily to avoid scanning
  /// the list and removing entries from it.
  SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;

  /// If non-null, the updated current \c RefSCC being processed.
  ///
  /// This is set when a graph refinement takes place an the "current" point in
  /// the graph moves "down" or earlier in the post-order walk. This will often
  /// cause the "current" RefSCC to be a newly created RefSCC object and the
  /// old one to be added to the above worklist. When that happens, this
  /// pointer is non-null and can be used to continue processing the "top" of
  /// the post-order walk.
  LazyCallGraph::RefSCC *UpdatedRC;

  /// If non-null, the updated current \c SCC being processed.
  ///
  /// This is set when a graph refinement takes place an the "current" point in
  /// the graph moves "down" or earlier in the post-order walk. This will often
  /// cause the "current" SCC to be a newly created SCC object and the old one
  /// to be added to the above worklist. When that happens, this pointer is
  /// non-null and can be used to continue processing the "top" of the
  /// post-order walk.
  LazyCallGraph::SCC *UpdatedC;
};

/// \brief The core module pass which does a post-order walk of the SCCs and
/// runs a CGSCC pass over each one.
///
/// Designed to allow composition of a CGSCCPass(Manager) and
/// a ModulePassManager. Note that this pass must be run with a module analysis
/// manager as it uses the LazyCallGraph analysis. It will also run the
/// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
/// pass over the module to enable a \c FunctionAnalysisManager to be used
/// within this run safely.
template <typename CGSCCPassT>
class ModuleToPostOrderCGSCCPassAdaptor
    : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
public:
  explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false)
      : Pass(std::move(Pass)), DebugLogging(DebugLogging) {}
  // We have to explicitly define all the special member functions because MSVC
  // refuses to generate them.
  ModuleToPostOrderCGSCCPassAdaptor(
      const ModuleToPostOrderCGSCCPassAdaptor &Arg)
      : Pass(Arg.Pass), DebugLogging(Arg.DebugLogging) {}
  ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
      : Pass(std::move(Arg.Pass)), DebugLogging(Arg.DebugLogging) {}
  friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
                   ModuleToPostOrderCGSCCPassAdaptor &RHS) {
    using std::swap;
    swap(LHS.Pass, RHS.Pass);
    swap(LHS.DebugLogging, RHS.DebugLogging);
  }
  ModuleToPostOrderCGSCCPassAdaptor &
  operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
    swap(*this, RHS);
    return *this;
  }

  /// \brief Runs the CGSCC pass across every SCC in the module.
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
    // Setup the CGSCC analysis manager from its proxy.
    CGSCCAnalysisManager &CGAM =
        AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();

    // Get the call graph for this module.
    LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);

    // We keep worklists to allow us to push more work onto the pass manager as
    // the passes are run.
    SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
    SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;

    // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
    // iterating off the worklists.
    SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
    SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;

    CGSCCUpdateResult UR = {RCWorklist,    CWorklist, InvalidRefSCCSet,
                            InvalidSCCSet, nullptr,   nullptr};

    PreservedAnalyses PA = PreservedAnalyses::all();
    for (LazyCallGraph::RefSCC &InitialRC : CG.postorder_ref_sccs()) {
      assert(RCWorklist.empty() &&
             "Should always start with an empty RefSCC worklist");
      // The postorder_ref_sccs range we are walking is lazily constructed, so
      // we only push the first one onto the worklist. The worklist allows us
      // to capture *new* RefSCCs created during transformations.
      //
      // We really want to form RefSCCs lazily because that makes them cheaper
      // to update as the program is simplified and allows us to have greater
      // cache locality as forming a RefSCC touches all the parts of all the
      // functions within that RefSCC.
      RCWorklist.insert(&InitialRC);

      do {
        LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
        if (InvalidRefSCCSet.count(RC)) {
          if (DebugLogging)
            dbgs() << "Skipping an invalid RefSCC...\n";
          continue;
        }

        assert(CWorklist.empty() &&
               "Should always start with an empty SCC worklist");

        if (DebugLogging)
          dbgs() << "Running an SCC pass across the RefSCC: " << *RC << "\n";

        // Push the initial SCCs in reverse post-order as we'll pop off the the
        // back and so see this in post-order.
        for (LazyCallGraph::SCC &C : reverse(*RC))
          CWorklist.insert(&C);

        do {
          LazyCallGraph::SCC *C = CWorklist.pop_back_val();
          // Due to call graph mutations, we may have invalid SCCs or SCCs from
          // other RefSCCs in the worklist. The invalid ones are dead and the
          // other RefSCCs should be queued above, so we just need to skip both
          // scenarios here.
          if (InvalidSCCSet.count(C)) {
            if (DebugLogging)
              dbgs() << "Skipping an invalid SCC...\n";
            continue;
          }
          if (&C->getOuterRefSCC() != RC) {
            if (DebugLogging)
              dbgs() << "Skipping an SCC that is now part of some other "
                        "RefSCC...\n";
            continue;
          }

          do {
            // Check that we didn't miss any update scenario.
            assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
            assert(C->begin() != C->end() && "Cannot have an empty SCC!");
            assert(&C->getOuterRefSCC() == RC &&
                   "Processing an SCC in a different RefSCC!");

            UR.UpdatedRC = nullptr;
            UR.UpdatedC = nullptr;
            PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);

            // We handle invalidating the CGSCC analysis manager's information
            // for the (potentially updated) SCC here. Note that any other SCCs
            // whose structure has changed should have been invalidated by
            // whatever was updating the call graph. This SCC gets invalidated
            // late as it contains the nodes that were actively being
            // processed.
            CGAM.invalidate(*(UR.UpdatedC ? UR.UpdatedC : C), PassPA);

            // Then intersect the preserved set so that invalidation of module
            // analyses will eventually occur when the module pass completes.
            PA.intersect(std::move(PassPA));

            // The pass may have restructured the call graph and refined the
            // current SCC and/or RefSCC. We need to update our current SCC and
            // RefSCC pointers to follow these. Also, when the current SCC is
            // refined, re-run the SCC pass over the newly refined SCC in order
            // to observe the most precise SCC model available. This inherently
            // cannot cycle excessively as it only happens when we split SCCs
            // apart, at most converging on a DAG of single nodes.
            // FIXME: If we ever start having RefSCC passes, we'll want to
            // iterate there too.
            RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
            C = UR.UpdatedC ? UR.UpdatedC : C;
            if (DebugLogging && UR.UpdatedC)
              dbgs() << "Re-running SCC passes after a refinement of the "
                        "current SCC: "
                     << *UR.UpdatedC << "\n";
          } while (UR.UpdatedC);

        } while (!CWorklist.empty());
      } while (!RCWorklist.empty());
    }

    // By definition we preserve the call garph, all SCC analyses, and the
    // analysis proxies by handling them above and in any nested pass managers.
    PA.preserve<LazyCallGraphAnalysis>();
    PA.preserve<AllAnalysesOn<LazyCallGraph::SCC>>();
    PA.preserve<CGSCCAnalysisManagerModuleProxy>();
    PA.preserve<FunctionAnalysisManagerModuleProxy>();
    return PA;
  }

private:
  CGSCCPassT Pass;
  bool DebugLogging;
};

/// \brief A function to deduce a function pass type and wrap it in the
/// templated adaptor.
template <typename CGSCCPassT>
ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false) {
  return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass), DebugLogging);
}

/// A proxy from a \c FunctionAnalysisManager to an \c SCC.
///
/// When a module pass runs and triggers invalidation, both the CGSCC and
/// Function analysis manager proxies on the module get an invalidation event.
/// We don't want to fully duplicate responsibility for most of the
/// invalidation logic. Instead, this layer is only responsible for SCC-local
/// invalidation events. We work with the module's FunctionAnalysisManager to
/// invalidate function analyses.
class FunctionAnalysisManagerCGSCCProxy
    : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
public:
  class Result {
  public:
    explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}

    /// \brief Accessor for the analysis manager.
    FunctionAnalysisManager &getManager() { return *FAM; }

    bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
                    CGSCCAnalysisManager::Invalidator &Inv);

  private:
    FunctionAnalysisManager *FAM;
  };

  /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);

private:
  friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
  static AnalysisKey Key;
};

// Ensure the \c FunctionAnalysisManagerCGSCCProxy is provided as an extern
// template.
extern template class InnerAnalysisManagerProxy<
    FunctionAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;

extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
/// A proxy from a \c CGSCCAnalysisManager to a \c Function.
typedef OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>
    CGSCCAnalysisManagerFunctionProxy;

/// Helper to update the call graph after running a function pass.
///
/// Function passes can only mutate the call graph in specific ways. This
/// routine provides a helper that updates the call graph in those ways
/// including returning whether any changes were made and populating a CG
/// update result struct for the overall CGSCC walk.
LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
    LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, bool DebugLogging = false);

/// \brief Adaptor that maps from a SCC to its functions.
///
/// Designed to allow composition of a FunctionPass(Manager) and
/// a CGSCCPassManager. Note that if this pass is constructed with a pointer
/// to a \c CGSCCAnalysisManager it will run the
/// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
/// pass over the SCC to enable a \c FunctionAnalysisManager to be used
/// within this run safely.
template <typename FunctionPassT>
class CGSCCToFunctionPassAdaptor
    : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
public:
  explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass, bool DebugLogging = false)
      : Pass(std::move(Pass)), DebugLogging(DebugLogging) {}
  // We have to explicitly define all the special member functions because MSVC
  // refuses to generate them.
  CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
      : Pass(Arg.Pass), DebugLogging(Arg.DebugLogging) {}
  CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
      : Pass(std::move(Arg.Pass)), DebugLogging(Arg.DebugLogging) {}
  friend void swap(CGSCCToFunctionPassAdaptor &LHS,
                   CGSCCToFunctionPassAdaptor &RHS) {
    using std::swap;
    swap(LHS.Pass, RHS.Pass);
    swap(LHS.DebugLogging, RHS.DebugLogging);
  }
  CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
    swap(*this, RHS);
    return *this;
  }

  /// \brief Runs the function pass across every function in the module.
  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
    // Setup the function analysis manager from its proxy.
    FunctionAnalysisManager &FAM =
        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();

    SmallVector<LazyCallGraph::Node *, 4> Nodes;
    for (LazyCallGraph::Node &N : C)
      Nodes.push_back(&N);

    // The SCC may get split while we are optimizing functions due to deleting
    // edges. If this happens, the current SCC can shift, so keep track of
    // a pointer we can overwrite.
    LazyCallGraph::SCC *CurrentC = &C;

    if (DebugLogging)
      dbgs() << "Running function passes across an SCC: " << C << "\n";

    PreservedAnalyses PA = PreservedAnalyses::all();
    for (LazyCallGraph::Node *N : Nodes) {
      // Skip nodes from other SCCs. These may have been split out during
      // processing. We'll eventually visit those SCCs and pick up the nodes
      // there.
      if (CG.lookupSCC(*N) != CurrentC)
        continue;

      PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);

      // We know that the function pass couldn't have invalidated any other
      // function's analyses (that's the contract of a function pass), so
      // directly handle the function analysis manager's invalidation here.
      FAM.invalidate(N->getFunction(), PassPA);

      // Then intersect the preserved set so that invalidation of module
      // analyses will eventually occur when the module pass completes.
      PA.intersect(std::move(PassPA));

      // Update the call graph based on this function pass. This may also
      // update the current SCC to point to a smaller, more refined SCC.
      CurrentC = &updateCGAndAnalysisManagerForFunctionPass(
          CG, *CurrentC, *N, AM, UR, DebugLogging);
      assert(CG.lookupSCC(*N) == CurrentC &&
             "Current SCC not updated to the SCC containing the current node!");
    }

    // By definition we preserve the proxy. And we preserve all analyses on
    // Functions. This precludes *any* invalidation of function analyses by the
    // proxy, but that's OK because we've taken care to invalidate analyses in
    // the function analysis manager incrementally above.
    PA.preserve<AllAnalysesOn<Function>>();
    PA.preserve<FunctionAnalysisManagerCGSCCProxy>();

    // We've also ensured that we updated the call graph along the way.
    PA.preserve<LazyCallGraphAnalysis>();

    return PA;
  }

private:
  FunctionPassT Pass;
  bool DebugLogging;
};

/// \brief A function to deduce a function pass type and wrap it in the
/// templated adaptor.
template <typename FunctionPassT>
CGSCCToFunctionPassAdaptor<FunctionPassT>
createCGSCCToFunctionPassAdaptor(FunctionPassT Pass, bool DebugLogging = false) {
  return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass),
                                                   DebugLogging);
}
}

#endif