keepAlive# primop

[Sylvain Henry]

Hi ghc-devs,

After a discussion today about `keepAlive#`, I think Option E [1] is 
even more appealing.

To recap the idea was to have keep-alive variable sets attached to 
case-expressions in Core. E.g. `case {k} x of ...`


1. One of the issue was the semantics of `keepAlive#`. `keepAlive#` is 
very intricate with evaluation. As Simon mentioned we want a semantics like:

keepAlive# k x ==> x `seq` touch# k `seq` x

with potentially a special `seq` to deal with diverging `x`.

With `case {k} x of ...` we have this semantics. Even if we throw the 
case alternatives if `x` diverges, we don't throw the keep-alive set so 
we're good.


2. Simon wanted to push `keepAlive#` into case-expressions. With this 
approach we should only have to fix case-of-case to take keep-alive sets 
into account.

case {k} (case {k2} x of .. -> a; ... -> b) of
C0 .. -> e1
C1 .. -> e2

===>

case {k,k2} x of
... -> case {k} a of { C0 .. -> e1; C1 ... -> e2 }
... -> case {k} b of { C0 .. -> e1; C1 ... -> e2 }


3. Compared to other approaches: we don't have to use stack frames (good 
for performance) and we don't have to deal with a continuation (good for 
Core optimizations, hence perf).

4. Implementing this approach is quite straightforward even if it 
modifies Core. I did it last month in [2]. This patch doesn't fully work 
yet with `-O` because some transformation (related to join points IIRC) 
doesn't take keep-alive sets into account but it should be pretty easy 
to fix if we want to use this approach.


Given how hard it is to come up with a good design/implementation of 
other approaches, this one strikes me as probably the more principled we 
have and yet it is relatively easy to implement. What do you think?

Cheers,
Sylvain


[1] 
https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables

[2] https://gitlab.haskell.org/hsyl20/ghc/-/commits/hsyl20-keepalive



On 13/04/2020 19:51, Ben Gamari wrote:
> Ccing ghc-devs@ since this discussion is something of general interest
> to the community.
>
>
> Sylvain Henry <sylvain at haskus.fr> writes:
>
>> Simon, Ben,
>>
>> I've been reading and thinking about `readRW#` issues which are very
>> related to issues we have with `keepAlive#` primop.
>>
>> To recap, the problem is that we want some transformations (that Simon
>> has listed in [1]) to consider:
>>
>> ```
>> case runRW# f of ...
>>
>> case keepAlive# k a of ...
>> ```
>>
>> as if they were really:
>>
>> ```
>> case f realWorld# of ...
>>
>> case a of ...
>> ```
>>
>> BUT without breaking the semantics of runRW# and keepAlive#.
>>
>> I have been thinking about a solution that I have described on the wiki:
>> https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables
>>
>> The idea is to keep a set of variable names in each Core case-expression
>> that are kept alive during the evaluation of the scrutinee.
>>
>> I think it would work very nicely with your `newState#` primop described
>> in [2], both for `runST` and for `unsafeDupablePerformIO` (details on
>> the wiki).
>>
>> It requires a little more upfront work to adapt the code involving
>> case-expressions. But it will force us to review all transformations to
>> check if they are sound when keep-alive sets are not empty, which we
>> would have to do anyway if we implemented another option. We could start
>> by disabling transformations involving non-empty keep-alive sets and
>> iterate to enable the sound ones.
>>
>> I would like your opinions on the approach. I may have totally missed
>> something.
> Thanks for writing this down!
>
> Indeed it is an interesting idea. However, as expressed on IRC, I
> wonder whether this problem rises to the level where it warrants an
> adaptation to our Core representation. It feels a bit like the
> tail is wagging the dog here, especially given how the "tail" here
> merely exists to support FFI.
>
> That being said, this is one of the few options which remain on the
> table that doesn't require changes to user code. Moreover, the
> applicability to runRW# is quite intriguing.
>
> Another (admittedly, more ad-hoc) option that would avoid modifying Core
> would be to teach the simplifier about the class of
> "continuation-passing" primops (e.g. `keepAlive#` and `runRW#`), allowing it
> to push case analyses into the continuation argument. That is,
>
>      case keepAlive# x expr of pat -> rhs
>
>              ~>
>
>      keepAlive# x (case expr of pat -> rhs)
>
> Of course, doing this is a bit tricky since one must rewrite the
> application of keepAlive# to ensure that the resulting application is
> well-typed. Admittedly, this doesn't help the runRW# case (although this
> could presumably be accommodated by touch#'ing the final state token in
> the runRW# desugaring emitted by CorePrep).
>
> On the whole, I'm not a fan of this ad-hoc option. It increases the
> complexity of the simplifier all to support a single operation. By
> comparison, the Core extension looks somewhat appealing.
>
> Cheers,
>
> - Ben
>
>
> [1] https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables
>
> P.S. A minor note: the keepAlive# "pseudo-instruction" mentioned on the
> Wiki [1] is precisely the touch# operation we have today.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20200526/d02ae888/attachment.html>