Course coverage:

This course will cover the following topics:

    1. Code optimization
    2. Techniques of data-flow analysis
    3. Register assignment
    4. Generation of high quality target code
    5. Vectorization and parallelization of code
    6. (Subject to feasibility) Selected current topics in compilation techniques and their applications, e.g., exploiting multi-core CPUs, parallelization of data flow analysis and optimization.

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. Compilers---Principles, Techniques, and Tools (Second edition), A. V. Aho, M. Lam, R. Sethi, J. D. Ullman, Pearson Education.
    2. Slides on code optimization and data-flow analysis
    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 (21 July 2014)
Course introduction: Desirable compilers background. Description of course contents.
Introduction to code optimization.

Lecture 2 (24 July 2014)
Concept mapping as a knowledge representation tool.  Slides on concept maps  An example: Pravin's concept maps zip file
Different kinds of language processors. Static and dynamic issues. Features of adaptive software.
Introduction to code optimization---Preconitions for an optimizing transformation.
Optimizing transformations of (a) Compile-time optimization, (b) Common subexpression elimination

Lecture 3 (28 July 2014)
Variable propagation.
Local and Global optimization---Control flow graph and Basic blocks, DAG-based local optimization.
Loop optimization.

Lecture 4 (31 July 2014)
Control flow analysis---Basic blocks and program points, depth-first numbering, reducible graphs, single entry regions and loops.
Code movement optimization. Safety of code movement optimization. Strength reduction and loop test replacement.

Lecture 5 (4 August 2014)
Exercise on designing an algorithm for strength reduction.
Introduction to data flow analysis. Available expressions. MOP solution of a data flow problem.

Lecture 6 (7 August 2014)
Data flow equations---round-robin iterative data flow analysis
Lattice theoretic framework for data flow analysis---determining lattice top and bot values; initializations for iterative data flow analysis.

Lecture 7 (11 August 2014)
Lattice theoretic framework for data flow analysis (contd.)---implications of distributivity, monotonicity and k-boundedness.
Bit-vector problems---separability of solution and 2-boundedness. Importance of 2-bounded problems.

Lecture 8 (18 August 2014)
Depth of a CFG and complexity of round-robin iterative data flow analysis. Worklist iterative data flow analysis.

Lecture 9 (22 August 2014)
Revisit 2-boundedness, depth of a CFG, and worklist iterative data flow analysis.
Introduction to partial redundancy elimination (PRE). Slides on partial redundancy elimination 

Lecture 10 (25 August 2014)
Safety of code insertion. Computational optimality and Lifetime optimality.
Eliminatability path and E_path_PRE data flow equations.

Lecture 11 (28 August 2014)
The SSA representation of programs.
Constant propagation algorithms from Wegman--Zadeck paper.
The constant propagation lattice. Sparse Simple Constant.

Lecture 12 (1 September 2014)
Constant propagation algorithms using SSA representation (contd.)
Sparse Conditional Constant.

Lecture 13 (4 September 2014)
Recap before mid-sem.

Lecture 14 (15 September 2014)
Efficient construction of SSA representation---Dominance frontier.

Lecture 15 (18 September 2014)
Control dominance and its use in dead code elimination.
Register assignment: Chow-Hennessy approach, Live ranges and Interference graph.

Lecture 16 (22 September 2014)
Chow-Hennessy register assignment approach.

Lecture 17 (25 September 2014)
Register assignment (Contd.) : Live ranges and live splitting in Chow-Hennessy algorithm.
Overview of optimistic colouring algorithm of Briggs et al.
Introduction to optimal code generation for expressions---Ershov numbers.

Lecture 18 (29 September 2014)
Revisit Ershow numbers and Sethi-Ullman algorithm. Introduction to Aho-Johnson algorithm for optimal code generation for expressions.

Lecture 19 (9 October 2014)
Aho=Johnson algorithm (contd.)

Lecture 20 (13 October 2014)
Code scheduling: Basic-block scheduling.

Lecture 21 (16 October 2014)
Code scheduling: Region scheduling.

Lecture 22 (20 October 2014)
Software pipelining: Scheduling of acyclic dependences.

Lecture 23 (27 October 2014)
Software pipelining: Scheduling of cyclic dependences.

Lecture 24 (30 October 2014)
``Advanced compiler optimizations for supercomputers", by Padua, Wolfe, CACM, 1986.
Data-dependence direction. Vectorization of loops.
Concurrentization of loops. Synchronization issues in concurrentization of loops.
Node splitting. Removal of output and antidependences.
Loop interchange for concurrentization and vectorization. Loop fission, loop fusion.

Lecture 25 (3 November 2014)
Introduction to optimization for parallelization and locality from A-L-S-U. Affine spaces.
Representing the iteration space: Matrix representation of inequalities.
Projection. Fourier-Metzkin elimination. Generation of loop bounds. Change of axes.

Lecture 26 (5 November 2014)
Synchronization free parallelization.