LCOV - code coverage report
Current view: top level - include/llvm/Analysis - CGSCCPassManager.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 124 125 99.2 %
Date: 2017-09-14 15:23:50 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             : /// \brief 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             : /// \brief 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          64 :     (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             :   /// \brief Accessor for the analysis manager.
     179             :   CGSCCAnalysisManager &getManager() { return *InnerAM; }
     180             : 
     181             :   /// \brief 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             : /// \brief 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        1338 : class ModuleToPostOrderCGSCCPassAdaptor
     316             :     : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
     317             : public:
     318          15 :   explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
     319         461 :       : 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         447 :   ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
     328         922 :       : 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             :   /// \brief Runs the CGSCC pass across every SCC in the module.
     342         238 :   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     343             :     // Setup the CGSCC analysis manager from its proxy.
     344         238 :     CGSCCAnalysisManager &CGAM =
     345         238 :         AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
     346             : 
     347             :     // Get the call graph for this module.
     348         238 :     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         476 :     SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
     353         476 :     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         476 :     SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
     358         476 :     SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
     359             : 
     360             :     SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
     361         476 :         InlinedInternalEdges;
     362             : 
     363         238 :     CGSCCUpdateResult UR = {RCWorklist,          CWorklist, InvalidRefSCCSet,
     364             :                             InvalidSCCSet,       nullptr,   nullptr,
     365             :                             InlinedInternalEdges};
     366             : 
     367             :     PreservedAnalyses PA = PreservedAnalyses::all();
     368         238 :     CG.buildRefSCCs();
     369         238 :     for (auto RCI = CG.postorder_ref_scc_begin(),
     370             :               RCE = CG.postorder_ref_scc_end();
     371        1025 :          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        1574 :       RCWorklist.insert(&*RCI++);
     386             : 
     387             :       do {
     388         810 :         LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
     389         810 :         if (InvalidRefSCCSet.count(RC)) {
     390             :           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             :         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 the
     401             :         // back and so see this in post-order.
     402        4900 :         for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
     403         838 :           CWorklist.insert(&C);
     404             : 
     405             :         do {
     406         876 :           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         876 :           if (InvalidSCCSet.count(C)) {
     412             :             DEBUG(dbgs() << "Skipping an invalid SCC...\n");
     413           5 :             continue;
     414             :           }
     415         871 :           if (&C->getOuterRefSCC() != RC) {
     416             :             DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
     417             :                             "RefSCC...\n");
     418          18 :             continue;
     419             :           }
     420             : 
     421         885 :           do {
     422             :             // Check that we didn't miss any update scenario.
     423             :             assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
     424             :             assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     425             :             assert(&C->getOuterRefSCC() == RC &&
     426             :                    "Processing an SCC in a different RefSCC!");
     427             : 
     428         885 :             UR.UpdatedRC = nullptr;
     429         885 :             UR.UpdatedC = nullptr;
     430        1770 :             PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
     431             : 
     432             :             // We handle invalidating the CGSCC analysis manager's information
     433             :             // for the (potentially updated) SCC here. Note that any other SCCs
     434             :             // whose structure has changed should have been invalidated by
     435             :             // whatever was updating the call graph. This SCC gets invalidated
     436             :             // late as it contains the nodes that were actively being
     437             :             // processed.
     438         885 :             CGAM.invalidate(*(UR.UpdatedC ? UR.UpdatedC : C), PassPA);
     439             : 
     440             :             // Then intersect the preserved set so that invalidation of module
     441             :             // analyses will eventually occur when the module pass completes.
     442         885 :             PA.intersect(std::move(PassPA));
     443             : 
     444             :             // The pass may have restructured the call graph and refined the
     445             :             // current SCC and/or RefSCC. We need to update our current SCC and
     446             :             // RefSCC pointers to follow these. Also, when the current SCC is
     447             :             // refined, re-run the SCC pass over the newly refined SCC in order
     448             :             // to observe the most precise SCC model available. This inherently
     449             :             // cannot cycle excessively as it only happens when we split SCCs
     450             :             // apart, at most converging on a DAG of single nodes.
     451             :             // FIXME: If we ever start having RefSCC passes, we'll want to
     452             :             // iterate there too.
     453         885 :             RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
     454         885 :             C = UR.UpdatedC ? UR.UpdatedC : C;
     455             :             if (UR.UpdatedC)
     456             :               DEBUG(dbgs() << "Re-running SCC passes after a refinement of the "
     457             :                               "current SCC: "
     458             :                            << *UR.UpdatedC << "\n");
     459             : 
     460             :             // Note that both `C` and `RC` may at this point refer to deleted,
     461             :             // invalid SCC and RefSCCs respectively. But we will short circuit
     462             :             // the processing when we check them in the loop above.
     463         885 :           } while (UR.UpdatedC);
     464         876 :         } while (!CWorklist.empty());
     465             : 
     466             :         // We only need to keep internal inlined edge information within
     467             :         // a RefSCC, clear it to save on space and let the next time we visit
     468             :         // any of these functions have a fresh start.
     469             :         InlinedInternalEdges.clear();
     470         810 :       } while (!RCWorklist.empty());
     471             :     }
     472             : 
     473             :     // By definition we preserve the call garph, all SCC analyses, and the
     474             :     // analysis proxies by handling them above and in any nested pass managers.
     475         238 :     PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
     476         238 :     PA.preserve<LazyCallGraphAnalysis>();
     477         238 :     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
     478         238 :     PA.preserve<FunctionAnalysisManagerModuleProxy>();
     479         238 :     return PA;
     480             :   }
     481             : 
     482             : private:
     483             :   CGSCCPassT Pass;
     484             : };
     485             : 
     486             : /// \brief A function to deduce a function pass type and wrap it in the
     487             : /// templated adaptor.
     488             : template <typename CGSCCPassT>
     489             : ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
     490         216 : createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
     491         922 :   return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass));
     492             : }
     493             : 
     494             : /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
     495             : ///
     496             : /// When a module pass runs and triggers invalidation, both the CGSCC and
     497             : /// Function analysis manager proxies on the module get an invalidation event.
     498             : /// We don't want to fully duplicate responsibility for most of the
     499             : /// invalidation logic. Instead, this layer is only responsible for SCC-local
     500             : /// invalidation events. We work with the module's FunctionAnalysisManager to
     501             : /// invalidate function analyses.
     502             : class FunctionAnalysisManagerCGSCCProxy
     503             :     : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> {
     504             : public:
     505             :   class Result {
     506             :   public:
     507             :     explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
     508             : 
     509             :     /// \brief Accessor for the analysis manager.
     510        1193 :     FunctionAnalysisManager &getManager() { return *FAM; }
     511             : 
     512             :     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
     513             :                     CGSCCAnalysisManager::Invalidator &Inv);
     514             : 
     515             :   private:
     516             :     FunctionAnalysisManager *FAM;
     517             :   };
     518             : 
     519             :   /// Computes the \c FunctionAnalysisManager and stores it in the result proxy.
     520             :   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &);
     521             : 
     522             : private:
     523             :   friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>;
     524             : 
     525             :   static AnalysisKey Key;
     526             : };
     527             : 
     528             : extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
     529             : 
     530             : /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
     531             : using CGSCCAnalysisManagerFunctionProxy =
     532             :     OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
     533             : 
     534             : /// Helper to update the call graph after running a function pass.
     535             : ///
     536             : /// Function passes can only mutate the call graph in specific ways. This
     537             : /// routine provides a helper that updates the call graph in those ways
     538             : /// including returning whether any changes were made and populating a CG
     539             : /// update result struct for the overall CGSCC walk.
     540             : LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
     541             :     LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
     542             :     CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
     543             : 
     544             : /// \brief Adaptor that maps from a SCC to its functions.
     545             : ///
     546             : /// Designed to allow composition of a FunctionPass(Manager) and
     547             : /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
     548             : /// to a \c CGSCCAnalysisManager it will run the
     549             : /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
     550             : /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
     551             : /// within this run safely.
     552             : template <typename FunctionPassT>
     553         546 : class CGSCCToFunctionPassAdaptor
     554             :     : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
     555             : public:
     556           8 :   explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
     557         190 :       : Pass(std::move(Pass)) {}
     558             : 
     559             :   // We have to explicitly define all the special member functions because MSVC
     560             :   // refuses to generate them.
     561             :   CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
     562             :       : Pass(Arg.Pass) {}
     563             : 
     564         190 :   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
     565         380 :       : Pass(std::move(Arg.Pass)) {}
     566             : 
     567             :   friend void swap(CGSCCToFunctionPassAdaptor &LHS,
     568             :                    CGSCCToFunctionPassAdaptor &RHS) {
     569             :     std::swap(LHS.Pass, RHS.Pass);
     570             :   }
     571             : 
     572             :   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
     573             :     swap(*this, RHS);
     574             :     return *this;
     575             :   }
     576             : 
     577             :   /// \brief Runs the function pass across every function in the module.
     578         356 :   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
     579             :                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     580             :     // Setup the function analysis manager from its proxy.
     581         356 :     FunctionAnalysisManager &FAM =
     582         356 :         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
     583             : 
     584         712 :     SmallVector<LazyCallGraph::Node *, 4> Nodes;
     585        2354 :     for (LazyCallGraph::Node &N : C)
     586         465 :       Nodes.push_back(&N);
     587             : 
     588             :     // The SCC may get split while we are optimizing functions due to deleting
     589             :     // edges. If this happens, the current SCC can shift, so keep track of
     590             :     // a pointer we can overwrite.
     591         356 :     LazyCallGraph::SCC *CurrentC = &C;
     592             : 
     593             :     DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n");
     594             : 
     595             :     PreservedAnalyses PA = PreservedAnalyses::all();
     596        1533 :     for (LazyCallGraph::Node *N : Nodes) {
     597             :       // Skip nodes from other SCCs. These may have been split out during
     598             :       // processing. We'll eventually visit those SCCs and pick up the nodes
     599             :       // there.
     600         465 :       if (CG.lookupSCC(*N) != CurrentC)
     601          40 :         continue;
     602             : 
     603         850 :       PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
     604             : 
     605             :       // We know that the function pass couldn't have invalidated any other
     606             :       // function's analyses (that's the contract of a function pass), so
     607             :       // directly handle the function analysis manager's invalidation here.
     608         425 :       FAM.invalidate(N->getFunction(), PassPA);
     609             : 
     610             :       // Then intersect the preserved set so that invalidation of module
     611             :       // analyses will eventually occur when the module pass completes.
     612         425 :       PA.intersect(std::move(PassPA));
     613             : 
     614             :       // If the call graph hasn't been preserved, update it based on this
     615             :       // function pass. This may also update the current SCC to point to
     616             :       // a smaller, more refined SCC.
     617         425 :       auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
     618         425 :       if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
     619         139 :         CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
     620             :                                                               AM, UR);
     621             :         assert(
     622             :             CG.lookupSCC(*N) == CurrentC &&
     623             :             "Current SCC not updated to the SCC containing the current node!");
     624             :       }
     625             :     }
     626             : 
     627             :     // By definition we preserve the proxy. And we preserve all analyses on
     628             :     // Functions. This precludes *any* invalidation of function analyses by the
     629             :     // proxy, but that's OK because we've taken care to invalidate analyses in
     630             :     // the function analysis manager incrementally above.
     631         356 :     PA.preserveSet<AllAnalysesOn<Function>>();
     632         356 :     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
     633             : 
     634             :     // We've also ensured that we updated the call graph along the way.
     635         356 :     PA.preserve<LazyCallGraphAnalysis>();
     636             : 
     637         356 :     return PA;
     638             :   }
     639             : 
     640             : private:
     641             :   FunctionPassT Pass;
     642             : };
     643             : 
     644             : /// \brief A function to deduce a function pass type and wrap it in the
     645             : /// templated adaptor.
     646             : template <typename FunctionPassT>
     647             : CGSCCToFunctionPassAdaptor<FunctionPassT>
     648          91 : createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
     649         380 :   return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
     650             : }
     651             : 
     652             : /// A helper that repeats an SCC pass each time an indirect call is refined to
     653             : /// a direct call by that pass.
     654             : ///
     655             : /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
     656             : /// change shape, we may also want to repeat an SCC pass if it simply refines
     657             : /// an indirect call to a direct call, even if doing so does not alter the
     658             : /// shape of the graph. Note that this only pertains to direct calls to
     659             : /// functions where IPO across the SCC may be able to compute more precise
     660             : /// results. For intrinsics, we assume scalar optimizations already can fully
     661             : /// reason about them.
     662             : ///
     663             : /// This repetition has the potential to be very large however, as each one
     664             : /// might refine a single call site. As a consequence, in practice we use an
     665             : /// upper bound on the number of repetitions to limit things.
     666             : template <typename PassT>
     667         984 : class DevirtSCCRepeatedPass
     668             :     : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
     669             : public:
     670             :   explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations)
     671         112 :       : Pass(std::move(Pass)), MaxIterations(MaxIterations) {}
     672             : 
     673             :   /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
     674             :   /// whenever an indirect call is refined.
     675         122 :   PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
     676             :                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     677             :     PreservedAnalyses PA = PreservedAnalyses::all();
     678             : 
     679             :     // The SCC may be refined while we are running passes over it, so set up
     680             :     // a pointer that we can update.
     681         122 :     LazyCallGraph::SCC *C = &InitialC;
     682             : 
     683             :     // Collect value handles for all of the indirect call sites.
     684         244 :     SmallVector<WeakTrackingVH, 8> CallHandles;
     685             : 
     686             :     // Struct to track the counts of direct and indirect calls in each function
     687             :     // of the SCC.
     688             :     struct CallCount {
     689             :       int Direct;
     690             :       int Indirect;
     691             :     };
     692             : 
     693             :     // Put value handles on all of the indirect calls and return the number of
     694             :     // direct calls for each function in the SCC.
     695           0 :     auto ScanSCC = [](LazyCallGraph::SCC &C,
     696         251 :                       SmallVectorImpl<WeakTrackingVH> &CallHandles) {
     697             :       assert(CallHandles.empty() && "Must start with a clear set of handles.");
     698             : 
     699         251 :       SmallVector<CallCount, 4> CallCounts;
     700        1522 :       for (LazyCallGraph::Node &N : C) {
     701         259 :         CallCounts.push_back({0, 0});
     702         518 :         CallCount &Count = CallCounts.back();
     703        3003 :         for (Instruction &I : instructions(N.getFunction()))
     704        2226 :           if (auto CS = CallSite(&I)) {
     705         217 :             if (CS.getCalledFunction()) {
     706         217 :               ++Count.Direct;
     707             :             } else {
     708          20 :               ++Count.Indirect;
     709          60 :               CallHandles.push_back(WeakTrackingVH(&I));
     710             :             }
     711             :           }
     712             :       }
     713             : 
     714         251 :       return CallCounts;
     715             :     };
     716             : 
     717             :     // Populate the initial call handles and get the initial call counts.
     718         244 :     auto CallCounts = ScanSCC(*C, CallHandles);
     719             : 
     720         130 :     for (int Iteration = 0;; ++Iteration) {
     721         138 :       PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
     722             : 
     723             :       // If the SCC structure has changed, bail immediately and let the outer
     724             :       // CGSCC layer handle any iteration to reflect the refined structure.
     725         130 :       if (UR.UpdatedC && UR.UpdatedC != C) {
     726           1 :         PA.intersect(std::move(PassPA));
     727         123 :         break;
     728             :       }
     729             : 
     730             :       // Check that we didn't miss any update scenario.
     731             :       assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
     732             :       assert(C->begin() != C->end() && "Cannot have an empty SCC!");
     733             :       assert((int)CallCounts.size() == C->size() &&
     734             :              "Cannot have changed the size of the SCC!");
     735             : 
     736             :       // Check whether any of the handles were devirtualized.
     737          15 :       auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
     738          15 :         if (!CallH)
     739             :           return false;
     740          26 :         auto CS = CallSite(CallH);
     741          13 :         if (!CS)
     742             :           return false;
     743             : 
     744             :         // If the call is still indirect, leave it alone.
     745           7 :         Function *F = CS.getCalledFunction();
     746             :         if (!F)
     747             :           return false;
     748             : 
     749             :         DEBUG(dbgs() << "Found devirutalized call from "
     750             :                      << CS.getParent()->getParent()->getName() << " to "
     751             :                      << F->getName() << "\n");
     752             : 
     753             :         // We now have a direct call where previously we had an indirect call,
     754             :         // so iterate to process this devirtualization site.
     755             :         return true;
     756             :       };
     757         258 :       bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
     758             : 
     759             :       // Rescan to build up a new set of handles and count how many direct
     760             :       // calls remain. If we decide to iterate, this also sets up the input to
     761             :       // the next iteration.
     762         129 :       CallHandles.clear();
     763         137 :       auto NewCallCounts = ScanSCC(*C, CallHandles);
     764             : 
     765             :       // If we haven't found an explicit devirtualization already see if we
     766             :       // have decreased the number of indirect calls and increased the number
     767             :       // of direct calls for any function in the SCC. This can be fooled by all
     768             :       // manner of transformations such as DCE and other things, but seems to
     769             :       // work well in practice.
     770         129 :       if (!Devirt)
     771         365 :         for (int i = 0, Size = C->size(); i < Size; ++i)
     772         371 :           if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
     773           6 :               CallCounts[i].Direct < NewCallCounts[i].Direct) {
     774             :             Devirt = true;
     775             :             break;
     776             :           }
     777             : 
     778         129 :       if (!Devirt) {
     779         120 :         PA.intersect(std::move(PassPA));
     780         120 :         break;
     781             :       }
     782             : 
     783             :       // Otherwise, if we've already hit our max, we're done.
     784           9 :       if (Iteration >= MaxIterations) {
     785             :         DEBUG(dbgs() << "Found another devirtualization after hitting the max "
     786             :                         "number of repetitions ("
     787             :                      << MaxIterations << ") on SCC: " << *C << "\n");
     788           1 :         PA.intersect(std::move(PassPA));
     789           1 :         break;
     790             :       }
     791             : 
     792             :       DEBUG(dbgs()
     793             :             << "Repeating an SCC pass after finding a devirtualization in: "
     794             :             << *C << "\n");
     795             : 
     796             :       // Move over the new call counts in preparation for iterating.
     797          16 :       CallCounts = std::move(NewCallCounts);
     798             : 
     799             :       // Update the analysis manager with each run and intersect the total set
     800             :       // of preserved analyses so we're ready to iterate.
     801           8 :       AM.invalidate(*C, PassPA);
     802           8 :       PA.intersect(std::move(PassPA));
     803             :     }
     804             : 
     805             :     // Note that we don't add any preserved entries here unlike a more normal
     806             :     // "pass manager" because we only handle invalidation *between* iterations,
     807             :     // not after the last iteration.
     808         122 :     return PA;
     809             :   }
     810             : 
     811             : private:
     812             :   PassT Pass;
     813             :   int MaxIterations;
     814             : };
     815             : 
     816             : /// \brief A function to deduce a function pass type and wrap it in the
     817             : /// templated adaptor.
     818             : template <typename PassT>
     819             : DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
     820             :                                                          int MaxIterations) {
     821         224 :   return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
     822             : }
     823             : 
     824             : // Clear out the debug logging macro.
     825             : #undef DEBUG_TYPE
     826             : 
     827             : } // end namespace llvm
     828             : 
     829             : #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H

Generated by: LCOV version 1.13