Optimising Compilers

Handout and slides PDF - the notes followed by slides 8-up

Further information:

• A summary of the 3-address instuctions used as intermediate code in the course.
• Dominic Orchard's explanation of Constraint-Based Analysis
• addr3.c, a 1-page C program to convert arithmetic expressions into 3-address code (cf. TRN from the Part IB Compiling Techniques course)
• Domagoj Stolfa's example register allocator that demonstrates some of the concepts from the course (graph colouring, clash graphs, spilling)
• Exercise sheets: ex1, ex2, ex3, ex4.
  (Thanks to Alan Mycroft, Dominic Orchard, Tomas Petricek, Raoul Urma and Tobias Kohn for suggesting exercises and solutions.)

Some of the articles referenced in the notes. (Note: although these are listed as `background reading', it is not expected that candidates know this material -- it is really only there for keen interests such as potential PhD students in this area and even so much of it pretty inaccessible. An exception is the Decompilation Page which is very readable, as well as the CACM article on compiler optimisations.)

• CACM article on exploring compiler optimisations and the Compiler Explorer website it describes.
• The Decompilation Page and its Legality of Decompilation page appearing as part of www.program-transformation.org WIKI.
• Cifuentes, C. Reverse Compilation Techniques [not for the fainthearted],
  PhD thesis, University of Queensland, 1994.
  First 8 pages of Chapter 6 of Cifuentes' PhD
• Mycroft, A. and Norman, A.C. Optimising compilation---classical imperative languages. Proc. XIX SOFSEM 92, Ždiar, Czechoslovakia. INFOSTAT, Bratislava, 1992. Also available in technical report 269, Cambridge University Computer Laboratory.
• Mycroft, A. and Norman, A.C. Optimising compilation---lazy functional languages. Proc. XIX SOFSEM 92, Ždiar, Czechoslovakia. INFOSTAT, Bratislava, 1992. Also available in technical report 269, Cambridge University Computer Laboratory.
• Mycroft, A. Type-Based Decompilation [not for the fainthearted].
  Lecture Notes in Computer Science: Proc. ESOP'99, vol. 1576, Springer-Verlag, 1999.
• Johnson, N.E. and Mycroft, A. Combined Code Motion and Register Allocation using the Value State Dependence Graph [not for the fainthearted].
  Lecture Notes in Computer Science: Proc. CC'03, vol. 2622, Springer-Verlag, 2003.
• Touati, S.-A.-A. Register Pressure in Instruction Level Parallelism [not for the fainthearted],
  PhD thesis, University of Versailles, 2002.

Access to some of these links is restricted to machines within the Computer Laboratory.

Thanks to Alan Mycroft for drawing most of this together over a number of years.