Hi Sanjoy:
>> How will you handle (potentially variably sized) alloca instructions
>> that cannot be elided by promotion to SSA? E.g.
>>
>> void cor() {
>> int a = 0;
>> escape(&a);
>> for (;;) yield(a++);
>> }
Any escaped allocas go to the coroutine frame. It is an important
use case with async coroutines:
task<void> f() {
char buf[N];
... fill buff with stuff
await async_send(buf); // <suspend-point>
... do more
}
Even though an alloca is not mentioned after suspend point, it is still
need to go to the coroutine frame, as async_send will be referencing it
while coroutine is suspended (and its stack frame gone).
CoroSplit pass is doing two interesting things.
1) Creates the coroutine frame.
2) Chops up the coroutine into pieces
Here is a brief description:
=======================Coroutine Frame Building
=======================
Coroutine frame building algorithm has two parts:
* Deal with allocas
* Deal with virtual registers.
Alloca part
-----------
Step 1: Compute the blocks that will end up in resume and destroy
Step 2: Classify alloca into three buckets
Start Only: Only used in start
Resume Only: Only used in resume/destroy
Shared: Used in both (or escaped)
Step 3: Put all shared values in the coroutine frame, RAUW shared allocas with
GEPs from coroutine frame
Step 4: Move all resume only allocas to the new entry block in resume/destroy
(Future Work)
Step X-1:
insert dbg.values properly
Step X:
Utilize lifetime information for shared allocas to decide how to pack them
tightly in coroutine frame. At the moment I throw away lifetime intrinsics.
Step X+1:
Deal with variable allocas. One way to deal with them is to chain them
to the coroutine frame using the same allocation and deallocation routines
used for coroutine frame itself). Until step X+1, no var.size alloca can
go into a coroutine frame. Start only or Resume only allocas don't
cause problems.
Virtual Register part
---------------------
Step 1: Precompute block relationship X(B1,B2), when B1 dominates B2 and there
is a path from B1 to B2 that crosses a suspend point.
Step 2:
Check if a path from a use of value in a resume/destroy block to a
definition crosses a suspend point, ie X(Bd,Bu) == true, where
Bu is a block with the use
Bd is a block with the definition or an entry block if d is func argument
Step 3:
Check if we already have value 'd' in the coroutine frame, if so,
replace
the use with GEP from the coroutine frame. Otherwise, spill 'd' into
the
coroutine frame and replace the use with GEP.
(future)
Step X:
Make step 3 spilling and reloading smarter.
Step X + 1:
Do live-ranges, coloring, etc to make coroutine frame
really really tiny.
Cheers,
Gor
On Sat, Jun 11, 2016 at 6:09 PM, Sanjoy Das
<sanjoy at playingwithpointers.com> wrote:> Hi Gor,
>
> How will you handle (potentially variably sized) alloca instructions
> that cannot be elided by promotion to SSA? E.g.
>
> void cor() {
> int a = 0;
> escape(&a);
> for (;;) yield(a++);
> }
>
> -- Sanjoy
>
> On Sat, Jun 11, 2016 at 5:43 PM, Gor Nishanov via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> (Dropped llvm-dev by accident. Putting it back)
>>
>>
>> HI Eli:
>>
>>>> coro.barrier() doesn't work: if the address of the alloca
doesn't escape,
>>>> alias analysis will assume the barrier can't read or write
the value of
>>>> the alloca, so the barrier doesn't actually block code
movement.
>>
>> Got it. I am new to this and learning a lot over the course
>> of this thread. Thank you for being patient with me.
>>
>> Two questions and one clarification:
>>
>> Q1: Do we have to have a load here?
>> ==================================>>
>>>> block1:
>>>> %first_time = load... <--- What are we loading here?
>>>> br i1 %first_time, label return, label suspend1
>>>>
>>>> supend1:
>>>> %0 = coro.suspend()
>>>> switch %0 (resume1, destroy1)
>>
>> Can we use three way coro.suspend instead?
>>
>> Block1:
>> %0 = call i8 coro.suspend()
>> switch i8 %0, label suspend1 [i8 0 %return] ; or icmp + br i1
>> Suspend1:
>> switch i8 %0, label %resume1 [i8 1 %destroy1] ; or icmp + br i1
>>
>> One problem I can see is that someone can write a pass that might merge
>> two branches / switches into one switch and we are back where we were.
>> I guess what you meant by load, is to call some coro.is.first.time()
intrinsic.
>> So it looks like:
>>
>>>> block1:
>>>> %first_time = call i1 coro.is.first.time()
>>>> br i1 %first_time, label return, label suspend1
>>>>
>>>> supend1:
>>>> %0 = coro.suspend()
>>>> switch %0 (resume1, destroy1)
>>
>> This looks fine, there may be more uses for this intrinsic in the
frontend.
>> Killing two birds with one stone. Good.
>>
>> Question 2: Why the switch in the return block?
>> ==============================================>>
>> I would think that **pre-split** return block would be simply:
>>
>> return:
>> <run dtors for parameters, if required>
>> <conversion ops for ret value, if required>
>> <ret void> or <ret whatever>
>>
>> Where and why I should put a switch that you mentioned in this return
block?
>>
>> BTW, I am speaking of the return block as if it is one block,
>> but, it could be a dominating block over all the blocks that together
>> run the destructors, do return value conversion, etc.
>>
>> Clarification:
>> =============>>
>>>> Also, if some non-C++ language wants to generate coroutines,
>>>> it might not have to generate the return block at all.
>>
>> C++ coroutines are flexible. The semantic of a coroutine is defined via
>> traits, so you may define a coroutine that returns void. It does not
have
>> to return coroutine handle or some struct that wraps the coroutine
handle.
>>
>> For example, a developer may have a queue of suspended coroutines that
is
>> processed by a scheduler, so a coroutine can queue its handle on
suspension
>> either into a global queue or thread_local queue. If there are no
destructors
>> to run for parameters, the return block would be simply:
>>
>> return:
>> ret void
>>
>>
>> Cheers,
>> Gor
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> --
> Sanjoy Das
> http://playingwithpointers.com