[llvm-dev] [RFC] LLVM Coroutines

[Eli Friedman via llvm-dev]

On Fri, Jun 10, 2016 at 5:25 PM, Gor Nishanov <gornishanov at gmail.com> wrote:

> Hi Eli:
>
> >> Naively, you would expect that it would be legal to hoist the store...
> >> but that breaks your coroutine semantics because the global could be
> mutated
> >> between the first return and the resume.
>
> Hmmm... I don't see the problem. I think hoisting the store is perfectly
> legal
> transformation with all semantics preserved.
>
> Let's look at your example:
>
> >> block1:
> >>   suspend
> >>   switch (resume, destroy, return)
> >>
> >> resume:
> >>   store zero  to global @g
> >>   doA()
> >>   [...]
> >>
> >> destroy:
> >>   store zero  to global @g
> >>   doB()
> >>   [...]
> >>
> >> return:
> >>   store zero to global @g
> >>   doC
> >>   [...]
>
> As written the behavior is:
>
>   1) when we encounter a suspend during the first pass through the
> function,
>      store 0 to @g and doC()
>
>   2) when we encounter a suspend after coroutine was resumed
>      ret void
>
>   3) When coroutine is resumed:
>      store 0 to @g and doA()
>
>   4) When coroutine is destroyed:
>      store 0 to @g and doB()
>
> If this is a coroutine that can be resumed asynchronously from a different
> thread there is a data race. For example, if resume happens before 'f'
> returns,
> doA() can write something useful to @g, and 'f' will clobber it with zero.
> But, this race is already present in the code and is not introduced by
> LLVM.
>
> Let's hoist the store and see what happens:
>
> >> block1:
> >>   suspend
> >>   store zero  to global @g
> >>   switch (resume, destroy, return)
> >>
> >> resume:
> >>   doA()
> >>   [...]
> >>
> >> destroy:
> >>   doB()
> >>   [...]
> >>
> >> return:
> >>   doC()
> >>   [...]
>
> Now, let's split it up:
>   1. RAUW coro.suspend with -1,0,1 in f, f.resume and f.destroy
>   2. remove coro.suspend in f, replace with ret void in f.resume
>
> void f() {
>   [...]
>   store zero  to global @g
>   doC();
>   [...]
> }
>
> void @f.resume() {
> entry:
>   store zero  to global @g
>   doA();
>   [....]
> }
>
> void @f.destroy() {
> entry:
>   store zero  to global @g
>   doB();
>   [....]
> }
>
> Behavior looks exactly as before. What am I missing?
>
>
Err... I guess nothing; sorry, I got myself confused.  Essentially
executing a return statement, then jumping back, seems wrong, but I'm
having trouble coming up with a good example of how it would actually break
something.  I guess there aren't really any issues on a pure control-flow
basis: you can't execute a global side-effect a different number of times
than it would otherwise happen.

You might run into problems with allocas: LLVM's optimizer will assume the
lifetime of any alloca in the current function ends when you hit a "ret"
instruction, so jumping back from the ret to the middle of the function
could lead to wrong results.  Silly example:

x = alloca...

block1:
  suspend
  ; increment could get moved here.
  switch (resume, destroy, return)

resume:
  x += 1
   [...]

destroy:
  x += 1
   [...]

return:
  (don't touch x)
  [...]

The increment is only supposed to execute once, but instead executes twice.

This isn't a great example... and I'm not sure issues are limited to
allocas... but that's the idea, anyway.

-Eli
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160610/39f19df7/attachment.html>