SIC 201, Slot 5: Wednesday 9.30-10.55, Friday 9.30-10.55

Course coverage:

This course will cover the following topics:

    1. Code optimization
    2. Data flow analysis
    3. Register assignment
    4. Generation of high quality code
    5. Selected current topics, e.g., use of execution-time information in optimization and in debugging of optimized code.

For each topic, we cover the classical techniques and a few research papers.

The course will contain homework assignments (with very little weightage), group projects, individual paper reading & presentation assignments, and exams.

The primary sources for the FIRST FEW lectures would be:

    1. Chapter 10 of Aho-Sethi-Ullman Compilers book, or corresponding material in Aho-Lam-Sethi-Ullman Compilers book.

    2. Slides on code optimization and data flow analysis ( pdf version.)

    3. Slides on partial redundancy elimination  and a brief paper on E-path based PRE  

    4. Advanced Compiler Design & Implementation, Steven S Muchnick, Harcourt Asia/Morgan Kaufmann, 1997.

Honesty policy

Unless otherwise specified, students are both permitted and encouraged to discuss assignment problems but each person must write his/her own assignment completely independently.

Discussion of project ideas is also permitted and encouraged, but looking over other persons' code is forbidden.

Plan / Log of lectures

Lecture 1 (5 Jan 2009) : Introduction to the course. Cost-effectiveness of optimization. Role of execution frequency information.

Lecture 2 (6 Jan 2009) : Introduction to optimization. Slides 1--11.

Lecture 3 (9 Jan 2009) : Variable propogation. Code movement and loop optimization.
Introduction to partial redundancy elimination. Notion of safety.

Lecture 4 (14 Jan 2009) :
Loop test replacement and dead code elimination. Slides 12--23.
Local optimization. Slides 20--28.

Reference for local optimization: Muchnick, pp 344-348.

Lecture 5 (16 Jan 2009) : Global optimization: control flow analysis. Introduction to data flow analysis. The notion of available expressions.
MOP and Data flow equations-based analysis for available expressions.
Slides 35 onwards.

Lecture 6 (21 Jan 2009) : Distributivity of data flows. Reaching definitions, and Live variables.
Forward and backward data flows.

Lecture 7 (23 Jan 2009) : The data flow of busy expressions.
Solution of data flows: Monotonicity and convergence of iterative data flow analysis.
Depth of a program flow graph and complexity of iterative data flow analysis.
Worklist iterative data flow analysis.

Lecture 8 (28 Jan 2009) : Lattice theoretic foundations of data flow analysis.
Definition of MFP; initializations for obtaining the MFP.
Effective height of a lattice and k-boundedness.

Lecture 9 (30 Jan 2009) : Chow-Hennessy approach to register assignment. Live ranges. Interference graph.
Non-interference and consistency of assignment.

Lecture 10 (4 Feb 2009): Improvements to graph-colouring based approach to register assignment.

Lecture 11 (6 Feb 2009): Partial redundancy elimination.

Lecture 12 (11 Feb 2009): Partial redundancy elimination.

Lecture 13 (13 Feb 2009): Conversion to SSA-form. Sparse Conditional Constant algorithm.

Lecture 14 (25 Feb 2009) : Use of Data and control dependence information in program slicing.
Problems in debugging of optimized code: Dynamic currency determination. (Ref Dhamdhere-Sankaranarayanan paper .)

Lecture 15 (27 Feb 2009) : Static currency determination. Recovery of noncurrent variables.

Lecture 16 (4 March 2009) : Code generation: Ershov numbers, contiguous evaluation, Aho-Johnson algorithm

Lecture 17 (6 March 2009) : Aho-Johnsom contd.
Presentation of paper reading assignment

Lecture 18 (13 March 2009) : Presentation of paper reading assignment.

Lecture 19 (18 March 2009) : Aho-Johnson contd. Proebsting-Fischer paper.

Lecture 20 (20 March 2009) : Proebsting-Fischer paper.

Lecture 21 (25 March 2009) : Local and Global code scheduling. ALSU book.

Lecture 22 (27 March 2009) : Software pipelining : Acyclic dependences. ALSU book.

Lecture 23 (1 April 2009) : Software pipelining : Cyclic dependences. ALSU book.

Lecture 24 (3 April 2009) : Alias analysis from Muchnick book.

Lecture 25 (8 April 2009) : Alias analysis from Muchnick book.

Lecture 26 (10 April 2009) : Interprocedural side-effect analysis from Muchnick book