CS 614 ADVANCED COMPILERS

SIC 305, Slot 5: Wednesdays and Fridays 9.30 - 10.55 am

TA: Rahul Sharma (rahulsh@cse)

Office Hours: 10.55 am onwards on Wednesdays and Fridays outside SIC-305 and by mutual agreement at other times (send me a mail to fix the time).


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, compilation of atomic operations.

For each topic, we cover the classical techniques and a few research papers. Lectures will use active learning techniques extensively.

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.

Any evidence of use of dishonest means will be dealt with strictly but fairly.

Plan/log of lectures

Lectures 1 and 2 (20 and 22 July 2016)
Course introduction: Desirable compilers background. Description of course contents.
Introduction to code optimization.

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 (27 July 2016)
Optimizing transformations of (a) Compile-time optimization, (b) Common subexpression elimination, (c) Constant and variable propagation
Stating preconditions for optimizations
DAG-based local optimization
Overview of Global optimization. Control Flow analysis. The Control Flow Graph.

Lecture 4 (29 July 2016)
Data flow concepts---Notions of Available expressions and Reaching definitions
State preconditions of CSE and constant propagation using Available expressions and Reaching definitions
Dead code elimination and the notion of Live Variables

Lecture 5 (3 August 2016)
Approaches to Data flow analysis. The notion of data flow function of a basic block.
The meet over paths (MOP) approach.
Approach using data flow equations: Setting up data flow equations. Iterative data flow analysis. The issue of initializations.

Lecture 6 (5 August 2016)
Data Flow Analysis in GCC: Tutorial conducted by TA Rahul Sharma.

Lecture 7 (10 August 2016)
Issues in round-robin iterative data flow analysis---Initializations, fixed point, termination, and complexity.
Lattice theory foundations for data flow analysis. Importance of distributivity and monotonicity of data flows.

Lecture 8 (12 August 2016)
Implications of k-boundedness. Bit vector problems and separability of solution.
Depth of a CFG. Worklist iterative data flow analysis.

Notions of safey of code placement.

Lecture 9 (17 August 2016)
Partial redundancy elimination and subsumption of CSE and loop optimization. Computational optimality and lifetime optimality.
Introduction to E-path_PRE. (from slides)

Lecture 10 (19 August 2016)
E-path_PRE (completed)
The SSA representation of programs and sparse data flow analysis. Constant Propagation problems (from Wegmna-Zadeck paper). Algorithm SSC.

Lecture 11 (24 August 2016)
Constant propagation problems (Contd.)---Sparse simple constant and sparse conditional constant algorithms.
Construction of the SSA form (from Cytron et al paper)