Introduce a CallGraph updater helper class

[jdoerfert]

Summary

The CallGraphUpdater is a helper that simplifies the process of updating
the call graph, both old and new style, while running an CG-SCC pass.

The uses are, for now, contained in different commits, e.g. D70767.

More functionality, e.g., replace a function with a new version, is
added as we need it.

[merge_guards_bot]

Build result: pass - 60395 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[jdoerfert]

Add comment

[merge_guards_bot]

Build result: pass - 60558 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[jdoerfert]

@hfinkel ping, this is a dependence for 2 CG-SCC patches

[hfinkel]

llvm/lib/Analysis/CGSCCPassManager.cpp

456 ↗

(On Diff #232584)

This patch seems to be doing two things. One, is fixing this FIXME, and the second is adding the CallGraphUpdater wrapper. Can you split out these two changes?

Also, can you add unit tests for these various things?

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

46

What's the state of this? Should we have an assert for now?

[jdoerfert]

Extract parts into D72025, improve the existing functionality, add unit tests.

[merge_guards_bot]

Unit tests: pass. 61163 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[modocache]

Thanks for this! I'm depending on this patch in D71899.

I noticed an edge case when using the CallGraphUpdater to introduce coroutine funclets for recursive coroutine functions, specifically when compiling this: https://github.com/lewissbaker/cppcoro/blob/d83ee9352ea2652fbc4f02885f9d19770f5e9608/test/recursive_generator_tests.cpp#L164. I reduced this to a small unit test, and what I think may be a reasonable fix, in D72226. Please feel free to review my patch, merge it into this one, or to address the issue however you like. And please let me know if it's actually just a user error on my part.

I had a question about where registerOutlinedFunction belongs, but other than that this LGTM! I'm not an expert, though, so maybe @chandlerc or someone could review this.

llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h

27

Because it's a friend of LazyCallGraph and so can modify its internal state, I'd say CallGraphUpdater is a lot more than just a wrapper to unify the two interfaces. I rely on CallGraphUpdater in my patch D71899 because it allows me to insert an outlined function node into the call graph via CallGraphUpdater:: registerOutlinedFunction, defined below.

This makes me wonder whether the functionality implemented in the body of CallGraphUpdater::registerOutlinedFunction should actually be moved, to a public member function on LazyCallGraph or one of its other helper classes. The body of that function reaches into internal mappings in LazyCallGraph and modifies them -- that seems like something only LazyCallGraph itself should be responsible for.

The other member functions of CallGraphUpdater only use CallGraph and LazyCallGraph API that are public, so those do seem like "wrappers" to me. But CallGraphUpdater::registerOutlinedFunction seems like something different. If that function is going to remain, I'd suggest updating this docblock to indicate that CallGraphUpdater provides an interface that isn't available on LazyCallGraph itself.

44

Just echoing my nit-pick comment on D72025, but I think "CGSCC" is the canonical abbreviation. "CG-SCC" only appears in this diff and D72025.

[jdoerfert]

More tests, late function removal and other improvements

[merge_guards_bot]

Unit tests: pass. 61278 tests passed, 0 failed and 736 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[modocache]

Friendly ping for review on this one. @jdoerfert is there anything blocking this besides code review? I think the clang-tidy errors are legitimate, FWIW, but they shouldn't be blockers for code review.

Reviewers: this is a blocker for @jdoerfert's patch for an attributor CGSCC pass, as well as for a series of patches supporting coroutine passes in the new pass manager.

[jdoerfert]

Improvements after running the Attributor SCC pass on the LLVM test suite

[merge_guards_bot]

Unit tests: fail. 62156 tests passed, 7 failed and 811 were skipped.

failed: LLVM-Unit.Analysis/_/AnalysisTests/CGSCCPassManagerTest.TestUpdateCGAndAnalysisManagerForPasses8
failed: libc++.std/language_support/cmp/cmp_partialord/partialord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongeq/cmp.strongeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongord/strongord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakeq/cmp.weakeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakord/weakord.pass.cpp
failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_mutex_requirements_mutex/thread_mutex_recursive/lock.pass.cpp

clang-tidy: fail. clang-tidy found 0 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[hfinkel]

llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h

32

Please add some documentation explaining why you have a separate list of dead Comdat functions.

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

98

I agree with @modocache, this looks like an internal implementation detail of LCG. Can you move the logic into that class?

[jdoerfert]

Add documentation

[jdoerfert]

llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h

27

Resolved by making it part of the LazyCallGraph API.

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

98

@modocache Has a patch for this already (D72226) which I somehow missed for a month.
Options are to merge them or to apply them in order. I don't care which we choose.

[merge_guards_bot]

Unit tests: fail. 62406 tests passed, 1 failed and 839 were skipped.

failed: LLVM-Unit.Analysis/_/AnalysisTests/CGSCCPassManagerTest.TestUpdateCGAndAnalysisManagerForPasses8

clang-tidy: fail. clang-tidy found 0 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[jdoerfert]

Fix the tests

[merge_guards_bot]

Unit tests: pass. 62406 tests passed, 0 failed and 839 were skipped.

clang-tidy: fail. clang-tidy found 0 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[modocache]

Sorry if it's presumptuous of me to request changes, but I guess @hfinkel may agree with me here that registerOutlinedFunction ought to be moved to LazyCallGraph or one of its inner classes.

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

98

My revision D72226 builds on the idea of adding a CallGraphUpdater class, adding a specific function I need when outlining. I need something like this in order to make my particular CGSCC pass, coro-split, work with LazyCallGraph.

That being said, my (relatively new LLVM contributor) opinion is that CallGraphUpdater reaches a bit too deep into the LazyCallGraph internals -- it needs to be friends with LazyCallGraph, LazyCallGraph::SCC, and LazyCallGraph::Node in order to accomplish what it's doing here: modifying the DFSNumber and LowLink members of the node, both of which seem to be like implementation details of the Tarjan DFS algorithm being used under the hood. It seems like @hfinkel agrees with me, that the logic to perform the specific SCC discovery algorithm should be encapsulated entirely within LazyCallGraph. And I would not mind modifying my patch D72226 to work with such an approach.

[jdoerfert]

In D70927#1855168, @modocache wrote:

Sorry if it's presumptuous of me to request changes,

That is always OK.

but I guess @hfinkel may agree with me here that registerOutlinedFunction ought to be moved to LazyCallGraph or one of its inner classes.

I'm confused. I mentioned in my last response that you moved the "problematic" logic into LazyCallGraph in your patch (D72226), or did you do something different?
Please clarify what you want me to do that is different, or the same, to your patch. I'm happy to move logic into the LazyCallGraph class for example.

I mean in your patch registerOutlinedFunction looks "clean":

void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
  if (CG) {
    CG->addToCallGraph(&NewFn);
  } else if (LCG) {
    LazyCallGraph::Node &CGNode = createNode(*LCG, NewFn);
    addNodeToSCC(*LCG, *SCC, CGNode);
  }
}

---

EDIT: I moved the logic into LazyCallGraph::addNewFunctionIntoSCC. Does that address your concerns? (It also allowed me to remove the updater as a friend)

[jdoerfert]

Fix spelling and try to address concerns

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 5 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[jdoerfert]

Fix typo and remove last CallGraphUpdater friend decl by exposing a single API function.

[jdoerfert]

Fixed copy/paste error, eliminated warnings

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: fail. clang-tidy found 5 errors and 2 warnings. 0 of them are added as review comments below (why?).

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[merge_guards_bot]

Unit tests: pass. 62436 tests passed, 0 failed and 845 were skipped.

clang-tidy: pass.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[jdoerfert]

Fix clang format (empty line)

[modocache]

I mentioned in my last response that you moved the "problematic" logic into LazyCallGraph in your patch (D72226), or did you do something different? Please clarify what you want me to do that is different, or the same, to your patch. I'm happy to move logic into the LazyCallGraph class for example.

Ah, yes, I see the confusion! In D72226 I still have the logic in CallGraphUpdater, I didn't move it into LazyCallGraph. In D72226, I moved the "problematic" logic into new member functions on CallGraphUpdater:

LazyCallGraph::Node &CallGraphUpdater::createNode(LazyCallGraph &LCG,
                                                  Function &Fn) {
  assert(!LCG.lookup(Fn) && "node already exists");

  LazyCallGraph::Node &CGNode = LCG.get(Fn);
  LCG.NodeMap[&Fn] = &CGNode;
  CGNode.DFSNumber = CGNode.LowLink = -1;  // <- HERE, I think this implementation detail ought not be exposed to CallGraphUpdater
  CGNode.populate();
  return CGNode;
}

void CallGraphUpdater::addNodeToSCC(LazyCallGraph &LCG, LazyCallGraph::SCC &SCC,
                                    LazyCallGraph::Node &N) {
  SCC.Nodes.push_back(&N);
  LCG.SCCMap[&N] = &SCC;  // <- HERE, I think this implementation detail ought not be exposed to CallGraphUpdater
}

So my specific suggestion would be to move the lines marked "HERE" into a member function on LazyCallGraph, thus removing the need for CallGraphUpdater to be marked as a friend.

EDIT: I moved the logic into LazyCallGraph::addNewFunctionIntoSCC. Does that address your concerns? (It also allowed me to remove the updater as a friend)

Yes, that's exactly what I meant! Sorry I wasn't clearer!

Your latest update addressed all of my comments -- thank you! I do wish someone who's authored more of CallGraph or LazyCallGraph could chime in here, but this at least LGTM. Thanks for this work! It was a tremendous help in my own work to adapt coroutines to the new pass manager.

llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h

32

Nit-pick typo: s/seperatly/separately/g.

[modocache]

llvm/include/llvm/Analysis/LazyCallGraph.h

1062

Ah, I missed one thing; I think this deserves its own unit test in LazyCallGraphTest.cpp.

[jdoerfert]

Add (simple) unit test for LazyCallGraph::addNewFunctionIntoSCC

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[merge_guards_bot]

Unit tests: pass. 62437 tests passed, 0 failed and 845 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[hfinkel]

LGTM

llvm/include/llvm/Analysis/CallGraph.h

class CallGraph {
 
   /// Replace the function represented by this node by another.
   ///
   /// This does not rescan the body of the function, so it is suitable when
   /// splicing the body of one function to another while also updating all
   /// callers from the old function to the new.
   void spliceFunction(const Function *From, const Function *To);
 
-  /// Add a function to the call graph, and link the node to all of the
-  /// functions that it calls.
-  void addToCallGraph(Function *F);
-
 public:
   explicit CallGraph(Module &M);
   CallGraph(CallGraph &&Arg);
   ~CallGraph();
 
   void print(raw_ostream &OS) const;
   void dump() const;
 
public:
   /// destroyed.  This is only valid if the function does not call any other
   /// functions (ie, there are no edges in it's CGN).  The easiest way to do
   /// this is to dropAllReferences before calling this.
   Function *removeFunctionFromModule(CallGraphNode *CGN);
 
   /// Similar to operator[], but this will insert a new CallGraphNode for
   /// \c F if one does not already exist.
   CallGraphNode *getOrInsertFunction(const Function *F);
+
+  /// Populate \p CGN based on the calls inside the associated function.
+  void populateCallGraphNode(CallGraphNode *CGN);
+
+  /// Add a function to the call graph, and link the node to all of the
+  /// functions that it calls.
+  void addToCallGraph(Function *F);
 };
 
 /// A node in the call graph for a module.
 ///
 /// Typically represents a function in the call graph. There are also special
 /// "null" nodes used to represent theoretical entries in the call graph.
 class CallGraphNode {
 public:

llvm/include/llvm/Analysis/LazyCallGraph.h

#endif
   /// 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);
 
+  /// Introduce a node for the function \p NewF in the SCC \p C.
+  void addNewFunctionIntoSCC(Function &NewF, SCC &C);
+
   ///@}
 
   ///@{
   /// \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.

llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h

+//===- CallGraphUpdater.h - A (lazy) call graph update helper ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file provides interfaces used to manipulate a call graph, regardless
+/// if it is a "old style" CallGraph or an "new style" LazyCallGraph.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CALLGRAPHUPDATER_H
+#define LLVM_TRANSFORMS_UTILS_CALLGRAPHUPDATER_H
+
+#include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Analysis/LazyCallGraph.h"
+
+namespace llvm {
+
+/// Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph. This
+/// simplifies the interface and the call sites, e.g., new and old pass manager
+/// passes can share the same code.
+class CallGraphUpdater {
+  /// Containers for functions which we did replace or want to delete when
+  /// `finalize` is called. This can happen explicitly or as part of the
+  /// destructor. Dead functions in comdat sections are tracked seperatly
+  /// because a function with discardable linakage in a COMDAT should only
+  /// be dropped if the entire COMDAT is dropped, see git ac07703842cf.
+  ///{
+  SmallPtrSet<Function *, 16> ReplacedFunctions;
+  SmallVector<Function *, 16> DeadFunctions;
+  SmallVector<Function *, 16> DeadFunctionsInComdats;
+  ///}
+
+  /// Old PM variables
+  ///{
+  CallGraph *CG = nullptr;
+  CallGraphSCC *CGSCC = nullptr;
+  ///}
+
+  /// New PM variables
+  ///{
+  LazyCallGraph *LCG = nullptr;
+  LazyCallGraph::SCC *SCC = nullptr;
+  CGSCCAnalysisManager *AM = nullptr;
+  CGSCCUpdateResult *UR = nullptr;
+  ///}
+
+public:
+  CallGraphUpdater() {}
+  ~CallGraphUpdater() { finalize(); }
+
+  /// Initializers for usage outside of a CGSCC pass, inside a CGSCC pass in
+  /// the old and new pass manager (PM).
+  ///{
+  void initialize(CallGraph &CG, CallGraphSCC &SCC) {
+    this->CG = &CG;
+    this->CGSCC = &SCC;
+  }
+  void initialize(LazyCallGraph &LCG, LazyCallGraph::SCC &SCC,
+                  CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) {
+    this->LCG = &LCG;
+    this->SCC = &SCC;
+    this->AM = &AM;
+    this->UR = &UR;
+  }
+  ///}
+
+  /// Finalizer that will trigger actions like function removal from the CG.
+  bool finalize();
+
+  /// Remove \p Fn from the call graph.
+  void removeFunction(Function &Fn);
+
+  /// After an CGSCC pass changes a function in ways that affect the call
+  /// graph, this method can be called to update it.
+  void reanalyzeFunction(Function &Fn);
+
+  /// If a new function was created by outlining, this method can be called
+  /// to update the call graph for the new function. Note that the old one
+  /// still needs to be re-analyzed or manually updated.
+  void registerOutlinedFunction(Function &NewFn);
+
+  /// Replace \p OldFn in the call graph (and SCC) with \p NewFn. The uses
+  /// outside the call graph and the function \p OldFn are not modified.
+  /// Note that \p OldFn is also removed from the call graph
+  /// (\see removeFunction).
+  void replaceFunctionWith(Function &OldFn, Function &NewFn);
+
+  /// Remove the call site \p CS from the call graph.
+  void removeCallSite(CallBase &CS);
+
+  /// Replace \p OldCS with the new call site \p NewCS.
+  /// \return True if the replacement was successful, otherwise False. In the
+  /// latter case the parent function of \p OldCB needs to be re-analyzed.
+  bool replaceCallSite(CallBase &OldCS, CallBase &NewCS);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CALLGRAPHUPDATER_H

llvm/lib/Analysis/CallGraph.cpp

 void CallGraph::addToCallGraph(Function *F) {
   CallGraphNode *Node = getOrInsertFunction(F);
 
   // If this function has external linkage or has its address taken, anything
   // could call it.
   if (!F->hasLocalLinkage() || F->hasAddressTaken())
     ExternalCallingNode->addCalledFunction(nullptr, Node);
 
+  populateCallGraphNode(Node);
+}
+
+void CallGraph::populateCallGraphNode(CallGraphNode *Node) {
+  Function *F = Node->getFunction();
+
   // If this function is not defined in this translation unit, it could call
   // anything.
   if (F->isDeclaration() && !F->isIntrinsic())
     Node->addCalledFunction(nullptr, CallsExternalNode.get());
 
   // Look for calls by this function.
   for (BasicBlock &BB : *F)
     for (Instruction &I : BB) {

llvm/lib/Analysis/CallGraphSCCPass.cpp

 
 /// This informs the SCC and the pass manager that the specified
 /// Old node has been deleted, and New is to be used in its place.
 void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
   assert(Old != New && "Should not replace node with self");
   for (unsigned i = 0; ; ++i) {
     assert(i != Nodes.size() && "Node not in SCC");
     if (Nodes[i] != Old) continue;
+    if (New)
       Nodes[i] = New;
+    else
+      Nodes.erase(Nodes.begin() + i);
     break;
   }
 
   // Update the active scc_iterator so that it doesn't contain dangling
   // pointers to the old CallGraphNode.
   scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
   CGI->ReplaceNode(Old, New);
 }

llvm/lib/Analysis/LazyCallGraph.cpp

void LazyCallGraph::removeDeadFunction(Function &F) {
   C.clear();
   RC.clear();
   RC.G = nullptr;
 
   // Nothing to delete as all the objects are allocated in stable bump pointer
   // allocators.
 }
 
+void LazyCallGraph::addNewFunctionIntoSCC(Function &NewF, SCC &C) {
+  Node &CGNode = get(NewF);
+  CGNode.DFSNumber = CGNode.LowLink = -1;
+  CGNode.populate();
+  C.Nodes.push_back(&CGNode);
+  SCCMap[&CGNode] = &C;
+  NodeMap[&NewF] = &CGNode;
+}
+
 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
   return *new (MappedN = BPA.Allocate()) Node(*this, F);
 }
 
 void LazyCallGraph::updateGraphPtrs() {
   // Walk the node map to update their graph pointers. While this iterates in
   // an unstable order, the order has no effect so it remains correct.
   for (auto &FunctionNodePair : NodeMap)

llvm/lib/Transforms/Utils/CMakeLists.txt

 add_llvm_component_library(LLVMTransformUtils
   AMDGPUEmitPrintf.cpp
   ASanStackFrameLayout.cpp
   AddDiscriminators.cpp
   BasicBlockUtils.cpp
   BreakCriticalEdges.cpp
   BuildLibCalls.cpp
   BypassSlowDivision.cpp
   CallPromotionUtils.cpp
+  CallGraphUpdater.cpp
   CanonicalizeAliases.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CodeExtractor.cpp
   CodeMoverUtils.cpp
   CtorUtils.cpp
   Debugify.cpp
   DemoteRegToStack.cpp

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

+//===- CallGraphUpdater.cpp - A (lazy) call graph update helper -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file provides interfaces used to manipulate a call graph, regardless
+/// if it is a "old style" CallGraph or an "new style" LazyCallGraph.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CallGraphUpdater.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
+
+using namespace llvm;
+
+bool CallGraphUpdater::finalize() {
+  if (!DeadFunctionsInComdats.empty()) {
+    filterDeadComdatFunctions(*DeadFunctionsInComdats.front()->getParent(),
+                              DeadFunctionsInComdats);
+    DeadFunctions.append(DeadFunctionsInComdats.begin(),
+                         DeadFunctionsInComdats.end());
+  }
+
+  for (Function *DeadFn : DeadFunctions) {
+    DeadFn->removeDeadConstantUsers();
+
+    if (CG) {
+      CallGraphNode *OldCGN = CG->getOrInsertFunction(DeadFn);
+      CG->getExternalCallingNode()->removeAnyCallEdgeTo(OldCGN);
+      OldCGN->removeAllCalledFunctions();
+      DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
+
+      assert(OldCGN->getNumReferences() == 0);
+
+      delete CG->removeFunctionFromModule(OldCGN);
+      continue;
+    }
+
+    // The old style call graph (CG) has a value handle we do not want to
+    // replace with undef so we do this here.
+    DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
+
+    if (LCG && !ReplacedFunctions.count(DeadFn)) {
+      // Taken mostly from the inliner:
+      FunctionAnalysisManager &FAM =
+          AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*SCC, *LCG)
+              .getManager();
+
+      LazyCallGraph::Node &N = LCG->get(*DeadFn);
+      auto *DeadSCC = LCG->lookupSCC(N);
+      assert(DeadSCC && DeadSCC->size() == 1 &&
+             &DeadSCC->begin()->getFunction() == DeadFn);
+      auto &DeadRC = DeadSCC->getOuterRefSCC();
+
+      FAM.clear(*DeadFn, DeadFn->getName());
+      AM->clear(*DeadSCC, DeadSCC->getName());
+      LCG->removeDeadFunction(*DeadFn);
+
+      // Mark the relevant parts of the call graph as invalid so we don't visit
+      // them.
+      UR->InvalidatedSCCs.insert(DeadSCC);
+      UR->InvalidatedRefSCCs.insert(&DeadRC);
+    }
+
+    // The function is now really dead and de-attached from everything.
+    DeadFn->eraseFromParent();
+  }
+
+  bool Changed = !DeadFunctions.empty();
+  DeadFunctionsInComdats.clear();
+  DeadFunctions.clear();
+  return Changed;
+}
+
+void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
+  if (CG) {
+    CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
+    OldCGN->removeAllCalledFunctions();
+    CG->populateCallGraphNode(OldCGN);
+  } else if (LCG) {
+    LazyCallGraph::Node &N = LCG->get(Fn);
+    LazyCallGraph::SCC *C = LCG->lookupSCC(N);
+    updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR);
+  }
+}
+
+void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
+  if (CG)
+    CG->addToCallGraph(&NewFn);
+  else if (LCG)
+    LCG->addNewFunctionIntoSCC(NewFn, *SCC);
+}
+
+void CallGraphUpdater::removeFunction(Function &DeadFn) {
+  DeadFn.deleteBody();
+  DeadFn.setLinkage(GlobalValue::ExternalLinkage);
+  if (DeadFn.hasComdat())
+    DeadFunctionsInComdats.push_back(&DeadFn);
+  else
+    DeadFunctions.push_back(&DeadFn);
+}
+
+void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
+  ReplacedFunctions.insert(&OldFn);
+  if (CG) {
+    // Update the call graph for the newly promoted function.
+    // CG->spliceFunction(&OldFn, &NewFn);
+    CallGraphNode *OldCGN = (*CG)[&OldFn];
+    CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
+    NewCGN->stealCalledFunctionsFrom(OldCGN);
+
+    // And update the SCC we're iterating as well.
+    CGSCC->ReplaceNode(OldCGN, NewCGN);
+  } else if (LCG) {
+    // Directly substitute the functions in the call graph.
+    LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
+    SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
+  }
+  removeFunction(OldFn);
+}
+
+bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
+  // This is only necessary in the (old) CG.
+  if (!CG)
+    return true;
+
+  Function *Caller = OldCS.getCaller();
+  CallGraphNode *NewCalleeNode =
+      CG->getOrInsertFunction(NewCS.getCalledFunction());
+  CallGraphNode *CallerNode = (*CG)[Caller];
+  if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
+        return CR.first == &OldCS;
+      }))
+    return false;
+  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
+  return true;
+}
+
+void CallGraphUpdater::removeCallSite(CallBase &CS) {
+  // This is only necessary in the (old) CG.
+  if (!CG)
+    return;
+
+  Function *Caller = CS.getCaller();
+  CallGraphNode *CallerNode = (*CG)[Caller];
+  CallerNode->removeCallEdgeFor(CS);
+}

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/SourceMgr.h"
+#include "llvm/Transforms/Utils/CallGraphUpdater.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 class TestModuleAnalysis : public AnalysisInfoMixin<TestModuleAnalysis> {
 public:

 
 struct LambdaSCCPassNoPreserve : public PassInfoMixin<LambdaSCCPassNoPreserve> {
   template <typename T>
   LambdaSCCPassNoPreserve(T &&Arg) : Func(std::forward<T>(Arg)) {}
 
   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     Func(C, AM, CG, UR);
-    return PreservedAnalyses::none();
+    PreservedAnalyses PA;
+    // We update the core CGSCC data structures and so can preserve the proxy to
+    // the function analysis manager.
+    PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+    return PA;
   }
 
   std::function<void(LazyCallGraph::SCC &, CGSCCAnalysisManager &,
                      LazyCallGraph &, CGSCCUpdateResult &)>
       Func;
 };
 
 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses0) {
ASSERT_DEATH(updateCGAndAnalysisManagerForFunctionPass(CG, C, FN, AM, UR),
                  "Any new calls should be modeled as");
   }));
 
   ModulePassManager MPM(/*DebugLogging*/ true);
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
   MPM.run(*M, MAM);
 }
 
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses4) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(f)")
+          return;
+
+        Function *FnF = M->getFunction("f");
+        Function *FnewF = Function::Create(FnF->getFunctionType(),
+                                           FnF->getLinkage(), "newF", *M);
+        BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
+        ReturnInst::Create(FnewF->getContext(), BB);
+
+        // Use the CallGraphUpdater to update the call graph for the new
+        // function.
+        CallGraphUpdater CGU;
+        CGU.initialize(CG, C, AM, UR);
+        CGU.registerOutlinedFunction(*FnewF);
+
+        // And insert a call to `newF`
+        Instruction *IP = &FnF->getEntryBlock().front();
+        (void)CallInst::Create(FnewF, {}, "", IP);
+
+        auto &FN = *llvm::find_if(
+            C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
+
+        ASSERT_NO_FATAL_FAILURE(
+            updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses5) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
+                                           CGSCCAnalysisManager &AM,
+                                           LazyCallGraph &CG,
+                                           CGSCCUpdateResult &UR) {
+    if (C.getName() != "(f)")
+      return;
+
+    Function *FnF = M->getFunction("f");
+    Function *FnewF =
+        Function::Create(FnF->getFunctionType(), FnF->getLinkage(), "newF", *M);
+    BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
+    ReturnInst::Create(FnewF->getContext(), BB);
+
+    // Use the CallGraphUpdater to update the call graph for the new
+    // function.
+    CallGraphUpdater CGU;
+    CGU.initialize(CG, C, AM, UR);
+    CGU.registerOutlinedFunction(*FnewF);
+
+    // And insert a call to `newF`
+    Instruction *IP = &FnF->getEntryBlock().front();
+    (void)CallInst::Create(FnewF, {}, "", IP);
+
+    auto &FN = *llvm::find_if(
+        C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
+
+    ASSERT_DEATH(updateCGAndAnalysisManagerForFunctionPass(CG, C, FN, AM, UR),
+                 "Any new calls should be modeled as");
+  }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses6) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(h3, h1, h2)")
+          return;
+
+        Function *FnX = M->getFunction("x");
+        Function *FnH1 = M->getFunction("h1");
+        Function *FnH2 = M->getFunction("h2");
+        Function *FnH3 = M->getFunction("h3");
+        ASSERT_NE(FnX, nullptr);
+        ASSERT_NE(FnH1, nullptr);
+        ASSERT_NE(FnH2, nullptr);
+        ASSERT_NE(FnH3, nullptr);
+
+        // And insert a call to `h1`, `h2`, and `h3`.
+        Instruction *IP = &FnH2->getEntryBlock().front();
+        (void)CallInst::Create(FnH1, {}, "", IP);
+        (void)CallInst::Create(FnH2, {}, "", IP);
+        (void)CallInst::Create(FnH3, {}, "", IP);
+
+        // Use the CallGraphUpdater to update the call graph for the new
+        // function.
+        CallGraphUpdater CGU;
+        CGU.initialize(CG, C, AM, UR);
+        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnH2));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses7) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(f)")
+          return;
+
+        Function *FnF = M->getFunction("f");
+        Function *FnH2 = M->getFunction("h2");
+        ASSERT_NE(FnF, nullptr);
+        ASSERT_NE(FnH2, nullptr);
+
+        // And insert a call to `h2`
+        Instruction *IP = &FnF->getEntryBlock().front();
+        (void)CallInst::Create(FnH2, {}, "", IP);
+
+        // Use the CallGraphUpdater to update the call graph for the new
+        // function.
+        CallGraphUpdater CGU;
+        CGU.initialize(CG, C, AM, UR);
+        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnF));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses8) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(f)")
+          return;
+
+        Function *FnF = M->getFunction("f");
+        Function *FnewF = Function::Create(FnF->getFunctionType(),
+                                           FnF->getLinkage(), "newF", *M);
+        BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
+        auto *RI = ReturnInst::Create(FnewF->getContext(), BB);
+        while (FnF->getEntryBlock().size() > 1)
+          FnF->getEntryBlock().front().moveBefore(RI);
+        ASSERT_NE(FnF, nullptr);
+
+        // Use the CallGraphUpdater to update the call graph.
+        CallGraphUpdater CGU;
+        CGU.initialize(CG, C, AM, UR);
+        ASSERT_NO_FATAL_FAILURE(CGU.replaceFunctionWith(*FnF, *FnewF));
+        ASSERT_TRUE(FnF->isDeclaration());
+        ASSERT_EQ(FnF->getNumUses(), 0U);
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses9) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(f)")
+          return;
+
+        Function *FnF = M->getFunction("f");
+
+        // Use the CallGraphUpdater to update the call graph.
+        {
+          CallGraphUpdater CGU;
+          CGU.initialize(CG, C, AM, UR);
+          ASSERT_NO_FATAL_FAILURE(CGU.removeFunction(*FnF));
+          ASSERT_EQ(M->getFunctionList().size(), 6U);
+        }
+        ASSERT_EQ(M->getFunctionList().size(), 5U);
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses10) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(h3, h1, h2)")
+          return;
+
+        Function *FnX = M->getFunction("x");
+        Function *FnH1 = M->getFunction("h1");
+        Function *FnH2 = M->getFunction("h2");
+        Function *FnH3 = M->getFunction("h3");
+        ASSERT_NE(FnX, nullptr);
+        ASSERT_NE(FnH1, nullptr);
+        ASSERT_NE(FnH2, nullptr);
+        ASSERT_NE(FnH3, nullptr);
+
+        // And insert a call to `h1`, and `h3`.
+        Instruction *IP = &FnH1->getEntryBlock().front();
+        (void)CallInst::Create(FnH1, {}, "", IP);
+        (void)CallInst::Create(FnH3, {}, "", IP);
+
+        // Remove the `h2` call.
+        ASSERT_TRUE(isa<CallBase>(IP));
+        ASSERT_EQ(cast<CallBase>(IP)->getCalledFunction(), FnH2);
+        IP->eraseFromParent();
+
+        // Use the CallGraphUpdater to update the call graph.
+        CallGraphUpdater CGU;
+        CGU.initialize(CG, C, AM, UR);
+        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnH1));
+        ASSERT_NO_FATAL_FAILURE(CGU.removeFunction(*FnH2));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
 #endif
 } // namespace

llvm/unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
+  TransformUtils
   )
 
 add_llvm_unittest(AnalysisTests
   AliasAnalysisTest.cpp
   AliasSetTrackerTest.cpp
   BasicAliasAnalysisTest.cpp
   BlockFrequencyInfoTest.cpp
   BranchProbabilityInfoTest.cpp

llvm/unittests/Analysis/LazyCallGraphTest.cpp

TEST(LazyCallGraphTest, BasicGraphMutation) {
 
   CG.removeEdge(C, C);
   EXPECT_EQ(0, std::distance(C->begin(), C->end()));
 
   CG.removeEdge(B, C);
   EXPECT_EQ(0, std::distance(B->begin(), B->end()));
 }
 
+TEST(LazyCallGraphTest, BasicGraphMutationOutlining) {
+  LLVMContext Context;
+  std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
+                                                     "entry:\n"
+                                                     "  call void @b()\n"
+                                                     "  call void @c()\n"
+                                                     "  ret void\n"
+                                                     "}\n"
+                                                     "define void @b() {\n"
+                                                     "entry:\n"
+                                                     "  ret void\n"
+                                                     "}\n"
+                                                     "define void @c() {\n"
+                                                     "entry:\n"
+                                                     "  ret void\n"
+                                                     "}\n");
+  LazyCallGraph CG = buildCG(*M);
+
+  LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c"));
+  A.populate();
+  B.populate();
+  C.populate();
+  CG.buildRefSCCs();
+
+  // Add a new function that is called from @b and verify it is in the same SCC.
+  Function &BFn = B.getFunction();
+  Function *NewFn =
+      Function::Create(BFn.getFunctionType(), BFn.getLinkage(), "NewFn", *M);
+  auto IP = BFn.getEntryBlock().getFirstInsertionPt();
+  CallInst::Create(NewFn, "", &*IP);
+  CG.addNewFunctionIntoSCC(*NewFn, *CG.lookupSCC(B));
+
+  EXPECT_EQ(CG.lookupSCC(A)->size(), 1U);
+  EXPECT_EQ(CG.lookupSCC(B)->size(), 2U);
+  EXPECT_EQ(CG.lookupSCC(C)->size(), 1U);
+  EXPECT_EQ(CG.lookupSCC(*CG.lookup(*NewFn))->size(), 2U);
+  EXPECT_EQ(CG.lookupSCC(*CG.lookup(*NewFn))->size(), CG.lookupSCC(B)->size());
+}
+
 TEST(LazyCallGraphTest, InnerSCCFormation) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
   LazyCallGraph CG = buildCG(*M);
 
   // Now mutate the graph to connect every node into a single RefSCC to ensure
   // that our inner SCC formation handles the rest.
   LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1"));

llvm/unittests/IR/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   Passes
+  TransformUtils
   )
 
 add_llvm_unittest(IRTests
   AsmWriterTest.cpp
   AttributesTest.cpp
   BasicBlockTest.cpp
   CFGBuilder.cpp
   ConstantRangeTest.cpp

llvm/unittests/IR/LegacyPassManagerTest.cpp

 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OptBisect.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/CallGraphUpdater.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace llvm {
   void initializeModuleNDMPass(PassRegistry&);
   void initializeFPassPass(PassRegistry&);
   void initializeCGPassPass(PassRegistry&);
Module *makeLLVMModule(LLVMContext &Context) {
         BranchInst::Create(label_bb1, label_return, int1_f, label_bb1);
 
         // Block return (label_return)
         ReturnInst::Create(Context, label_return);
       }
       return mod;
     }
 
+    struct CGModifierPass : public CGPass {
+      unsigned NumSCCs = 0;
+      unsigned NumFns = 0;
+      bool SetupWorked = true;
+
+      CallGraphUpdater CGU;
+
+      bool runOnSCC(CallGraphSCC &SCMM) override {
+        ++NumSCCs;
+        for (CallGraphNode *N : SCMM)
+          if (N->getFunction())
+            ++NumFns;
+
+        CGPass::run();
+
+        if (SCMM.size() <= 1)
+          return false;
+
+        CallGraphNode *N = *(SCMM.begin());
+        Function *F = N->getFunction();
+        Module *M = F->getParent();
+        Function *Test1F = M->getFunction("test1");
+        Function *Test2F = M->getFunction("test2");
+        Function *Test3F = M->getFunction("test3");
+        auto InSCC = [&](Function *Fn) {
+          return llvm::any_of(SCMM, [Fn](CallGraphNode *CGN) {
+            return CGN->getFunction() == Fn;
+          });
+        };
+
+        if (!Test1F || !Test2F || !Test3F || !InSCC(Test1F) || !InSCC(Test2F) ||
+            !InSCC(Test3F))
+          return SetupWorked = false;
+
+        CallInst *CI = dyn_cast<CallInst>(&Test1F->getEntryBlock().front());
+        if (!CI || CI->getCalledFunction() != Test2F)
+          return SetupWorked = false;
+
+        CI->setCalledFunction(Test3F);
+
+        CGU.initialize(const_cast<CallGraph &>(SCMM.getCallGraph()), SCMM);
+        CGU.removeFunction(*Test2F);
+        CGU.reanalyzeFunction(*Test1F);
+        return true;
+      }
+
+      bool doFinalization(CallGraph &CG) override { return CGU.finalize(); }
+    };
+
+    TEST(PassManager, CallGraphUpdater0) {
+      // SCC#1: test1->test2->test3->test1
+      // SCC#2: test4
+      // SCC#3: indirect call node
+
+      LLVMContext Context;
+      std::unique_ptr<Module> M(makeLLVMModule(Context));
+      ASSERT_EQ(M->getFunctionList().size(), 4U);
+      CGModifierPass *P = new CGModifierPass();
+      legacy::PassManager Passes;
+      Passes.add(P);
+      Passes.run(*M);
+      ASSERT_TRUE(P->SetupWorked);
+      ASSERT_EQ(P->NumSCCs, 3U);
+      ASSERT_EQ(P->NumFns, 4U);
+      ASSERT_EQ(M->getFunctionList().size(), 3U);
+    }
   }
 }
 
 INITIALIZE_PASS(ModuleNDM, "mndm", "mndm", false, false)
 INITIALIZE_PASS_BEGIN(CGPass, "cgp","cgp", false, false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_END(CGPass, "cgp","cgp", false, false)
 INITIALIZE_PASS(FPass, "fp","fp", false, false)
 INITIALIZE_PASS_BEGIN(LPass, "lp","lp", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(LPass, "lp","lp", false, false)