[LCG] Add the first round of mutation support to the lazy call graph.

This implements the core functionality necessary to remove an edge from
the call graph and correctly update both the basic graph and the SCC
structure. As part of that it has to run a tiny (in number of nodes)
Tarjan-style DFS walk of an SCC being mutated to compute newly formed
SCCs, etc.

This is *very rough* and a WIP. I have a bunch of FIXMEs for code
cleanup that will reduce the boilerplate in this change substantially.
I also have a bunch of simplifications to various parts of both
algorithms that I want to make, but first I'd like to have a more
holistic picture. Ideally, I'd also like more testing. I'll probably add
quite a few more unit tests as I go here to cover the various different
aspects and corner cases of removing edges from the graph.

Still, this is, so far, successfully updating the SCC graph in-place
without disrupting the identity established for the existing SCCs even
when we do challenging things like delete the critical edge that made an
SCC cycle at all and have to reform things as a tree of smaller SCCs.
Getting this to work is really critical for the new pass manager as it
is going to associate significant state with the SCC instance and needs
it to be stable. That is also the motivation behind the return of the
newly formed SCCs. Eventually, I'll wire this all the way up to the
public API so that the pass manager can use it to correctly re-enqueue
newly formed SCCs into a fresh postorder traversal.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206968 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 14 insertions, 0 deletions

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index aefad6f913..ada278b114 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -223,6 +223,12 @@ public:
 
     SCC() {}
 
+    void removeEdge(LazyCallGraph &G, Function &Caller, Function &Callee,
+                    SCC &CalleeC);
+
+    SmallVector<LazyCallGraph::SCC *, 1>
+    removeInternalEdge(LazyCallGraph &G, Node &Caller, Node &Callee);
+
   public:
     typedef SmallVectorImpl<Node *>::const_iterator iterator;
     typedef SmallSetVector<SCC *, 1>::const_iterator parent_iterator;
@@ -334,6 +340,14 @@ public:
     return insertInto(F, N);
   }
 
+  /// \brief Update the call graph after deleting an edge.
+  void removeEdge(Node &Caller, Function &Callee);
+
+  /// \brief Update the call graph after deleting an edge.
+  void removeEdge(Function &Caller, Function &Callee) {
+    return removeEdge(*get(Caller), Callee);
+  }
+
 private:
   /// \brief Allocator that holds all the call graph nodes.
   SpecificBumpPtrAllocator<Node> BPA;