llvm.org GIT mirror llvm / stable include / llvm / Analysis / CGSCCPassManager.h
stable

Tree @stable (Download .tar.gz)

CGSCCPassManager.h @stableraw · 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
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
//===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \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/DenseSet.h"
#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <utility>

namespace llvm {

struct CGSCCUpdateResult;
class Module;

// Allow debug logging in this inline function.
#define DEBUG_TYPE "cgscc"

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

extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;

/// The CGSCC analysis manager.
///
/// See the documentation for the AnalysisManager template for detail
/// documentation. This type 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.
using CGSCCAnalysisManager =
    AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;

// 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 &>;

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

/// 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.
using CGSCCAnalysisManagerModuleProxy =
    InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;

/// 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) {}

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

  /// 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.
using ModuleAnalysisManagerCGSCCProxy =
    OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
                              LazyCallGraph &>;

/// 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;

  /// Preserved analyses across SCCs.
  ///
  /// We specifically want to allow CGSCC passes to mutate ancestor IR
  /// (changing both the CG structure and the function IR itself). However,
  /// this means we need to take special care to correctly mark what analyses
  /// are preserved *across* SCCs. We have to track this out-of-band here
  /// because within the main `PassManeger` infrastructure we need to mark
  /// everything within an SCC as preserved in order to avoid repeatedly
  /// invalidating the same analyses as we unnest pass managers and adaptors.
  /// So we track the cross-SCC version of the preserved analyses here from any
  /// code that does direct invalidation of SCC analyses, and then use it
  /// whenever we move forward in the post-order walk of SCCs before running
  /// passes over the new SCC.
  PreservedAnalyses CrossSCCPA;

  /// A hacky area where the inliner can retain history about inlining
  /// decisions that mutated the call graph's SCC structure in order to avoid
  /// infinite inlining. See the comments in the inliner's CG update logic.
  ///
  /// FIXME: Keeping this here seems like a big layering issue, we should look
  /// for a better technique.
  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
      &InlinedInternalEdges;
};

/// 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)
      : Pass(std::move(Pass)) {}

  // We have to explicitly define all the special member functions because MSVC
  // refuses to generate them.
  ModuleToPostOrderCGSCCPassAdaptor(
      const ModuleToPostOrderCGSCCPassAdaptor &Arg)
      : Pass(Arg.Pass) {}

  ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
      : Pass(std::move(Arg.Pass)) {}

  friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
                   ModuleToPostOrderCGSCCPassAdaptor &RHS) {
    std::swap(LHS.Pass, RHS.Pass);
  }

  ModuleToPostOrderCGSCCPassAdaptor &
  operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
    swap(*this, RHS);
    return *this;
  }

  /// Runs the CGSCC pass across every SCC in the module.
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);

private:
  CGSCCPassT Pass;
};

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

/// 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) {}

    /// 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;
};

extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;

/// A proxy from a \c CGSCCAnalysisManager to a \c Function.
using CGSCCAnalysisManagerFunctionProxy =
    OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;

/// 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);

/// 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)
      : Pass(std::move(Pass)) {}

  // We have to explicitly define all the special member functions because MSVC
  // refuses to generate them.
  CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
      : Pass(Arg.Pass) {}

  CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
      : Pass(std::move(Arg.Pass)) {}

  friend void swap(CGSCCToFunctionPassAdaptor &LHS,
                   CGSCCToFunctionPassAdaptor &RHS) {
    std::swap(LHS.Pass, RHS.Pass);
  }

  CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
    swap(*this, RHS);
    return *this;
  }

  /// 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;

    LLVM_DEBUG(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;

      Function &F = N->getFunction();

      PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
      if (!PI.runBeforePass<Function>(Pass, F))
        continue;

      PreservedAnalyses PassPA = Pass.run(F, FAM);

      PI.runAfterPass<Function>(Pass, F);

      // 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(F, 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));

      // If the call graph hasn't been preserved, update it based on this
      // function pass. This may also update the current SCC to point to
      // a smaller, more refined SCC.
      auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
      if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
        CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
                                                              AM, UR);
        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.preserveSet<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;
};

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

/// A helper that repeats an SCC pass each time an indirect call is refined to
/// a direct call by that pass.
///
/// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
/// change shape, we may also want to repeat an SCC pass if it simply refines
/// an indirect call to a direct call, even if doing so does not alter the
/// shape of the graph. Note that this only pertains to direct calls to
/// functions where IPO across the SCC may be able to compute more precise
/// results. For intrinsics, we assume scalar optimizations already can fully
/// reason about them.
///
/// This repetition has the potential to be very large however, as each one
/// might refine a single call site. As a consequence, in practice we use an
/// upper bound on the number of repetitions to limit things.
template <typename PassT>
class DevirtSCCRepeatedPass
    : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
public:
  explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
      : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}

  /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
  /// whenever an indirect call is refined.
  PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
    PreservedAnalyses PA = PreservedAnalyses::all();
    PassInstrumentation PI =
        AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);

    // The SCC may be refined while we are running passes over it, so set up
    // a pointer that we can update.
    LazyCallGraph::SCC *C = &InitialC;

    // Collect value handles for all of the indirect call sites.
    SmallVector<WeakTrackingVH, 8> CallHandles;

    // Struct to track the counts of direct and indirect calls in each function
    // of the SCC.
    struct CallCount {
      int Direct;
      int Indirect;
    };

    // Put value handles on all of the indirect calls and return the number of
    // direct calls for each function in the SCC.
    auto ScanSCC = [](LazyCallGraph::SCC &C,
                      SmallVectorImpl<WeakTrackingVH> &CallHandles) {
      assert(CallHandles.empty() && "Must start with a clear set of handles.");

      SmallVector<CallCount, 4> CallCounts;
      for (LazyCallGraph::Node &N : C) {
        CallCounts.push_back({0, 0});
        CallCount &Count = CallCounts.back();
        for (Instruction &I : instructions(N.getFunction()))
          if (auto CS = CallSite(&I)) {
            if (CS.getCalledFunction()) {
              ++Count.Direct;
            } else {
              ++Count.Indirect;
              CallHandles.push_back(WeakTrackingVH(&I));
            }
          }
      }

      return CallCounts;
    };

    // Populate the initial call handles and get the initial call counts.
    auto CallCounts = ScanSCC(*C, CallHandles);

    for (int Iteration = 0;; ++Iteration) {

      if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
        continue;

      PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);

      if (UR.InvalidatedSCCs.count(C))
        PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
      else
        PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);

      // If the SCC structure has changed, bail immediately and let the outer
      // CGSCC layer handle any iteration to reflect the refined structure.
      if (UR.UpdatedC && UR.UpdatedC != C) {
        PA.intersect(std::move(PassPA));
        break;
      }

      // Check that we didn't miss any update scenario.
      assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
      assert(C->begin() != C->end() && "Cannot have an empty SCC!");
      assert((int)CallCounts.size() == C->size() &&
             "Cannot have changed the size of the SCC!");

      // Check whether any of the handles were devirtualized.
      auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
        if (!CallH)
          return false;
        auto CS = CallSite(CallH);
        if (!CS)
          return false;

        // If the call is still indirect, leave it alone.
        Function *F = CS.getCalledFunction();
        if (!F)
          return false;

        LLVM_DEBUG(dbgs() << "Found devirutalized call from "
                          << CS.getParent()->getParent()->getName() << " to "
                          << F->getName() << "\n");

        // We now have a direct call where previously we had an indirect call,
        // so iterate to process this devirtualization site.
        return true;
      };
      bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);

      // Rescan to build up a new set of handles and count how many direct
      // calls remain. If we decide to iterate, this also sets up the input to
      // the next iteration.
      CallHandles.clear();
      auto NewCallCounts = ScanSCC(*C, CallHandles);

      // If we haven't found an explicit devirtualization already see if we
      // have decreased the number of indirect calls and increased the number
      // of direct calls for any function in the SCC. This can be fooled by all
      // manner of transformations such as DCE and other things, but seems to
      // work well in practice.
      if (!Devirt)
        for (int i = 0, Size = C->size(); i < Size; ++i)
          if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
              CallCounts[i].Direct < NewCallCounts[i].Direct) {
            Devirt = true;
            break;
          }

      if (!Devirt) {
        PA.intersect(std::move(PassPA));
        break;
      }

      // Otherwise, if we've already hit our max, we're done.
      if (Iteration >= MaxIterations) {
        LLVM_DEBUG(
            dbgs() << "Found another devirtualization after hitting the max "
                      "number of repetitions ("
                   << MaxIterations << ") on SCC: " << *C << "\n");
        PA.intersect(std::move(PassPA));
        break;
      }

      LLVM_DEBUG(
          dbgs()
          << "Repeating an SCC pass after finding a devirtualization in: " << *C
          << "\n");

      // Move over the new call counts in preparation for iterating.
      CallCounts = std::move(NewCallCounts);

      // Update the analysis manager with each run and intersect the total set
      // of preserved analyses so we're ready to iterate.
      AM.invalidate(*C, PassPA);
      PA.intersect(std::move(PassPA));
    }

    // Note that we don't add any preserved entries here unlike a more normal
    // "pass manager" because we only handle invalidation *between* iterations,
    // not after the last iteration.
    return PA;
  }

private:
  PassT Pass;
  int MaxIterations;
};

/// A function to deduce a function pass type and wrap it in the
/// templated adaptor.
template <typename PassT>
DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
                                                         int MaxIterations) {
  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
}

// Out-of-line implementation details for templates below this point.

template <typename CGSCCPassT>
PreservedAnalyses
ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::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;

  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
      InlinedInternalEdges;

  CGSCCUpdateResult UR = {
      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};

  // Request PassInstrumentation from analysis manager, will use it to run
  // instrumenting callbacks for the passes later.
  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);

  PreservedAnalyses PA = PreservedAnalyses::all();
  CG.buildRefSCCs();
  for (auto RCI = CG.postorder_ref_scc_begin(),
            RCE = CG.postorder_ref_scc_end();
       RCI != RCE;) {
    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.
    //
    // We also eagerly increment the iterator to the next position because
    // the CGSCC passes below may delete the current RefSCC.
    RCWorklist.insert(&*RCI++);

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

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

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

      // Push the initial SCCs in reverse post-order as we'll pop off the
      // back and so see this in post-order.
      for (LazyCallGraph::SCC &C : llvm::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)) {
          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
          continue;
        }
        if (&C->getOuterRefSCC() != RC) {
          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
                               "RefSCC...\n");
          continue;
        }

        // Ensure we can proxy analysis updates from from the CGSCC analysis
        // manager into the Function analysis manager by getting a proxy here.
        // FIXME: This seems like a bit of a hack. We should find a cleaner
        // or more costructive way to ensure this happens.
        (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG);

        // Each time we visit a new SCC pulled off the worklist,
        // a transformation of a child SCC may have also modified this parent
        // and invalidated analyses. So we invalidate using the update record's
        // cross-SCC preserved set. This preserved set is intersected by any
        // CGSCC pass that handles invalidation (primarily pass managers) prior
        // to marking its SCC as preserved. That lets us track everything that
        // might need invalidation across SCCs without excessive invalidations
        // on a single SCC.
        //
        // This essentially allows SCC passes to freely invalidate analyses
        // of any ancestor SCC. If this becomes detrimental to successfully
        // caching analyses, we could force each SCC pass to manually
        // invalidate the analyses for any SCCs other than themselves which
        // are mutated. However, that seems to lose the robustness of the
        // pass-manager driven invalidation scheme.
        //
        // FIXME: This is redundant in one case -- the top of the worklist may
        // *also* be the same SCC we just ran over (and invalidated for). In
        // that case, we'll end up doing a redundant invalidation here as
        // a consequence.
        CGAM.invalidate(*C, UR.CrossSCCPA);

        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;

          // Check the PassInstrumentation's BeforePass callbacks before
          // running the pass, skip its execution completely if asked to
          // (callback returns false).
          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
            continue;

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

          if (UR.InvalidatedSCCs.count(C))
            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
          else
            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);

          // Update the SCC and RefSCC if necessary.
          C = UR.UpdatedC ? UR.UpdatedC : C;
          RC = UR.UpdatedRC ? UR.UpdatedRC : RC;

          // If the CGSCC pass wasn't able to provide a valid updated SCC,
          // the current SCC may simply need to be skipped if invalid.
          if (UR.InvalidatedSCCs.count(C)) {
            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
            break;
          }
          // Check that we didn't miss any update scenario.
          assert(C->begin() != C->end() && "Cannot have an empty SCC!");

          // 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(*C, PassPA);

          // Then intersect the preserved set so that invalidation of module
          // analyses will eventually occur when the module pass completes.
          // Also intersect with the cross-SCC preserved set to capture any
          // cross-SCC invalidation.
          UR.CrossSCCPA.intersect(PassPA);
          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.
          if (UR.UpdatedC)
            LLVM_DEBUG(dbgs()
                       << "Re-running SCC passes after a refinement of the "
                          "current SCC: "
                       << *UR.UpdatedC << "\n");

          // Note that both `C` and `RC` may at this point refer to deleted,
          // invalid SCC and RefSCCs respectively. But we will short circuit
          // the processing when we check them in the loop above.
        } while (UR.UpdatedC);
      } while (!CWorklist.empty());

      // We only need to keep internal inlined edge information within
      // a RefSCC, clear it to save on space and let the next time we visit
      // any of these functions have a fresh start.
      InlinedInternalEdges.clear();
    } 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.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
  PA.preserve<LazyCallGraphAnalysis>();
  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
  PA.preserve<FunctionAnalysisManagerModuleProxy>();
  return PA;
}

// Clear out the debug logging macro.
#undef DEBUG_TYPE

} // end namespace llvm

#endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H