This is an archive of the discontinued LLVM Phabricator instance.

[Coroutines] Part 5: Add CGSCC restart trigger
ClosedPublic

Authored by GorNishanov on Aug 5 2016, 9:56 PM.
Tokens
"Yellow Medal" token, awarded by GorNishanov.

Details

Summary

CoroSplit pass processes the coroutine twice. First, it lets it go through
complete IPO optimization pipeline as a single function. It forces restart
of the pipeline by inserting an indirect call to an empty function "coro.devirt.trigger"
which is devirtualized by CoroElide pass that triggers a restart of the pipeline by CGPassManager.
(In later patches, when CoroSplit pass sees the same coroutine the second time, it splits it up,
adds coroutine subfunctions to the SCC to be processed by IPO pipeline.)

Documentation and overview is here: http://llvm.org/docs/Coroutines.html.

Upstreaming sequence (rough plan)
1.Add documentation. (https://reviews.llvm.org/D22603)
2.Add coroutine intrinsics. (https://reviews.llvm.org/D22659)
3.Add empty coroutine passes. (https://reviews.llvm.org/D22847)
4.Add coroutine devirtualization + tests.
ab) Lower coro.resume and coro.destroy (https://reviews.llvm.org/D22998)
c) Do devirtualization (https://reviews.llvm.org/D23229)
5.Add CGSCC restart trigger + tests. <= we are here
6.Add coroutine heap elision + tests.
7.Add the rest of the logic (split into more patches)

Diff Detail

Event Timeline

GorNishanov updated this revision to Diff 67063.Aug 5 2016, 9:56 PM
GorNishanov retitled this revision from to [Coroutines] Part 5: Add CGSCC restart trigger.
GorNishanov updated this object.
GorNishanov added reviewers: mehdi_amini, majnemer.
GorNishanov added a subscriber: llvm-commits.
mehdi_amini edited edge metadata.Aug 5 2016, 10:22 PM

This seems "hacky", but it is maybe because I don't grasp the complexity of what is achieved here.

majnemer added inline comments.Aug 5 2016, 11:29 PM
lib/Transforms/Coroutines/CoroSplit.cpp
23

Would you consider prepare instead of makeReady?

31–34

Any reason why you don't just use EntryBlock.getFirstInsertionPt()?

67

auto *?

70

Ditto.

74

I've updated this API to be a little more reasonable, just pass in Nodes.

106

Can this be auto *?

This seems "hacky", but it is maybe because I don't grasp the complexity of what is achieved here.

I considered three other less hacky alternatives to force a restart of CGSCC pipeline. They all had an unfortunate property of slowing down (slightly) compilation even if the module has no coroutines at all. I found the hacky alternative offered by this patch tolerable because it:

a) does not affect non-coroutines, thus, no impact on compilation of regular functions
b) we already have devirtualization logic for coro.resume and coro.destroy and we utilize it as a restart trigger

Less hacky alternatives:

Option 1: make CGPassManager a little bit of coroutine aware.
http://reviews.llvm.org/D21569
I dislike this approach as I’d like to keep Coroutine specific logic in coroutine passes

Option 2: Generalization runOnSCC(SCC, bool& restartRequired) – now any pass can request a restart
http://reviews.llvm.org/D21570
Not sure about this one either, it is very “in your face”. On the other hand, it is very straightforward way of specifying the desired behavior compare to:

Option 3: Add virtual bool CallGraphSCCPass::restartRequested() const; CGManager will call it after each call to runOnSCC to check if restart is required

http://reviews.llvm.org/D21572
Well, I am not sure about this one either. It is slightly more convoluted way to do option 2.
On the plus side, this is not a breaking change, and also, forcing people to work a little harder to demand restart, may give them a chance to think and realize that may be they don’t need to rerun the pipeline at all.

GorNishanov updated this revision to Diff 67074.Aug 6 2016, 7:32 AM
GorNishanov edited edge metadata.

Addressed code review feedback:

  1. s/makeReadyForSplit/prepareForSplit
  2. no longer skipping over DbgInst in the entry block
  3. auto * galore
  4. updated to match new interface to SCC.initialize
GorNishanov marked 6 inline comments as done.
GorNishanov added inline comments.
lib/Transforms/Coroutines/CoroSplit.cpp
31–34

getFirstInsertionPt does not skip over AllocaInst. Some passes, Reg2Mem, Inliner, for example, assume that entry block starts with (possibly empty) sequence of AllocaInst.

I don't have to skip over DbgInfoIntrinsic though. I can make this loop to be simply:

while (isa<AllocaInst>(*It)) ++It;

I'm still struggling to figure why you need to force the restart, can you point to a document that explains it?
(I think it should be explained in the code somehow as well).

GorNishanov marked an inline comment as done.Aug 6 2016, 10:44 AM

I'm still struggling to figure why you need to force the restart, can you point to a document that explains it?
(I think it should be explained in the code somehow as well).

Would this comment address your concerns? I can add it to the beginning of CoroSplit.cpp

// We present a coroutine to an LLVM as an ordinary function with suspension
// points marked up with intrinsics. We let the optimizer party on the coroutine
// as a single function for as long as possible. Shortly before the coroutine is
// eligible to be inlined into its callers, we split up the coroutine into parts
// corresponding to an initial, resume and destroy invocations of the coroutine,
// adds them to the current SCC and restart the IPO pipeline to optimize the
// coroutine subfunctions we extracted before proceeding to the caller of the
// coroutine.

P.S.

This was discussed in RFC: Coroutine Optimization Passes: http://lists.llvm.org/pipermail/llvm-dev/2016-July/102337.html .

Added a comment to CoroSplit.

uploaded with more context (-U999999)

use terminator instruction of the entry block as an insertion point for the restart trigger function call.

majnemer accepted this revision.Aug 6 2016, 1:09 PM
majnemer edited edge metadata.

LGTM w/ nits addressed.

lib/Transforms/Coroutines/CoroElide.cpp
16–17

Could we remove this include?

lib/Transforms/Coroutines/CoroInternal.h
36

I'd name this define CORO_PRESPLIT_ATTR.

37–38

Maybe just PREPARED_FOR_SPLIT and UNPREPARED_FOR_SPLIT ?

lib/Transforms/Coroutines/CoroSplit.cpp
15

Are you using this? I cannot quite see where...

This revision is now accepted and ready to land.Aug 6 2016, 1:09 PM
GorNishanov updated this revision to Diff 67086.Aug 6 2016, 1:27 PM
GorNishanov edited edge metadata.

Nits addressed

GorNishanov marked 4 inline comments as done.Aug 6 2016, 1:29 PM
This revision was automatically updated to reflect the committed changes.