<div dir="ltr">Sorry for the novice question, but how are coroutines lowered in the backend? It requires making operating system calls to something like pthreads right?</div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jun 8, 2016 at 11:57 PM, Gor Nishanov via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all:<br>
<br>
Below is a proposal to add experimental coroutine support to LLVM. Though this<br>
proposal is motivated primarily by the desire to support C++ Coroutines [1],<br>
the llvm representation is language neutral and can be used to support<br>
coroutines in other languages as well.<br>
<br>
Clang + llvm coroutines allows you to take this code:<br>
<br>
generator<int> range(int from, int to) {<br>
for(int i = from; i < to; ++n)<br>
co_yield i;<br>
}<br>
int main() {<br>
int sum = 0;<br>
for (auto v: range(1,100))<br>
sum += v;<br>
return sum;<br>
}<br>
<br>
And translate it down to this:<br>
<br>
define i32 @main() #5 {<br>
entry:<br>
ret i32 4950<br>
}<br>
<br>
I prototyped llvm changes to support this proposal and extended clang coroutine<br>
implementation [2] to emit proposed intrinsics to smoke test the proposed<br>
design and to get simple generator and async task style coroutines working.<br>
See "More Attention Required" in the doc/Coroutines.rst for details on what<br>
addition work is required beyond cleanup and bug fixes.<br>
<br>
I would like to start the discussion on the overall design, representation and<br>
a roadmap to start upstreaming the changes with the intention to continue the<br>
development in-tree incrementally.<br>
<br>
Roadmap:<br>
--------<br>
1) Get agreement on coroutine representation and overall direction (this mail).<br>
.. repeat 1) until happy<br>
2) Get agreement on how coroutine transformation passes integrate into the<br>
optimizer pipeline.<br>
.. repeat 2) until happy<br>
3) update IR/Intrinsics.td + doc/Coroutines.rst + doc/index.rst<br>
4) trickle in coroutine transformation passes + tests in digestible chunks.<br>
5) get clang changes in (sometime after step 3).<br>
6) fix bugs / remove limitations / add functionality to coroutine passes<br>
.. repeat 6) until happy<br>
<br>
Background<br>
==========<br>
Coroutine representation is the result of several offline discussions<br>
with Richard Smith,<br>
Reid Kleckner, and David Majnemer. All of the good came from the<br>
collective effort.<br>
All the yuckiness was sneaked in by me after those discussions.<br>
<br>
I'll start with a quick overview.<br>
<br>
LLVM coroutines are functions that have one or more `suspend points`.<br>
When a suspend point is reached, the execution of a coroutine is suspended and<br>
control is returned back to its caller. A suspended coroutine can be resumed<br>
to continue execution from the last suspend point or be destroyed.<br>
<br>
In the following example, function `f` (which may or may not be a<br>
coroutine itself)<br>
returns a handle to a suspended coroutine (**coroutine handle**) that is used<br>
by `main` to resume the coroutine twice and then destroy it:<br>
<br>
.. code-block:: llvm<br>
<br>
define i32 @main() {<br>
entry:<br>
%hdl = call i8* @f(i32 4)<br>
call void @llvm.experimental.coro.resume(i8* %hdl)<br>
call void @llvm.experimental.coro.resume(i8* %hdl)<br>
call void @llvm.experimental.coro.destroy(i8* %hdl)<br>
ret i32 0<br>
}<br>
<br>
In addition to the function stack frame which exists when a coroutine<br>
is executing,<br>
there is an additional region of storage that contains values that keep the<br>
coroutine state when a coroutine is suspended. This region of storage<br>
is called **coroutine frame**. It is created when a coroutine is called. It is<br>
destroyed when a coroutine runs to completion or destroyed by a call to<br>
the `coro.destroy`_ intrinsic. Unlike stackful coroutines [3] which maintains a<br>
stack per coroutine, an llvm coroutine frame only contains the values that need<br>
to persist across suspend points (there is a path from a use to the definition<br>
that crosses a suspend point).<br>
<br>
Overall idea is that a coroutine is presented to an llvm as an ordinary function<br>
with suspension points marked up with intrinsics. We let the optimizer party<br>
on the coroutine for awhile. Shortly before the coroutine is eligible to be<br>
inlined into its callers, we outline parts of the coroutine that correspond to<br>
the code that needs to get executed after the coroutine is resumed or destroyed.<br>
The coroutine resumption intrinsics get replaced with direct calls to those<br>
outlined functions where possible. Then inliner can inline much leaner and nicer<br>
coroutine or any of the outlined parts as desired.<br>
<br>
If we discover that the lifetime of a coroutine is fully enclosed in<br>
the lifetime<br>
of the caller, we remove dynamic allocation for coroutine frame and replace it<br>
with an `alloca` on the caller's frame.<br>
<br>
Please see doc/Coroutines.rst for more details:<br>
<br>
doc/Coroutines.rst: <a href="http://reviews.llvm.org/D21170" rel="noreferrer" target="_blank">http://reviews.llvm.org/D21170</a><br>
IR/Intrinsics.td: <a href="http://reviews.llvm.org/D21169" rel="noreferrer" target="_blank">http://reviews.llvm.org/D21169</a><br>
<br>
Concerns:<br>
=========<br>
(This section assumes that you looked at doc/Coroutins.rst and IR/Intrinsics.td)<br>
<br>
Invoke like intrinsics via call + conditional branch:<br>
-----------------------------------------------------<br>
<br>
The `llvm.experimental.coro.fork` and `llvm.experimental.coro.suspend`<br>
intrinsics model behavior somewhat similar to the invoke instruction. Namely,<br>
they are used to show a normal continuation branch and an alternative branch.<br>
<br>
They are used in the following pattern:<br>
<br>
%<a href="http://where.to" rel="noreferrer" target="_blank">where.to</a> = call i1 @llvm.experimental.coro.XXXX()<br>
br i1 %<a href="http://where.to" rel="noreferrer" target="_blank">where.to</a>, label %normal, label %alternative<br>
<br>
My concern is that this is somewhat fragile. After optimizations some code can<br>
sneak in between the intrinsic and the branch and cause trouble. I am looking<br>
for suggestions on how to make it more robust. One thought I had was to put some<br>
intrinsics at the beginning of the %normal and %alternative blocks so as to<br>
prevent code motion above them. Something like:<br>
<br>
...<br>
%<a href="http://where.to" rel="noreferrer" target="_blank">where.to</a> = call i1 @llvm.experimental.coro.XXXX()<br>
br i1 %<a href="http://where.to" rel="noreferrer" target="_blank">where.to</a>, label %normal, label %alternative<br>
normal:<br>
<phi><br>
call i1 @llvm.experimental.coro.normal();<br>
...<br>
alternative:<br>
<phi><br>
call i1 @llvm.experimental.coro.alt();<br>
...<br>
<br>
After coro.xxx is lowered, coro.normal and coro.alt are removed.<br>
<br>
Looking up outlined coroutine parts<br>
-----------------------------------<br>
<br>
Last parameter of the `llvm.experimental.coro.init" intrinsic is a pointer to<br>
a coroutine function. To get to the outlined parts, I get the name of that<br>
function and glue ".resume", ".destroy" or ".cleanup" suffixes to it and then<br>
look them up by name.<br>
<br>
Probably a better alternative is for a coroutine f to create a constant<br>
containing an array of pointers to f.resume, f.destroy and other parts of the<br>
coroutine and use the last parameter to refer to that constant.<br>
<br>
Other questions<br>
---------------<br>
<br>
I have more questions about the best way of plugging in coroutine optimization<br>
passes into the PassManager, but, I will defer those for later discussion.<br>
<br>
All the feedback and comments is greatly appreciated!!!<br>
<br>
Thank you,<br>
Gor<br>
<br>
References:<br>
===========<br>
<br>
[1] <a href="http://open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0057r4.pdf" rel="noreferrer" target="_blank">http://open-std.org/JTC1/SC22/WG21/docs/papers/2016/p0057r4.pdf</a><br>
[2] <a href="http://llvmweekly.org/issue/95" rel="noreferrer" target="_blank">http://llvmweekly.org/issue/95</a> (Coroutine support added to clang)<br>
[3] <a href="http://www.boost.org/doc/libs/1_61_0/libs/coroutine/doc/html/index.html" rel="noreferrer" target="_blank">http://www.boost.org/doc/libs/1_61_0/libs/coroutine/doc/html/index.html</a><br>
<br>
Review Links:<br>
=============<br>
<br>
doc/Coroutines.rst: <a href="http://reviews.llvm.org/D21170" rel="noreferrer" target="_blank">http://reviews.llvm.org/D21170</a><br>
IR/Intrinsics.td: <a href="http://reviews.llvm.org/D21169" rel="noreferrer" target="_blank">http://reviews.llvm.org/D21169</a><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div><br></div>