SIC 305, Slot 2: Monday 9.30-10.25, Tuesday 10.35-11.30, Thursday 11.35-12.30
TA: Abhirup Ghosh (abhirup@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., exploiting multi-core CPUs
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.
Plan/log of lectures
Lectures 1,2 (3, 4 January 2011)
Course introduction.
Introduction to code optimization - kinds of optimization, levels of optimization
Lecture 3 (6 January 2011)
Optimizing transformations - compile time evaluation, CSE, constant propagation, variable propagation, code movement optimization,
loop optimization
Safety of code movement
Lecture 4 (10 January 2011)
Strength reduction, loop test replacement, Dead code elimination
DAG based local optimization
Lecture 5 (11 January 2011)
Abstract syntax tree, triples, quadruples.
Global optimization: Control flow analysis---dominators and post dominators. Data flow analysis---available expressions
Lecture 6 (13 January 2011)
Quiz 1
Data flow property, Transfer functions for basic blocks.
Lecture 7 (17 January 2011)
Available expressions.
MOP solution. Data flow equations.
Lecture 8 (18 January 2011)
Iterative solution of data flow equations.
Complexity of round-robin iterative data flow analysis.
Lecture 9 (18 January 2011)
Reaching definitions and Live variables.
The meet semi-lattice: Determining the lattice top and lattice bottom elements,
partial order, etc.
Initializations of iterative data flow analysis for obtaining MFP.
Lecture 10 (24 January 2011)
Busy and very busy expressions.
Revisiting the meet semi-lattice theory---Monotonicity and its implications for
complexity of round robin iterative analysis.
Worklist iterative data flow analysis.
Elements of the partial redundancy elimination (PRE) problem.
Lecture 11 (25 January 2011)
Partial redundancy elimination (PRE)---overview, historical.
PRE by using eliminatability paths.
Lecture 12 (31 January 2011)
E-path_PRE data flows and example.
Introduction to the SSA form.
Lecture 13 (1 February 2011)
Constant propagation using the SSA form (Paper by Wegman, Zadeck):
Simple constant, Sparse Simple constant. Ideas of Simple conditional constant
propagation.
Lecture 14 (3 February 2011)
Sparse Conditional Constant Propagation.
Construction of the SSA representation (paper by Cytron et al.)
Lecture 15 (7 February 2011)
Discussion on construction of SSA representation.
Control dependence and its use in program slicing.
Introduction to register assignment.
Lecture 16 (8 February 2011)
Approaches to register assignment by Chow-Hennessey and Chaitin et al.
Chow-Hennessy approach.
Lecture 17 (10 February 2011)
Chow-Hennessy approach to register assignment.
Key idea of improved colouring approach by Briggs et al.
Lecture 18 (14 February 2011)
Comparison of Chow_Hennessy and Chaiting approaches.
Optimal code generation for expressions: Key issues---instruction selection,
evaluation order, register utilization.
Parsing and pattern matching approaches.
Lecture 19 (15 February 2011)
Optimal code generation for expressions: Ershov approach---contiguous evaluation of an expression, register requirement of nodes in expression trees.
Overview of the Aho-Johnson approach. Width of program.
Lecture 20 (17 February 2011)
Strongly contiguous evaluation of an expression.
Lecture 21 (28 February 2011)
Code generation algorithm of Aho-Johnson.
Lecture 22 (1 March 2011)
Instruction-level parallelism.
Lecture 23 (3 March 2011)
Instruction scheduling within basic blocks.
Lecture 24 (7 March 2011)
Mid-sem #2.
Lecture 25 (8 March 2011)
Global scheduling of code.
Lecture 26 (10 March 2011)
Software Pipelining.
Lecture 27 (14 March 2011)
Software pipelining of acyclic dependences.
Lecture 28 (15 March 2011)
Software pipelining of cyclic dependences.
Lecture 29 (17 March 2011)
Software pipelining of cyclic dependences (contd.).
``Advanced compiler optimizations for supercomputers", by Padua, Wolfe,
CACM, 1986.
Lecture 30 (21 March 2011)
Padua-Wolfe paper (contd.)
Lecture 31 (25 March 2011)
Impact of loop fusion and loop fission on cache performance.
Concurrentization in the presence of loop-carried dependences.
Affine expressions in array access. Iteration spaces. Data dependence and
data reuse.
Lecture 32 (24 March 2011)
Overview of concurrentization in presence of loop-carried dependences ---
Affine space partitioning.
Representing the iteration space: Matrix representation of inequalities.
Projection. Fourier-Metzkin elimination.
Lecture 33 (28 March 2011)
Determination of loop bounds. Change of axis.
Lecture 34 (29 March 2011)
Legality of loop interchange.
Detection of data reuse.
Lecture 35 (31 March 2011)
Affine partitioning---formulation of space-partition constraints.
Lecture 36 (5 April 2011)
Determining processor loop bounds in concurrentized program.
Lecture 37 (7 April 2011)
Improving a concurrent program: Eliminating empty iterations.
Lecture 38 (11 April 2011)
Improving a concurrent program: Eliminating tests from loops.
Lecture 39 (12 April 2011)
Primitive affine transforms.