[llvm-dev] RFC: Coroutine Optimization Passes

[Gor Nishanov via llvm-dev]

Hi Vadim

> Can't this transform be performed entirely in the front-end?

Absolutely it can. But, such a coroutine becomes unoptimizable. Once
split, we lose SSA-form, don't see the control flow clearly. The
wonderful property of the proposed approach is that a coroutine stays
intact looking like a normal function for as long as possible. We let
the optimizer to clean it up, doing constant propagation, constant
folding, CSE, dead code elimination, heap allocation elision, etc.

The frontend does not have the tools to make coroutines efficient.

Cheers,
Gor

On Thu, Jul 14, 2016 at 10:48 PM, Vadim Chugunov <vadimcn at gmail.com> wrote:
> Hi!
> Sorry for jumping in late, but I have a general question (that I perhaps
> should have asked during round 1):
>
> This proposal jumps straight into the thick of implementation, but I don't
> think I've seen a motivation of why coroutines need to be represented at the
> LLVM IR level.   Can't this transform be performed entirely in the
> front-end?
>
> Vadim
>
> On Thu, Jul 14, 2016 at 9:28 PM, Gor Nishanov via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>> Hi David:
>>
>> >> How do you deal with basic blocks which appear to be used by multiple
>> >> parts
>> >> of the coroutine? We handled this in WinEHPrepare by cloning any BBs
>> >> which
>> >> were shared.
>>
>> I experimented with several approaches, but, cloning ended up being the
>> simplest
>> and most reliable. Suspend points express three different control flows
>> that
>> can happen at the suspend point: a suspension (default), resumption (0)
>> and
>> destruction (1).
>>
>>   %0 = call i8 @llvm.coro.suspend([..])
>>   switch i8 %0, label %suspend [i8 0, label %resume,
>>                                 i8 1, label %destroy]
>>
>> I slap a switch that jumps to all suspend points in the function. Then I
>> clone
>> the function twice (one will become resume clone, and another destroy
>> clone).
>> This switch becomes the entry block in the clones. Then, I RAUW
>> coro.suspends
>> with -1, 0, or 1 (in original, resume and destroy clones respectively) and
>> let
>> SimplifyCFG do the rest. (This is slightly simplified explanation, but it
>> should
>>  give the idea).
>>
>> >> I would remove the attribute.  There are all sorts of tricks you can do
>> >> to
>> >> avoid scanning the function for calls to the intrinsic.  For example,
>> >> you
>> >> can see if a declaration of your intrinsic exists and, if so, if it has
>> >> an
>> >> users in the function in question (under the assumption that there are
>> >> few).
>>
>> Aye-aye. Will remove the attribute.
>>
>> With respect to lessening the impact of coroutine passes, one approach I
>> tried
>> was to look during doInitialize whether there are any uses of coroutine
>> intrinsics and set a flag if there are any, or maybe build a set of
>> functions
>> with coroutines intrinsics in doInitialize, so that in runOnFunction, I
>> can just
>> check whether the function is in the set and skip if it is not.
>>
>> Then, I scared myself silly that some optimization passes can materialize
>> new functions or new function bodies and I will miss them. So I stopped
>> doing
>> that.
>>
>> I think your approach takes care of my "materialization" concern. (BTW, I
>> don't
>> even know if that is a real concern). But may not be profitable if there
>> are a
>> lot of small functions that are faster to scan for coroutine intrinsics
>> then to
>> scan potentially longer list of coroutine intrinsics users.
>>
>> BTW, Do you have a preference on how to restart CGSCC pipeline? One of the
>> four
>> options I listed (repeated in P.S), or even some better way I did not
>> think
>> about?
>>
>> Thank you,
>> Gor
>>
>> P.S.
>>
>> Option 1: https://reviews.llvm.org/D21569 (no longer relevant, since we
>> are
>>                                            removing AttrKind::Coroutine)
>> Option 2: https://reviews.llvm.org/D21570 (bool& Devirt in runSCC)
>> Option 3: https://reviews.llvm.org/D21572 (virtual bool
>> restatedRequested())
>> Option 4: Fake devirtualized call in a function pass, so that RefreshSCC
>> will
>>           detect devirtualization and restart the pipeline by itself.
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>