Index: include/llvm/Analysis/CGSCCPassManager.h =================================================================== --- include/llvm/Analysis/CGSCCPassManager.h +++ include/llvm/Analysis/CGSCCPassManager.h @@ -26,53 +26,76 @@ namespace llvm { -extern template class PassManager<LazyCallGraph::SCC>; -/// \brief The CGSCC pass manager. -/// -/// See the documentation for the PassManager template for details. It runs -/// a sequency of SCC passes over each SCC that the manager is run over. This -/// typedef serves as a convenient way to refer to this construct. -typedef PassManager<LazyCallGraph::SCC> CGSCCPassManager; +struct CGSCCUpdateResult; -extern template class AnalysisManager<LazyCallGraph::SCC>; +extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>; /// \brief The CGSCC analysis manager. /// /// See the documentation for the AnalysisManager template for detail /// documentation. This typedef serves as a convenient way to refer to this /// construct in the adaptors and proxies used to integrate this into the larger /// pass manager infrastructure. -typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager; +typedef AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &> CGSCCAnalysisManager; + +extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, + LazyCallGraph &, CGSCCUpdateResult &>; +/// \brief The CGSCC pass manager. +/// +/// See the documentation for the PassManager template for details. It runs +/// a sequency of SCC passes over each SCC that the manager is run over. This +/// typedef serves as a convenient way to refer to this construct. +typedef PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, + CGSCCUpdateResult &> + CGSCCPassManager; + +/// An explicit specialization of the require analysis template pass. +template <typename AnalysisT> +struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager, + LazyCallGraph &, CGSCCUpdateResult &> + : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, + CGSCCAnalysisManager, LazyCallGraph &, + CGSCCUpdateResult &>> { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &) { + (void)AM.template getResult<AnalysisT>(C, CG); + return PreservedAnalyses::all(); + } +}; extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>; /// A proxy from a \c CGSCCAnalysisManager to a \c Module. typedef InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module> CGSCCAnalysisManagerModuleProxy; -extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager, - LazyCallGraph::SCC>; +extern template class OuterAnalysisManagerProxy< + ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>; /// A proxy from a \c ModuleAnalysisManager to an \c SCC. -typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC> +typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC, + LazyCallGraph &> ModuleAnalysisManagerCGSCCProxy; -class CGInvalidationProxyAnalysis : public AnalysisInfoMixin<CGInvalidationProxyAnalysis> { -public: - struct Result { - LazyCallGraph::UpdateResult UR; - - bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA) { - // This isn't a traditional analysis pass, it is just a cache of - // information to convey between SCC passes and the adaptor walking SCCs. - return false; - } - }; - - Result run(LazyCallGraph::SCC &C, AnalysisManager<LazyCallGraph::SCC> &AM) { - return Result(); - } - -private: - friend AnalysisInfoMixin<CGInvalidationProxyAnalysis>; - static char PassID; +/// Support structure for SCC passes to communicate updates the call graph back +/// to the CGSCC pass manager infrsatructure. +/// +/// The CGSCC pass manager runs SCC passes which are allowed to update the call +/// graph and SCC structures. This means the structure the pass manager works +/// on is mutating underneath it. In order to support that, there needs to be +/// careful communication about the precise nature and rammifications of these +/// updates to the pass management infrastructure. +/// +/// All SCC passes will have to accept a reference to the management layer's +/// update result struct and use it to reflect the results of any CG updates +/// performed. +/// +/// Passes which do not change the call graph structure in any way can just +/// ignore this argument to their run method. +struct CGSCCUpdateResult { + SmallSetVector<LazyCallGraph::RefSCC *, 1> &RCWorklist; + SmallSetVector<LazyCallGraph::SCC *, 1> &CWorklist; + SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs; + SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs; + + LazyCallGraph::SCC *UpdatedC; }; /// \brief The core module pass which does a post-order walk of the SCCs and @@ -119,18 +142,20 @@ // We keep worklists to allow us to push more work onto the pass manager as // the passes are run. - SmallVector<LazyCallGraph::RefSCC *, 1> RCWorklist; - SmallVector<LazyCallGraph::SCC *, 1> CWorklist; + SmallSetVector<LazyCallGraph::RefSCC *, 1> RCWorklist; + SmallSetVector<LazyCallGraph::SCC *, 1> CWorklist; // Keep sets for invalidated SCCs and RefSCCs that should be skipped when // iterating off the worklists. SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet; SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet; + CGSCCUpdateResult UR = {RCWorklist, CWorklist, InvalidRefSCCSet, InvalidSCCSet, nullptr}; + PreservedAnalyses PA = PreservedAnalyses::all(); for (LazyCallGraph::RefSCC &InitialRC : CG.postorder_ref_sccs()) { assert(RCWorklist.empty() && "Should always start with an empty RefSCC worklist"); - RCWorklist.push_back(&InitialRC); + RCWorklist.insert(&InitialRC); do { LazyCallGraph::RefSCC &RC = *RCWorklist.pop_back_val(); @@ -143,49 +168,31 @@ // Push the initial SCCs in reverse post-order as we'll pop off the the // back and so see this in post-order. for (LazyCallGraph::SCC &C : reverse(RC)) - CWorklist.push_back(&C); + CWorklist.insert(&C); do { LazyCallGraph::SCC &C = *CWorklist.pop_back_val(); if (InvalidSCCSet.count(&C)) continue; - // Before we run the pass over this SCC, clear the invalidation - // proxy so that we can collect any call graph invalidation - // information provided by the pass. - LazyCallGraph::UpdateResult &UR = - CGAM.getResult<CGInvalidationProxyAnalysis>(C).UR; - assert(UR.empty() && - "Didn't start with a clean invalidation result!"); + PreservedAnalyses PassPA = Pass.run(C, CGAM, CG, UR); - PreservedAnalyses PassPA = Pass.run(C, CGAM); + // The pass may have mutated the call graph and so we need reference + // a potentially newly updated SCC. + LazyCallGraph::SCC &UpdatedC = *(UR.UpdatedC ? UR.UpdatedC : &C); - // We know that the CGSCC pass couldn't have invalidated any other - // SCC's analyses (that's the contract of a CGSCC pass), so - // directly handle the CGSCC analysis manager's invalidation here. - // We also update the preserved set of analyses to reflect that - // invalidated analyses are now safe to preserve. - PassPA = CGAM.invalidate(C, std::move(PassPA)); + // We handle invalidating the CGSCC analysis manager's information + // for the (potentially updated) SCC here. Note that any other SCCs + // whose structure has changed should have been invalidated by + // whatever was updating the call graph. This SCC gets invalidated + // late as it contains the nodes that were actively being processed. + PassPA = CGAM.invalidate(UpdatedC, std::move(PassPA)); // Then intersect the preserved set so that invalidation of module // analyses will eventually occur when the module pass completes. PA.intersect(std::move(PassPA)); - // We also need to handle invalidated and newly added SCCs and - // RefSCCs. - for (auto *InvalidRC : UR.InvalidatedRefSCCs) - InvalidRefSCCSet.insert(InvalidRC); - for (auto *InvalidC : UR.InvalidatedSCCs) { - InvalidSCCSet.insert(InvalidC); - // FIXME: need to clear this SCC from the analysis manager. - } - // Note that we append in reverse order as the worklist is consumed - // from the end. - RCWorklist.append(UR.NewRefSCCs.rbegin(), UR.NewRefSCCs.rend()); - CWorklist.append(UR.NewSCCs.rbegin(), UR.NewSCCs.rend()); - UR.clear(); } while (!CWorklist.empty()); - } while (!RCWorklist.empty()); } @@ -210,9 +217,9 @@ } extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager, - LazyCallGraph::SCC>; + LazyCallGraph::SCC, LazyCallGraph &>; /// A proxy from a \c FunctionAnalysisManager to an \c SCC. -typedef InnerAnalysisManagerProxy<FunctionAnalysisManager, LazyCallGraph::SCC> +typedef InnerAnalysisManagerProxy<FunctionAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &> FunctionAnalysisManagerCGSCCProxy; extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>; @@ -220,6 +227,16 @@ typedef OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function> CGSCCAnalysisManagerFunctionProxy; +/// Helper to update the call graph after running a function pass. +/// +/// Function passes can only mutate the call graph in specific ways. This +/// routine provides a helper that updates the call graph in those ways +/// including returning whether any changes were made and populating a CG +/// update result struct for the overall CGSCC walk. +LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass( + LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, + CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR); + /// \brief Adaptor that maps from a SCC to its functions. /// /// Designed to allow composition of a FunctionPass(Manager) and @@ -251,25 +268,48 @@ } /// \brief Runs the function pass across every function in the module. - PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR) { // Setup the function analysis manager from its proxy. FunctionAnalysisManager &FAM = - AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager(); + AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager(); + + SmallVector<LazyCallGraph::Node *, 4> Nodes; + for (LazyCallGraph::Node &N : C) + Nodes.push_back(&N); + + // The SCC may get split while we are optimizing functions due to deleting + // edges. If this happens, the current SCC can shift, so keep track of + // a pointer we can overwrite. + LazyCallGraph::SCC *CurrentC = &C; PreservedAnalyses PA = PreservedAnalyses::all(); - for (LazyCallGraph::Node &N : C) { - PreservedAnalyses PassPA = Pass.run(N.getFunction(), FAM); + for (LazyCallGraph::Node *N : Nodes) { + // Skip nodes from other SCCs. These may have been split out during + // processing. We'll eventually visit those SCCs and pick up the nodes + // there. + if (CG.lookupSCC(*N) != CurrentC) + continue; + + PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM); // We know that the function pass couldn't have invalidated any other // function's analyses (that's the contract of a function pass), so // directly handle the function analysis manager's invalidation here. // Also, update the preserved analyses to reflect that once invalidated // these can again be preserved. - PassPA = FAM.invalidate(N.getFunction(), std::move(PassPA)); + PassPA = FAM.invalidate(N->getFunction(), std::move(PassPA)); // Then intersect the preserved set so that invalidation of module // analyses will eventually occur when the module pass completes. PA.intersect(std::move(PassPA)); + + // Update the call graph based on this function pass. This may also + // update the current SCC to point to a smaller, more refined SCC. + CurrentC = + &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N, AM, UR); + assert(CG.lookupSCC(*N) == CurrentC && + "Current SCC not updated to the SCC containing the current node!"); } // By definition we preserve the proxy. This precludes *any* invalidation @@ -278,12 +318,8 @@ // incrementally above. PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); - // Do a full re-scan of the functions in this SCC in order to update the - // call graph based on any function-local changes made. - auto &CG = *AM.getCachedResult<LazyCallGraphAnalysis>(C); - LazyCallGraph::UpdateResult &UR = - AM.getCachedResult<CGInvalidationProxyAnalysis>(C)->UR; - CG.updateSCC(C, UR); + // We've also ensured that we updated the call graph along the way. + PA.preserve<LazyCallGraphAnalysis>(); return PA; } Index: include/llvm/Analysis/LazyCallGraph.h =================================================================== --- include/llvm/Analysis/LazyCallGraph.h +++ include/llvm/Analysis/LazyCallGraph.h @@ -509,7 +509,8 @@ /// TargetN. The newly added nodes are added *immediately* and contiguously /// prior to the TargetN SCC and so they may be iterated starting from /// there. - void switchInternalEdgeToRef(Node &SourceN, Node &TargetN); + iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN, + Node &TargetN); /// Make an existing outgoing ref edge into a call edge. /// @@ -761,37 +762,31 @@ ///@} ///@{ - /// \name Generic SCC Update API + /// \name Static helpers for code doing updates to the call graph. /// - /// This provides generic top-level update APIs that operate after the RefSCC - /// traversal has started. - - struct UpdateResult { - SmallVector<RefSCC *, 4> InvalidatedRefSCCs; - SmallVector<SCC *, 4> InvalidatedSCCs; - SmallVector<RefSCC *, 4> NewRefSCCs; - SmallVector<SCC *, 4> NewSCCs; - - bool empty() const { - return InvalidatedRefSCCs.empty() && InvalidatedSCCs.empty() && - NewRefSCCs.empty() && NewSCCs.empty(); + /// These helpers are used to implement parts of the call graph but are also + /// useful to code doing updates or otherwise wanting to walk the IR in the + /// same patterns as when we build the call graph. + + template <typename CallbackT> + static void visitReferences(SmallVectorImpl<Constant *> &Worklist, + SmallPtrSetImpl<Constant *> &Visited, + CallbackT Callback) { + while (!Worklist.empty()) { + Constant *C = Worklist.pop_back_val(); + + if (Function *F = dyn_cast<Function>(C)) { + Callback(*F); + continue; + } + + for (Value *Op : C->operand_values()) + if (Visited.insert(cast<Constant>(Op)).second) + Worklist.push_back(cast<Constant>(Op)); } - void clear() { - InvalidatedRefSCCs.clear(); - InvalidatedSCCs.clear(); - NewRefSCCs.clear(); - NewSCCs.clear(); - } - }; - - /// Do a full re-scan of an SCC and update the call graph based upon any - /// function-local changes made to that SCC. - /// - /// FIXME: describe accurately the full constraints on this routine! - void updateSCC(SCC &C, UpdateResult &UR); - - ///@} + ///@} +} private: typedef SmallVectorImpl<Node *>::reverse_iterator node_stack_iterator; Index: include/llvm/IR/PassManager.h =================================================================== --- include/llvm/IR/PassManager.h +++ include/llvm/IR/PassManager.h @@ -519,12 +519,35 @@ return AnalysisResults.empty(); } + /// \brief Clear any results for a single unit of IR. + /// + /// This doesn't invalidate but directly clears the results. It is useful + /// when the IR is being removed and we want to clear out all the memory + /// pinned for it. + void clear(IRUnitT &IR) { + if (DebugLogging) + dbgs() << "Clearing all analysis results for: " << IR.getName() << "\n"; + + // Clear all the invalidated results associated specifically with this + // function. + SmallVector<void *, 8> InvalidatedPassIDs; + auto ResultsListI = AnalysisResultLists.find(&IR); + if (ResultsListI == AnalysisResultLists.end()) + return; + // Clear the map pointing into the results list. + for (auto &PassIDAndResult : ResultsListI->second) + AnalysisResults.erase(std::make_pair(PassIDAndResult.first, &IR)); + + // And actually destroy and erase the results associated with this IR. + AnalysisResultLists.erase(ResultsListI); + } + /// \brief Clear the analysis result cache. /// /// This routine allows cleaning up when the set of IR units itself has /// potentially changed, and thus we can't even look up a a result and - /// invalidate it directly. Notably, this does *not* call invalidate functions - /// as there is nothing to be done for them. + /// invalidate it directly. Notably, this does *not* call invalidate + /// functions as there is nothing to be done for them. void clear() { AnalysisResults.clear(); AnalysisResultLists.clear(); Index: include/llvm/Transforms/IPO/FunctionAttrs.h =================================================================== --- include/llvm/Transforms/IPO/FunctionAttrs.h +++ include/llvm/Transforms/IPO/FunctionAttrs.h @@ -30,7 +30,8 @@ /// attribute. It also discovers function arguments that are not captured by /// the function and marks them with the nocapture attribute. struct PostOrderFunctionAttrsPass : PassInfoMixin<PostOrderFunctionAttrsPass> { - PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM); + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR); }; /// Create a legacy pass manager instance of a pass to compute function attrs Index: lib/Analysis/CGSCCPassManager.cpp =================================================================== --- lib/Analysis/CGSCCPassManager.cpp +++ lib/Analysis/CGSCCPassManager.cpp @@ -8,17 +8,213 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/IR/CallSite.h" using namespace llvm; // Explicit instantiations for the core proxy templates. namespace llvm { -template class PassManager<LazyCallGraph::SCC>; -template class AnalysisManager<LazyCallGraph::SCC>; +template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>; +template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, + LazyCallGraph &, CGSCCUpdateResult &>; template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>; template class OuterAnalysisManagerProxy<ModuleAnalysisManager, - LazyCallGraph::SCC>; + LazyCallGraph::SCC, LazyCallGraph &>; template class InnerAnalysisManagerProxy<FunctionAnalysisManager, - LazyCallGraph::SCC>; + LazyCallGraph::SCC, LazyCallGraph &>; template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>; } + +namespace { +/// Helper function for \c updatecGAndAnalysisManagerForFunctionPass that can't +/// be a lambda because it would need to be a generic lambda. +template <typename SCCRangeT> +LazyCallGraph::SCC *processNewSCCRange(const SCCRangeT &NewSCCRange, + LazyCallGraph &G, LazyCallGraph::Node &N, + LazyCallGraph::SCC *C, + CGSCCAnalysisManager &AM, + CGSCCUpdateResult &UR) { + typedef LazyCallGraph::SCC SCC; + + if (NewSCCRange.begin() == NewSCCRange.end()) + return C; + + // Invalidate the analyses of the current SCC and add it to the worklist since + // it has changed its shape. + AM.invalidate(*C, PreservedAnalyses::none()); + UR.CWorklist.insert(C); + + SCC *OldC = C; + + // Update the current SCC. Note that if we have new SCCs, this must actually + // change the SCC. + assert(C != &*NewSCCRange.begin() && + "Cannot insert new SCCs without changing current SCC!"); + C = &*NewSCCRange.begin(); + assert(G.lookupSCC(N) == C && "Failed to update current SCC!"); + + for (SCC &NewC : + reverse(make_range(std::next(NewSCCRange.begin()), NewSCCRange.end()))) { + assert(C != &NewC && "No need to re-visit the current SCC!"); + assert(OldC != &NewC && "Already handled the original SCC!"); + UR.CWorklist.insert(&NewC); + } + return C; +} +} + +LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( + LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, + CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) { + typedef LazyCallGraph::Node Node; + typedef LazyCallGraph::Edge Edge; + typedef LazyCallGraph::SCC SCC; + typedef LazyCallGraph::RefSCC RefSCC; + + SCC *C = &InitialC; + RefSCC *RC = &C->getOuterRefSCC(); + Function &F = N.getFunction(); + + // Walk the function body and build up the set of retained, promoted, and + // demoted edges. + SmallVector<Constant *, 16> Worklist; + SmallPtrSet<Constant *, 16> Visited; + SmallPtrSet<Function *, 16> RetainedEdges; + SmallSetVector<Function *, 4> PromotedCallTargets; + SmallSetVector<Function *, 4> DemotedRefTargets; + for (BasicBlock &BB : F) + for (Instruction &I : BB) { + if (auto CS = CallSite(&I)) + if (Function *Callee = CS.getCalledFunction()) { + const Edge *E = N.lookup(*Callee); + // FIXME: We should really handle adding new calls. While it will + // make downstream usage more complex, there is no fundamental + // limitation and it will allow passes within the CGSCC to be a bit + // more flexible in what transforms they can do. Until then, we + // verify that new calls haven't been introduced. + assert(E && "No function transformations should introduce *new* " + "call edges! Any new calls should be modeled as " + "promoted existing ref edges!"); + RetainedEdges.insert(Callee); + if (!E->isCall()) + PromotedCallTargets.insert(Callee); + } + + for (Value *Op : I.operand_values()) + if (Constant *C = dyn_cast<Constant>(Op)) + if (Visited.insert(C).second) + Worklist.push_back(C); + + LazyCallGraph::visitReferences(Worklist, Visited, [&](Function &Referee) { + const Edge *E = N.lookup(Referee); + // FIXME: Similarly to new calls, we also currently preclude + // introducing new references. See above for details. + assert(E && "No function transformations should introduce *new* ref " + "edges! Any new ref edges would require IPO which " + "function passes aren't allowed to do!"); + RetainedEdges.insert(&Referee); + if (E->isCall()) + DemotedRefTargets.insert(&Referee); + }); + } + + // First remove all of the edges that are no longer present in this function. + // We have to build a list of dead targets first and then remove them as the + // data structures will all be invalidated by removing them. + SmallVector<PointerIntPair<Node *, 1, Edge::Kind>, 4> DeadTargets; + for (Edge &E : N) + if (!RetainedEdges.count(&E.getFunction())) + DeadTargets.push_back({E.getNode(), E.isCall() ? Edge::Call : Edge::Ref}); + for (auto DeadTarget : DeadTargets) { + Node &TargetN = *DeadTarget.getPointer(); + bool IsCall = DeadTarget.getInt() == Edge::Call; + SCC &TargetC = *G.lookupSCC(TargetN); + RefSCC &TargetRC = TargetC.getOuterRefSCC(); + + if (&TargetRC != RC) { + RC->removeOutgoingEdge(N, TargetN); + continue; + } + + if (IsCall) + C = processNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G, N, C, + AM, UR); + + auto NewRefSCCs = RC->removeInternalRefEdge(N, TargetN); + if (!NewRefSCCs.empty()) { + // Note that we don't bother to invalidate analyses as ref-edge + // connectivity is not really observable in any way and is intended + // exclusively to be used for ordering of transforms rather than for + // analysis conclusions. + UR.RCWorklist.insert(NewRefSCCs.rbegin(), NewRefSCCs.rend()); + RC = &C->getOuterRefSCC(); + assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!"); + } + } + + // Next demote all the call edges that are now ref edges. This helps make + // the SCCs small which should minimize the work below as we don't want to + // form cycles that this would break. + for (Function *RefTarget : DemotedRefTargets) { + Node &TargetN = *G.lookup(*RefTarget); + SCC &TargetC = *G.lookupSCC(TargetN); + RefSCC &TargetRC = TargetC.getOuterRefSCC(); + + // The easy case is when the target RefSCC is not this RefSCC. This is + // only supported when the target RefSCC is a child of this RefSCC. + if (&TargetRC != RC) { + assert(RC->isAncestorOf(TargetRC) && + "Cannot potentially form RefSCC cycles here!"); + RC->switchOutgoingEdgeToRef(N, TargetN); + continue; + } + + // Otherwise we are switching an internal call edge to a ref edge. This + // may split up some SCCs. + C = processNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G, N, C, AM, + UR); + } + + // Now promote ref edges into call edges. + for (Function *CallTarget : PromotedCallTargets) { + Node &TargetN = *G.lookup(*CallTarget); + SCC &TargetC = *G.lookupSCC(TargetN); + RefSCC &TargetRC = TargetC.getOuterRefSCC(); + + // The easy case is when the target RefSCC is not this RefSCC. This is + // only supported when the target RefSCC is a child of this RefSCC. + if (&TargetRC != RC) { + assert(RC->isAncestorOf(TargetRC) && + "Cannot potentially form RefSCC cycles here!"); + RC->switchOutgoingEdgeToCall(N, TargetN); + continue; + } + + // Otherwise we are switching an internal ref edge to a call edge. This + // may merge away some SCCs, and we add those to the UpdateResult. + auto InvalidatedSCCs = RC->switchInternalEdgeToCall(N, TargetN); + if (!InvalidatedSCCs.empty()) { + C = &TargetC; + assert(G.lookupSCC(N) == C && "Failed to update current SCC!"); + + // Any analyses cached for this SCC are no longer valid as the shape has + // changed by introducing this cycle. + AM.invalidate(*C, PreservedAnalyses::none()); + + for (SCC *InvalidatedC : InvalidatedSCCs) { + assert(InvalidatedC != C && "Cannot invalidate the current SCC!"); + UR.InvalidatedSCCs.insert(InvalidatedC); + + // Also clear any cached analyses for the SCCs that are dead. This + // isn't really necessary for correctness but can release memory. + AM.clear(*InvalidatedC); + } + } + } + + // Record the current SCC for higher layers of the CGSCC pass + // manager now that all the updates have been applied. + UR.UpdatedC = C; + + return *C; +} Index: lib/Analysis/LazyCallGraph.cpp =================================================================== --- lib/Analysis/LazyCallGraph.cpp +++ lib/Analysis/LazyCallGraph.cpp @@ -40,24 +40,6 @@ } } -template <typename CallbackT> -static void visitReferences(SmallVectorImpl<Constant *> &Worklist, - SmallPtrSetImpl<Constant *> &Visited, - CallbackT Callback) { - while (!Worklist.empty()) { - Constant *C = Worklist.pop_back_val(); - - if (Function *F = dyn_cast<Function>(C)) { - Callback(*F); - continue; - } - - for (Value *Op : C->operand_values()) - if (Visited.insert(cast<Constant>(Op)).second) - Worklist.push_back(cast<Constant>(Op)); - } -} - LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) : G(&G), F(F), DFSNumber(0), LowLink(0) { DEBUG(dbgs() << " Adding functions called by '" << F.getName() @@ -470,8 +452,8 @@ return DeletedSCCs; } -void LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, - Node &TargetN) { +iterator_range<LazyCallGraph::RefSCC::iterator> +LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) { assert(SourceN[TargetN].isCall() && "Must start with a call edge!"); SCC &SourceSCC = *G->lookupSCC(SourceN); @@ -492,7 +474,7 @@ // Check that the RefSCC is still valid. verify(); #endif - return; + return make_range(SCCs.end(), SCCs.end()); } // Otherwise we are removing a call edge from a single SCC. This may break @@ -659,6 +641,9 @@ // We're done. Check the validity on our way out. verify(); #endif + + return make_range(SCCs.begin() + OldIdx, + SCCs.begin() + OldIdx + NewSCCs.size()); } void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN, @@ -1232,88 +1217,6 @@ return SourceN.removeEdgeInternal(Target); } -void LazyCallGraph::updateSCC(SCC &C, UpdateResult &UR) { - RefSCC &RC = C.getOuterRefSCC(); - SmallVector<Constant *, 16> Worklist; - SmallSetVector<Function *, 4> NewCallTargets; - SmallSetVector<Function *, 4> PromotedCallTargets; - SmallSetVector<Function *, 4> NewRefTargets; - SmallSetVector<Function *, 4> DemotedRefTargets; - SmallPtrSet<Constant *, 16> Visited; - - for (Node &N : C) { - Function &F = N.getFunction(); - - for (BasicBlock &BB : F) - for (Instruction &I : BB) { - if (auto CS = CallSite(&I)) - if (Function *Callee = CS.getCalledFunction()) { - const Edge *E = N.lookup(*Callee); - if (!E) - NewCallTargets.insert(Callee); - else if (!E->isCall()) - PromotedCallTargets.insert(Callee); - } - - for (Value *Op : I.operand_values()) - if (Constant *C = dyn_cast<Constant>(Op)) - if (Visited.insert(C).second) - Worklist.push_back(C); - - visitReferences(Worklist, Visited, [&](Function &Referee) { - const Edge *E = N.lookup(Referee); - if (!E) - NewRefTargets.insert(&Referee); - else if (E->isCall()) - DemotedRefTargets.insert(&Referee); - }); - } - - for (Function *CallTarget : NewCallTargets) { - Node &TargetN = *lookup(*CallTarget); - SCC &TargetC = *lookupSCC(TargetN); - RefSCC &TargetRC = TargetC.getOuterRefSCC(); - - // The easy case is when the target RefSCC is not this RefSCC. This is - // only supported when the target RefSCC is a child of this RefSCC. - if (&TargetRC != &RC) { - assert(RC.isAncestorOf(TargetRC) && - "Cannot potentially form RefSCC cycles here!"); - RC.insertOutgoingEdge(N, TargetN, Edge::Call); - continue; - } - - // Otherwise we need to first insert a ref edge, and then convert it to - // a call edge. This may merge some SCCs, and we add those to the - // UpdateResult. - RC.insertInternalRefEdge(N, TargetN); - - auto InvalidatedSCCs = RC.switchInternalEdgeToCall(N, TargetN); - UR.InvalidatedSCCs.append(InvalidatedSCCs.begin(), InvalidatedSCCs.end()); - } - - for (Function *CallTarget : PromotedCallTargets) { - Node &TargetN = *lookup(*CallTarget); - SCC &TargetC = *lookupSCC(TargetN); - RefSCC &TargetRC = TargetC.getOuterRefSCC(); - - // The easy case is when the target RefSCC is not this RefSCC. This is - // only supported when the target RefSCC is a child of this RefSCC. - if (&TargetRC != &RC) { - assert(RC.isAncestorOf(TargetRC) && - "Cannot potentially form RefSCC cycles here!"); - RC.switchOutgoingEdgeToCall(N, TargetN); - continue; - } - - // Otherwise we are switching an internal ref edgo to a call edge. This - // may merge some SCCs, and we add those to the UpdateResult. - auto InvalidatedSCCs = RC.switchInternalEdgeToCall(N, TargetN); - UR.InvalidatedSCCs.append(InvalidatedSCCs.begin(), InvalidatedSCCs.end()); - } - } -} - LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) { return *new (MappedN = BPA.Allocate()) Node(*this, F); } Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -125,7 +125,8 @@ /// \brief No-op CGSCC pass which does nothing. struct NoOpCGSCCPass { PreservedAnalyses run(LazyCallGraph::SCC &C, - AnalysisManager<LazyCallGraph::SCC> &) { + CGSCCAnalysisManager &, LazyCallGraph &, + CGSCCUpdateResult &UR) { return PreservedAnalyses::all(); } static StringRef name() { return "NoOpCGSCCPass"; } @@ -138,7 +139,7 @@ public: struct Result {}; - Result run(LazyCallGraph::SCC &, AnalysisManager<LazyCallGraph::SCC> &) { + Result run(LazyCallGraph::SCC &, CGSCCAnalysisManager &, LazyCallGraph &G) { return Result(); } static StringRef name() { return "NoOpCGSCCAnalysis"; } @@ -358,7 +359,8 @@ if (Name == "require<" NAME ">") { \ CGPM.addPass(RequireAnalysisPass< \ std::remove_reference<decltype(CREATE_PASS)>::type, \ - LazyCallGraph::SCC>()); \ + LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, \ + CGSCCUpdateResult &>()); \ return true; \ } \ if (Name == "invalidate<" NAME ">") { \ Index: lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/FunctionAttrs.cpp +++ lib/Transforms/IPO/FunctionAttrs.cpp @@ -991,12 +991,14 @@ } PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C, - CGSCCAnalysisManager &AM) { + CGSCCAnalysisManager &AM, + LazyCallGraph &CG, + CGSCCUpdateResult &) { Module &M = *C.begin()->getFunction().getParent(); const ModuleAnalysisManager &MAM = - AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C).getManager(); + AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager(); FunctionAnalysisManager &FAM = - AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager(); + AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager(); // FIXME: Need some way to make it more reasonable to assume that this is // always cached. Index: unittests/Analysis/CGSCCPassManagerTest.cpp =================================================================== --- unittests/Analysis/CGSCCPassManagerTest.cpp +++ unittests/Analysis/CGSCCPassManagerTest.cpp @@ -59,7 +59,7 @@ TestSCCAnalysis(int &Runs) : Runs(Runs) {} - Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) { + Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &) { ++Runs; return Result(C.size()); } @@ -149,13 +149,14 @@ AnalyzedModuleFunctionCount(AnalyzedModuleFunctionCount), OnlyUseCachedResults(OnlyUseCachedResults) {} - PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR) { ++RunCount; const ModuleAnalysisManager &MAM = - AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C).getManager(); + AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager(); FunctionAnalysisManager &FAM = - AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager(); + AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager(); if (TestModuleAnalysis::Result *TMA = MAM.getCachedResult<TestModuleAnalysis>( *C.begin()->getFunction().getParent())) @@ -171,7 +172,7 @@ AnalyzedInstrCount += FAR->InstructionCount; } else { // Typical path just runs the analysis as needed. - TestSCCAnalysis::Result &AR = AM.getResult<TestSCCAnalysis>(C); + TestSCCAnalysis::Result &AR = AM.getResult<TestSCCAnalysis>(C, CG); AnalyzedSCCFunctionCount += AR.FunctionCount; for (LazyCallGraph::Node &N : C) { TestFunctionAnalysis::Result &FAR =