Feature request bounty
Joachim Breitner
mail at joachim-breitner.de
Thu Sep 8 21:05:10 UTC 2016
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 <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/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 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%7cf392a423fac64
> > > > > > 06e1e440
> > > > > > 8d3d74
> > > > > > d61be%7c72f988bf86f141af91ab2d7cd011db47%7c1%7c0%7c63608869
> > > > > > 97683024
> > > > > > 40&sda ta=jfQ62xjhLsZ8okc09JLpi6csdqDV2Y8IiLTvXwb5fN4%3d
> > > > _______________________________________________
> > > > ghc-devs mailing list
> > > > ghc-devs at 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
--
Joachim “nomeata” Breitner
mail at joachim-breitner.de • https://www.joachim-breitner.de/
XMPP: nomeata at joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F
Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: This is a digitally signed message part
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20160908/f0470673/attachment.sig>
More information about the ghc-devs
mailing list