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

1593

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 ↗

(On Diff #242245)

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 ↗

(On Diff #244564)

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/lib/Analysis/LazyCallGraph.cpp

#endif
   SCC &TargetSCC = *G->lookupSCC(TargetN);
   assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "
                                                 "the same SCC to require the "
                                                 "full CG update.");
 
   // Set the edge kind.
   SourceN->setEdgeKind(TargetN, Edge::Ref);
 
-  // Otherwise we are removing a call edge from a single SCC. This may break
-  // the cycle. In order to compute the new set of SCCs, we need to do a small
+  // Otherwise, we are removing a call edge from a single SCC. This may break
+  // the cycle. However, one trivial case remains that we check for now: a
+  // node is always strongly connected to itself, so demoting an edge from a
+  // node to itself cannot break a cycle, and does not introduce any new SCCs.
+  if (&SourceN == &TargetN)
+    return range(iterator(), iterator());
+
+  // In order to compute the new set of SCCs, we need to do a small
   // DFS over the nodes within the SCC to form any sub-cycles that remain as
   // distinct SCCs and compute a postorder over the resulting SCCs.
   //
   // However, we specially handle the target node. The target node is known to
   // reach all other nodes in the original SCC by definition. This means that
   // we want the old SCC to be replaced with an SCC containing that node as it
   // will be the root of whatever SCC DAG results from the DFS. Assumptions
   // about an SCC such as the set of functions called will continue to hold,

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

CGPM.addPass(LambdaSCCPassNoPreserve(
         ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnF));
       }));
 
   ModulePassManager MPM(/*DebugLogging*/ true);
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
   MPM.run(*M, MAM);
 }
 
+TEST_F(CGSCCPassManagerTest, TestDemotionOfSelfReferentialCallEdge) {
+  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) {
+        CallGraphUpdater CGUpdater(CG, AM, 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;
+
+          // "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());
+
+          // Create a new function 'g' and use the CallGraphUpdater to insert
+          // a node for 'g' into the call graph. This also connects creates a
+          // ref edge 'f -> g'.
+          auto *G =
+              llvm::Function::Create(F.getFunctionType(), F.getLinkage(),
+                                     F.getAddressSpace(), "g", F.getParent());
+          llvm::BasicBlock::Create(F.getParent()->getContext(), "entry", G);
+          CGUpdater.registerOutlinedFunction(*G, &C);
+
+          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