Index: include/llvm/Analysis/CGSCCPassManager.h =================================================================== --- include/llvm/Analysis/CGSCCPassManager.h +++ include/llvm/Analysis/CGSCCPassManager.h @@ -26,34 +26,78 @@ namespace llvm { -extern template class PassManager; -/// \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 CGSCCPassManager; +struct CGSCCUpdateResult; -extern template class AnalysisManager; +extern template class AnalysisManager; /// \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 CGSCCAnalysisManager; +typedef AnalysisManager CGSCCAnalysisManager; + +extern template class PassManager; +/// \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 + CGSCCPassManager; + +/// An explicit specialization of the require analysis template pass. +template +struct RequireAnalysisPass + : PassInfoMixin> { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &) { + (void)AM.template getResult(C, CG); + return PreservedAnalyses::all(); + } +}; extern template class InnerAnalysisManagerProxy; /// A proxy from a \c CGSCCAnalysisManager to a \c Module. typedef InnerAnalysisManagerProxy CGSCCAnalysisManagerModuleProxy; -extern template class OuterAnalysisManagerProxy; +extern template class OuterAnalysisManagerProxy< + ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>; /// A proxy from a \c ModuleAnalysisManager to an \c SCC. -typedef OuterAnalysisManagerProxy +typedef OuterAnalysisManagerProxy ModuleAnalysisManagerCGSCCProxy; +/// 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 &RCWorklist; + SmallSetVector &CWorklist; + SmallPtrSetImpl &InvalidatedRefSCCs; + SmallPtrSetImpl &InvalidatedSCCs; + + LazyCallGraph::SCC *UpdatedC; +}; + /// \brief The core module pass which does a post-order walk of the SCCs and /// runs a CGSCC pass over each one. /// @@ -96,25 +140,61 @@ // Get the call graph for this module. LazyCallGraph &CG = AM.getResult(M); + // We keep worklists to allow us to push more work onto the pass manager as + // the passes are run. + SmallSetVector RCWorklist; + SmallSetVector CWorklist; + + // Keep sets for invalidated SCCs and RefSCCs that should be skipped when + // iterating off the worklists. + SmallPtrSet InvalidRefSCCSet; + SmallPtrSet InvalidSCCSet; + + CGSCCUpdateResult UR = {RCWorklist, CWorklist, InvalidRefSCCSet, InvalidSCCSet, nullptr}; + PreservedAnalyses PA = PreservedAnalyses::all(); - for (LazyCallGraph::RefSCC &OuterC : CG.postorder_ref_sccs()) - for (LazyCallGraph::SCC &C : OuterC) { - PreservedAnalyses PassPA = Pass.run(C, CGAM); - - // 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. - // FIXME: This isn't quite correct. We need to handle the case where the - // pass updated the CG, particularly some child of the current SCC, and - // invalidate its analyses. - PassPA = CGAM.invalidate(C, 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)); - } + for (LazyCallGraph::RefSCC &InitialRC : CG.postorder_ref_sccs()) { + assert(RCWorklist.empty() && "Should always start with an empty RefSCC worklist"); + RCWorklist.insert(&InitialRC); + + do { + LazyCallGraph::RefSCC &RC = *RCWorklist.pop_back_val(); + if (InvalidRefSCCSet.count(&RC)) + continue; + + assert(CWorklist.empty() && + "Should always start with an empty SCC worklist"); + + // 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.insert(&C); + + do { + LazyCallGraph::SCC &C = *CWorklist.pop_back_val(); + if (InvalidSCCSet.count(&C)) + continue; + + PreservedAnalyses PassPA = Pass.run(C, CGAM, CG, UR); + + // 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 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)); + + } while (!CWorklist.empty()); + } while (!RCWorklist.empty()); + } // By definition we preserve the proxy. This precludes *any* invalidation // of CGSCC analyses by the proxy, but that's OK because we've taken @@ -137,9 +217,9 @@ } extern template class InnerAnalysisManagerProxy; + LazyCallGraph::SCC, LazyCallGraph &>; /// A proxy from a \c FunctionAnalysisManager to an \c SCC. -typedef InnerAnalysisManagerProxy +typedef InnerAnalysisManagerProxy FunctionAnalysisManagerCGSCCProxy; extern template class OuterAnalysisManagerProxy; @@ -147,6 +227,16 @@ typedef OuterAnalysisManagerProxy 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 @@ -178,34 +268,59 @@ } /// \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(C).getManager(); + AM.getResult(C, CG).getManager(); + + SmallVector 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 // of function analyses by the proxy, but that's OK because we've taken // care to invalidate analyses in the function analysis manager // incrementally above. - // FIXME: We need to update the call graph here to account for any deleted - // edges! PA.preserve(); + + // We've also ensured that we updated the call graph along the way. + PA.preserve(); + return PA; } Index: include/llvm/Analysis/LazyCallGraph.h =================================================================== --- include/llvm/Analysis/LazyCallGraph.h +++ include/llvm/Analysis/LazyCallGraph.h @@ -239,6 +239,11 @@ } const Edge &operator[](Node &N) const { return (*this)[N.getFunction()]; } + const Edge *lookup(Function &F) const { + auto EI = EdgeIndexMap.find(&F); + return EI != EdgeIndexMap.end() ? &Edges[EI->second] : nullptr; + } + call_edge_iterator call_begin() const { return call_edge_iterator(Edges.begin(), Edges.end()); } @@ -520,7 +525,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 switchInternalEdgeToRef(Node &SourceN, + Node &TargetN); /// Make an existing outgoing ref edge into a call edge. /// @@ -771,6 +777,33 @@ ///@} + ///@{ + /// \name Static helpers for code doing updates to the call graph. + /// + /// 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 + static void visitReferences(SmallVectorImpl &Worklist, + SmallPtrSetImpl &Visited, + CallbackT Callback) { + while (!Worklist.empty()) { + Constant *C = Worklist.pop_back_val(); + + if (Function *F = dyn_cast(C)) { + Callback(*F); + continue; + } + + for (Value *Op : C->operand_values()) + if (Visited.insert(cast(Op)).second) + Worklist.push_back(cast(Op)); + } + + ///@} +} + private: typedef SmallVectorImpl::reverse_iterator node_stack_iterator; typedef iterator_range node_stack_range; 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 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 { - 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,220 @@ //===----------------------------------------------------------------------===// #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; -template class AnalysisManager; +template class AnalysisManager; +template class PassManager; template class InnerAnalysisManagerProxy; template class OuterAnalysisManagerProxy; + LazyCallGraph::SCC, LazyCallGraph &>; template class InnerAnalysisManagerProxy; + LazyCallGraph::SCC, LazyCallGraph &>; template class OuterAnalysisManagerProxy; } + +namespace { +/// Helper function for \c updatecGAndAnalysisManagerForFunctionPass that can't +/// be a lambda because it would need to be a generic lambda. +template +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 Worklist; + SmallPtrSet Visited; + SmallPtrSet RetainedEdges; + SmallSetVector PromotedCallTargets; + SmallSetVector DemotedRefTargets; + // First walk the function and handle all called functions. We do this first + // because if there is a single call edge, whether there are ref edges is + // irrelevant. + for (BasicBlock &BB : F) + for (Instruction &I : BB) + if (auto CS = CallSite(&I)) + if (Function *Callee = CS.getCalledFunction()) + if (Visited.insert(Callee).second) { + 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); + } + + // Now walk all references. + for (BasicBlock &BB : F) + for (Instruction &I : BB) { + for (Value *Op : I.operand_values()) + if (Constant *C = dyn_cast(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, 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 @@ -41,24 +41,6 @@ } } -static void findReferences(SmallVectorImpl &Worklist, - SmallPtrSetImpl &Visited, - SmallVectorImpl &Edges, - DenseMap &EdgeIndexMap) { - while (!Worklist.empty()) { - Constant *C = Worklist.pop_back_val(); - - if (Function *F = dyn_cast(C)) { - addEdge(Edges, EdgeIndexMap, *F, LazyCallGraph::Edge::Ref); - continue; - } - - for (Value *Op : C->operand_values()) - if (Visited.insert(cast(Op)).second) - Worklist.push_back(cast(Op)); - } -} - LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) : G(&G), F(F), DFSNumber(0), LowLink(0) { DEBUG(dbgs() << " Adding functions called by '" << F.getName() @@ -91,7 +73,9 @@ // We've collected all the constant (and thus potentially function or // function containing) operands to all of the instructions in the function. // Process them (recursively) collecting every function found. - findReferences(Worklist, Visited, Edges, EdgeIndexMap); + visitReferences(Worklist, Visited, [&](Function &F) { + addEdge(Edges, EdgeIndexMap, F, LazyCallGraph::Edge::Ref); + }); } void LazyCallGraph::Node::insertEdgeInternal(Function &Target, Edge::Kind EK) { @@ -141,7 +125,9 @@ DEBUG(dbgs() << " Adding functions referenced by global initializers to the " "entry set.\n"); - findReferences(Worklist, Visited, EntryEdges, EntryIndexMap); + visitReferences(Worklist, Visited, [&](Function &F) { + addEdge(EntryEdges, EntryIndexMap, F, LazyCallGraph::Edge::Ref); + }); for (const Edge &E : EntryEdges) RefSCCEntryNodes.push_back(&E.getFunction()); @@ -467,8 +453,8 @@ return DeletedSCCs; } -void LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, - Node &TargetN) { +iterator_range +LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) { assert(SourceN[TargetN].isCall() && "Must start with a call edge!"); SCC &SourceSCC = *G->lookupSCC(SourceN); @@ -489,7 +475,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 @@ -656,6 +642,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, Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -126,7 +126,8 @@ /// \brief No-op CGSCC pass which does nothing. struct NoOpCGSCCPass { PreservedAnalyses run(LazyCallGraph::SCC &C, - AnalysisManager &) { + CGSCCAnalysisManager &, LazyCallGraph &, + CGSCCUpdateResult &UR) { return PreservedAnalyses::all(); } static StringRef name() { return "NoOpCGSCCPass"; } @@ -139,7 +140,7 @@ public: struct Result {}; - Result run(LazyCallGraph::SCC &, AnalysisManager &) { + Result run(LazyCallGraph::SCC &, CGSCCAnalysisManager &, LazyCallGraph &G) { return Result(); } static StringRef name() { return "NoOpCGSCCAnalysis"; } @@ -359,7 +360,8 @@ if (Name == "require<" NAME ">") { \ CGPM.addPass(RequireAnalysisPass< \ std::remove_reference::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(C).getManager(); + AM.getResult(C, CG).getManager(); FunctionAnalysisManager &FAM = - AM.getResult(C).getManager(); + AM.getResult(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(C).getManager(); + AM.getResult(C, CG).getManager(); FunctionAnalysisManager &FAM = - AM.getResult(C).getManager(); + AM.getResult(C, CG).getManager(); if (TestModuleAnalysis::Result *TMA = MAM.getCachedResult( *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(C); + TestSCCAnalysis::Result &AR = AM.getResult(C, CG); AnalyzedSCCFunctionCount += AR.FunctionCount; for (LazyCallGraph::Node &N : C) { TestFunctionAnalysis::Result &FAR =