Feature request bounty

[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 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