[llvm-dev] Advice on porting SCC pass 'coro-split' to the new pass manager?

[Brian Gesiak via llvm-dev]

Hi all!

I'm working on porting the LLVM passes for C++20 coroutines over to
the new pass manager infrastructure. Of the 4 passes, 3 are function
passes, and so porting them is straightforward and easy (my thanks to
those involved -- the design is great!). However, I'm struggling with
'coro-split', which is an SCC pass. Specifically, I'd like advice on
how to appropriately update the new pass manager's preferred
representation of the SCC: 'llvm::LazyCallGraph'.

Before I ask my specific questions about 'LazyCallGraph', it may help
to explain my understanding of the 'coro-split' pass and how it
modifies the call graph:

The coro-split pass "clones" coroutine functions. For example, for a
coroutine function 'foo', it creates declarations for 3 new functions
('foo.resume', 'foo.destroy', and 'foo.cleanup') using the static
member function 'llvm::Function::Create'. It then uses
'llvm::CloneFunctionInto' to copy the 'foo' function's attributes,
arguments, basic blocks, and instructions, into each of the 3 new
functions. Finally, the coro-split pass replaces the entry basic
blocks of the function to read a value from a global store of
coroutine state called the coroutine frame, and uses that value to
determine which part of the cloned coroutine function should be
executed upon "resumption" of the coroutine.

Of course, once the coro-split SCC pass has done all this, it must
update LLVM's representation of the call graph. It does so using ~40
lines of code that you may read here:
https://github.com/llvm/llvm-project/blob/890c6ef1fb/llvm/lib/Transforms/Coroutines/Coroutines.cpp#L186-L224

To explain my understanding of the code in the above link: the
coro-split pass completely re-initializes the 'CallGraphSCC' object,
using the member function
'CallGraphSCC::initialize(ArrayRef<CallGraphNode*>)'. The array of
nodes it uses to re-initialize the SCC includes nodes for each of the
3 new functions, which it adds to the call graph using
'CallGraph::getOrInsertFunction'. For each of the new nodes, and for
the node representing the original function, the coro-split pass
iterates over each of the instructions in the function, and uses
'CallGraphNode::addCalledFunction' to add edges to the call graph.

The difficulty I'm having here in porting coro-split to the new pass
manager is that its SCC passes use 'LazyCallGraph' and
'LazyCallGraph::SCC'. These classes' documentation explains that they
are designed with the constraint that optimization passes shall not
delete, remove, or add edges that invalidate a bottom-up traversal of
the SCC DAG. Unfortunately, I understand the coro-split pass to be
doing exactly those things.

As a result, if I attempt to mimic the coro-split pass's logic by
inserting functions into the call graph using 'LazyCallGraph::get',
and then adding call edges with
'LazyCallGraph::RefSCC::insertTrivialRefEdge' and
'LazyCallGraph::RefSCC::switchInternalEdgeToCall', I'm met with an
assertion: llvm/lib/Analysis/CGSCCPassManager.cpp:463: [...]:
Assertion `E && "No function transformations should introduce *new* "
"call edges! Any new calls should be modeled as " "promoted existing
ref edges!"' failed.

Does anyone have any suggestions on how I can better work within the
constraints of the 'LazyCallGraph'?

In case it helps, you can see the code that currently hits this
assertion here:
https://github.com/modocache/llvm-project/commit/02c10528e9. Of
particular interest may be the functions 'buildLazyCallGraphNode' and
'updateCallGraphAfterSplit'.

One idea a colleague of mine suggested was to have an earlier
coroutine function pass insert declarations of 'foo.resume',
'foo.destroy', and 'foo.cleanup', which we could then promote to call
edges. However, they also found this FIXME in CGSCCPassManager.cpp:
"We should really handle adding new calls. While it will make
downstream usage more complex, there is no fundamental limitation and
it will allow passes within the CGSCC to be a bit more flexible in
what transforms they can do. Until then, we verify that new calls
haven't been introduced."

As a result, I'm now unsure whether I ought to modify coro-split's
implementation for the new pass manager, or modify 'CGSCCPassManager'
to allow for the insertion of new calls. Any and all advice would be
greatly appreciated!

- Brian Gesiak