[GHC] #9476: Implement late lambda-lifting

[GHC]

#9476: Implement late lambda-lifting
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  sgraf
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.8.2
      Resolution:                    |             Keywords:  LateLamLift
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #8763 #13286      |  Differential Rev(s):
       Wiki Page:  LateLamLift       |
-------------------------------------+-------------------------------------

Comment (by sgraf):

 > That seems correct doesn't it? i.e. the implementation doesn't lift such
 functions, and it shouldn't.

 The implementation doesn't lift these functions because we ''think'' they
 won't lead to a beneficial lift anyway. But that's rather a heuristic and
 for illustrative purposes (e.g., look how things get worse when we allow
 this) we ''could'' implement the transformation in a way that it can cope
 with these cases.

 But after having played with it for a few hours yesterday, I came to
 realise that this has more serious consequences than I anticipated. In
 addition to the StgApp case, the Constructor application and PrimOp cases
 are particularly egregious, because they require to return floats along
 with the actual tranformed RHS. I'm no longer convinced that the
 illustrative purpose justifies complicating the implementation so much.

 > So why do you say "I realised a few things here and there that I could
 change in the transformation"?

 In the process of writing the paper, I repeatedly had to double-check what
 the transformation does and that it actually does the right thing. For
 example, thinking about how to formulate the function computing closure
 growth resulting from a lifting decision lead me to realise that we in
 fact could make better use of strictness in addition to usage (i.e. one-
 shot) information.

 Example:

 {{{
 let f = [x y]. \z -> ...
     g = [x y f]. \u -> ... x ... y ... f u ...
 in g 1
 }}}

 What's the closure growth resulting from lambda lifting `f`? Previously,
 although `g`s closure would shrink by one slot (so closure growth -1 from
 `g`s RHS), we can't be certain that this benefit would be visible on every
 program path, so we'd have to return 0 here.

 But that's too conservative, because in fact `g` is called strictly with
 one argument (strictness demand `C(S)`), which means closure growth for
 the expression is actually -1 (not yet counting in the saved two slots
 from not having to allocate a closure for `f`).

 > What about the implementation. Are you done? Ready to submit a Phab
 patch for review? With an up-to-date wiki page describing what it does?

 I consider the implementation done (probably should've submitted a patch
 much earlier). I'll bring the wiki page up to date and then submit a patch
 within the next week or so.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9476#comment:42>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler