[RFC] Coroutines passes in the new pass manager

Hello all,

It's been a month since my previous email on the topic, and since then
I've done some initial work on porting the coroutines passes to the
new pass manager. In total there are 6 patches -- that's a lot to
review, so allow me to introduce the changes being made in each of
them.

# What's finished

In these first 6 patches, I focused on lowering coroutine intrinsics
correctly. With the patches applied, Clang is able to successfully use
the new pass manager to build and test a major open source C++20
coroutines library, https://github.com/lewissbaker/cppcoro.

1. https://reviews.llvm.org/D71898
New pass manager implementation of the coro-early function pass, with
LLVM regression tests for this pass updated to test both the new and
legacy implementations.

2. ⚙ D71899 [Coroutines][2/6] New pass manager: coro-split
Same thing, but for coro-split CGSCC pass. This patch adds support to
the new pass manager for only the C++20 switch-based coroutines ABI.
I'd like to implement support for the Swift returned-continuation ABI
in a future patch.

3. ⚙ D71900 [Coroutines][3/6] New pass manager: coro-elide
4. ⚙ D71901 [Coroutines][4/6] New pass manager: coro-cleanup
Same thing, but for the coro-elide and coro-cleanup function passes.

5. ⚙ D71902 [Coroutines][5/6] Add coroutine passes to pipeline
The first 4 patches allow users to run coroutine passes by invoking,
for example 'opt -passes=coro-early'. However, most of LLVM's tests
for coroutines use 'opt -enable-coroutines', which adds all 4
coroutines passes, in the correct order, to the pass pipeline. This
5th patch adds a similar feature but in a way that can be used by the
new pass manager: a pipeline parser that understands 'opt
-passes=coroutines'.

6. https://reviews.llvm.org/D71903
Finally, this patch modifies Clang to run the new coroutine passes
when the experimental pass manager is being used with coroutines
enabled (either via '-fcoroutines-ts' or '-std=c++2a'). With all 6
patches applied, the cppcoro library builds and tests successfully
with a Clang built with 'ENABLE_EXPERIMENTAL_NEW_PASS_MANAGER=On'.

# What's yet to be done: Swift "returned-continuation" coroutines &
the "devirtualization trigger"

Two things are missing from these initial 6 patches: the first is, as
I mentioned above, support for returned-continuation coroutines, which
are used by Swift. I think this will be fairly straightforward for me
(or others, if interested) to add in an upcoming patch.

The second missing feature has to do with how CGSCC passes are re-run
by the pass manager infrastructure.

The legacy coro-split and coro-elide passes work in tandem: the
coro-split pass first introduces an indirect call to a dummy
"devirtualization trigger" function, and then the coro-elide pass
devirtualizes it. The legacy CGSCC pass manager checks for
devirtualizations after each pass and, if any occur, it re-runs the
CGSCC pass pipeline. In other words: coro-split is run, a check is
made for devirtualization, then coro-elide is run, and another check
is made.

The new pass manager allows for a series of CGSCC passes to be wrapped
in a DevirtSCCRepeatedPass, but this only checks for devirtualizations
after all passes are run. In the case of coro-split and coro-elide,
the indirect function call is added and then devirtualized within a
single pass of the repeater, so DevirtSCCRepeatedPass never sees the
devirtualization and thus doesn't perform a repeat iteration. In other
words: a check is made, coro-split is run and it adds an indirect
call, coro-elide is run and it devirtualizes that call, and then
another check is made. From the repeater pass's point of view, nothing
has changed.

This is something I'd like to tweak in future patches (my thinking is
to add a member to CGSCCUpdateResult to allow passes to manually
inform the pass manager about devirtualizations, but I'm very open to
alternative ideas). But for now, I simply have Clang manually schedule
two iterations of the coro-split pass, rather than have it rely on the
repeater detecting a devirtualization and automatically scheduling
another coro-split iteration. As a result, the new pass manager
implementation of coroutines realizes correct program behavior, but
fails to realize some of the optimization patterns that are tested for
in the regression tests in 'llvm/test/Transforms/Coroutines'.

I'd greatly appreciate code review on my patches! Or, please reply
here with any questions/comments.

- Brian Gesiak

Hey all,

Thanks to reviews by Wenlei He and JunMa (junparser), I have a stack
of patches that implement the C++20 coroutine transformations in the
new LLVM pass manager. The stack builds and optimizes coroutines in
major open source coroutine libraries like
http://github.com/lewissbaker/cppcoro. I also use the patches in my
employer's downstream fork of LLVM/Clang, and it successfully compiles
large C++ codebases that make use of C++17 and coroutines.

The coroutine patches exist as a stack of 6 Phabricator revisions [1].
Crucially, they make use of 3 patches related to LazyCallGraph, the
call graph representation used by the new pass manager:

1. https://reviews.llvm.org/D72025 (by Johannes Doerfert)
2. https://reviews.llvm.org/D70927 (ditto)
3. https://reviews.llvm.org/D72226 (this one by me)

I only have moderate experience using the new pass manager, so I'd
greatly appreciate a review of these patches. My coroutine patches
rely on the interfaces they add to the LazyCallGraph abstraction.
Could someone chime in with whether those interfaces could be merged
to trunk?

- Brian Gesiak

[1] Sequentially, https://reviews.llvm.org/D71898 through
https://reviews.llvm.org/D71903. Reviews are welcome here as well!

CCing Chandler and Fedor for feedback on the new pass manager.

    Hey all,
    
    Thanks to reviews by Wenlei He and JunMa (junparser), I have a stack
    of patches that implement the C++20 coroutine transformations in the
    new LLVM pass manager. The stack builds and optimizes coroutines in
    major open source coroutine libraries like
    http://github.com/lewissbaker/cppcoro. I also use the patches in my
    employer's downstream fork of LLVM/Clang, and it successfully compiles
    large C++ codebases that make use of C++17 and coroutines.
    
    The coroutine patches exist as a stack of 6 Phabricator revisions [1].
    Crucially, they make use of 3 patches related to LazyCallGraph, the
    call graph representation used by the new pass manager:
    
    1. https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D72025&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=kpLjtimhsMhNjVPLzvuD8eGmq-jcSv20Uju_AdarTTE&e= (by Johannes Doerfert)
    2. https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D70927&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=XRnY-8Zn_EoSKY6Wu5mmuDVf8TKU07Au19I4L2dt1kU&e= (ditto)
    3. https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D72226&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=P08bstAo5XXdmeDExMssmt7dU_favQOQ2k634si0BC0&e= (this one by me)
    
    I only have moderate experience using the new pass manager, so I'd
    greatly appreciate a review of these patches. My coroutine patches
    rely on the interfaces they add to the LazyCallGraph abstraction.
    Could someone chime in with whether those interfaces could be merged
    to trunk?
    
    - Brian Gesiak
    
    [1] Sequentially, https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D71898&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=lxA19e74ycegcH6AbWGuBs13m5WDDqf5TPcTAmYCYNs&e= through
    https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D71903&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=xKsheT47ZKP7XdEGNXzQeNCRsCNoZYmKFXAZjYsgkfU&e= . Reviews are welcome here as well!

Also CCing Philip Pfaffe.

    CCing Chandler and Fedor for feedback on the new pass manager.
    
        Hey all,
        
        Thanks to reviews by Wenlei He and JunMa (junparser), I have a stack
        of patches that implement the C++20 coroutine transformations in the
        new LLVM pass manager. The stack builds and optimizes coroutines in
        major open source coroutine libraries like
        http://github.com/lewissbaker/cppcoro. I also use the patches in my
        employer's downstream fork of LLVM/Clang, and it successfully compiles
        large C++ codebases that make use of C++17 and coroutines.
        
        The coroutine patches exist as a stack of 6 Phabricator revisions [1].
        Crucially, they make use of 3 patches related to LazyCallGraph, the
        call graph representation used by the new pass manager:
        
        1. https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D72025&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=kpLjtimhsMhNjVPLzvuD8eGmq-jcSv20Uju_AdarTTE&e= (by Johannes Doerfert)
        2. https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D70927&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=XRnY-8Zn_EoSKY6Wu5mmuDVf8TKU07Au19I4L2dt1kU&e= (ditto)
        3. https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D72226&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=P08bstAo5XXdmeDExMssmt7dU_favQOQ2k634si0BC0&e= (this one by me)
        
        I only have moderate experience using the new pass manager, so I'd
        greatly appreciate a review of these patches. My coroutine patches
        rely on the interfaces they add to the LazyCallGraph abstraction.
        Could someone chime in with whether those interfaces could be merged
        to trunk?
        
        - Brian Gesiak
        
        [1] Sequentially, https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D71898&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=lxA19e74ycegcH6AbWGuBs13m5WDDqf5TPcTAmYCYNs&e= through
        https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D71903&d=DwIGaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=o3kDXzdBUE3ljQXKeTWOMw&m=7kZTN83WVu9bhfqIZtRR15pR0tbwTrUmjZ3Ajjfa9wY&s=xKsheT47ZKP7XdEGNXzQeNCRsCNoZYmKFXAZjYsgkfU&e= . Reviews are welcome here as well!