From c718b8e7c35d0677a68ecdfd8d575b58205a970f Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sat, 5 Aug 2017 05:47:37 +0000 Subject: [LCG] Add the concept of a "dead" node and use it to avoid a complex walk over the parent set. When removing a single function from the call graph, we previously would walk the entire RefSCC's parent set and then walk every outgoing edge just to find the ones to remove. In addition to this being quite high complexity in theory, it is also the last fundamental use of the parent sets. With this change, when we remove a function we transform the node containing it to be recognizably "dead" and then teach the edge iterators to recognize edges to such nodes and skip them the same way they skip null edges. We can't move fully to using "dead" nodes -- when disconnecting two live nodes we need to null out the edge. But the complexity this adds to the edge sequence isn't too bad and the simplification of lazily handling this seems like a significant win. llvm-svn: 310169 --- llvm/lib/Analysis/LazyCallGraph.cpp | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) (limited to 'llvm/lib/Analysis/LazyCallGraph.cpp') diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp index 46e29828990..6c55a3f0406 100644 --- a/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/llvm/lib/Analysis/LazyCallGraph.cpp @@ -1644,14 +1644,6 @@ void LazyCallGraph::removeDeadFunction(Function &F) { assert(C.size() == 1 && "Dead functions must be in a singular SCC"); assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC"); - // Clean up any remaining reference edges. Note that we walk an unordered set - // here but are just removing and so the order doesn't matter. - for (RefSCC &ParentRC : RC.parents()) - for (SCC &ParentC : ParentRC) - for (Node &ParentN : ParentC) - if (ParentN.isPopulated()) - ParentN->removeEdgeInternal(N); - // Now remove this RefSCC from any parents sets and the leaf list. for (Edge &E : *N) if (RefSCC *TargetRC = lookupRefSCC(E.getNode())) @@ -1673,6 +1665,7 @@ void LazyCallGraph::removeDeadFunction(Function &F) { // components. N.clear(); N.G = nullptr; + N.F = nullptr; C.clear(); RC.clear(); RC.G = nullptr; -- cgit v1.2.3