Optimising Compilers

Lecturer: Dr A. Mycroft (am@cl.cam.ac.uk)

No. of lectures: 12

Prerequisite course: Compiler Construction

Introduction and motivation.

Outline of an optimising compiler. Optimisation partitioned: analysis shows a property holds which enables a transformation.

Kinds of optimisation.

Local optimisation, peephole optimisation, code selection, instruction scheduling. Global optimisation, common sub-expressions, code motion, strength reduction. Interprocedural optimisation.

Classical dataflow analysis.

Graph algorithms, live and avail sets. Register allocation by register colouring. Common sub-expression elimination. 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.

Recommended book:

Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: Principles, Techniques and Tools. Addison-Wesley.