SIC 304, Slot 2: Monday 9.30-10.25, Tuesday 10.35-11.30, Thursday 11.35-12.30

TA: Ambika Agarwal (ambika@cse).

Course coverage:

This course will cover the following topics:

    1. Code optimization
    2. Data flow analysis
    3. Register assignment
    4. Vectorization and parallelization of code     5. Generation of high quality target code
    6. 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. The 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.

Log of lectures (compiled by Jojumon Kavalan)

Lecture 2 & 3 - 5/01/10 & 7/01/10
Introduction to code optimization - kinds of optimization, levels of optimization
Optimizing transformations - compile time evaluation, CSE, constant propagation, variable propagation, code movement optimization,
loop optimization
Safety of code movement

Lecture 4 - 11/01/10
Strength reduction, loop test replacement, Dead code elimination
DAG based local optimization

Lecture 5 - 12/01/10
Abstract syntax tree, triples, quadruples.
Global optimization: Control flow analysis---dominators and post dominators. Data flow analysis---available expressions

Lecture 6 - 14/01/10
Data flow property, Data flow equations, distributivity of DF problem.

Lecture 7 - 18/01/10
Separability of DF solution, lattice theory, meet over path, fixed point and maximum fixed point.
Reaching definitions

Lecture 8 - 19/01/10
Round-robin iterative data flow analysis, monotonicity and convergence of iterative DFA, complexity of data flow analysis.
Worklist based iterative technique

Lecture 9 - 21/01/10
Complexity of worklist approach.
Reaching definitions, live variables, busy expressions, very busy expressions Introduction to register assignment.

Lecture 10 - 25/01/10
Live range, Chow-Hennessy register allocation.

Lecture 11 - 28/01/10
Interference graph, Live range splitting in Chow-Hennessy approach.
Static single assignment(SSA), def-use chain.

Lecture 12 - 01/02/10
Sparse simple constant propagation, conditional constant propagation, sparse conditional constant propagation.

Lecture 13 - 02/02/10
Sparse Conditional Constant.
Conversion to the SSA form: Dominance frontier, placement of phi function, renaming.
Control dependence.

Lecture 14 - 04/02/10
Tutorial on data flow analysis for CSE.
Register allocation paper by Briggs.

Lecture 15 - 08/02/10
Register Allocation paper by Briggs (Contd.)
Introduction to partial redundancy elimination (PRE).

Lecture 16 - 09/02/10
Epath-PRE.

Lecture 17 - 22/02/10
Advanced compiler optimization for supercomputers (Padua and Wolfe paper).
Advanced architectures - vector instructions, multi-core systems Data dependence - Flow/true, anti, and output dependences.
Loop independent and loop carried dependences. Control dependence.

Lecture 18 - 23/02/10
Tutorial on topics covered in lecture 17. Effect of dependences in nested loops.

Lecture 19 - 25/02/10
Allen and Kennedy paper on Vector code generation. Code improving transformations - variable renaming, loop interchanging

Lecture 20 - 02/03/10
Code improving transformations contd - thresholding.
Parallelization of programs (based on chapter 11 in ALSU book) Types of parallelization, issues with synchronization and communication, blocking to improve cache performance. SPMD.
Basic affine transformations - fission, fusion, re-indexing, scaling.

Lecture 21 - 04/03/10
Basic affine transformations contd- reversal, permutation, skewing.
Matrix formulation of inequalities. Self re-use, group-reuse, affine partitions.

Lecture 22 - 08/03/10
Affine expressions. Self spatial use, more on group re-use. Basis vector of null space.
Example of affine space partition

Lecture 23 - 09/03/10
Example of affine space partition revisited and worked out

Lecture 24 - 11/03/10
Code generation - issues in code generation, Sethi-Ullman algorithm, introduction to Aho-Johnson algorithm

Lecture 25 - 15/03/10
Aho-Johnson algorithm contd - machine model, register re-arrangement theorem, contiguous programs

Lecture 26 - 18/03/10
Aho-Johnson algorithm contd - Cover algorithm, mark algorithm, code generation Introduction to RISC architecture, pipelined machines and speculative load instruction machines

Lecture 27 - 22/03/10
Code scheduling constraints Pipelined machines, VLIW machines, special instructions (prefetch, predicated instructions, etc) Code scheduling (local)

Lecture 28 - 23/03/10
Code scheduling (local)contd. Global code scheduling - hoisting of instructions, sinking of instructions, global scheduling algorithm, control equivalence, dominated successor Aho-Johnson algorithm revisited

Lecture 29 - 25/03/10
Software pipelining - machine model, inter iteration interval, bound on inter iteration interval due to resource constraints and data dependence

Lecture 30 - 30/3/10
Software pipelining contd. - Scheduling algorithm for acyclic graph, example

Lecture 31 - 05/04/10
Software pipelining example contd., scalar expansion

Lecture 32 - 06/04/10
Alias analysis - may alias, must alias, flow sensitive alias, flow insensitive alias

Lecture 33 - 08/04/10
Discussion on Aho-Johnson algorithm