Next: Security
Up: Lent Term 2001: Part
Previous: Numerical Analysis II
Lecturer: Dr A. Mycroft
(am@cl.cam.ac.uk)
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.
Phase-order problem.
- Kinds of optimisation.
Local optimisation, peephole optimisation, code selection, 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.
- Functional program analysis.
Abstract interpretation. Strictness analysis.
Control flow analysis for
lambda-calculus.
Rule-based inference of program properties.
Types and effect systems.
- Target-dependent optimisations.
Instruction selection. Instruction scheduling.
Scheduling may require additional registers.
- De-compilation.
Legal/ethical issues. Some basic ideas, type discovery and inference.
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
Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers:
Principles, Techniques and Tools. Addison-Wesley.
Hankin, C.L., Nielson, F. & Nielson, H.R. (1999).
Principles of Program Analysis. Springer.
Next: Security
Up: Lent Term 2001: Part
Previous: Numerical Analysis II
Christine Northeast
Wed Sep 20 15:13:44 BST 2000