[GHC] #14826: Flatten data types extending other data types in STG

19 Feb 2018

      #14826: Flatten data types extending other data types in STG
-------------------------------------+-------------------------------------
           Reporter:  nomeata        |             Owner:  (none)
               Type:  feature        |            Status:  new
  request                            |
           Priority:  low            |         Milestone:
          Component:  Compiler       |           Version:  8.5
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 This idea was triggered by https://mail.haskell.org/pipermail/haskell-
 cafe/2018-February/128570.html although it does not solve that particular
 case. Hence I don’t know if there is any practical use for it, but I
 wanted to jot it down.

 Consider a data type
 {{{
 data Result = Ok !Foo | NotOK Error
 }}}
 where `Foo` is a concrete algebraic data type with $n$ constructors.

 Then the following transformation should be safe:

  * Do not generate an info table for `Ok`
  * Give the `NotOK` the constructor number $n+1$.
  * Replace calls to `Ok` with `id`
  * Replace
    {{{
    case r as b of Of f    -> E[b,f] | NotOk e -> E[b,e]
    }}}
    with
    {{{
    case r as b of DEFAULT -> E[b,b] | NotOk e -> E[b,e]
    }}}

 This effectively makes every constructor or `Foo` a constructor of `Ok`,
 and eliminates the pointer indirection introduced by `Foo`. Checking if a
 `Result` is `Ok` is now a simple check of the pointer tag (if `Foo` and
 `Result` do not have too many constructors).

 Note that `Result` could have additional constructors, but only one can be
 eliminated. This one constructor needs to

   * have one argument
   * be strict in that argument
   * that argument must be an algebraic data type (even after this
 flattening) does not have `NotOk` as a constructor.

 We currently cannot do this in `Core`, but we could if our safe coercions
 were directed.

 Do you think you have a case where this could give a performance boost?
 Maybe some parser library? You can try this now using pattern synonyms and
 `unsafeCoerce`. If you think there is something to be gained here, then we
 can consider implementing this.

-- 
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14826
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler