From 95f263eb86dd50d6bbf0814f7d0fe99e246c4faf Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Sat, 5 Aug 2017 05:47:37 +0000
Subject: [PATCH] [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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@310169 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/LazyCallGraph.h | 24 +++++++++++++++++++++---
 lib/Analysis/LazyCallGraph.cpp        |  9 +--------
 2 files changed, 22 insertions(+), 11 deletions(-)

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index f2918cb595f..0cf0a6fdd1c 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -256,11 +256,16 @@ public:
     Edge &operator[](int i) { return Edges[i]; }
     Edge &operator[](Node &N) {
       assert(EdgeIndexMap.find(&N) != EdgeIndexMap.end() && "No such edge!");
-      return Edges[EdgeIndexMap.find(&N)->second];
+      auto &E = Edges[EdgeIndexMap.find(&N)->second];
+      assert(E && "Dead or null edge!");
+      return E;
     }
     Edge *lookup(Node &N) {
       auto EI = EdgeIndexMap.find(&N);
-      return EI != EdgeIndexMap.end() ? &Edges[EI->second] : nullptr;
+      if (EI == EdgeIndexMap.end())
+        return nullptr;
+      auto &E = Edges[EI->second];
+      return E ? &E : nullptr;
     }
 
     call_iterator call_begin() {
@@ -331,6 +336,17 @@ public:
     /// Tests whether the node has been populated with edges.
     bool isPopulated() const { return Edges.hasValue(); }
 
+    /// Tests whether this is actually a dead node and no longer valid.
+    ///
+    /// Users rarely interact with nodes in this state and other methods are
+    /// invalid. This is used to model a node in an edge list where the
+    /// function has been completely removed.
+    bool isDead() const {
+      assert(!G == !F &&
+             "Both graph and function pointers should be null or non-null.");
+      return !G;
+    }
+
     // We allow accessing the edges by dereferencing or using the arrow
     // operator, essentially wrapping the internal optional.
     EdgeSequence &operator*() const {
@@ -1185,7 +1201,9 @@ private:
 inline LazyCallGraph::Edge::Edge() : Value() {}
 inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {}
 
-inline LazyCallGraph::Edge::operator bool() const { return Value.getPointer(); }
+inline LazyCallGraph::Edge::operator bool() const {
+  return Value.getPointer() && !Value.getPointer()->isDead();
+}
 
 inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const {
   assert(*this && "Queried a null edge!");
diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 46e29828990..6c55a3f0406 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/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;
-- 
2.50.1