diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2024-07-27 23:34:35 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2024-10-23 18:26:01 +0000 |
commit | 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583 (patch) | |
tree | 6cf5ab1f05330c6773b1f3f64799d56a9c7a1faa /contrib/llvm-project/llvm/lib/Analysis/LazyCallGraph.cpp | |
parent | 6b9f7133aba44189d9625c352bc2c2a59baf18ef (diff) | |
parent | ac9a064cb179f3425b310fa2847f8764ac970a4d (diff) |
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Analysis/LazyCallGraph.cpp')
-rw-r--r-- | contrib/llvm-project/llvm/lib/Analysis/LazyCallGraph.cpp | 135 |
1 files changed, 73 insertions, 62 deletions
diff --git a/contrib/llvm-project/llvm/lib/Analysis/LazyCallGraph.cpp b/contrib/llvm-project/llvm/lib/Analysis/LazyCallGraph.cpp index 473ae75b5d25..e6bf8c9cbb28 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/LazyCallGraph.cpp @@ -211,6 +211,14 @@ LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) updateGraphPtrs(); } +#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS) +void LazyCallGraph::verify() { + for (RefSCC &RC : postorder_ref_sccs()) { + RC.verify(); + } +} +#endif + bool LazyCallGraph::invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &) { // Check whether the analysis, all analyses on functions, or the function's @@ -1152,8 +1160,8 @@ void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) { } SmallVector<LazyCallGraph::RefSCC *, 1> -LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, - ArrayRef<Node *> TargetNs) { +LazyCallGraph::RefSCC::removeInternalRefEdges( + ArrayRef<std::pair<Node *, Node *>> Edges) { // We return a list of the resulting *new* RefSCCs in post-order. SmallVector<RefSCC *, 1> Result; @@ -1171,25 +1179,21 @@ LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, #endif // First remove the actual edges. - for (Node *TargetN : TargetNs) { - assert(!(*SourceN)[*TargetN].isCall() && + for (auto [SourceN, TargetN] : Edges) { + assert(!(**SourceN)[*TargetN].isCall() && "Cannot remove a call edge, it must first be made a ref edge"); - bool Removed = SourceN->removeEdgeInternal(*TargetN); + bool Removed = (*SourceN)->removeEdgeInternal(*TargetN); (void)Removed; assert(Removed && "Target not in the edge set for this caller?"); } // Direct self references don't impact the ref graph at all. - if (llvm::all_of(TargetNs, - [&](Node *TargetN) { return &SourceN == TargetN; })) - return Result; - // If all targets are in the same SCC as the source, because no call edges // were removed there is no RefSCC structure change. - SCC &SourceC = *G->lookupSCC(SourceN); - if (llvm::all_of(TargetNs, [&](Node *TargetN) { - return G->lookupSCC(*TargetN) == &SourceC; + if (llvm::all_of(Edges, [&](std::pair<Node *, Node *> E) { + return E.first == E.second || + G->lookupSCC(*E.first) == G->lookupSCC(*E.second); })) return Result; @@ -1491,7 +1495,7 @@ void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) { assert(Removed && "Target not in the edge set for this caller?"); } -void LazyCallGraph::removeDeadFunction(Function &F) { +void LazyCallGraph::markDeadFunction(Function &F) { // FIXME: This is unnecessarily restrictive. We should be able to remove // functions which recursively call themselves. assert(F.hasZeroLiveUses() && @@ -1503,63 +1507,70 @@ void LazyCallGraph::removeDeadFunction(Function &F) { "Must not remove lib functions from the call graph!"); auto NI = NodeMap.find(&F); - if (NI == NodeMap.end()) - // Not in the graph at all! - return; + assert(NI != NodeMap.end() && "Removed function should be known!"); Node &N = *NI->second; - // Cannot remove a function which has yet to be visited in the DFS walk, so - // if we have a node at all then we must have an SCC and RefSCC. - auto CI = SCCMap.find(&N); - assert(CI != SCCMap.end() && - "Tried to remove a node without an SCC after DFS walk started!"); - SCC &C = *CI->second; - RefSCC *RC = &C.getOuterRefSCC(); - - // In extremely rare cases, we can delete a dead function which is still in a - // non-trivial RefSCC. This can happen due to spurious ref edges sticking - // around after an IR function reference is removed. - if (RC->size() != 1) { - SmallVector<Node *, 0> NodesInRC; - for (SCC &OtherC : *RC) { - for (Node &OtherN : OtherC) - NodesInRC.push_back(&OtherN); + // Remove all call edges out of dead function. + for (Edge E : *N) { + if (E.isCall()) + N->setEdgeKind(E.getNode(), Edge::Ref); + } +} + +void LazyCallGraph::removeDeadFunctions(ArrayRef<Function *> DeadFs) { + if (DeadFs.empty()) + return; + + // Group dead functions by the RefSCC they're in. + DenseMap<RefSCC *, SmallVector<Node *, 1>> RCs; + for (Function *DeadF : DeadFs) { + Node *N = lookup(*DeadF); +#ifndef NDEBUG + for (Edge &E : **N) { + assert(!E.isCall() && + "dead function shouldn't have any outgoing call edges"); } - for (Node *OtherN : NodesInRC) { - if ((*OtherN)->lookup(N)) { - auto NewRefSCCs = - RC->removeInternalRefEdge(*OtherN, ArrayRef<Node *>(&N)); - // If we've split into multiple RefSCCs, RC is now invalid and the - // RefSCC containing C will be different. - if (!NewRefSCCs.empty()) - RC = &C.getOuterRefSCC(); +#endif + RefSCC *RC = lookupRefSCC(*N); + RCs[RC].push_back(N); + } + // Remove outgoing edges from all dead functions. Dead functions should + // already have had their call edges removed in markDeadFunction(), so we only + // need to worry about spurious ref edges. + for (auto [RC, DeadNs] : RCs) { + SmallVector<std::pair<Node *, Node *>> InternalEdgesToRemove; + for (Node *DeadN : DeadNs) { + for (Edge &E : **DeadN) { + if (lookupRefSCC(E.getNode()) == RC) + InternalEdgesToRemove.push_back({DeadN, &E.getNode()}); + else + RC->removeOutgoingEdge(*DeadN, E.getNode()); } } + // We ignore the returned RefSCCs since at this point we're done with CGSCC + // iteration and don't need to add it to any worklists. + (void)RC->removeInternalRefEdges(InternalEdgesToRemove); + for (Node *DeadN : DeadNs) { + RefSCC *DeadRC = lookupRefSCC(*DeadN); + assert(DeadRC->size() == 1); + assert(DeadRC->begin()->size() == 1); + DeadRC->clear(); + DeadRC->G = nullptr; + } } + // Clean up data structures. + for (Function *DeadF : DeadFs) { + Node &N = *lookup(*DeadF); - NodeMap.erase(NI); - EntryEdges.removeEdgeInternal(N); - SCCMap.erase(CI); - - // This node must be the only member of its SCC as it has no callers, and - // that SCC must be the only member of a RefSCC as it has no references. - // Validate these properties first. - assert(C.size() == 1 && "Dead functions must be in a singular SCC"); - assert(RC->size() == 1 && "Dead functions must be in a singular RefSCC"); - - // Finally clear out all the data structures from the node down through the - // components. postorder_ref_scc_iterator will skip empty RefSCCs, so no need - // to adjust LazyCallGraph data structures. - N.clear(); - N.G = nullptr; - N.F = nullptr; - C.clear(); - RC->clear(); - RC->G = nullptr; - - // Nothing to delete as all the objects are allocated in stable bump pointer - // allocators. + EntryEdges.removeEdgeInternal(N); + SCCMap.erase(SCCMap.find(&N)); + NodeMap.erase(NodeMap.find(DeadF)); + + N.clear(); + N.G = nullptr; + N.F = nullptr; + } } // Gets the Edge::Kind from one function to another by looking at the function's |