[GHC] #9476: Implement late lambda-lifting

[GHC]

#9476: Implement late lambda-lifting
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  sgraf
            Type:  feature request   |               Status:  patch
        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):  Phab:D5224
       Wiki Page:  LateLamLift       |
-------------------------------------+-------------------------------------

Comment (by sgraf):

 I realised that while the heuristics currently employed work quite well,
 we are too pessimistic wrt. unsaturated applications.

 Currently, we don't lift binders that have undersaturated calls
 [https://github.com/sgraf812/ghc/blob/c4b8c04f26b5045da8015dd7289cd176a4addff2/compiler/simplStg/StgLiftLams/Analysis.hs#L250
 at all]. But there's nothing wrong with lifting those, as long as
 allocations don't get worse. So I set out to get rid of that heuristic and
 replaced it with a check that disallows occurrences in argument position
 instead (previously, this would be subsumed by the undersaturated call
 check).

 The results are inconclusive, with some significant slow-downs which I
 could pin-point to a bug in the heuristic that detects known calls.
 Currently, we say that a call to some variable would be lowered as a known
 call when `idArity bndr > 0`. But there actually are thunks (e.g. arity 0)
 of function type, which count as known calls. Abstracting over these
 thunks makes for an increase in allocation and runtime. I'm investigating
 more robust ways of detecting known calls.

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