[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

1 files changed, 1 insertions, 8 deletions

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;