I can't guarantee I'll be able to understand things well enough to take your advice, but I'd be willing to give it a shot. Where would be the right place to stick this? I am not at all familiar with the GHC code generation system. Also, what might I have to do to avoid forcing the same object repeatedly? If I have multiple such constructors, and someone does case x of Con1 (Con2 (Con3 (Con4 y))) -> e I want to smash this down to something that looks like case x of y { _ -> e } Do I need to worry about this, or will some later C-- pass take care of it? On Wed, Sep 7, 2016 at 4:46 PM, Simon Peyton Jones wrote:

I can advise about how (see comment:9 of #1965). I can only see how to do it in an un-typed way in the back end.

Simon

| -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of David | Feuer | Sent: 07 September 2016 19:33 | To: ghc-devs | Subject: Feature request bounty | | I'd like to place a small bounty on | https://ghc.haskell.org/trac/ghc/wiki/NewtypeOptimizationForGADTS . | | If someone implements this request by GHC 8.2, I will buy them 24 bottles | of high-end root beer (e.g., Maine Root) or something of similar value | agreeable to both parties. (*) | | Thanks, | David Feuer | | (*) Recipient responsible for customs/duty/taxes/shipping fees beyond | US$10. | _______________________________________________ | ghc-devs mailing list | ghc-devs@haskell.org | https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.hask | ell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc- | devs&data=02%7c01%7csimonpj%40microsoft.com%7cf392a423fac6406e1e4408d3d74 | d61be%7c72f988bf86f141af91ab2d7cd011db47%7c1%7c0%7c636088699768302440&sda | ta=jfQ62xjhLsZ8okc09JLpi6csdqDV2Y8IiLTvXwb5fN4%3d

Omer: yes you have it right. I agree with your remarks about follow-up simplifications. That's jolly annoying. I don't know a good path here. I suppose we could make a simple STG simplifier.... Stuff on email gets lost/buried. Would you like to extend the wiki page with your implementation notes? That would capture them. Simon | -----Original Message----- | From: Ömer Sinan Ağacan [mailto:omeragacan@gmail.com] | Sent: 08 September 2016 02:20 | To: Simon Peyton Jones | Cc: ghc-devs | Subject: Re: Feature request bounty | | Simon, | | As far as I understand we want to do these two transformations: | | (when D is a newtype-like data type constructor) | | | First: | D arg1 arg2 ... argN | ==> | nv_arg (where nv_arg is the only non-void argument) | | (but we somehow need to bind other args or do substitution. If we do | this | Stg though we don't need to bind those args as unarise doesn't care | about | what a void argument is as long as it's void it gets rid of it and it | can | check void-ness by looking at Id's type) | | Second: | case <exp1> of | D arg1 arg2 ... argN -> <exp2> | ==> | let arg1 = ... | arg2 = ... | arg3 = ... | in <exp2> | (we know only one of these args will be non-void, but all of them | should be | bound as they can be referred in <exp2>) | | Am I right? | | I think if we do this in Stg we lose some optimization opportunities and | generate ugly code. For example, if the first transformation happens in a | let-binding RHS maybe simplifier decides to inline it as it can't | duplicate work after the transformation. Similarly it can decide to | inline the non-void argument after second transformation which may lead | to further optimizations etc. | | For an example of an ugly code, suppose we had this: | | case <exp1> of | D (T x) -> <exp2> | | in Stg this looks like | | case <exp1> of | D v -> case v of | T x -> <exp2> | | So now if we do the second transformation we get | | let v = <exp1> in | case v of | T x -> <exp2> | | but ideally we'd get | | case <exp1> of | T x -> <exp2> | | I think simplifier would be able to do this after the second | transformation. | Am I making any sense? | | I have no idea how to do this in the simplifier without losing type | safety though... | | Are these two transformations also what you had in mind or do you have | something else? | | - Omer | | 2016-09-07 16:58 GMT-04:00 David Feuer : | > I can't guarantee I'll be able to understand things well enough to | > take your advice, but I'd be willing to give it a shot. Where would be | > the right place to stick this? I am not at all familiar with the GHC | > code generation system. Also, what might I have to do to avoid forcing | > the same object repeatedly? If I have multiple such constructors, and | > someone does | > | > case x of | > Con1 (Con2 (Con3 (Con4 y))) -> e | > | > I want to smash this down to something that looks like | > | > case x of y { | > _ -> e } | > | > Do I need to worry about this, or will some later C-- pass take care of | it? | > | > On Wed, Sep 7, 2016 at 4:46 PM, Simon Peyton Jones | > wrote: | >> I can advise about how (see comment:9 of #1965). I can only see how | to do it in an un-typed way in the back end. | >> | >> Simon | >> | >> | -----Original Message----- | >> | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of | >> | David Feuer | >> | Sent: 07 September 2016 19:33 | >> | To: ghc-devs | >> | Subject: Feature request bounty | >> | | >> | I'd like to place a small bounty on | >> | https://ghc.haskell.org/trac/ghc/wiki/NewtypeOptimizationForGADTS . | >> | | >> | If someone implements this request by GHC 8.2, I will buy them 24 | >> | bottles of high-end root beer (e.g., Maine Root) or something of | >> | similar value agreeable to both parties. (*) | >> | | >> | Thanks, | >> | David Feuer | >> | | >> | (*) Recipient responsible for customs/duty/taxes/shipping fees | >> | beyond US$10. | >> | _______________________________________________ | >> | ghc-devs mailing list | >> | ghc-devs@haskell.org | >> | https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmai | >> | l.hask | >> | ell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc- | >> | devs&data=02%7c01%7csimonpj%40microsoft.com%7cf392a423fac6406e1e440 | >> | 8d3d74 | >> | d61be%7c72f988bf86f141af91ab2d7cd011db47%7c1%7c0%7c6360886997683024 | >> | 40&sda ta=jfQ62xjhLsZ8okc09JLpi6csdqDV2Y8IiLTvXwb5fN4%3d | > _______________________________________________ | > ghc-devs mailing list | > ghc-devs@haskell.org | > https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.h | > askell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc-devs&data=02%7c01%7csi | > monpj%40microsoft.com%7c0cd3f91c657b41f8492108d3d7864917%7c72f988bf86f | > 141af91ab2d7cd011db47%7c1%7c0%7c636088944161132661&sdata=mfmxH%2bRbgRs | > XHzv6O0gBDC0DKzgi%2fNdNGxpxFOWEWqo%3d

Hi, slightly related (an other optimization around data types that is possible in STG, but not in Core): https://ghc.haskell.org/trac/ghc/ticket/9291 Greetings, Joachim Am Donnerstag, den 08.09.2016, 16:58 -0400 schrieb Ömer Sinan Ağacan:

I updated implementation section of the wiki page (https://ghc.haskell.org/trac/ghc/wiki/NewtypeOptimizationForGADTS).

2016-09-08 7:21 GMT-04:00 Simon Peyton Jones :

...

Omer: yes you have it right.

I agree with your remarks about follow-up simplifications.  That's jolly annoying.

I don't know a good path here.  I suppose we could make a simple STG simplifier....

Stuff on email gets lost/buried. Would you like to extend the wiki page with your implementation notes?  That would capture them.

Simon

...

-----Original Message----- From: Ömer Sinan Ağacan [mailto:omeragacan@gmail.com] Sent: 08 September 2016 02:20 To: Simon Peyton Jones Cc: ghc-devs Subject: Re: Feature request bounty

Simon,

As far as I understand we want to do these two transformations:

(when D is a newtype-like data type constructor)

First:     D arg1 arg2 ... argN     ==>     nv_arg (where nv_arg is the only non-void argument)

    (but we somehow need to bind other args or do substitution. If we do this     Stg though we don't need to bind those args as unarise doesn't care about     what a void argument is as long as it's void it gets rid of it and it can     check void-ness by looking at Id's type)

Second:     case <exp1> of       D arg1 arg2 ... argN -> <exp2>     ==>     let arg1 = ...         arg2 = ...         arg3 = ...      in <exp2>      (we know only one of these args will be non-void, but all of them should be      bound as they can be referred in <exp2>)

Am I right?

I think if we do this in Stg we lose some optimization opportunities and generate ugly code. For example, if the first transformation happens in a let-binding RHS maybe simplifier decides to inline it as it can't duplicate work after the transformation. Similarly it can decide to inline the non-void argument after second transformation which may lead to further optimizations etc.

For an example of an ugly code, suppose we had this:

    case <exp1> of       D (T x) -> <exp2>

in Stg this looks like

    case <exp1> of       D v -> case v of                T x -> <exp2>

So now if we do the second transformation we get

    let v = <exp1> in     case v of       T x -> <exp2>

but ideally we'd get

    case <exp1> of       T x -> <exp2>

I think simplifier would be able to do this after the second transformation. Am I making any sense?

I have no idea how to do this in the simplifier without losing type safety though...

Are these two transformations also what you had in mind or do you have something else?

- Omer

2016-09-07 16:58 GMT-04:00 David Feuer :

...

I can't guarantee I'll be able to understand things well enough to take your advice, but I'd be willing to give it a shot. Where would be the right place to stick this? I am not at all familiar with the GHC code generation system. Also, what might I have to do to avoid forcing the same object repeatedly? If I have multiple such constructors, and someone does

case x of   Con1 (Con2 (Con3 (Con4 y))) -> e

I want to smash this down to something that looks like

case x of y {   _ -> e }

Do I need to worry about this, or will some later C-- pass take care of

it?

...

On Wed, Sep 7, 2016 at 4:46 PM, Simon Peyton Jones wrote:

...

I can advise about how (see comment:9 of #1965).  I can only see how

to do it in an un-typed way in the back end.

...

...

Simon

...

-----Original Message----- From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of David Feuer Sent: 07 September 2016 19:33 To: ghc-devs Subject: Feature request bounty

I'd like to place a small bounty on https://ghc.haskell.org/trac/ghc/wiki/NewtypeOptimizationFo rGADTS .

If someone implements this request by GHC 8.2, I will buy them 24 bottles of high-end root beer (e.g., Maine Root) or something of similar value agreeable to both parties. (*)

Thanks, David Feuer

(*) Recipient responsible for customs/duty/taxes/shipping fees beyond US$10. _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org https://na01.safelinks.protection.outlook.com/?url=http%3a% 2f%2fmai l.hask ell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc- devs&data=02%7c01%7csimonpj%40microsoft.com%7cf392a423fac64 06e1e440 8d3d74 d61be%7c72f988bf86f141af91ab2d7cd011db47%7c1%7c0%7c63608869 97683024 40&sda ta=jfQ62xjhLsZ8okc09JLpi6csdqDV2Y8IiLTvXwb5fN4%3d

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2 fmail.h askell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc- devs&data=02%7c01%7csi monpj%40microsoft.com%7c0cd3f91c657b41f8492108d3d7864917%7c72f9 88bf86f 141af91ab2d7cd011db47%7c1%7c0%7c636088944161132661&sdata=mfmxH% 2bRbgRs XHzv6O0gBDC0DKzgi%2fNdNGxpxFOWEWqo%3d

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs -- Joachim “nomeata” Breitner   mail@joachim-breitner.de • https://www.joachim-breitner.de/   XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F   Debian Developer: nomeata@debian.org