[CGSCC][NewPM] Fix adding mutually recursive new functions

[aeubanks]

Summary

When adding a new function via addNewFunctionIntoRefSCC(), it creates a
new node and immediately populates the edges. Since populateSlow() calls
G->get() on all referenced functions, it will create a node (but not
populate it) for functions that haven't yet been added. If we add two
mutually recursive functions, the assert that the node should never have
been created will fire when the second function is added. So here we
remove that assert since the node may have already been created (but not
yet populated).

createNode() is only called from addNewFunctionInto{,Ref}SCC().

https://bugs.llvm.org/show_bug.cgi?id=47502

[jdoerfert]

Does it make sense to copy the unit test and keep the original one as well?

[aeubanks]

separate test into its own

[jdoerfert]

llvm/lib/Analysis/LazyCallGraph.cpp

1599

If lookup succeeds, should we just return the result or does it make sense to re-populate etc? We could call this getOrCreateNode?

[aeubanks]

llvm/lib/Analysis/LazyCallGraph.cpp

1599

get() will create a node but not populate it. In the adding mutually recursive functions case, we will have called get() on a new function, creating a new node, but not populate it. Then when we add the second function, the corresponding node will exist but not be populated, so it needs to be populated then.

So I think the current name still makes sense, it's "creating" a node in the sense that it populates it, although the node may have already been allocated. Open to suggestion though.

[jdoerfert]

LGTM

[asbirlea]

I'd like to revisit this and open a discussion. The createNode is only called in addNewFunctionIntoSCC and addNewFunctionIntoRefSCC, where the former is only called in unit tests and the latter is only used by co-routines. I'm trying to understand what the expected changes in the CallGraph are for some of these methods, if this is specific to coroutines or there are other usecases and if we can get better testing.
Is registerOutlinedFunction used out-of tree?

@jdoerfert, @modocache: Could you help me with some context please? (I'm happy to use llvm-dev@ for the discussion too.)

[jdoerfert]

In D87623#2275540, @asbirlea wrote:

I'd like to revisit this and open a discussion.

Sure. I assume we don't need to revert the patch but we can start a discussion with no pressure, right?

The createNode is only called in addNewFunctionIntoSCC and addNewFunctionIntoRefSCC, where the former is only called in unit tests and the latter is only used by co-routines. I'm trying to understand what the expected changes in the CallGraph are for some of these methods, if this is specific to coroutines or there are other usecases and if we can get better testing.
Is registerOutlinedFunction used out-of tree?

Except the Attributor and coroutines there is no user of the CallGraphUpdater (I know of).
The Attributor does not yet use this function but it is not unreasonable to expect it will be used.
There is a good chance the "shallow wrapper" functionality should actually do so, though that feature is on its own not the most useful anyway.

@jdoerfert, @modocache: Could you help me with some context please? (I'm happy to use llvm-dev@ for the discussion too.)

I'm fine with LLVM-dev, TBH I need to talk about updating the LazyCallGraph soon anyway. I think the current &updateCGAndAnalysisManagerForCGSCCPass in conjunction with the ::run method don't allow you to delete more than one function from the SCC at a time, which is bad. I might simply use it wrong but whatever it is, I'm all for a discussion on how we expose new PM CGSCC updates :) [= how we properly replace/implement something like the CallGraphUpdater]

[asbirlea]

In D87623#2275615, @jdoerfert wrote:

In D87623#2275540, @asbirlea wrote:

I'd like to revisit this and open a discussion.

Sure. I assume we don't need to revert the patch but we can start a discussion with no pressure, right?

Yes, exactly. The status before this patch was broken anyway, no sense reverting. I'm looking to understand whether there are ways to improve the infrastructure/APIs.

The createNode is only called in addNewFunctionIntoSCC and addNewFunctionIntoRefSCC, where the former is only called in unit tests and the latter is only used by co-routines. I'm trying to understand what the expected changes in the CallGraph are for some of these methods, if this is specific to coroutines or there are other usecases and if we can get better testing.
Is registerOutlinedFunction used out-of tree?

Except the Attributor and coroutines there is no user of the CallGraphUpdater (I know of).
The Attributor does not yet use this function but it is not unreasonable to expect it will be used.
There is a good chance the "shallow wrapper" functionality should actually do so, though that feature is on its own not the most useful anyway.

@jdoerfert, @modocache: Could you help me with some context please? (I'm happy to use llvm-dev@ for the discussion too.)

I'm fine with LLVM-dev, TBH I need to talk about updating the LazyCallGraph soon anyway. I think the current &updateCGAndAnalysisManagerForCGSCCPass in conjunction with the ::run method don't allow you to delete more than one function from the SCC at a time, which is bad. I might simply use it wrong but whatever it is, I'm all for a discussion on how we expose new PM CGSCC updates :) [= how we properly replace/implement something like the CallGraphUpdater]

SG, let's move the discussion to llvm-dev.
My goal for now is to understand the uses and desired updates, so the APIs doing the updates can be dedicated to those updates. For example, I'm not clear that the update used for the cloned functions in coroutines should be the same as for outlining, but perhaps a common API is the right approach. I don't have enough info at this point, and there aren't any uses for the outlining case that I can see.

[jdoerfert]

We have quite a few "outlining" passes but most are module passes I suppose.
Assuming we want to work towards CGSCC passes, and maybe, maybe parallelize them at some point, we should allow proper updates of the CG.

I am reasonably certain we will soonish look at integrating functionality that will subsume hot-cold splitting into the Attributor. At that point we will do real "outlining". Other use cases are certainly not unreasonable. What I try to say is that CoroSplit is probably not the only user of outlining.

[asbirlea]

In D87623#2275657, @jdoerfert wrote:

We have quite a few "outlining" passes but most are module passes I suppose.
Assuming we want to work towards CGSCC passes, and maybe, maybe parallelize them at some point, we should allow proper updates of the CG.

I am reasonably certain we will soonish look at integrating functionality that will subsume hot-cold splitting into the Attributor. At that point we will do real "outlining". Other use cases are certainly not unreasonable. What I try to say is that CoroSplit is probably not the only user of outlining.

Sounds great, that's exactly what I'd like to understand as use cases :-).

[aeubanks]

When I was looking into the history of these functions, I also felt like I was missing some background.

Also, I'm running into an issue where the newly added functions aren't having passes run on them. It seems like new call edges to outlined functions should be handled in updateCGAndAnalysisManagerForPass() and the addNewFunctionInto*SCC() shouldn't be necessary. In fact, there are a couple TODOs there about allowing more than just new trivial call/ref edges. Looking into that now.

llvm/lib/Analysis/LazyCallGraph.cpp

void LazyCallGraph::updateGraphPtrs() {
   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) {

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

CGPM.addPass(LambdaSCCPassNoPreserve(
         }
       }));
 
   ModulePassManager MPM(/*DebugLogging*/ true);
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
   MPM.run(*M, MAM);
 }
 
+TEST_F(CGSCCPassManagerTest, TestInsertionOfNewRefSCCMutuallyRecursive) {
+  std::unique_ptr<Module> M = parseIR("define void @f() {\n"
+                                      "entry:\n"
+                                      "  ret void\n"
+                                      "}\n");
+
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
+                                           CGSCCAnalysisManager &AM,
+                                           LazyCallGraph &CG,
+                                           CGSCCUpdateResult &UR) {
+    auto &FAM =
+        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
+
+    for (auto &N : C) {
+      auto &F = N.getFunction();
+      if (F.getName() != "f")
+        continue;
+
+      // Create mutually recursive functions (ref only) 'h1' and 'h2'.
+      auto *H1 = Function::Create(F.getFunctionType(), F.getLinkage(),
+                                  F.getAddressSpace(), "h1", F.getParent());
+      auto *H2 = Function::Create(F.getFunctionType(), F.getLinkage(),
+                                  F.getAddressSpace(), "h2", F.getParent());
+      BasicBlock *H1BB =
+          BasicBlock::Create(F.getParent()->getContext(), "entry", H1);
+      BasicBlock *H2BB =
+          BasicBlock::Create(F.getParent()->getContext(), "entry", H2);
+      (void)CastInst::CreatePointerCast(H2, Type::getInt8PtrTy(F.getContext()),
+                                        "h2.ref", H1BB);
+      (void)ReturnInst::Create(H1->getContext(), H1BB);
+      (void)CastInst::CreatePointerCast(H1, Type::getInt8PtrTy(F.getContext()),
+                                        "h1.ref", H2BB);
+      (void)ReturnInst::Create(H2->getContext(), H2BB);
+
+      // Add 'f -> h1' ref edge.
+      (void)CastInst::CreatePointerCast(H1, Type::getInt8PtrTy(F.getContext()),
+                                        "h.ref", &F.getEntryBlock().front());
+
+      CG.addNewFunctionIntoRefSCC(*H1, C.getOuterRefSCC());
+      CG.addNewFunctionIntoRefSCC(*H2, C.getOuterRefSCC());
+
+      ASSERT_NO_FATAL_FAILURE(
+          updateCGAndAnalysisManagerForCGSCCPass(CG, C, N, AM, UR, FAM))
+          << "Updating the call graph with a demoted, self-referential "
+             "call edge 'f -> f', a newly inserted ref edge 'f -> g', and "
+             "mutually recursive h1 <-> h2 caused a fatal failure";
+    }
+  }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
 #endif
 } // namespace