LCOV - code coverage report
Current view: top level - include/llvm/Analysis - CGSCCPassManager.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 87 88 98.9 %
Date: 2018-05-20 00:06:23 Functions: 16 18 88.9 %
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          64 :   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
     160             :                         LazyCallGraph &CG, CGSCCUpdateResult &) {
     161             :     (void)AM.template getResult<AnalysisT>(C, CG);
     162          64 :     return PreservedAnalyses::all();
     163             :   }
     164             : };
     165             : 
     166             : /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
     167             : using CGSCCAnalysisManagerModuleProxy =
     168             :     InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
     169             : 
     170             : /// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so
     171             : /// it can have access to the call graph in order to walk all the SCCs when
     172             : /// invalidating things.
     173             : template <> class CGSCCAnalysisManagerModuleProxy::Result {
     174             : public:
     175             :   explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G)
     176             :       : 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             :   /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based
     190             :   /// on the set of preserved analyses.
     191             :   bool invalidate(Module &M, const PreservedAnalyses &PA,
     192             :                   ModuleAnalysisManager::Invalidator &Inv);
     193             : 
     194             : private:
     195             :   CGSCCAnalysisManager *InnerAM;
     196             :   LazyCallGraph *G;
     197             : };
     198             : 
     199             : /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy
     200             : /// so it can pass the lazy call graph to the result.
     201             : template <>
     202             : CGSCCAnalysisManagerModuleProxy::Result
     203             : CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM);
     204             : 
     205             : // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern
     206             : // template.
     207             : extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
     208             : 
     209             : extern template class OuterAnalysisManagerProxy<
     210             :     ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
     211             : 
     212             : /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
     213             : using ModuleAnalysisManagerCGSCCProxy =
     214             :     OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
     215             :                               LazyCallGraph &>;
     216             : 
     217             : /// Support structure for SCC passes to communicate updates the call graph back
     218             : /// to the CGSCC pass manager infrsatructure.
     219             : ///
     220             : /// The CGSCC pass manager runs SCC passes which are allowed to update the call
     221             : /// graph and SCC structures. This means the structure the pass manager works
     222             : /// on is mutating underneath it. In order to support that, there needs to be
     223             : /// careful communication about the precise nature and ramifications of these
     224             : /// updates to the pass management infrastructure.
     225             : ///
     226             : /// All SCC passes will have to accept a reference to the management layer's
     227             : /// update result struct and use it to reflect the results of any CG updates
     228             : /// performed.
     229             : ///
     230             : /// Passes which do not change the call graph structure in any way can just
     231             : /// ignore this argument to their run method.
     232             : struct CGSCCUpdateResult {
     233             :   /// Worklist of the RefSCCs queued for processing.
     234             :   ///
     235             :   /// When a pass refines the graph and creates new RefSCCs or causes them to
     236             :   /// have a different shape or set of component SCCs it should add the RefSCCs
     237             :   /// to this worklist so that we visit them in the refined form.
     238             :   ///
     239             :   /// This worklist is in reverse post-order, as we pop off the back in order
     240             :   /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
     241             :   /// them in reverse post-order.
     242             :   SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist;
     243             : 
     244             :   /// Worklist of the SCCs queued for processing.
     245             :   ///
     246             :   /// When a pass refines the graph and creates new SCCs or causes them to have
     247             :   /// a different shape or set of component functions it should add the SCCs to
     248             :   /// this worklist so that we visit them in the refined form.
     249             :   ///
     250             :   /// Note that if the SCCs are part of a RefSCC that is added to the \c
     251             :   /// RCWorklist, they don't need to be added here as visiting the RefSCC will
     252             :   /// be sufficient to re-visit the SCCs within it.
     253             :   ///
     254             :   /// This worklist is in reverse post-order, as we pop off the back in order
     255             :   /// to observe SCCs in post-order. When adding SCCs, clients should add them
     256             :   /// in reverse post-order.
     257             :   SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist;
     258             : 
     259             :   /// The set of invalidated RefSCCs which should be skipped if they are found
     260             :   /// in \c RCWorklist.
     261             :   ///
     262             :   /// This is used to quickly prune out RefSCCs when they get deleted and
     263             :   /// happen to already be on the worklist. We use this primarily to avoid
     264             :   /// scanning the list and removing entries from it.
     265             :   SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;
     266             : 
     267             :   /// The set of invalidated SCCs which should be skipped if they are found
     268             :   /// in \c CWorklist.
     269             :   ///
     270             :   /// This is used to quickly prune out SCCs when they get deleted and happen
     271             :   /// to already be on the worklist. We use this primarily to avoid scanning
     272             :   /// the list and removing entries from it.
     273             :   SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
     274             : 
     275             :   /// If non-null, the updated current \c RefSCC being processed.
     276             :   ///
     277             :   /// This is set when a graph refinement takes place an the "current" point in
     278             :   /// the graph moves "down" or earlier in the post-order walk. This will often
     279             :   /// cause the "current" RefSCC to be a newly created RefSCC object and the
     280             :   /// old one to be added to the above worklist. When that happens, this
     281             :   /// pointer is non-null and can be used to continue processing the "top" of
     282             :   /// the post-order walk.
     283             :   LazyCallGraph::RefSCC *UpdatedRC;
     284             : 
     285             :   /// If non-null, the updated current \c SCC being processed.
     286             :   ///
     287             :   /// This is set when a graph refinement takes place an the "current" point in
     288             :   /// the graph moves "down" or earlier in the post-order walk. This will often
     289             :   /// cause the "current" SCC to be a newly created SCC object and the old one
     290             :   /// to be added to the above worklist. When that happens, this pointer is
     291             :   /// non-null and can be used to continue processing the "top" of the
     292             :   /// post-order walk.
     293             :   LazyCallGraph::SCC *UpdatedC;
     294             : 
     295             :   /// A hacky area where the inliner can retain history about inlining
     296             :   /// decisions that mutated the call graph's SCC structure in order to avoid
     297             :   /// infinite inlining. See the comments in the inliner's CG update logic.
     298             :   ///
     299             :   /// FIXME: Keeping this here seems like a big layering issue, we should look
     300             :   /// for a better technique.
     301             :   SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
     302             :       &InlinedInternalEdges;
     303             : };
     304             : 
     305             : /// The core module pass which does a post-order walk of the SCCs and
     306             : /// runs a CGSCC pass over each one.
     307             : ///
     308             : /// Designed to allow composition of a CGSCCPass(Manager) and
     309             : /// a ModulePassManager. Note that this pass must be run with a module analysis
     310             : /// manager as it uses the LazyCallGraph analysis. It will also run the
     311             : /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
     312             : /// pass over the module to enable a \c FunctionAnalysisManager to be used
     313             : /// within this run safely.
     314             : template <typename CGSCCPassT>
     315             : class ModuleToPostOrderCGSCCPassAdaptor
     316             :     : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
     317             : public:
     318             :   explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
     319             :       : 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         555 :   ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
     328             :       : Pass(std::move(Arg.Pass)) {}
     329             : 
     330             :   friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
     331             :                    ModuleToPostOrderCGSCCPassAdaptor &RHS) {
     332             :     std::swap(LHS.Pass, RHS.Pass);
     333             :   }
     334             : 
     335             :   ModuleToPostOrderCGSCCPassAdaptor &
     336             :   operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
     337             :     swap(*this, RHS);
     338             :     return *this;
     339             :   }
     340             : 
     341             :   /// Runs the CGSCC pass across every SCC in the module.
     342         306 :   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     343             :     // Setup the CGSCC analysis manager from its proxy.
     344         306 :     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             :     SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
     353             :     SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
     354             : 
     355             :     // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
     356             :     // iterating off the worklists.
     357             :     SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
     358             :     SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
     359             : 
     360             :     SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
     361             :         InlinedInternalEdges;
     362             : 
     363         306 :     CGSCCUpdateResult UR = {RCWorklist,          CWorklist, InvalidRefSCCSet,
     364             :                             InvalidSCCSet,       nullptr,   nullptr,
     365             :                             InlinedInternalEdges};
     366             : 
     367             :     PreservedAnalyses PA = PreservedAnalyses::all();
     368         306 :     CG.buildRefSCCs();
     369         306 :     for (auto RCI = CG.postorder_ref_scc_begin(),
     370             :               RCE = CG.postorder_ref_scc_end();
     371             :          RCI != RCE;) {
     372             :       assert(RCWorklist.empty() &&
     373             :              "Should always start with an empty RefSCC worklist");
     374             :       // The postorder_ref_sccs range we are walking is lazily constructed, so
     375             :       // we only push the first one onto the worklist. The worklist allows us
     376             :       // to capture *new* RefSCCs created during transformations.
     377             :       //
     378             :       // We really want to form RefSCCs lazily because that makes them cheaper
     379             :       // to update as the program is simplified and allows us to have greater
     380             :       // cache locality as forming a RefSCC touches all the parts of all the
     381             :       // functions within that RefSCC.
     382             :       //
     383             :       // We also eagerly increment the iterator to the next position because
     384             :       // the CGSCC passes below may delete the current RefSCC.
     385         947 :       RCWorklist.insert(&*RCI++);
     386             : 
     387             :       do {
     388             :         LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
     389         972 :         if (InvalidRefSCCSet.count(RC)) {
     390             :           LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
     391           4 :           continue;
     392             :         }
     393             : 
     394             :         assert(CWorklist.empty() &&
     395             :                "Should always start with an empty SCC worklist");
     396             : 
     397             :         LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
     398             :                           << "\n");
     399             : 
     400             :         // Push the initial SCCs in reverse post-order as we'll pop off the
     401             :         // back and so see this in post-order.
     402        1969 :         for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
     403        1001 :           CWorklist.insert(&C);
     404             : 
     405             :         do {
     406             :           LazyCallGraph::SCC *C = CWorklist.pop_back_val();
     407             :           // Due to call graph mutations, we may have invalid SCCs or SCCs from
     408             :           // other RefSCCs in the worklist. The invalid ones are dead and the
     409             :           // other RefSCCs should be queued above, so we just need to skip both
     410             :           // scenarios here.
     411        1040 :           if (InvalidSCCSet.count(C)) {
     412             :             LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
     413           5 :             continue;
     414             :           }
     415        1035 :           if (&C->getOuterRefSCC() != RC) {
     416             :             LLVM_DEBUG(dbgs()
     417             :                        << "Skipping an SCC that is now part of some other "
     418             :                           "RefSCC...\n");
     419          20 :             continue;
     420             :           }
     421             : 
     422        1046 :           do {
     423             :             // Check that we didn't miss any update scenario.
     424             :             assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
     425             :             assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     426             :             assert(&C->getOuterRefSCC() == RC &&
     427             :                    "Processing an SCC in a different RefSCC!");
     428             : 
     429        1048 :             UR.UpdatedRC = nullptr;
     430        1048 :             UR.UpdatedC = nullptr;
     431        2094 :             PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
     432             : 
     433             :             // Update the SCC and RefSCC if necessary.
     434        1048 :             C = UR.UpdatedC ? UR.UpdatedC : C;
     435        1048 :             RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
     436             : 
     437             :             // If the CGSCC pass wasn't able to provide a valid updated SCC,
     438             :             // the current SCC may simply need to be skipped if invalid.
     439        1048 :             if (UR.InvalidatedSCCs.count(C)) {
     440             :               LLVM_DEBUG(dbgs()
     441             :                          << "Skipping invalidated root or island SCC!\n");
     442           2 :               break;
     443             :             }
     444             :             // Check that we didn't miss any update scenario.
     445             :             assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     446             : 
     447             :             // We handle invalidating the CGSCC analysis manager's information
     448             :             // for the (potentially updated) SCC here. Note that any other SCCs
     449             :             // whose structure has changed should have been invalidated by
     450             :             // whatever was updating the call graph. This SCC gets invalidated
     451             :             // late as it contains the nodes that were actively being
     452             :             // processed.
     453        1046 :             CGAM.invalidate(*C, PassPA);
     454             : 
     455             :             // Then intersect the preserved set so that invalidation of module
     456             :             // analyses will eventually occur when the module pass completes.
     457        1046 :             PA.intersect(std::move(PassPA));
     458             : 
     459             :             // The pass may have restructured the call graph and refined the
     460             :             // current SCC and/or RefSCC. We need to update our current SCC and
     461             :             // RefSCC pointers to follow these. Also, when the current SCC is
     462             :             // refined, re-run the SCC pass over the newly refined SCC in order
     463             :             // to observe the most precise SCC model available. This inherently
     464             :             // cannot cycle excessively as it only happens when we split SCCs
     465             :             // apart, at most converging on a DAG of single nodes.
     466             :             // FIXME: If we ever start having RefSCC passes, we'll want to
     467             :             // iterate there too.
     468             :             if (UR.UpdatedC)
     469             :               LLVM_DEBUG(dbgs()
     470             :                          << "Re-running SCC passes after a refinement of the "
     471             :                             "current SCC: "
     472             :                          << *UR.UpdatedC << "\n");
     473             : 
     474             :             // Note that both `C` and `RC` may at this point refer to deleted,
     475             :             // invalid SCC and RefSCCs respectively. But we will short circuit
     476             :             // the processing when we check them in the loop above.
     477        1046 :           } while (UR.UpdatedC);
     478        1040 :         } while (!CWorklist.empty());
     479             : 
     480             :         // We only need to keep internal inlined edge information within
     481             :         // a RefSCC, clear it to save on space and let the next time we visit
     482             :         // any of these functions have a fresh start.
     483             :         InlinedInternalEdges.clear();
     484         972 :       } while (!RCWorklist.empty());
     485             :     }
     486             : 
     487             :     // By definition we preserve the call garph, all SCC analyses, and the
     488             :     // analysis proxies by handling them above and in any nested pass managers.
     489             :     PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
     490             :     PA.preserve<LazyCallGraphAnalysis>();
     491             :     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
     492             :     PA.preserve<FunctionAnalysisManagerModuleProxy>();
     493         306 :     return PA;
     494             :   }
     495             : 
     496             : private:
     497             :   CGSCCPassT Pass;
     498             : };
     499             : 
     500             : /// A function to deduce a function pass type and wrap it in the
     501             : /// templated adaptor.
     502             : template <typename CGSCCPassT>
     503             : ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
     504         263 : createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
     505         277 :   return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
     506             : }
     507             : 
     508             : /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
     509             : ///
     510             : /// When a module pass runs and triggers invalidation, both the CGSCC and
     511             : /// Function analysis manager proxies on the module get an invalidation event.
     512             : /// We don't want to fully duplicate responsibility for most of the
     513             : /// invalidation logic. Instead, this layer is only responsible for SCC-local
     514             : /// invalidation events. We work with the module's FunctionAnalysisManager to
     515             : /// invalidate function analyses.
     516             : class FunctionAnalysisManagerCGSCCProxy
     517             :     : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
     518             : public:
     519             :   class Result {
     520             :   public:
     521             :     explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
     522             : 
     523             :     /// Accessor for the analysis manager.
     524        2058 :     FunctionAnalysisManager &getManager() { return *FAM; }
     525             : 
     526             :     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
     527             :                     CGSCCAnalysisManager::Invalidator &Inv);
     528             : 
     529             :   private:
     530             :     FunctionAnalysisManager *FAM;
     531             :   };
     532             : 
     533             :   /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
     534             :   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
     535             : 
     536             : private:
     537             :   friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
     538             : 
     539             :   static AnalysisKey Key;
     540             : };
     541             : 
     542             : extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
     543             : 
     544             : /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
     545             : using CGSCCAnalysisManagerFunctionProxy =
     546             :     OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
     547             : 
     548             : /// Helper to update the call graph after running a function pass.
     549             : ///
     550             : /// Function passes can only mutate the call graph in specific ways. This
     551             : /// routine provides a helper that updates the call graph in those ways
     552             : /// including returning whether any changes were made and populating a CG
     553             : /// update result struct for the overall CGSCC walk.
     554             : LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
     555             :     LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
     556             :     CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
     557             : 
     558             : /// Adaptor that maps from a SCC to its functions.
     559             : ///
     560             : /// Designed to allow composition of a FunctionPass(Manager) and
     561             : /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
     562             : /// to a \c CGSCCAnalysisManager it will run the
     563             : /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
     564             : /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
     565             : /// within this run safely.
     566             : template <typename FunctionPassT>
     567             : class CGSCCToFunctionPassAdaptor
     568             :     : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
     569             : public:
     570             :   explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
     571             :       : Pass(std::move(Pass)) {}
     572             : 
     573             :   // We have to explicitly define all the special member functions because MSVC
     574             :   // refuses to generate them.
     575             :   CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
     576             :       : Pass(Arg.Pass) {}
     577             : 
     578         234 :   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
     579             :       : Pass(std::move(Arg.Pass)) {}
     580             : 
     581             :   friend void swap(CGSCCToFunctionPassAdaptor &LHS,
     582             :                    CGSCCToFunctionPassAdaptor &RHS) {
     583             :     std::swap(LHS.Pass, RHS.Pass);
     584             :   }
     585             : 
     586             :   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
     587             :     swap(*this, RHS);
     588             :     return *this;
     589             :   }
     590             : 
     591             :   /// Runs the function pass across every function in the module.
     592         405 :   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
     593             :                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     594             :     // Setup the function analysis manager from its proxy.
     595             :     FunctionAnalysisManager &FAM =
     596             :         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
     597             : 
     598             :     SmallVector<LazyCallGraph::Node *, 4> Nodes;
     599         919 :     for (LazyCallGraph::Node &N : C)
     600         514 :       Nodes.push_back(&N);
     601             : 
     602             :     // The SCC may get split while we are optimizing functions due to deleting
     603             :     // edges. If this happens, the current SCC can shift, so keep track of
     604             :     // a pointer we can overwrite.
     605             :     LazyCallGraph::SCC *CurrentC = &C;
     606             : 
     607             :     LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C
     608             :                       << "\n");
     609             : 
     610             :     PreservedAnalyses PA = PreservedAnalyses::all();
     611        1433 :     for (LazyCallGraph::Node *N : Nodes) {
     612             :       // Skip nodes from other SCCs. These may have been split out during
     613             :       // processing. We'll eventually visit those SCCs and pick up the nodes
     614             :       // there.
     615         514 :       if (CG.lookupSCC(*N) != CurrentC)
     616          40 :         continue;
     617             : 
     618         948 :       PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
     619             : 
     620             :       // We know that the function pass couldn't have invalidated any other
     621             :       // function's analyses (that's the contract of a function pass), so
     622             :       // directly handle the function analysis manager's invalidation here.
     623         474 :       FAM.invalidate(N->getFunction(), PassPA);
     624             : 
     625             :       // Then intersect the preserved set so that invalidation of module
     626             :       // analyses will eventually occur when the module pass completes.
     627         474 :       PA.intersect(std::move(PassPA));
     628             : 
     629             :       // If the call graph hasn't been preserved, update it based on this
     630             :       // function pass. This may also update the current SCC to point to
     631             :       // a smaller, more refined SCC.
     632             :       auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
     633         474 :       if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
     634         159 :         CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
     635             :                                                               AM, UR);
     636             :         assert(
     637             :             CG.lookupSCC(*N) == CurrentC &&
     638             :             "Current SCC not updated to the SCC containing the current node!");
     639             :       }
     640             :     }
     641             : 
     642             :     // By definition we preserve the proxy. And we preserve all analyses on
     643             :     // Functions. This precludes *any* invalidation of function analyses by the
     644             :     // proxy, but that's OK because we've taken care to invalidate analyses in
     645             :     // the function analysis manager incrementally above.
     646             :     PA.preserveSet<AllAnalysesOn<Function>>();
     647             :     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
     648             : 
     649             :     // We've also ensured that we updated the call graph along the way.
     650             :     PA.preserve<LazyCallGraphAnalysis>();
     651             : 
     652         405 :     return PA;
     653             :   }
     654             : 
     655             : private:
     656             :   FunctionPassT Pass;
     657             : };
     658             : 
     659             : /// A function to deduce a function pass type and wrap it in the
     660             : /// templated adaptor.
     661             : template <typename FunctionPassT>
     662             : CGSCCToFunctionPassAdaptor<FunctionPassT>
     663         113 : createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
     664         113 :   return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
     665             : }
     666             : 
     667             : /// A helper that repeats an SCC pass each time an indirect call is refined to
     668             : /// a direct call by that pass.
     669             : ///
     670             : /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
     671             : /// change shape, we may also want to repeat an SCC pass if it simply refines
     672             : /// an indirect call to a direct call, even if doing so does not alter the
     673             : /// shape of the graph. Note that this only pertains to direct calls to
     674             : /// functions where IPO across the SCC may be able to compute more precise
     675             : /// results. For intrinsics, we assume scalar optimizations already can fully
     676             : /// reason about them.
     677             : ///
     678             : /// This repetition has the potential to be very large however, as each one
     679             : /// might refine a single call site. As a consequence, in practice we use an
     680             : /// upper bound on the number of repetitions to limit things.
     681             : template <typename PassT>
     682         474 : class DevirtSCCRepeatedPass
     683             :     : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
     684             : public:
     685             :   explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
     686          69 :       : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
     687             : 
     688             :   /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
     689             :   /// whenever an indirect call is refined.
     690         143 :   PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
     691             :                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     692             :     PreservedAnalyses PA = PreservedAnalyses::all();
     693             : 
     694             :     // The SCC may be refined while we are running passes over it, so set up
     695             :     // a pointer that we can update.
     696             :     LazyCallGraph::SCC *C = &InitialC;
     697             : 
     698             :     // Collect value handles for all of the indirect call sites.
     699         143 :     SmallVector<WeakTrackingVH, 8> CallHandles;
     700             : 
     701             :     // Struct to track the counts of direct and indirect calls in each function
     702             :     // of the SCC.
     703             :     struct CallCount {
     704             :       int Direct;
     705             :       int Indirect;
     706             :     };
     707             : 
     708             :     // Put value handles on all of the indirect calls and return the number of
     709             :     // direct calls for each function in the SCC.
     710           0 :     auto ScanSCC = [](LazyCallGraph::SCC &C,
     711         293 :                       SmallVectorImpl<WeakTrackingVH> &CallHandles) {
     712             :       assert(CallHandles.empty() && "Must start with a clear set of handles.");
     713             : 
     714             :       SmallVector<CallCount, 4> CallCounts;
     715         594 :       for (LazyCallGraph::Node &N : C) {
     716         301 :         CallCounts.push_back({0, 0});
     717         301 :         CallCount &Count = CallCounts.back();
     718        1701 :         for (Instruction &I : instructions(N.getFunction()))
     719        1400 :           if (auto CS = CallSite(&I)) {
     720             :             if (CS.getCalledFunction()) {
     721         258 :               ++Count.Direct;
     722             :             } else {
     723          22 :               ++Count.Indirect;
     724          66 :               CallHandles.push_back(WeakTrackingVH(&I));
     725             :             }
     726             :           }
     727             :       }
     728             : 
     729         293 :       return CallCounts;
     730             :     };
     731             : 
     732             :     // Populate the initial call handles and get the initial call counts.
     733         143 :     auto CallCounts = ScanSCC(*C, CallHandles);
     734             : 
     735           8 :     for (int Iteration = 0;; ++Iteration) {
     736         159 :       PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
     737             : 
     738             :       // If the SCC structure has changed, bail immediately and let the outer
     739             :       // CGSCC layer handle any iteration to reflect the refined structure.
     740         151 :       if (UR.UpdatedC && UR.UpdatedC != C) {
     741           1 :         PA.intersect(std::move(PassPA));
     742         144 :         break;
     743             :       }
     744             : 
     745             :       // Check that we didn't miss any update scenario.
     746             :       assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
     747             :       assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     748             :       assert((int)CallCounts.size() == C->size() &&
     749             :              "Cannot have changed the size of the SCC!");
     750             : 
     751             :       // Check whether any of the handles were devirtualized.
     752          16 :       auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
     753          16 :         if (!CallH)
     754             :           return false;
     755             :         auto CS = CallSite(CallH);
     756          14 :         if (!CS)
     757             :           return false;
     758             : 
     759             :         // If the call is still indirect, leave it alone.
     760             :         Function *F = CS.getCalledFunction();
     761             :         if (!F)
     762             :           return false;
     763             : 
     764             :         LLVM_DEBUG(dbgs() << "Found devirutalized call from "
     765             :                           << CS.getParent()->getParent()->getName() << " to "
     766             :                           << F->getName() << "\n");
     767             : 
     768             :         // We now have a direct call where previously we had an indirect call,
     769             :         // so iterate to process this devirtualization site.
     770             :         return true;
     771             :       };
     772             :       bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
     773             : 
     774             :       // Rescan to build up a new set of handles and count how many direct
     775             :       // calls remain. If we decide to iterate, this also sets up the input to
     776             :       // the next iteration.
     777             :       CallHandles.clear();
     778         150 :       auto NewCallCounts = ScanSCC(*C, CallHandles);
     779             : 
     780             :       // If we haven't found an explicit devirtualization already see if we
     781             :       // have decreased the number of indirect calls and increased the number
     782             :       // of direct calls for any function in the SCC. This can be fooled by all
     783             :       // manner of transformations such as DCE and other things, but seems to
     784             :       // work well in practice.
     785         150 :       if (!Devirt)
     786         427 :         for (int i = 0, Size = C->size(); i < Size; ++i)
     787         434 :           if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
     788           2 :               CallCounts[i].Direct < NewCallCounts[i].Direct) {
     789             :             Devirt = true;
     790             :             break;
     791             :           }
     792             : 
     793         150 :       if (!Devirt) {
     794         141 :         PA.intersect(std::move(PassPA));
     795         141 :         break;
     796             :       }
     797             : 
     798             :       // Otherwise, if we've already hit our max, we're done.
     799           9 :       if (Iteration >= MaxIterations) {
     800             :         LLVM_DEBUG(
     801             :             dbgs() << "Found another devirtualization after hitting the max "
     802             :                       "number of repetitions ("
     803             :                    << MaxIterations << ") on SCC: " << *C << "\n");
     804           1 :         PA.intersect(std::move(PassPA));
     805           1 :         break;
     806             :       }
     807             : 
     808             :       LLVM_DEBUG(
     809             :           dbgs()
     810             :           << "Repeating an SCC pass after finding a devirtualization in: " << *C
     811             :           << "\n");
     812             : 
     813             :       // Move over the new call counts in preparation for iterating.
     814             :       CallCounts = std::move(NewCallCounts);
     815             : 
     816             :       // Update the analysis manager with each run and intersect the total set
     817             :       // of preserved analyses so we're ready to iterate.
     818           8 :       AM.invalidate(*C, PassPA);
     819           8 :       PA.intersect(std::move(PassPA));
     820             :     }
     821             : 
     822             :     // Note that we don't add any preserved entries here unlike a more normal
     823             :     // "pass manager" because we only handle invalidation *between* iterations,
     824             :     // not after the last iteration.
     825         143 :     return PA;
     826             :   }
     827             : 
     828             : private:
     829             :   PassT Pass;
     830             :   int MaxIterations;
     831             : };
     832             : 
     833             : /// A function to deduce a function pass type and wrap it in the
     834             : /// templated adaptor.
     835             : template <typename PassT>
     836             : DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
     837             :                                                          int MaxIterations) {
     838          69 :   return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
     839             : }
     840             : 
     841             : // Clear out the debug logging macro.
     842             : #undef DEBUG_TYPE
     843             : 
     844             : } // end namespace llvm
     845             : 
     846             : #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H

Generated by: LCOV version 1.13