Re: Feature request bounty

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