Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Tripos Syllabus - Optimising Compilers
Computer Laboratory > Computer Science Tripos Syllabus - Optimising Compilers

Optimising Compilers next up previous contents
Next: Quantum Computing Up: Lent Term 2005: Part Previous: Numerical Analysis II   Contents


Optimising Compilers

Lecturer: Dr A. Mycroft

No. of lectures: 16

Prerequisite course: Compiler Construction


Aims


The aims of this course are to introduce the principles of program optimisation and related issues in decompilation. The course will cover optimisations of programs at the abstract syntax, flowgraph and target-code level. It will also examine how related techniques can be used in the process of decompilation.


Lectures

  • Introduction and motivation. Outline of an optimising compiler. Optimisation partitioned: analysis shows a property holds which enables a transformation. The flow graph; representation of programming concepts including argument and result passing. The phase-order problem.

  • Kinds of optimisation. Local optimisation: peephole optimisation, instruction scheduling. Global optimisation: common sub-expressions, code motion, strength reduction. Interprocedural optimisation. The call graph.

  • Classical dataflow analysis. Graph algorithms, live and avail sets. Register allocation by register colouring. Common sub-expression elimination. Spilling to memory; treatment of CSE-introduced temporaries. Data flow anomalies. Static Single Assignment (SSA) form.

  • Higher-level optimisations. Abstract interpretation, Strictness analysis. Constraint-based analysis, Control flow analysis for lambda-calculus. Rule-based inference of program properties, Types and effect systems.

  • Target-dependent optimisations. Instruction selection. Instruction scheduling and its phase-order problem.

  • De-compilation. Legal/ethical issues. Some basic ideas, control flow and type reconstruction.


Objectives


At the end of the course students should

  • be able to explain program analyses as dataflow equations on a flowgraph

  • know various techniques for high-level optimisation of programs at the abstract syntax level

  • understand how code may be re-scheduled to improve execution speed

  • know the basic ideas of decompilation


Recommended books


* Nielson, F., Nielson, H.R. & Hankin, C.L. (1999). Principles of program analysis. Springer. Good on part A and part B.
Appel, A. (1997). Modern compiler implementation in Java/C/ML (3 editions).
Muchnick, S. (1997). Advanced compiler design and implementation. Morgan Kaufmann.
Wilhelm, R. (1995). Compiler design. Addison-Wesley.
Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: principles, techniques and tools. Addison-Wesley. Now a bit long in the tooth and only covers part A of the course.



next up previous contents
Next: Quantum Computing Up: Lent Term 2005: Part Previous: Numerical Analysis II   Contents
Christine Northeast
Wed Sep 8 11:57:14 BST 2004