[LCG] Add the necessary functionality to the LazyCallGraph to support inlining.

[chandlerc]

Summary

The basic inlining operation makes the following changes to the call graph:

1. Add edges that were previously transitive edges. This is always trivial and this patch gives the LCG helper methods to make this more convenient.
2. Remove the inlined edge. We had existing support for this, but it contained bugs that needed to be fixed. Testing in the same pattern as the inliner exposes these bugs very nicely.
3. Delete a function when it becomes dead because it is internal and all calls have been inlined. The LCG had no support at all for this operation, so this adds that support.

Two unittests have been added that exercise this specific mutation pattern to
the call graph. They were extremely effective in uncovering bugs. Sadly,
a large fraction of the code here is just to implement those unit tests, but
I think they're paying for themselves. =]

This was split out of a patch that actually uses the routines to implement
inlining in the new pass manager. I'll send it out next, I just wanted to
isolate (with unit tests) the logic that was entirely within the LCG.

Depends on D24219

[sanjoy]

Hi Chandler,

I've not yet had a chance to look at this in detail, so I only have some superficial comments inline. However, I don't (yet! :) ) believe you when you say that inlining only does the three trivial transforms you outlined above. Because InlineFunction does some basic simplification I think it can introduce new SCCs. For instance, if I run opt -always-inline (and nothing else) on

define void @f(void()* %p) alwaysinline {
  call void %p()
  ret void
}

define void @g() {
  call void @f(void()* @h)
  ret void
}

define void @h() {
  call void @g()
  ret void
}

I get

; ModuleID = 'inl.ll'
source_filename = "inl.ll"

; Function Attrs: alwaysinline
define void @f(void ()* %p) #0 {
  call void %p()
  ret void
}

define void @g() {
  call void @h()
  ret void
}

define void @h() {
  call void @g()
  ret void
}

attributes #0 = { alwaysinline }

That is, we form a new SCC containing @g and @h.

lib/Analysis/LazyCallGraph.cpp

1215 ↗

(On Diff #70306)

Nit: spelling of sequnece

1302 ↗

(On Diff #70306)

Can we put this logic inside connectRefSCC ?

1413 ↗

(On Diff #70306)

llvm::find?

1496 ↗

(On Diff #70306)

Nit: s/fine/find/

[sanjoy]

"Marking as read"

[chandlerc]

In D24225#536730, @sanjoy wrote:

Hi Chandler,

I've not yet had a chance to look at this in detail, so I only have some superficial comments inline. However, I don't (yet! :) ) believe you when you say that inlining only does the three trivial transforms you outlined above. Because InlineFunction does some basic simplification I think it can introduce new SCCs. For instance, if I run opt -always-inline (and nothing else) on

define void @f(void()* %p) alwaysinline {
  call void %p()
  ret void
}

define void @g() {
  call void @f(void()* @h)
  ret void
}

define void @h() {
  call void @g()
  ret void
}

I get

; ModuleID = 'inl.ll'
source_filename = "inl.ll"

; Function Attrs: alwaysinline
define void @f(void ()* %p) #0 {
  call void %p()
  ret void
}

define void @g() {
  call void @h()
  ret void
}

define void @h() {
  call void @g()
  ret void
}

attributes #0 = { alwaysinline }

That is, we form a new SCC containing @g and @h.

Thanks for the example! I hadn't really thought a lot about devirtualization happening during the simplification, but of course it can easily happen as you show here.

I stand by my claim that this patch tests the *basic* graph updates necessary for inlining. ;] This is a bit more than "just" inlining, not that our APIs make that visible to the caller in any useful way.

I'll add this as a high-level test case for the inliner port patch and update it to take this into account. That may in turn motivate more unittests of the core LCG functionality, but even if so I'd prefer to put those extra tests in a separate patch if that's OK?

[chandlerc]

Rebase and ping...

[chandlerc]

Update to address some specific comments I missed previously, sorry about that.
Nothing really substantive though. Mostly using llvm's "find" that accepts
a range.

[chandlerc]

Sorry I missed the inline comments at first, addressed all but one and responded to that one below.

lib/Analysis/LazyCallGraph.cpp

1302 ↗

(On Diff #70306)

We already do related things in connectRefSCC, but there are callers to that which don't need to do the re-analysis?

[sanjoy]

lgtm with some comments inline

Ignore the comment with . as the body -- for some reason phabricator refused to delete a stale comment.

include/llvm/Analysis/LazyCallGraph.h

736 ↗

(On Diff #72449)

I'd drop the "strictly" (here and below). (Or clarify "strictly" as opposed to what?).

908 ↗

(On Diff #72449)

s/an SCC/a maximal SCC/, to make things 100% obvious.

Same for RefSCC

lib/Analysis/LazyCallGraph.cpp

1340 ↗

(On Diff #72449)

If we're inserting a call edge and &TargetRC == this then I think we should assert that the target SCC is equal to or a descendent of the source SCC.

Actually, perhaps we should assert the target SCC is equal to or a descendent of the source SCC whenever we're inserting a call edge (i.e. without regards to whether &TargetRC == this). That'll be partially redundant with TargetRC.isDescendantOf(*this) below, but I think that's fine.

1408 ↗

(On Diff #72449)

How about recursive functions? It seems reasonable to want to all removeDeadFunction on them too.

1413 ↗

(On Diff #72449)

Any reason why you can't compact the EntryEdges vector here (i.e. swap the last element with the EII->second th element, pop the last element and update EntryIndexMap)?

1425 ↗

(On Diff #72449)

.

1434 ↗

(On Diff #72449)

s/necesasry/necessary/

1440 ↗

(On Diff #72449)

llvm::all_of

[chandlerc]

Thanks again for the review! Committing shortly and will make two follow-ups to address the comments that seem separable (either needing more utility code unrelated to this patch, and/or needing more tests).

lib/Analysis/LazyCallGraph.cpp

1340 ↗

(On Diff #72449)

We don't have any utility code for checking if an SCC is a descendent of another SCC in the call graph, so writing these assertions is very verbose right now. So I'll plan add it in a follow-up with some utility code.

1408 ↗

(On Diff #72449)

Interesting. I mean, yes, it does. And yet the caller I wanted to call this has this exact check before calling it.

But I agree that it seems like a meaningless restriction at *this* layer of the API.

I've left a FIXME here for now as I'd like to add this in a follow-up commit with its own test case.

1413 ↗

(On Diff #72449)

It would make the iteration order dependent on the particular mutation order which seems ... unfortunate.

If the sparseness ever becomes an issue here, I'd like to add an ADT that handles this generically when growing the vector.

llvm/trunk/include/llvm/Analysis/LazyCallGraph.h

public:
     /// This requires that the edge is not null. If we have not yet built
     /// a graph node for the function this edge points to, this will first ask
     /// the graph to build that node, inserting it into all the relevant
     /// structures.
     Node &getNode(LazyCallGraph &G);
 
   private:
     friend class LazyCallGraph::Node;
+    friend class LazyCallGraph::RefSCC;
 
     PointerIntPair<PointerUnion<Function *, Node *>, 1, Kind> Value;
 
     void setKind(Kind K) { Value.setInt(K); }
   };
 
   typedef SmallVector<Edge, 4> EdgeVectorT;
   typedef SmallVectorImpl<Edge> EdgeVectorImplT;
 
   /// A node in the call graph.
   ///
   /// This represents a single node. It's primary roles are to cache the list of
   /// callees, de-duplicate and provide fast testing of whether a function is
   /// a callee, and facilitate iteration of child nodes in the graph.
   class Node {
     friend class LazyCallGraph;
     friend class LazyCallGraph::SCC;
+    friend class LazyCallGraph::RefSCC;
 
     LazyCallGraph *G;
     Function &F;
 
     // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
     // stored directly within the node. These are both '-1' when nodes are part
     // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk.
     int DFSNumber;
class Node {
     void insertEdgeInternal(Node &ChildN, Edge::Kind EK);
 
     /// Internal helper to change an edge kind.
     void setEdgeKind(Function &ChildF, Edge::Kind EK);
 
     /// Internal helper to remove the edge to the given function.
     void removeEdgeInternal(Function &ChildF);
 
+    void clear() {
+      Edges.clear();
+      EdgeIndexMap.clear();
+    }
+
     /// Print the name of this node's function.
     friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) {
       return OS << N.F.getName();
     }
 
     /// Dump the name of this node's function to stderr.
     void dump() const;
 
class RefSCC {
 
     /// A map from SCC to index in the postorder list.
     SmallDenseMap<SCC *, int, 4> SCCIndices;
 
     /// Fast-path constructor. RefSCCs should instead be constructed by calling
     /// formRefSCCFast on the graph itself.
     RefSCC(LazyCallGraph &G);
 
+    void clear() {
+      Parents.clear();
+      SCCs.clear();
+      SCCIndices.clear();
+    }
+
     /// Print a short description useful for debugging or logging.
     ///
     /// We print the SCCs wrapped in '[]'s and skipping the middle SCCs if
     /// there are a large number.
     //
     // Note: this is defined inline to dodge issues with GCC's interpretation
     // of enclosing namespaces for friend function declarations.
     friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) {
#ifndef NDEBUG
     /// graph. This makes it useful even when partially through an update.
     ///
     /// Invariants checked:
     /// - SCCs and their indices match.
     /// - The SCCs list is in fact in post-order.
     void verify();
 #endif
 
+    /// Handle any necessary parent set updates after inserting a trivial ref
+    /// or call edge.
+    void handleTrivialEdgeInsertion(Node &SourceN, Node &TargetN);
+
   public:
     typedef pointee_iterator<SmallVectorImpl<SCC *>::const_iterator> iterator;
     typedef iterator_range<iterator> range;
     typedef pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator>
         parent_iterator;
 
     iterator begin() const { return SCCs.begin(); }
     iterator end() const { return SCCs.end(); }
public:
     /// effort has been made to minimize the overhead of common cases such as
     /// self-edges and edge removals which result in a spanning tree with no
     /// more cycles. There are also detailed comments within the implementation
     /// on techniques which could substantially improve this routine's
     /// efficiency.
     SmallVector<RefSCC *, 1> removeInternalRefEdge(Node &SourceN,
                                                    Node &TargetN);
 
+    /// A convenience wrapper around the above to handle trivial cases of
+    /// inserting a new call edge.
+    ///
+    /// This is trivial whenever the target is in the same SCC as the source or
+    /// the edge is an outgoing edge to some descendant SCC. In these cases
+    /// there is no change to the cyclic structure of SCCs or RefSCCs.
+    ///
+    /// To further make calling this convenient, it also handles inserting
+    /// already existing edges.
+    void insertTrivialCallEdge(Node &SourceN, Node &TargetN);
+
+    /// A convenience wrapper around the above to handle trivial cases of
+    /// inserting a new ref edge.
+    ///
+    /// This is trivial whenever the target is in the same RefSCC as the source
+    /// or the edge is an outgoing edge to some descendant RefSCC. In these
+    /// cases there is no change to the cyclic structure of the RefSCCs.
+    ///
+    /// To further make calling this convenient, it also handles inserting
+    /// already existing edges.
+    void insertTrivialRefEdge(Node &SourceN, Node &TargetN);
+
     ///@}
   };
 
   /// A post-order depth-first SCC iterator over the call graph.
   ///
   /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
   /// the call graph, walking it lazily in depth-first post-order. That is, it
   /// always visits SCCs for a callee prior to visiting the SCC for a caller
#endif
 
   ///@{
   /// \name Pre-SCC Mutation API
   ///
   /// These methods are only valid to call prior to forming any SCCs for this
   /// call graph. They can be used to update the core node-graph during
   /// a node-based inorder traversal that precedes any SCC-based traversal.
   ///
-  /// Once you begin manipulating a call graph's SCCs, you must perform all
-  /// mutation of the graph via the SCC methods.
+  /// Once you begin manipulating a call graph's SCCs, most mutation of the
+  /// graph must be performed via a RefSCC method. There are some exceptions
+  /// below.
 
   /// Update the call graph after inserting a new edge.
   void insertEdge(Node &Caller, Function &Callee, Edge::Kind EK);
 
   /// Update the call graph after inserting a new edge.
   void insertEdge(Function &Caller, Function &Callee, Edge::Kind EK) {
     return insertEdge(get(Caller), Callee, EK);
   }
 
   /// Update the call graph after deleting an edge.
   void removeEdge(Node &Caller, Function &Callee);
 
   /// Update the call graph after deleting an edge.
   void removeEdge(Function &Caller, Function &Callee) {
     return removeEdge(get(Caller), Callee);
   }
 
   ///@}
 
   ///@{
+  /// \name General Mutation API
+  ///
+  /// There are a very limited set of mutations allowed on the graph as a whole
+  /// once SCCs have started to be formed. These routines have strict contracts
+  /// but may be called at any point.
+
+  /// Remove a dead function from the call graph (typically to delete it).
+  ///
+  /// Note that the function must have an empty use list, and the call graph
+  /// must be up-to-date prior to calling this. That means it is by itself in
+  /// a maximal SCC which is by itself in a maximal RefSCC, etc. No structural
+  /// changes result from calling this routine other than potentially removing
+  /// entry points into the call graph.
+  ///
+  /// If SCC formation has begun, this function must not be part of the current
+  /// DFS in order to call this safely. Typically, the function will have been
+  /// fully visited by the DFS prior to calling this routine.
+  void removeDeadFunction(Function &F);
+
+  ///@}
+
+  ///@{
   /// \name Static helpers for code doing updates to the call graph.
   ///
   /// These helpers are used to implement parts of the call graph but are also
   /// useful to code doing updates or otherwise wanting to walk the IR in the
   /// same patterns as when we build the call graph.
 
   template <typename CallbackT>
   static void visitReferences(SmallVectorImpl<Constant *> &Worklist,

llvm/trunk/lib/Analysis/LazyCallGraph.cpp

 #ifndef NDEBUG
   if (!Result.empty())
     assert(!IsLeaf && "This SCC cannot be a leaf as we have split out new "
                       "SCCs by removing this edge.");
   if (none_of(G->LeafRefSCCs, [&](RefSCC *C) { return C == this; }))
     assert(!IsLeaf && "This SCC cannot be a leaf as it already had child "
                       "SCCs before we removed this edge.");
 #endif
+  // And connect both this RefSCC and all the new ones to the correct parents.
+  // The easiest way to do this is just to re-analyze the old parent set.
+  SmallVector<RefSCC *, 4> OldParents(Parents.begin(), Parents.end());
+  Parents.clear();
+  for (RefSCC *ParentRC : OldParents)
+    for (SCC *ParentC : ParentRC->SCCs)
+      for (Node &ParentN : *ParentC)
+        for (Edge &E : ParentN) {
+          assert(E.getNode() && "Cannot have a missing node in a visited SCC!");
+          RefSCC &RC = *G->lookupRefSCC(*E.getNode());
+          RC.Parents.insert(ParentRC);
+        }
+
   // If this SCC stopped being a leaf through this edge removal, remove it from
   // the leaf SCC list. Note that this DTRT in the case where this was never
   // a leaf.
   // FIXME: As LeafRefSCCs could be very large, we might want to not walk the
   // entire list if this RefSCC wasn't a leaf before the edge removal.
   if (!Result.empty())
     G->LeafRefSCCs.erase(
         std::remove(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(), this),
         G->LeafRefSCCs.end());
 
   // Return the new list of SCCs.
   return Result;
 }
 
+void LazyCallGraph::RefSCC::handleTrivialEdgeInsertion(Node &SourceN,
+                                                       Node &TargetN) {
+  // The only trivial case that requires any graph updates is when we add new
+  // ref edge and may connect different RefSCCs along that path. This is only
+  // because of the parents set. Every other part of the graph remains constant
+  // after this edge insertion.
+  assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
+  RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
+  if (&TargetRC == this) {
+
+    return;
+  }
+
+  assert(TargetRC.isDescendantOf(*this) &&
+         "Target must be a descendant of the Source.");
+  // The only change required is to add this RefSCC to the parent set of the
+  // target. This is a set and so idempotent if the edge already existed.
+  TargetRC.Parents.insert(this);
+}
+
+void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
+                                                  Node &TargetN) {
+#ifndef NDEBUG
+  // Check that the RefSCC is still valid when we finish.
+  auto ExitVerifier = make_scope_exit([this] { verify(); });
+#endif
+  // First insert it into the source or find the existing edge.
+  auto InsertResult = SourceN.EdgeIndexMap.insert(
+      {&TargetN.getFunction(), SourceN.Edges.size()});
+  if (!InsertResult.second) {
+    // Already an edge, just update it.
+    Edge &E = SourceN.Edges[InsertResult.first->second];
+    if (E.isCall())
+      return; // Nothing to do!
+    E.setKind(Edge::Call);
+  } else {
+    // Create the new edge.
+    SourceN.Edges.emplace_back(TargetN, Edge::Call);
+  }
+
+  // Now that we have the edge, handle the graph fallout.
+  handleTrivialEdgeInsertion(SourceN, TargetN);
+}
+
+void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
+#ifndef NDEBUG
+  // Check that the RefSCC is still valid when we finish.
+  auto ExitVerifier = make_scope_exit([this] { verify(); });
+#endif
+  // First insert it into the source or find the existing edge.
+  auto InsertResult = SourceN.EdgeIndexMap.insert(
+      {&TargetN.getFunction(), SourceN.Edges.size()});
+  if (!InsertResult.second)
+    // Already an edge, we're done.
+    return;
+
+  // Create the new edge.
+  SourceN.Edges.emplace_back(TargetN, Edge::Ref);
+
+  // Now that we have the edge, handle the graph fallout.
+  handleTrivialEdgeInsertion(SourceN, TargetN);
+}
+
 void LazyCallGraph::insertEdge(Node &SourceN, Function &Target, Edge::Kind EK) {
   assert(SCCMap.empty() && DFSStack.empty() &&
          "This method cannot be called after SCCs have been formed!");
 
   return SourceN.insertEdgeInternal(Target, EK);
 }
 
 void LazyCallGraph::removeEdge(Node &SourceN, Function &Target) {
   assert(SCCMap.empty() && DFSStack.empty() &&
          "This method cannot be called after SCCs have been formed!");
 
   return SourceN.removeEdgeInternal(Target);
 }
 
+void LazyCallGraph::removeDeadFunction(Function &F) {
+  // FIXME: This is unnecessarily restrictive. We should be able to remove
+  // functions which recursively call themselves.
+  assert(F.use_empty() &&
+         "This routine should only be called on trivially dead functions!");
+
+  auto EII = EntryIndexMap.find(&F);
+  if (EII != EntryIndexMap.end()) {
+    EntryEdges[EII->second] = Edge();
+    EntryIndexMap.erase(EII);
+  }
+
+  // It's safe to just remove un-visited functions from the RefSCC entry list.
+  // FIXME: This is a linear operation which could become hot and benefit from
+  // an index map.
+  auto RENI = find(RefSCCEntryNodes, &F);
+  if (RENI != RefSCCEntryNodes.end())
+    RefSCCEntryNodes.erase(RENI);
+
+  auto NI = NodeMap.find(&F);
+  if (NI == NodeMap.end())
+    // Not in the graph at all!
+    return;
+
+  Node &N = *NI->second;
+  NodeMap.erase(NI);
+
+  if (SCCMap.empty() && DFSStack.empty()) {
+    // No SCC walk has begun, so removing this is fine and there is nothing
+    // else necessary at this point but clearing out the node.
+    N.clear();
+    return;
+  }
+
+  // Check that we aren't going to break the DFS walk.
+  assert(all_of(DFSStack,
+                [&N](const std::pair<Node *, edge_iterator> &Element) {
+                  return Element.first != &N;
+                }) &&
+         "Tried to remove a function currently in the DFS stack!");
+  assert(find(PendingRefSCCStack, &N) == PendingRefSCCStack.end() &&
+         "Tried to remove a function currently pending to add to a RefSCC!");
+
+  // 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;
+  SCCMap.erase(CI);
+  RefSCC &RC = C.getOuterRefSCC();
+
+  // 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");
+  assert(RC.Parents.empty() && "Cannot have parents of a dead RefSCC!");
+
+  // Now remove this RefSCC from any parents sets and the leaf list.
+  for (Edge &E : N)
+    if (Node *TargetN = E.getNode())
+      if (RefSCC *TargetRC = lookupRefSCC(*TargetN))
+        TargetRC->Parents.erase(&RC);
+  // FIXME: This is a linear operation which could become hot and benefit from
+  // an index map.
+  auto LRI = find(LeafRefSCCs, &RC);
+  if (LRI != LeafRefSCCs.end())
+    LeafRefSCCs.erase(LRI);
+
+  auto RCIndexI = RefSCCIndices.find(&RC);
+  int RCIndex = RCIndexI->second;
+  PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex);
+  RefSCCIndices.erase(RCIndexI);
+  for (int i = RCIndex, Size = PostOrderRefSCCs.size(); i < Size; ++i)
+    RefSCCIndices[PostOrderRefSCCs[i]] = i;
+
+  // Finally clear out all the data structures from the node down through the
+  // components.
+  N.clear();
+  C.clear();
+  RC.clear();
+
+  // Nothing to delete as all the objects are allocated in stable bump pointer
+  // allocators.
+}
+
 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
   return *new (MappedN = BPA.Allocate()) Node(*this, F);
 }
 
 void LazyCallGraph::updateGraphPtrs() {
   // Process all nodes updating the graph pointers.
   {
     SmallVector<Node *, 16> Worklist;
for (Node &N : C)
                "Cannot have a missing node in a visited part of the graph!");
         RefSCC &ChildRC = *lookupRefSCC(*E.getNode());
         if (&ChildRC == &RC)
           continue;
         ChildRC.Parents.insert(&RC);
         IsLeaf = false;
       }
 
-  // For the SCCs where we fine no child SCCs, add them to the leaf list.
+  // For the SCCs where we find no child SCCs, add them to the leaf list.
   if (IsLeaf)
     LeafRefSCCs.push_back(&RC);
 }
 
 bool LazyCallGraph::buildNextRefSCCInPostOrder() {
   if (DFSStack.empty()) {
     Node *N;
     do {

llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp

 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 #include <memory>
 
TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
 
   // And verify the post-order walk reflects the updated structure.
   auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end();
   ASSERT_NE(I, End);
   EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
   EXPECT_EQ(++I, End);
 }
 
+TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
+  LLVMContext Context;
+  // We want to ensure we can delete nodes from relatively complex graphs and
+  // so use the diamond of triangles graph defined above.
+  //
+  // The ascii diagram is repeated here for easy reference.
+  //
+  //         d1       |
+  //        /  \      |
+  //       d3--d2     |
+  //      /     \     |
+  //     b1     c1    |
+  //   /  \    /  \   |
+  //  b3--b2  c3--c2  |
+  //       \  /       |
+  //        a1        |
+  //       /  \       |
+  //      a3--a2      |
+  //
+  std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
+  LazyCallGraph CG(*M);
+
+  // Force the graph to be fully expanded.
+  for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
+    dbgs() << "Formed RefSCC: " << RC << "\n";
+
+  LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
+  LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
+  LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
+  LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
+  LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
+  LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
+  LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
+  LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
+  LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
+  LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
+  LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
+  LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
+  LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
+  LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
+  LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
+  LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
+  ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
+  ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
+  ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
+  ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
+  ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
+
+  // Delete d2 from the graph, as if it had been inlined.
+  //
+  //         d1         |
+  //        / /         |
+  //       d3--.        |
+  //      /     \       |
+  //     b1     c1      |
+  //   /  \    /  \     |
+  //  b3--b2  c3--c2    |
+  //       \  /         |
+  //        a1          |
+  //       /  \         |
+  //      a3--a2        |
+
+  Function &D2F = D2.getFunction();
+  CallInst *C1Call = nullptr, *D1Call = nullptr;
+  for (User *U : D2F.users()) {
+    CallInst *CI = dyn_cast<CallInst>(U);
+    ASSERT_TRUE(CI) << "Expected a call: " << *U;
+    if (CI->getParent()->getParent() == &C1.getFunction()) {
+      ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
+      C1Call = CI;
+    } else if (CI->getParent()->getParent() == &D1.getFunction()) {
+      ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
+      D1Call = CI;
+    } else {
+      FAIL() << "Found an unexpected call instruction: " << *CI;
+    }
+  }
+  ASSERT_NE(C1Call, nullptr);
+  ASSERT_NE(D1Call, nullptr);
+  ASSERT_EQ(&D2F, C1Call->getCalledFunction());
+  ASSERT_EQ(&D2F, D1Call->getCalledFunction());
+  C1Call->setCalledFunction(&D3.getFunction());
+  D1Call->setCalledFunction(&D3.getFunction());
+  ASSERT_EQ(0u, D2F.getNumUses());
+
+  // Insert new edges first.
+  CRC.insertTrivialCallEdge(C1, D3);
+  DRC.insertTrivialCallEdge(D1, D3);
+
+  // Then remove the old ones.
+  LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);
+  auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);
+  EXPECT_EQ(&DC, CG.lookupSCC(D2));
+  EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
+  LazyCallGraph::SCC &NewDC = *NewCs.begin();
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
+  auto NewRCs = DRC.removeInternalRefEdge(D1, D2);
+  EXPECT_EQ(&DRC, CG.lookupRefSCC(D2));
+  EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin()));
+  LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin();
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_FALSE(NewDRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+  CRC.removeOutgoingEdge(C1, D2);
+  EXPECT_FALSE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+
+  // Now that we've updated the call graph, D2 is dead, so remove it.
+  CG.removeDeadFunction(D2F);
+
+  // Check that the graph still looks the same.
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+
+  // Verify the post-order walk hasn't changed.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
+  ASSERT_NE(++I, E);
+  EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
+  ASSERT_NE(++I, E);
+  EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
+  ASSERT_NE(++I, E);
+  EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
+  EXPECT_EQ(++I, E);
+}
+
+TEST(LazyCallGraphTest, InlineAndDeleteFunctionMidTraversal) {
+  LLVMContext Context;
+  // This is the same fundamental test as the previous, but we perform it
+  // having only partially walked the RefSCCs of the graph.
+  //
+  // The ascii diagram is repeated here for easy reference.
+  //
+  //         d1       |
+  //        /  \      |
+  //       d3--d2     |
+  //      /     \     |
+  //     b1     c1    |
+  //   /  \    /  \   |
+  //  b3--b2  c3--c2  |
+  //       \  /       |
+  //        a1        |
+  //       /  \       |
+  //      a3--a2      |
+  //
+  std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
+  LazyCallGraph CG(*M);
+
+  // Walk the RefSCCs until we find the one containing 'c1'.
+  auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
+  ASSERT_NE(I, E);
+  LazyCallGraph::RefSCC &DRC = *I;
+  ASSERT_NE(&DRC, nullptr);
+  ++I;
+  ASSERT_NE(I, E);
+  LazyCallGraph::RefSCC &CRC = *I;
+  ASSERT_NE(&CRC, nullptr);
+
+  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1")));
+  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2")));
+  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3")));
+  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1")));
+  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2")));
+  ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3")));
+  LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
+  LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
+  LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
+  LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
+  LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
+  LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C1));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
+  ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D1));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
+  ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
+  ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
+
+  // Delete d2 from the graph, as if it had been inlined.
+  //
+  //         d1         |
+  //        / /         |
+  //       d3--.        |
+  //      /     \       |
+  //     b1     c1      |
+  //   /  \    /  \     |
+  //  b3--b2  c3--c2    |
+  //       \  /         |
+  //        a1          |
+  //       /  \         |
+  //      a3--a2        |
+
+  Function &D2F = D2.getFunction();
+  CallInst *C1Call = nullptr, *D1Call = nullptr;
+  for (User *U : D2F.users()) {
+    CallInst *CI = dyn_cast<CallInst>(U);
+    ASSERT_TRUE(CI) << "Expected a call: " << *U;
+    if (CI->getParent()->getParent() == &C1.getFunction()) {
+      ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
+      C1Call = CI;
+    } else if (CI->getParent()->getParent() == &D1.getFunction()) {
+      ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
+      D1Call = CI;
+    } else {
+      FAIL() << "Found an unexpected call instruction: " << *CI;
+    }
+  }
+  ASSERT_NE(C1Call, nullptr);
+  ASSERT_NE(D1Call, nullptr);
+  ASSERT_EQ(&D2F, C1Call->getCalledFunction());
+  ASSERT_EQ(&D2F, D1Call->getCalledFunction());
+  C1Call->setCalledFunction(&D3.getFunction());
+  D1Call->setCalledFunction(&D3.getFunction());
+  ASSERT_EQ(0u, D2F.getNumUses());
+
+  // Insert new edges first.
+  CRC.insertTrivialCallEdge(C1, D3);
+  DRC.insertTrivialCallEdge(D1, D3);
+
+  // Then remove the old ones.
+  LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);
+  auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);
+  EXPECT_EQ(&DC, CG.lookupSCC(D2));
+  EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
+  LazyCallGraph::SCC &NewDC = *NewCs.begin();
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
+  EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
+  auto NewRCs = DRC.removeInternalRefEdge(D1, D2);
+  EXPECT_EQ(&DRC, CG.lookupRefSCC(D2));
+  EXPECT_EQ(NewRCs.end(), std::next(NewRCs.begin()));
+  LazyCallGraph::RefSCC &NewDRC = **NewRCs.begin();
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_FALSE(NewDRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+  CRC.removeOutgoingEdge(C1, D2);
+  EXPECT_FALSE(CRC.isParentOf(DRC));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+  EXPECT_TRUE(DRC.isParentOf(NewDRC));
+
+  // Now that we've updated the call graph, D2 is dead, so remove it.
+  CG.removeDeadFunction(D2F);
+
+  // Check that the graph still looks the same.
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
+  EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
+  EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
+  EXPECT_TRUE(CRC.isParentOf(NewDRC));
+
+  // Verify that the post-order walk reflects the updated but still incomplete
+  // structure.
+  auto J = CG.postorder_ref_scc_begin();
+  EXPECT_NE(J, E);
+  EXPECT_EQ(&NewDRC, &*J) << "Actual RefSCC: " << *J;
+  ++J;
+  EXPECT_NE(J, E);
+  EXPECT_EQ(&CRC, &*J) << "Actual RefSCC: " << *J;
+  EXPECT_EQ(I, J);
+
+  // Check that we can form the last two RefSCCs now, and even that we can do
+  // it with alternating iterators.
+  ++J;
+  EXPECT_NE(J, E);
+  LazyCallGraph::RefSCC &BRC = *J;
+  EXPECT_NE(&BRC, nullptr);
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))));
+  EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))));
+  EXPECT_TRUE(BRC.isParentOf(NewDRC));
+  ++I;
+  EXPECT_EQ(J, I);
+  EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
+
+  // Increment I this time to form the new RefSCC, flopping back to the first
+  // iterator.
+  ++I;
+  EXPECT_NE(I, E);
+  LazyCallGraph::RefSCC &ARC = *I;
+  EXPECT_NE(&ARC, nullptr);
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))));
+  EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))));
+  EXPECT_TRUE(ARC.isParentOf(BRC));
+  EXPECT_TRUE(ARC.isParentOf(CRC));
+  ++J;
+  EXPECT_EQ(I, J);
+  EXPECT_EQ(&ARC, &*J) << "Actual RefSCC: " << *J;
+  ++I;
+  EXPECT_EQ(E, I);
+  ++J;
+  EXPECT_EQ(E, J);
+}
+
 TEST(LazyCallGraphTest, InternalEdgeMutation) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
                                                      "entry:\n"
                                                      "  call void @b()\n"
                                                      "  ret void\n"
                                                      "}\n"
                                                      "define void @b() {\n"