Advanced compiler construction seminar

Main course literature

• (PJ92): Simon Peyton Jones, "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine", JFL 2 (1992)
• (MPJ06): Simon Marlow and Simon Peyton Jones, "Making a fast curry: push/enter vs. eval/apply for higher-order languages", JFL 16 (2006).
• (Boq99) Urban Boquist, "Code Optimisation Techniques for Lazy Functional Languages",, 1999. Also available in a 2-pages-on-1 version

Additional reading

• How to install UHC on your system, or specifically How to install UHC on a Windows system
• The architecture of UHC (with slides)
• Technical overview of EHC source files
• GHC implementation commentary

Meetings

• Monday 9 Nov 2009 (13.15-15.00 hour, room BBL-509)
  Introduction.
• Thursday 12 Nov 2009 (9.45-11.30 hour, room BBL-471)
  Read PJ92 sec 1-3
  Read MPJ06 sec 1-3
• Monday 16 Nov 2009 (13.15-15.00 hour, room BBL-509)
  Read PJ92 sec 4: Haskell to STG translation
  Read MPJ06 sec 4: operational semantics
  Skim PJ92 sec 5: operational semantics
  Skim MPJ06 sec 5: implement push/enter
  Read MPJ06 sec 6: implement eval/apply
• Thursday 19 Nov 2009 (9.00-10.30 hour, room BBL-471)
  Read PJ92 sec 6-8: jumps in C, heap layout,
  Skim PJ92 sec 9: compilation to C
  Read MPJ06 sec 7-8: results
• Monday 23 Nov 2009 (13.15-15.00 hour, room BBL-509)
  Read Boq99 chapter 1 (skip sec 1.3) (=16 pages)
  Read Boq99 chapter 2 (=37 pages)
  View EHC/src/ehc/GrinCode/AbsSyn.cag
  Challenge: download the GHC sources and find the implementation of stgApplyNP. Hint: it is spelled stg_ap_
• Thursday 26 Nov 2009 (9.00-10.45 hour, room BBL-471)
  Read Boq99 chapter 3 (=13 pages)
  Read Boq99 chapter 4 until page 88 (=12 pages)
  Compare it to the paper describing the implementation as used in EHC (section 1-3)
  
• Monday 30 Nov 2009 (13.15-15.00 hour, room BBL-509)
  Read the remainder of the EHC Implementation paper.
  compare it with the implementation of the HPT algorithm in the EHC source repository:
  - /src/ehc/GrinCode/Common.chs (some common data types an functions)
  - /src/ehc/GrinCode/PointsToAnalysis.cag (the collection of Euqations describing properties of the program)
  - /src/ehc/GrinCode/SolveEqs.chs (a fixpoint algorithm for solving the equations)
• Thursday 3 Dec 2009 (9.45-11.30 hour, room BBL-471)
  Read Boq99 until page 137 (=49 pages)
• Monday 7 Dec 2009 (13.15-15.00 hour, room BBL-509)
  Read rest of Boq99.
• Thursday 10 Dec 2009 (9.45-11.30 hour, room BBL-471)
  Read Haskell Program Coverage by Andy Gill and Colin Runciman, Haskell Workshop 2007.
• Monday 14 Dec 2009 (13.15-15.00 hour, room BBL-509)
  Read Secrets of the Haskell Inliner by Simon Peyton Jones and Simon Marlow, (revised edition for JFP 2002), pages 1-21.
• Thursday 17 Dec 2009 (9.45-11.15 hour, room BBL-471)
  Read the rest of the Inlining paper (page 22-46).
• Monday 11 Jan 2010 (13.15-15.00 hour, room BBL-458)
  First session in the new year.
• Thursday 14 Jan 2010 (10.00-11.40 hour, room BBL-079)
  Project work.
• Monday 18 Jan 2010 (13.15-15.00 hour, room BBL-458)
  Project work.
• Thursday 21 Jan 2010 (10.00-11.40 hour, room BBL-079)
  Project work.
• Monday 25 Jan 2010 (13.15-15.00 hour, room BBL-458)
  Project work.
• Thursday 28 Jan 2010 (10.00-11.40 hour, room BBL-079)
  Project work.
• Monday 1 Feb 2010 (13.15-15.00 hour, room BBL-458)
  Project work.
• Thursday 4 Feb 2010 (11.00-12.45 hour, room BBL-079)
  Final project presentations.
  • 11.00: Timon Bijlsma and Tamar Christina: Stack tracing
    Sometimes even Haskell programs crash with a runtime error. Calling head on an empty list crashes the program, but which call to head was the culprit? Adding explicit stack traces to the program makes it possible to print the call stack in case of errors.
  • 11.20: Remy Willems and Julian Verdurmen: Inlining
    Our project's subject is inlining and more specificaly improving the inliner present in the EHC compiler. We have implemented the inlining of mutual recursive functions using loopbreakers, and are trying to unfold calls to recursive functions.
  • 11.40: break
  • 11.55: Levin Fritz: Cases
    The whole-program optimization backend of UHC generates C code with a large number of switch statements, which are used to distinguish between different constructors and functions. I tried different ways to create these statements in order to improve the performance of generated code.
  • 12.10: Steven Keuchel and Bas van Gijzel: Helium
  • 12.30: Ruud Koot: LVM