SIC 301, Slot 4: Monday 11.35-12.30, Tuesday 8.30-9.25, Thursday 9.30 - 10.25

A draft course description:

This course covers the following topics: code optimization, theory of data flow analysis, register assignment, optimal code generation, Use of execution-time information in optimization, current issues.

The course will contain individual or group projects and paper reading & presentation assignments.

The primary sources for the FIRST FEW lectures would be:

1. Chapter 10 of Aho-Sethi-Ullman Compilers book.

2. My slides on code optimization and data flow analysis  in postscript format.

3. My slides on Partial redundancy elimination  in PPT format.

4. A very useful supplementary source is :
Advanced Compiler Design & Implementation by Steven S Muchnick
Harcourt Asia/Morgan Kaufmann, 1997.

Homework 1 (Due ***): Problems 10.3 (except part (b)), 10.4, 10.5 (except part (a)), 10.6, 10.7 and 10.9 from Aho-Sethi-Ullman.

Homework 2 (Due ***): Problems 10.21, 10.24, 10.25 and 10.35 from Aho-Sethi-Ullman.

Homework 3 (Due ***): 1. Give an example of a specific data flow problem and an instance for which the MOP and MFP solutions are different.
2. Perform E-path_PRE for the program flow graph of Fig. 10.5 in Aho-Sethi-Ullman (page 591).

Plan/log of lectures:

Lecture 1 (3 Jan 2007) : Introduction to code optimization. Slides 1-17.

Lecture 2 (31 Dec 2003) : Optimization (contd.) Control and data flow analysis. Slides 18-29, 35-42.

Lecture 3 (2 Jan 2004) : Fundamentals of data flow analysis. Slides 43-51.

Lecture 4 (6 Jan 2004) : Fundamentals of data flow analysis (contd.) Slides 52-64.

Lecture 5 (7 Jan 2004) : Iterative data flow analysis: Round-robin iterative analysis. Slides 71-84. Worklist iterative analysis.

Lecture 6 (9 Jan 2004) : Lattice theoretic view of data flow analysis: Meet semi-lattice, `top' and `bot' elements, partial order, absence of total order. Properties of data of flow functions.
Performing data flow analysis: determining top, bot elements and meet operator for a data flow problem, monotonicity and distributivity (already done in lectures 4 and 5, resp.),
initializations to obtain MFP of data flow equations.

Lecture 7 (13 Jan 2004) : Review of lattice-theoretic foundations of data flow analysis. Introduction to partial redundancy elimination (PRE) using sources 4 and 5 above.

Lecture 8 (14 Jan 2004) : Partial redundancy elimination using source 4.

Lecture 9 (16 Jan 2004) : PRE data flows.

Lecture 10 (20 Jan 2004) : PRE completed. Worklist iterative data flow analysis.

Lecture 11 (21 Jan 2004) : Strength reduction (Cocke-Kennedy CACM 1976, Aho-Sethi-Ullman, Dhaneshwar-Dhamdhere Computer Languages, 1995: Soft copy available on my home page).
Introduction to SSA and Constant Propagation using SSA. (Refs: Cytron et al (Toplas v 13, n 4, 1994) and Wegman-Zadeck (Toplas v 13, n 2, 1991)).

Lecture 12 (23 Jan 2004) : Iterated join and Iterated dominance frontiers. \phi insertion.

Lecture 13 (27 Jan 2004) : Conversion of a program to SSA Form: Computation of dominance frontier. Renaming. The notion of data dependence. Computing control dependence.

Lecture 14 (28 Jan 2004) : Tutorial: Applications of data and control dependence: Slicing.

Lecture 15 (30 Jan 2004) : Tutorial: Static and dynamic slicing (contd.)

Lecture 16 (3 Feb 2004) : Tutorial: Dynamic slicing (deferred). Preliminary ideas on JIT, Applications of profiling to optimization (hot paths), Problems in debugging of optimized code.

Lecture 17 (4 Feb 2004) : Hot path analysis, etc.

Lecture 18 (6 Feb 2004) : Debugging of optimized code: Static and Dynamic currency analysis.
Register allocation: Correctness conditions for 1-1, many-1 and many-few allocation.

Lecture 19 (10 Feb 2004) : Dynamic currency analysis. A brief 5 minute overview of Chow, Hennessy paper.

Lecture 20 (11 Feb 2004) : Graph colouring based approaches for register allocation. (Refs: Chow, Hennessy and Briggs et al.)

Lecture 21 (13 Feb 2004): Register assignment (contd.)
Introduction to generalized theory of bit vector data flow analysis- Height of the lattice and closure of a data flow function.

Lecture 22 (17 Feb 2004): Generalized theory (contd.)
Separability of solution and Effective height of lattice. Influence of effective height on complexity of data flow analysis.

Lecture 23 (20 Feb 2004): Generalized theory (contd.)
Loop closure again. Section 3.3: Safe assignment and fixed point. Information flow paths. Complexity of data flow analysis.
Generalized data flow equations.

Lecture 24 (3 March 2004): Introduction to code generation issues: Instruction selection and Evaluation order.
Limitations of code generation through LR parsing. Sethi-Ullman algorithm.
Why Aho-Johnsonn algorithm is important: Handles k-ary instructions, Handles instructions like r <- ind + r c.

Lecture 25 (5 March 2004): Aho-Johnson algorithm---Normal form, Cover algorithm, Dynamic programming.

Lecture 26 (8 March 2004): Aho-Johnson: Cover algorithm. Cost evaluation. Code generation algorithm.

Lecture 27 (10 March 2004): Aho-Johnson: Code generation algorithm.
Introduction to Chase paper. Pattern Forest. Finding matchsets.

Lecture 28 (12 March 2004): Chase: Table generation algorithm.

Lecture 29 (16 March 2004): Chase: Aj equivalence. Generation of compressed tables.

Lecture 30 (17 March 2004): Balachandran paper: Machine grammar. Minimum cost Derivations.
Rule cost and cost of rule. Item-sets. Preliminaries of building item-sets.

Lecture 31 (19 March 2004): Balachandran paper: Building item sets. NT-closure. Outline of the algorithm. A-j equivalence.

Lecture 32 (23 March 2004): Aho and Johnson revisited: Mark algorithm problems. Using the algorithm for an `n' register machine with a variable no of registers reserved for global allocation.

Lecture 33 (24 March 2004): Balachandran paper: Beta and Alpha equivalence.

Lecture 34 (26 March 2004): Hennessy and Gross: Interlocks. Blocking of the code generator. Implications of Safe Position.

Lecture 35 (30 March 2004): Hennessy and Gross: Safe position. Safe Path. Implications of non-overlapping safe paths and code scheduling without blocking.