Feature request bounty

[Ömer Sinan Ağacan]

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%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
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs