<div dir="ltr">cc llvm-dev</div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 21, 2016 at 9:57 AM, Vadim Chugunov <span dir="ltr"><<a href="mailto:vadimcn@gmail.com" target="_blank">vadimcn@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Gor,<div>Does you design support resumption with parameter(s)? (such as Python's generator.send(x)). I suppose the "promise" could be used for passing data both ways, but if that's the plan, please mention this explicitly in the design doc.</div><div>Also, how is loading/storing to promise going to be lowered?</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Vadim</div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jul 11, 2016 at 6:47 AM, 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>
Thank you very much for the feedback during the first round! Special thanks to<br>
Eli, Sanjoy, Hal and Chandler for their detailed public and private comments.<br>
The model is simpler now and the intrinsics have nice symmetry to them:<br>
coro.begin + coro.end, coro.alloc + coro.free. Compared to the previous RFC,<br>
coro.fork is gone, coro.init and coro.start are collapsed into one coro.begin,<br>
coro.suspend is three-way as opposed to two-way. coro.elide and coro.delete<br>
renamed coro.alloc and coro.free.<br>
<br>
All the changes implemented and tested. Full document, (nicely formatted by<br>
github is at:<br>
<br>
<a href="https://github.com/GorNishanov/llvm/blob/coro-rfc/docs/Coroutines.rst" rel="noreferrer" target="_blank">https://github.com/GorNishanov/llvm/blob/coro-rfc/docs/Coroutines.rst</a><br>
<br>
Below is a summary of a proposal to add coroutine support to LLVM.<br>
The proposal is motivated primarily by the desire to support C++ Coroutines [1],<br>
however the llvm representation is language neutral and can be used<br>
to support 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>
You can also use coroutines in plain C, by calling the builtins mapping to the<br>
intrinsics described by this proposal, so that your coroutine can look like:<br>
<br>
#include "Inputs/coro.h"<br>
void print(int v);<br>
<br>
void* f(int n) {<br>
CORO_BEGIN(malloc);<br>
<br>
while (n-- > 0) {<br>
print(n+1);<br>
CORO_SUSPEND();<br>
}<br>
<br>
CORO_END(free);<br>
}<br>
<br>
// CHECK-LABEL: @main<br>
int main() {<br>
void* coro = f(4);<br>
CORO_RESUME(coro);<br>
CORO_RESUME(coro);<br>
CORO_DESTROY(coro);<br>
}<br>
<br>
<a href="https://github.com/GorNishanov/clang/blob/coro-rfc/test/Coroutines/coro.c" rel="noreferrer" target="_blank">https://github.com/GorNishanov/clang/blob/coro-rfc/test/Coroutines/coro.c</a><br>
<a href="https://github.com/GorNishanov/clang/blob/coro-rfc/test/Coroutines/Inputs/coro.h" rel="noreferrer" target="_blank">https://github.com/GorNishanov/clang/blob/coro-rfc/test/Coroutines/Inputs/coro.h</a><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. See "More Attention Required" in the doc/Coroutines.rst [4]for details<br>
on what additional work is required beyond cleanup and bug fixes.<br>
<br>
I would like to continue the discussion on the overall design, representation<br>
and a roadmap to start upstreaming the changes with the intention to continue<br>
the 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 <=== ARE ARE HERE<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/LangRef.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>
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 it can be destroyed.<br>
<br>
In the following example, function `f` (which may or may not be a coroutine<br>
itself) returns a handle to a suspended coroutine (**coroutine handle**) that is<br>
used 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.coro.resume(i8* %hdl)<br>
call void @llvm.coro.resume(i8* %hdl)<br>
call void @llvm.coro.destroy(i8* %hdl)<br>
ret i32 0<br>
}<br>
<br>
In addition to the stack frame which exists when a coroutine 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 and<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 the<br>
lifetime of its caller, we remove dynamic allocation for coroutine frame and<br>
replace it with a static `alloca` on the caller's frame.<br>
<br>
Please see doc/Coroutines.rst for more details:<br>
<br>
<a href="https://github.com/GorNishanov/llvm/blob/coro-rfc/docs/Coroutines.rst" rel="noreferrer" target="_blank">https://github.com/GorNishanov/llvm/blob/coro-rfc/docs/Coroutines.rst</a><br>
<br>
Concerns:<br>
=========<br>
(This section assumes that you looked at doc/Coroutins.rst)<br>
<br>
coro.begin: 4 arguments or 5?<br>
-----------------------------<br>
<br>
Background:<br>
<br>
For standard allocation functions recognized by LLVM, coroutine frame allocation<br>
code looks like:<br>
<br>
entry:<br>
%size = call i32 @llvm.coro.size.i32(i8* null)<br>
%alloc = call i8* @malloc(i32 %size)<br>
%hdl = call noalias i8* @llvm.coro.begin(i8* %alloc, i32 0, i8* null,<br>
i8* null)<br>
<br>
To enable coroutine heap elision with custom allocation functions, `coro.alloc`<br>
intrinsic is used to exclude the allocation code when not needed.<br>
<br>
entry:<br>
%elide = call i8* @llvm.coro.alloc()<br>
%0 = icmp ne i8* %elide, null<br>
br i1 %0, label %coro.begin, label %coro.alloc<br>
<br>
coro.alloc:<br>
%frame.size = call i32 @llvm.coro.size()<br>
%alloc = call i8* @MyAlloc(i32 %frame.size)<br>
br label %coro.begin<br>
<br>
coro.begin:<br>
%phi = phi i8* [ %elide, %entry ], [ %alloc, %coro.alloc ]<br>
%frame = call i8* @llvm.coro.begin(i8* %phi, i32 0, i8* null, i8* null)<br>
<br>
When using a static alloca for coroutine frame, coro.begin and coro.alloc<br>
intrinsics are replaced with that very alloca (bitcasted to i8* to match the<br>
type).<br>
<br>
To find a coro.alloc matching a particular coro.begin, I hunt through the %phi<br>
until I find definition of coro.alloc. Probably more robust implementation<br>
need to use alias analysis to check whether the %phi and %elide may alias.<br>
<br>
A simpler approach would be just to add another parameter to directly point to<br>
`coro.alloc`. With this change, coro.begin block above would look like:<br>
<br>
coro.begin:<br>
%phi = phi i8* [ %elide, %entry ], [ %alloc, %coro.alloc ]<br>
%frame = call i8* @llvm.coro.begin(i8* %phi, i8 %elide, i32 0, i8* null,<br>
^^^^^^^^^ i8* null)<br>
<br>
All feedback and comments are 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>
[4] <a href="https://github.com/GorNishanov/llvm/blob/coro-rfc/docs/Coroutines.rst" rel="noreferrer" target="_blank">https://github.com/GorNishanov/llvm/blob/coro-rfc/docs/Coroutines.rst</a><br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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>
</div></div></blockquote></div><br></div>