<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 14, 2016 at 7:52 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>
I've included below a brief description of coroutine related optimization<br>
passes and some questions/thoughts related to them. Looking forward to your<br>
feedback, comments and questions.<br>
<br>
Thank you!<br>
<br>
Roadmap:<br>
========<br>
1) Get agreement on coroutine representation and overall direction.<br>
.. repeat 1) until happy<br>
<br>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2016-June/100838.html" rel="noreferrer" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/2016-June/100838.html</a> (Initial)<br>
<a href="http://lists.llvm.org/pipermail/llvm-dev/2016-July/102133.html" rel="noreferrer" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/2016-July/102133.html</a> (Round 2)<br>
<br>
2) Get agreement on how coroutine transformation passes integrate into the<br>
optimizer pipeline. (this mail) <=== WE ARE HERE<br>
.. repeat 2) until happy<br>
<br>
3) update IR/Intrinsics.td + doc/Coroutines.rst + doc/LangRef.rst<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>
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>
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 it can be destroyed.<br>
<br>
CoroSplit Pass: (CGSCC Pass @ new extension point EP_CGSCCOptimizerLate)<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 as a single function for as long as possible. Shortly before<br>
the coroutine is eligible to be inlined into its callers, we outline parts of<br>
the coroutine that correspond to the code that needs to get executed after the<br>
coroutine is resumed or destroyed.</blockquote><div><br></div><div>Seems reasonable. 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.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> We also create a struct that will keep the<br>
objects that need to persist across suspend points. This transformation is<br>
done by CoroSplit CGSCC pass run as a part of the IPO optimizations pipeline.<br>
<br>
CoroElide Pass: (Function Pass @ EP_ScalarOptimizerLate extension point)<br>
---------------<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 the caller, we remove dynamic allocation of coroutine state and<br>
replace it with an `alloca` on the caller's frame.<br>
<br>
These optimizations are done by a function pass CoroElide run by the main IPO<br>
optimization at EP_ScalarOptimizerLate extension point.<br>
<br>
CoroEarly Pass: (Function Pass @ EP_EarlyAsPossible)<br>
---------------<br>
Pretty boring pass that lowers coroutine intrinsics that are not needed for<br>
later coroutine passes.<br>
<br>
CoroCleanup Pass: (Function Pass @ EP_OptimizerLast)<br>
--------------<br>
Another boring pass that lowers all remaining coroutine intrinsics that were not<br>
processed by earlier coroutine passes.<br>
<br>
Questions / Concerns / Thoughts:<br>
================================<br>
<br>
Coroutine attribute or not.<br>
---------------------------<br>
I added a AttrKind::coroutine to flag the pre-split coroutine. The intention is<br>
to lessen the impact of CoroSpit pass since it can simply check for an attribute<br>
to learn if there is any work to be done on a function or not. Without the<br>
attribute, it would need to examine every functions body to see if it has an<br>
llvm.coro.begin. On the other hand, three other coroutine passes have to look at<br>
every function body anyway to lower other coroutine related intrinsics, so we<br>
only saving a little. Another negative aspect of having this attribute is that<br>
there is a possibility of other passes checking if a function is a coroutine or<br>
not a doing and doing something differently if it is. I'd like to avoid this<br>
development and keep all coroutine logic in the coroutine passes and not affect<br>
other optimizations passes. Currently I am leaning towards removing this<br>
attribute.<br></blockquote><div><br></div><div>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).</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Integration with CGSCC pipeline.<br>
--------------------------------<br>
<br>
As mentioned in the introduction, I would like to run entire IPO pipeline on<br>
pre-split coroutine, then, split it, add the new functions to the SCC and<br>
repeat the pipeline on the updated SCC before proceeding to the next SCC.<br>
<br>
To facilitate that, CoroSplit pass ignores the coroutine the first time it sees<br>
it, and requests restart of the pipeline and splits the coroutine when it sees<br>
it the second time around. There are at least four different ways how I can<br>
request a restart of the pipeline, and I would like to solicit your advice on<br>
which one to pick.<br>
<br>
Option 1: Force revisit of the SCC if there are any coroutine in it. This makes<br>
CGPassManager aware of a coroutine attribute and keep restarting the pipeline<br>
until no functions in SCC has coroutine attribute on them.<br>
<br>
<a href="https://reviews.llvm.org/D21569" rel="noreferrer" target="_blank">https://reviews.llvm.org/D21569</a><br>
<br>
Option 2: Add a ref parameter bool& Devirt parameter to runSCC virtual method.<br>
If a pass sets Devirt to true, it indicates to CGPassManager that the changes<br>
were made that require restart of the pipeline.<br>
<br>
<a href="https://reviews.llvm.org/D21570" rel="noreferrer" target="_blank">https://reviews.llvm.org/D21570</a><br>
<br>
Option 3: Similar to Option 2, but instead of an extra parameter to runSCC, I<br>
add another virtual function to CGSCC pass:<br>
<br>
virtual bool restartRequested() const { return false; }<br>
<br>
a pass can override it and return true, if restart is required.<br>
<br>
Option 4: CoroSplit can add a fake indirect call to be replaced later with a<br>
direct call in a CoroElide function pass. CGPassManager::RefreshCallGraph will<br>
detect devirtualization and restart the pipeline. Hacky, but, no changes to<br>
CGPassManager required.<br>
<br>
Out of these four options, I have a slight preference for 2 or 3, but, I would<br>
like to hear your opinion.<br>
<br>
Thoughts on ThinLTO and LTO<br>
===========================<br>
<br>
CoroEarly can run during regular compilation. CoroSplit, CoroEarly and<br>
CoroCleanup would run during the link optimization step to take advantage of<br>
more inlining opportunities.<br>
<br>
This is all for now.<br>
All the feedback and comments are greatly appreciated!!!<br>
<br>
Thank you,<br>
Gor<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></div>