LCOV - code coverage report
Current view: top level - include/llvm/Analysis - CGSCCPassManager.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 249 290 85.9 %
Date: 2018-10-19 05:06:59 Functions: 10 22 45.5 %
Legend: Lines: hit not hit

          Line data    Source code
       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           0 :   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
     160             :                         LazyCallGraph &CG, CGSCCUpdateResult &) {
     161             :     (void)AM.template getResult<AnalysisT>(C, CG);
     162             :     return PreservedAnalyses::all();
     163             :   }
     164           0 : };
     165             : 
     166             : /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
     167             : using CGSCCAnalysisManagerModuleProxy =
     168             :     InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
     169           0 : 
     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           0 : public:
     175             :   explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
     176             :       : InnerAM(&InnerAM), G(&G) {}
     177             : 
     178             :   /// Accessor for the analysis manager.
     179             :   CGSCCAnalysisManager &getManager() { return *InnerAM; }
     180             : 
     181             :   /// Handler for invalidation of the Module.
     182             :   ///
     183             :   /// If the proxy analysis itself is preserved, then we assume that the set of
     184             :   /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the
     185             :   /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear
     186             :   /// on the CGSCCAnalysisManager.
     187             :   ///
     188             :   /// Regardless of whether this analysis is marked as preserved, all of the
     189           0 :   /// 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           0 : 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             :       : 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             :       : Pass(std::move(Arg.Pass)) {}
     329             : 
     330          34 :   friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
     331             :                    ModuleToPostOrderCGSCCPassAdaptor &RHS) {
     332             :     std::swap(LHS.Pass, RHS.Pass);
     333             :   }
     334             : 
     335             :   ModuleToPostOrderCGSCCPassAdaptor &
     336             :   operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
     337          27 :     swap(*this, RHS);
     338             :     return *this;
     339             :   }
     340             : 
     341             :   /// Runs the CGSCC pass across every SCC in the module.
     342         178 :   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     343             :     // Setup the CGSCC analysis manager from its proxy.
     344             :     CGSCCAnalysisManager &CGAM =
     345             :         AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
     346             : 
     347             :     // Get the call graph for this module.
     348             :     LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
     349             : 
     350             :     // We keep worklists to allow us to push more work onto the pass manager as
     351             :     // the passes are run.
     352          27 :     SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
     353             :     SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
     354             : 
     355          27 :     // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
     356             :     // iterating off the worklists.
     357         303 :     SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
     358             :     SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
     359             : 
     360         303 :     SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
     361             :         InlinedInternalEdges;
     362             : 
     363             :     CGSCCUpdateResult UR = {RCWorklist,          CWorklist, InvalidRefSCCSet,
     364             :                             InvalidSCCSet,       nullptr,   nullptr,
     365             :                             InlinedInternalEdges};
     366             : 
     367             :     // Request PassInstrumentation from analysis manager, will use it to run
     368             :     // instrumenting callbacks for the passes later.
     369             :     PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
     370             : 
     371             :     PreservedAnalyses PA = PreservedAnalyses::all();
     372             :     CG.buildRefSCCs();
     373          27 :     for (auto RCI = CG.postorder_ref_scc_begin(),
     374             :               RCE = CG.postorder_ref_scc_end();
     375             :          RCI != RCE;) {
     376             :       assert(RCWorklist.empty() &&
     377             :              "Should always start with an empty RefSCC worklist");
     378         303 :       // The postorder_ref_sccs range we are walking is lazily constructed, so
     379          27 :       // we only push the first one onto the worklist. The worklist allows us
     380             :       // to capture *new* RefSCCs created during transformations.
     381             :       //
     382          27 :       // We really want to form RefSCCs lazily because that makes them cheaper
     383          27 :       // to update as the program is simplified and allows us to have greater
     384         303 :       // cache locality as forming a RefSCC touches all the parts of all the
     385             :       // functions within that RefSCC.
     386             :       //
     387         303 :       // We also eagerly increment the iterator to the next position because
     388         303 :       // the CGSCC passes below may delete the current RefSCC.
     389             :       RCWorklist.insert(&*RCI++);
     390             : 
     391             :       do {
     392             :         LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
     393             :         if (InvalidRefSCCSet.count(RC)) {
     394             :           LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
     395             :           continue;
     396             :         }
     397             : 
     398             :         assert(CWorklist.empty() &&
     399         102 :                "Should always start with an empty SCC worklist");
     400             : 
     401             :         LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
     402             :                           << "\n");
     403         102 : 
     404         908 :         // Push the initial SCCs in reverse post-order as we'll pop off the
     405             :         // back and so see this in post-order.
     406             :         for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
     407             :           CWorklist.insert(&C);
     408         933 : 
     409             :         do {
     410             :           LazyCallGraph::SCC *C = CWorklist.pop_back_val();
     411             :           // Due to call graph mutations, we may have invalid SCCs or SCCs from
     412             :           // other RefSCCs in the worklist. The invalid ones are dead and the
     413             :           // other RefSCCs should be queued above, so we just need to skip both
     414             :           // scenarios here.
     415             :           if (InvalidSCCSet.count(C)) {
     416         208 :             LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
     417         106 :             continue;
     418             :           }
     419             :           if (&C->getOuterRefSCC() != RC) {
     420             :             LLVM_DEBUG(dbgs()
     421        1887 :                        << "Skipping an SCC that is now part of some other "
     422         958 :                           "RefSCC...\n");
     423             :             continue;
     424             :           }
     425         108 : 
     426             :           do {
     427             :             // Check that we didn't miss any update scenario.
     428             :             assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
     429         107 :             assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     430         995 :             assert(&C->getOuterRefSCC() == RC &&
     431             :                    "Processing an SCC in a different RefSCC!");
     432             : 
     433             :             UR.UpdatedRC = nullptr;
     434         991 :             UR.UpdatedC = nullptr;
     435             : 
     436         109 :             // Check the PassInstrumentation's BeforePass callbacks before
     437             :             // running the pass, skip its execution completely if asked to
     438             :             // (callback returns false).
     439             :             if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
     440             :               continue;
     441        1000 : 
     442             :             PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
     443         109 : 
     444         109 :             PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
     445             : 
     446             :             // Update the SCC and RefSCC if necessary.
     447             :             C = UR.UpdatedC ? UR.UpdatedC : C;
     448        1002 :             RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
     449        1111 : 
     450           0 :             // If the CGSCC pass wasn't able to provide a valid updated SCC,
     451             :             // the current SCC may simply need to be skipped if invalid.
     452         218 :             if (UR.InvalidatedSCCs.count(C)) {
     453             :               LLVM_DEBUG(dbgs()
     454        1111 :                          << "Skipping invalidated root or island SCC!\n");
     455           0 :               break;
     456             :             }
     457        2111 :             // Check that we didn't miss any update scenario.
     458         109 :             assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     459        1002 : 
     460             :             // We handle invalidating the CGSCC analysis manager's information
     461             :             // for the (potentially updated) SCC here. Note that any other SCCs
     462        1111 :             // whose structure has changed should have been invalidated by
     463        1002 :             // whatever was updating the call graph. This SCC gets invalidated
     464             :             // late as it contains the nodes that were actively being
     465           0 :             // processed.
     466             :             CGAM.invalidate(*C, PassPA);
     467        1002 : 
     468             :             // Then intersect the preserved set so that invalidation of module
     469             :             // analyses will eventually occur when the module pass completes.
     470           2 :             PA.intersect(std::move(PassPA));
     471             : 
     472             :             // The pass may have restructured the call graph and refined the
     473             :             // current SCC and/or RefSCC. We need to update our current SCC and
     474             :             // RefSCC pointers to follow these. Also, when the current SCC is
     475             :             // refined, re-run the SCC pass over the newly refined SCC in order
     476         109 :             // to observe the most precise SCC model available. This inherently
     477             :             // cannot cycle excessively as it only happens when we split SCCs
     478             :             // apart, at most converging on a DAG of single nodes.
     479             :             // FIXME: If we ever start having RefSCC passes, we'll want to
     480         109 :             // iterate there too.
     481        1000 :             if (UR.UpdatedC)
     482             :               LLVM_DEBUG(dbgs()
     483             :                          << "Re-running SCC passes after a refinement of the "
     484             :                             "current SCC: "
     485        1000 :                          << *UR.UpdatedC << "\n");
     486             : 
     487             :             // Note that both `C` and `RC` may at this point refer to deleted,
     488             :             // invalid SCC and RefSCCs respectively. But we will short circuit
     489             :             // the processing when we check them in the loop above.
     490             :           } while (UR.UpdatedC);
     491             :         } while (!CWorklist.empty());
     492             : 
     493             :         // We only need to keep internal inlined edge information within
     494             :         // a RefSCC, clear it to save on space and let the next time we visit
     495             :         // any of these functions have a fresh start.
     496             :         InlinedInternalEdges.clear();
     497             :       } while (!RCWorklist.empty());
     498             :     }
     499             : 
     500         109 :     // By definition we preserve the call garph, all SCC analyses, and the
     501         108 :     // analysis proxies by handling them above and in any nested pass managers.
     502             :     PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
     503             :     PA.preserve<LazyCallGraphAnalysis>();
     504             :     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
     505        1000 :     PA.preserve<FunctionAnalysisManagerModuleProxy>();
     506         995 :     return PA;
     507         102 :   }
     508             : 
     509             : private:
     510             :   CGSCCPassT Pass;
     511             : };
     512         933 : 
     513             : /// A function to deduce a function pass type and wrap it in the
     514             : /// templated adaptor.
     515             : template <typename CGSCCPassT>
     516          27 : ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
     517             : createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
     518             :   return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
     519             : }
     520             : 
     521         303 : /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
     522             : ///
     523         178 : /// 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         178 : /// invalidation logic. Instead, this layer is only responsible for SCC-local
     527          27 : /// invalidation events. We work with the module's FunctionAnalysisManager to
     528          27 : /// invalidate function analyses.
     529             : class FunctionAnalysisManagerCGSCCProxy
     530             :     : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
     531             : public:
     532             :   class Result {
     533             :   public:
     534             :     explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
     535             : 
     536             :     /// Accessor for the analysis manager.
     537           0 :     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         178 :   };
     545             : 
     546             :   /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
     547           0 :   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
     548             : 
     549             : private:
     550         178 :   friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
     551             : 
     552             :   static AnalysisKey Key;
     553         178 : };
     554         178 : 
     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         744 : 
     571             : /// Adaptor that maps from a SCC to its functions.
     572             : ///
     573             : /// Designed to allow composition of a FunctionPass(Manager) and
     574         768 : /// 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             :       : Pass(std::move(Pass)) {}
     585             : 
     586             :   // We have to explicitly define all the special member functions because MSVC
     587        1557 :   // refuses to generate them.
     588         793 :   CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
     589             :       : Pass(Arg.Pass) {}
     590             : 
     591             :   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
     592             :       : Pass(std::move(Arg.Pass)) {}
     593           0 : 
     594           0 :   friend void swap(CGSCCToFunctionPassAdaptor &LHS,
     595             :                    CGSCCToFunctionPassAdaptor &RHS) {
     596         829 :     std::swap(LHS.Pass, RHS.Pass);
     597             :   }
     598             : 
     599             :   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
     600         825 :     swap(*this, RHS);
     601          15 :     return *this;
     602           0 :   }
     603             : 
     604             :   /// Runs the function pass across every function in the module.
     605             :   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
     606             :                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     607         834 :     // Setup the function analysis manager from its proxy.
     608             :     FunctionAnalysisManager &FAM =
     609             :         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
     610             : 
     611             :     SmallVector<LazyCallGraph::Node *, 4> Nodes;
     612             :     for (LazyCallGraph::Node &N : C)
     613             :       Nodes.push_back(&N);
     614         836 : 
     615         884 :     // The SCC may get split while we are optimizing functions due to deleting
     616             :     // edges. If this happens, the current SCC can shift, so keep track of
     617             :     // a pointer we can overwrite.
     618             :     LazyCallGraph::SCC *CurrentC = &C;
     619          48 : 
     620         836 :     LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
     621           0 :                       << "\n");
     622         118 : 
     623        1740 :     PreservedAnalyses PA = PreservedAnalyses::all();
     624             :     for (LazyCallGraph::Node *N : Nodes) {
     625         836 :       // Skip nodes from other SCCs. These may have been split out during
     626             :       // processing. We'll eventually visit those SCCs and pick up the nodes
     627             :       // there.
     628         836 :       if (CG.lookupSCC(*N) != CurrentC)
     629         836 :         continue;
     630             : 
     631             :       Function &F = N->getFunction();
     632             : 
     633         836 :       PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
     634         118 :       if (!PI.runBeforePass<Function>(Pass, F))
     635             :         continue;
     636           2 : 
     637             :       PreservedAnalyses PassPA = Pass.run(F, FAM);
     638          70 : 
     639           0 :       PI.runAfterPass<Function>(Pass, F);
     640             : 
     641          70 :       // We know that the function pass couldn't have invalidated any other
     642             :       // function's analyses (that's the contract of a function pass), so
     643          70 :       // directly handle the function analysis manager's invalidation here.
     644          70 :       FAM.invalidate(F, PassPA);
     645           0 : 
     646             :       // Then intersect the preserved set so that invalidation of module
     647         974 :       // analyses will eventually occur when the module pass completes.
     648             :       PA.intersect(std::move(PassPA));
     649          70 : 
     650             :       // If the call graph hasn't been preserved, update it based on this
     651         834 :       // function pass. This may also update the current SCC to point to
     652             :       // a smaller, more refined SCC.
     653             :       auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
     654          70 :       if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
     655             :         CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
     656             :                                                               AM, UR);
     657             :         assert(
     658          70 :             CG.lookupSCC(*N) == CurrentC &&
     659             :             "Current SCC not updated to the SCC containing the current node!");
     660             :       }
     661             :     }
     662             : 
     663             :     // By definition we preserve the proxy. And we preserve all analyses on
     664          70 :     // Functions. This precludes *any* invalidation of function analyses by the
     665             :     // proxy, but that's OK because we've taken care to invalidate analyses in
     666          19 :     // the function analysis manager incrementally above.
     667             :     PA.preserveSet<AllAnalysesOn<Function>>();
     668             :     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
     669             : 
     670             :     // We've also ensured that we updated the call graph along the way.
     671         834 :     PA.preserve<LazyCallGraphAnalysis>();
     672         829 : 
     673             :     return PA;
     674             :   }
     675             : 
     676             : private:
     677             :   FunctionPassT Pass;
     678         768 : };
     679             : 
     680             : /// A function to deduce a function pass type and wrap it in the
     681             : /// templated adaptor.
     682             : template <typename FunctionPassT>
     683          48 : CGSCCToFunctionPassAdaptor<FunctionPassT>
     684             : createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
     685          48 :   return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
     686             : }
     687         178 : 
     688             : /// A helper that repeats an SCC pass each time an indirect call is refined to
     689         121 : /// a direct call by that pass.
     690             : ///
     691             : /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
     692         191 : /// change shape, we may also want to repeat an SCC pass if it simply refines
     693          70 : /// 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         118 :     : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
     705             : public:
     706             :   explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
     707             :       : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
     708          70 : 
     709           0 :   /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
     710          73 :   /// whenever an indirect call is refined.
     711          70 :   PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
     712             :                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     713          70 :     PreservedAnalyses PA = PreservedAnalyses::all();
     714          70 :     PassInstrumentation PI =
     715             :         AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
     716          73 : 
     717         140 :     // The SCC may be refined while we are running passes over it, so set up
     718             :     // a pointer that we can update.
     719         143 :     LazyCallGraph::SCC *C = &InitialC;
     720          73 : 
     721             :     // Collect value handles for all of the indirect call sites.
     722             :     SmallVector<WeakTrackingVH, 8> CallHandles;
     723             : 
     724          70 :     // Struct to track the counts of direct and indirect calls in each function
     725             :     // of the SCC.
     726             :     struct CallCount {
     727             :       int Direct;
     728          70 :       int Indirect;
     729             :     };
     730             : 
     731             :     // Put value handles on all of the indirect calls and return the number of
     732             :     // direct calls for each function in the SCC.
     733             :     auto ScanSCC = [](LazyCallGraph::SCC &C,
     734          70 :                       SmallVectorImpl<WeakTrackingVH> &CallHandles) {
     735             :       assert(CallHandles.empty() && "Must start with a clear set of handles.");
     736         155 : 
     737             :       SmallVector<CallCount, 4> CallCounts;
     738             :       for (LazyCallGraph::Node &N : C) {
     739             :         CallCounts.push_back({0, 0});
     740         137 :         CallCount &Count = CallCounts.back();
     741             :         for (Instruction &I : instructions(N.getFunction()))
     742             :           if (auto CS = CallSite(&I)) {
     743             :             if (CS.getCalledFunction()) {
     744             :               ++Count.Direct;
     745             :             } else {
     746             :               ++Count.Indirect;
     747             :               CallHandles.push_back(WeakTrackingVH(&I));
     748             :             }
     749             :           }
     750             :       }
     751             : 
     752             :       return CallCounts;
     753         322 :     };
     754         137 : 
     755           0 :     // Populate the initial call handles and get the initial call counts.
     756             :     auto CallCounts = ScanSCC(*C, CallHandles);
     757             : 
     758             :     for (int Iteration = 0;; ++Iteration) {
     759           0 : 
     760             :       if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
     761             :         continue;
     762         138 : 
     763           0 :       PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
     764             : 
     765             :       PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
     766         138 : 
     767             :       // If the SCC structure has changed, bail immediately and let the outer
     768             :       // CGSCC layer handle any iteration to reflect the refined structure.
     769             :       if (UR.UpdatedC && UR.UpdatedC != C) {
     770             :         PA.intersect(std::move(PassPA));
     771             :         break;
     772             :       }
     773         138 : 
     774           0 :       // Check that we didn't miss any update scenario.
     775             :       assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
     776             :       assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     777             :       assert((int)CallCounts.size() == C->size() &&
     778           0 :              "Cannot have changed the size of the SCC!");
     779           0 : 
     780         138 :       // Check whether any of the handles were devirtualized.
     781         138 :       auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
     782             :         if (!CallH)
     783           0 :           return false;
     784           0 :         auto CS = CallSite(CallH);
     785           0 :         if (!CS)
     786         138 :           return false;
     787           0 : 
     788             :         // If the call is still indirect, leave it alone.
     789         276 :         Function *F = CS.getCalledFunction();
     790             :         if (!F)
     791         138 :           return false;
     792             : 
     793             :         LLVM_DEBUG(dbgs() << "Found devirutalized call from "
     794         138 :                           << CS.getParent()->getParent()->getName() << " to "
     795         138 :                           << F->getName() << "\n");
     796             : 
     797             :         // We now have a direct call where previously we had an indirect call,
     798           0 :         // so iterate to process this devirtualization site.
     799         138 :         return true;
     800             :       };
     801             :       bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
     802           0 : 
     803             :       // Rescan to build up a new set of handles and count how many direct
     804           0 :       // calls remain. If we decide to iterate, this also sets up the input to
     805             :       // the next iteration.
     806           0 :       CallHandles.clear();
     807             :       auto NewCallCounts = ScanSCC(*C, CallHandles);
     808             : 
     809             :       // If we haven't found an explicit devirtualization already see if we
     810             :       // have decreased the number of indirect calls and increased the number
     811             :       // of direct calls for any function in the SCC. This can be fooled by all
     812             :       // manner of transformations such as DCE and other things, but seems to
     813         138 :       // work well in practice.
     814             :       if (!Devirt)
     815             :         for (int i = 0, Size = C->size(); i < Size; ++i)
     816             :           if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
     817         138 :               CallCounts[i].Direct < NewCallCounts[i].Direct) {
     818             :             Devirt = true;
     819             :             break;
     820             :           }
     821             : 
     822             :       if (!Devirt) {
     823           0 :         PA.intersect(std::move(PassPA));
     824             :         break;
     825             :       }
     826             : 
     827             :       // Otherwise, if we've already hit our max, we're done.
     828             :       if (Iteration >= MaxIterations) {
     829             :         LLVM_DEBUG(
     830             :             dbgs() << "Found another devirtualization after hitting the max "
     831             :                       "number of repetitions ("
     832             :                    << MaxIterations << ") on SCC: " << *C << "\n");
     833             :         PA.intersect(std::move(PassPA));
     834          15 :         break;
     835          15 :       }
     836             : 
     837         138 :       LLVM_DEBUG(
     838         138 :           dbgs()
     839             :           << "Repeating an SCC pass after finding a devirtualization in: " << *C
     840             :           << "\n");
     841             : 
     842             :       // Move over the new call counts in preparation for iterating.
     843             :       CallCounts = std::move(NewCallCounts);
     844         137 : 
     845             :       // Update the analysis manager with each run and intersect the total set
     846             :       // of preserved analyses so we're ready to iterate.
     847             :       AM.invalidate(*C, PassPA);
     848             :       PA.intersect(std::move(PassPA));
     849             :     }
     850             : 
     851             :     // Note that we don't add any preserved entries here unlike a more normal
     852             :     // "pass manager" because we only handle invalidation *between* iterations,
     853          73 :     // not after the last iteration.
     854             :     return PA;
     855          35 :   }
     856             : 
     857             : private:
     858          35 :   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             :                                                          int MaxIterations) {
     867             :   return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
     868             : }
     869             : 
     870             : // Clear out the debug logging macro.
     871             : #undef DEBUG_TYPE
     872             : 
     873             : } // end namespace llvm
     874             : 
     875             : #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H

Generated by: LCOV version 1.13