Implement late lambda lift
Needs ReviewPublic

Authored by sgraf on Fri, Oct 12, 5:19 AM.

Details

Reviewers
simonpj
bgamari
Trac Issues
#9476
Summary

This implements a selective lambda-lifting pass late in the STG pipeline.

Lambda lifting has the effect of avoiding closure allocation at the cost of having to make former free vars available at call sites, possibly enlarging closures surrounding call sites in turn.

We identify beneficial cases by means of an analysis that estimates closure growth.

There's a Wiki page at https://ghc.haskell.org/trac/ghc/wiki/LateLamLift.

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Branch
lift-lambda
Lint
Lint WarningsExcuse:
SeverityLocationCodeMessage
Warningcompiler/main/DynFlags.hs:893TXT3Line Too Long
Warningcompiler/main/DynFlags.hs:895TXT3Line Too Long
Warningcompiler/main/DynFlags.hs:897TXT3Line Too Long
Warningcompiler/main/DynFlags.hs:1784TXT3Line Too Long
Warningcompiler/main/DynFlags.hs:1785TXT3Line Too Long
Warningcompiler/main/DynFlags.hs:1786TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:142TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:162TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:184TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:196TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:231TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:268TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:359TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:362TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:397TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:400TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/Analysis.hs:422TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:51TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:55TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:74TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:159TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:182TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:187TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:190TXT3Line Too Long
Warningcompiler/simplStg/StgLiftLams/LiftM.hs:240TXT3Line Too Long
Unit
No Unit Test Coverage
Build Status
Buildable 23160
Build 54854: [GHC] Linux/amd64: Continuous Integration
Build 54853: [GHC] OSX/amd64: Continuous Integration
Build 54852: [GHC] Windows/amd64: Continuous Integration
Build 54851: arc lint + arc unit
sgraf created this revision.Fri, Oct 12, 5:19 AM
sgraf added a comment.EditedFri, Oct 12, 5:26 AM

I identified a few points worth discussing below.

I don't have the latest benchmarking numbers available on this machine, but https://ghc.haskell.org/trac/ghc/ticket/9476#comment:34 is still accurate.

The wiki page should be up to date now.

Edit: Also, this still lacks a unit test suite. Let's see what I can cook together...

compiler/simplStg/StgLiftLams/Analysis.hs
226

Is it OK to use demand info this late in the STG pipeline?

381

Note that this bit of code means we migh optimise differently when profiling. Is this acceptable behavior?

sgraf updated this revision to Diff 18303.Sat, Oct 13, 10:47 AM
  • Move StgSubst to stgSyn
  • Comments only
  • Remove dead binder
sgraf updated this revision to Diff 18382.Fri, Oct 19, 12:04 PM
  • Comments only

Here's a paste with the NoFib results: P189

Harbormaster edited this Differential Revision.Fri, Oct 19, 2:30 PM