Feature request bounty

Thu Sep 8 20:58:34 UTC 2016

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 <simonpj at microsoft.com>:
> 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 at gmail.com]
> | Sent: 08 September 2016 02:20
> | To: Simon Peyton Jones <simonpj at microsoft.com>
> | Cc: ghc-devs <ghc-devs at haskell.org>
> | 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 <david.feuer at gmail.com>:
> | > 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
> | > <simonpj at microsoft.com> 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 at haskell.org] On Behalf Of
> | >> | David Feuer
> | >> | Sent: 07 September 2016 19:33
> | >> | To: ghc-devs <ghc-devs at haskell.org>
> | >> | 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 at 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 at 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