[GHC] #9476: Implement late lambda-lifting

[GHC]

#9476: Implement late lambda-lifting
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  sgraf
            Type:  feature request   |               Status:  closed
        Priority:  normal            |            Milestone:  8.8.1
       Component:  Compiler          |              Version:  7.8.2
      Resolution:  fixed             |             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):  Phab:D5224
       Wiki Page:  LateLamLift       |
-------------------------------------+-------------------------------------

Comment (by sgraf):

 So, why does lambda lifting more bindings lead to better code here?
 Honestly,
 I'm at a loss. I identified that lifting `go` below is what seems to lead
 to a
 smaller working set, or at least lifting just this function leads to above
 speedups:

 {{{
 foo = go z
   where
     go [] = z2
     go (y:ys) =
       let sat2 = go ys2
           sat1 = C x y z
       in sat1:sat2
     x = ...
     y = ...
     z2 = ...
 }}}

 `go` has three free vars: `x`, `y` and `z2`. Lifting `go` implies an
 increase in
 allocations, because the closure for `sat2` grows under a multi-shot
 lambda:

 {{{
 go x y z2 [] = z2
 go x y z2 (y:ys) =
   let sat2 = go x y z2 ys2
       sat1 = C x y z
   in sat1:sat2

 foo = go x y z2 z
   where
     x = ...
     y = ...
     z2 = ...
 }}}

 Yet, the working set for the GC gets smaller, so it seems like the second
 version produces more, but shorter-lived garbage. Or at least the GC is
 smarter
 about the last version than about the first.

 I'm not sure what makes `go` so special! If I wouldn't have numbers, I'd
 totally
 say that it's not a worthwhile lift.

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