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

Generated by: LCOV version 1.13