Add LazyCallGraph API to add function to RefSCC

[modocache]

Summary

Depends on https://reviews.llvm.org/D70927.

LazyCallGraph::addNewFunctionIntoSCC allows users to insert a new
function node into a call graph, into a specific, existing SCC.

Extend this interface such that functions can be added even when they do
not belong in any existing SCC, but instead in a new SCC within an
existing RefSCC.

The ability to insert new functions as part of a RefSCC is necessary for
outlined functions that do not form a strongly connected cycle with the
function they are outlined from. An example of such a function would be the
coroutine funclets 'f.resume', etc., which are outlined from a coroutine 'f'.
Coroutine 'f' only references the funclets' addresses, it does not call
them directly.

[wenlei]

The short-circuit change makes sense to me. But what caused the creation of extra SCCs due to self-recursion? Is that because of the short-cut from line 808-825 and the clearing of SCC stack and DFS stack broke the LowLink and DFSNumber check of later Tarjan DFS?

Since this fix targets self-recursion specifically, just wanted to make sure the underlying issue doesn't go beyond self-recursion. Specifically, will we (incorrectly) create extra SCC if we have an indirect recursion/cycle from that target node, and we get caught by line 808-825 before every node in the original SCC is visited and placed on PendingSCCStack..

[modocache]

Yeah, very good questions. When I was writing this patch, I was focused more on getting my specific use case, the one covered by the unit test, to work without hitting an assert. (I also think this is potentially a performance optimization, but I haven't measured in any meaningful way.) But I'm also curious why this occurs, and will look into it a little more. I'd ideally like to get a unit test case that demonstrates the issue without being based on top of D70927, but I wasn't able to in this first iteration of the patch.

[modocache]

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

1624

I think I see the issue.

First of all, this comment is incorrect: CallGraphUpdater::registerOutlinedFunction doesn't automatically add any edges between f and g, that's up to the user to do themself -- it doesn't create a reference edge, a call edge, it doesn't create anything.

Here I'm inserting g into the same SCC as f, but for that to be a valid SCC to insert into, f and g need to be part of the same strongly-connected component, meaning a call edge path exists connecting f *-> g and g *-> f. (For typical "outlining" of a part of the body of f into some outlined function, a call edge path from f *-> g would almost certainly exist.)

However, in the case of coroutine funclets, there is only a ref edge f -> g. And in this example, there's not even a ref edge f -> g`.

So this is user error: I shouldn't be inserting f into g, I ought to instead create an SCC especially for g. If I do so, then later when the call graph is updated to handle the demotion of f -> f from a call edge to a ref edge, the DFS walk won't find a new SCC (g), and incorporateNewSCCRange won't be called with ranges [(g), (f)] for f.

That's my theory, anyway. If I end up being right, I'll probably end up abandoning this change and changing D71899 slightly.

[modocache]

I updated this patch such that it can address the underlying problem encountered by the coro-split pass in D71899: we need a method of inserting new ref edges into an existing call graph, whereas currently the CallGraphUpdater only allows the insertion of call edges. I don't know if there's any use for such an API in the old CallGraph, so I left that unimplemented. I also considered simply adding this functionality as a member function on LazyCallGraph or one of its inner classes, but decided to reuse CallGraphUpdater in order to share some of the logic.

[modocache]

Update fields in Phabricator.

[modocache]

Remove the now unneeded check for self-referential edges.

[modocache]

Sorry for the noise -- this undo's a comment change.

[modocache]

Add documentation for the new member function.

[modocache]

Rebase onto the latest revision of D70927.

[modocache]

Update based on @jdoerfert's latest version of revision D70927. Previous versions added a public member function to CallGraphUpdater, the latest versions instead add a public member function to LazyCallGraph. This update does the same, it moves the new member function, from CallGraphUpdater::registerReferredToOutlinedFunction, to LazyCallGraph::addNewFunctionIntoRefSCC.

[modocache]

Now that the underlying D70927 has been committed, this diff needs a code review. I'll add @hfinkel since he left some helpful review comments on D70927.

[jdoerfert]

You don't have a CallGraphUpdater interface for this. Is this on purpose? (The test mentions CallGraphUpdater still).

llvm/include/llvm/Analysis/LazyCallGraph.h

1064

You have to specify that the node will form a new SCC inside of \p RC

[modocache]

Thanks, @jdoerfert! As per your suggestions I updated the docblock and the test comments, and I added a test specifically for LazyCallGraph. Built and tested everything with ASAN and it passes.

[jdoerfert]

LGTM.

llvm/include/llvm/Analysis/LazyCallGraph.h

1065

Nit: -completely

[modocache]

Thanks for the reviews, @jdoerfert! I addressed your comment by removing the redundant 'completely'. I'll commit this in a few minutes.

llvm/include/llvm/Analysis/LazyCallGraph.h

#endif
   /// 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);
 
+  /// Introduce a node for the function \p NewF, as a single node in a
+  /// new SCC, in the RefSCC \p RC.
+  void addNewFunctionIntoRefSCC(Function &NewF, RefSCC &RC);
+
   ///@}
 
   ///@{
   /// \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.
private:
 
   /// Helper to insert a new function, with an already looked-up entry in
   /// the NodeMap.
   Node &insertInto(Function &F, Node *&MappedN);
 
   /// Helper to update pointers back to the graph object during moves.
   void updateGraphPtrs();
 
+  /// Helper to insert a new function, add it to the NodeMap, and populate its
+  /// node.
+  Node &createNode(Function &F);
+
+  /// Helper to add the given Node \p N to the SCCMap, mapped to the SCC \p C.
+  void addNodeToSCC(SCC &C, Node &N);
+
   /// Allocates an SCC and constructs it using the graph allocator.
   ///
   /// The arguments are forwarded to the constructor.
   template <typename... Ts> SCC *createSCC(Ts &&... Args) {
     return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...);
   }
 
   /// Allocates a RefSCC and constructs it using the graph allocator.

llvm/lib/Analysis/LazyCallGraph.cpp

void LazyCallGraph::removeDeadFunction(Function &F) {
   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;
+  addNodeToSCC(C, createNode(NewF));
+}
+
+void LazyCallGraph::addNewFunctionIntoRefSCC(Function &NewF, RefSCC &RC) {
+  Node &N = createNode(NewF);
+
+  auto *C = createSCC(RC, SmallVector<Node *, 1>());
+  addNodeToSCC(*C, N);
+
+  RC.SCCIndices[C] = RC.SCCIndices.size();
+  RC.SCCs.push_back(C);
 }
 
 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)
     FunctionNodePair.second->G = this;
 
   for (auto *RC : PostOrderRefSCCs)
     RC->G = this;
 }
 
+LazyCallGraph::Node &LazyCallGraph::createNode(Function &F) {
+  assert(!lookup(F) && "node already exists");
+
+  Node &N = get(F);
+  NodeMap[&F] = &N;
+  N.DFSNumber = N.LowLink = -1;
+  N.populate();
+  return N;
+}
+
+void LazyCallGraph::addNodeToSCC(LazyCallGraph::SCC &C, Node &N) {
+  C.Nodes.push_back(&N);
+  SCCMap[&N] = &C;
+}
+
 template <typename RootsT, typename GetBeginT, typename GetEndT,
           typename GetNodeT, typename FormSCCCallbackT>
 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
                                      GetEndT &&GetEnd, GetNodeT &&GetNode,
                                      FormSCCCallbackT &&FormSCC) {
   using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
 
   SmallVector<std::pair<Node *, EdgeItT>, 16> DFSStack;

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

CGPM.addPass(LambdaSCCPassNoPreserve(
         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");
CGPM.addPass(LambdaSCCPassNoPreserve(
         ASSERT_NO_FATAL_FAILURE(CGU.removeFunction(*FnH2));
       }));
 
   ModulePassManager MPM(/*DebugLogging*/ true);
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
   MPM.run(*M, MAM);
 }
 
+TEST_F(CGSCCPassManagerTest, TestInsertionOfNewRefSCC) {
+  std::unique_ptr<Module> M = parseIR("define void @f() {\n"
+                                      "entry:\n"
+                                      "  call void @f()\n"
+                                      "  ret void\n"
+                                      "}\n");
+
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        for (auto &N : C) {
+          auto &F = N.getFunction();
+          if (F.getName() != "f")
+            continue;
+          auto *Call = dyn_cast<CallInst>(F.begin()->begin());
+          if (!Call || Call->getCalledFunction()->getName() != "f")
+            continue;
+
+          // Create a new function 'g'.
+          auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
+                                     F.getAddressSpace(), "g", F.getParent());
+          BasicBlock::Create(F.getParent()->getContext(), "entry", G);
+          // Instruct the LazyCallGraph to create a new node for 'g', as the
+          // single node in a new SCC, into the call graph. As a result
+          // the call graph is composed of a single RefSCC with two SCCs:
+          // [(f), (g)].
+          CG.addNewFunctionIntoRefSCC(*G, C.getOuterRefSCC());
+
+          // "Demote" the 'f -> f' call egde to a ref edge.
+          // 1. Erase the call edge from 'f' to 'f'.
+          Call->eraseFromParent();
+          // 2. Insert a ref edge from 'f' to 'f'.
+          (void)CastInst::CreatePointerCast(&F,
+                                            Type::getInt8PtrTy(F.getContext()),
+                                            "f.ref", &*F.begin()->begin());
+
+          ASSERT_NO_FATAL_FAILURE(
+              updateCGAndAnalysisManagerForCGSCCPass(CG, C, N, AM, UR))
+              << "Updating the call graph with a demoted, self-referential "
+                 "call edge 'f -> f', and a newly inserted ref edge 'f -> g', "
+                 "caused a fatal failure";
+        }
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
 #endif
 } // namespace

llvm/unittests/Analysis/LazyCallGraphTest.cpp

TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) {
 
   // The only observable change should be that the RefSCC is gone from the
   // postorder sequence.
   I = CG.postorder_ref_scc_begin();
   EXPECT_EQ(&RC1, &*I++);
   EXPECT_EQ(&RC2, &*I++);
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 }
+
+TEST(LazyCallGraphTest, AddNewFunctionIntoRefSCC) {
+  LLVMContext Context;
+  // Build and populate a graph composed of a single, self-referential node.
+  std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
+                                                     "entry:\n"
+                                                     "  call void @f()\n"
+                                                     "  ret void\n"
+                                                     "}\n");
+  LazyCallGraph CG = buildCG(*M);
+  CG.buildRefSCCs();
+
+  // At this point 'f' is in the call graph.
+  auto &F = lookupFunction(*M, "f");
+  LazyCallGraph::Node *FN = CG.lookup(F);
+  EXPECT_NE(FN, nullptr);
+
+  // And it has an SCC, of course.
+  auto *FSCC = CG.lookupSCC(*FN);
+  EXPECT_NE(FSCC, nullptr);
+
+  // Now, create a new function 'g'.
+  auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
+                             F.getAddressSpace(), "g", F.getParent());
+  BasicBlock::Create(F.getParent()->getContext(), "entry", G);
+
+  // Instruct the LazyCallGraph to create a new node for 'g', within the same
+  // RefSCC as 'f', but in a separate SCC.
+  CG.addNewFunctionIntoRefSCC(*G, FSCC->getOuterRefSCC());
+
+  // 'g' should now be in the call graph.
+  LazyCallGraph::Node *GN = CG.lookup(*G);
+  EXPECT_NE(GN, nullptr);
+  // 'g' should have an SCC, composed of the singular node 'g'.
+  // ('f' should not be included in the 'g' SCC.)
+  LazyCallGraph::SCC *GSCC = CG.lookupSCC(*GN);
+  EXPECT_NE(GSCC, nullptr);
+  EXPECT_EQ(GSCC->size(), 1);
+  EXPECT_NE(GSCC, FSCC);
+  // 'g' and 'f' should be part of the same RefSCC.
+  EXPECT_EQ(&GSCC->getOuterRefSCC(), &FSCC->getOuterRefSCC());
+}
 }