CS5863: Introduction to Program Analysis and Compiler Optimization

January 2022 - May 2022

Credits: 3 credits (includes theory as well as lab component)
Prerequisites: CS5863 A grade of "A" in CS3320 and CS3423 for 3rd/4th year B.Techs; Course CS6240 at IITH or its equivalent for M.Techs and PhDs (Primarily 1st years: exceptions allowed. Please get a permission from me.)

Course Description (CS5863)

The objective of this course is to learn basic and program analysis and compiler optimization techniques, either traditional or modern in their scope.

The initial part of the course would be devoted to a collection of traditional and classic compiler analyses and optimizations that are primarily based on control flow and data flow analyses. This would be followed by studying some representations and high-level optimizations that are based on the static single assignment intermediate representation.

The latter part of this course would be devoted to a model named polyhedral compilation where for-loops can be transformed to run efficiently on advanced architectures like multi-core CPUs, or GPUs using rational and integer linear programming techniques. Here, the focus would be on basics of the three phase process of dependence analysis, affine scheduling and code generation.

A large part of this course would be about either reading programm analysis or compiler optimization papers, or studying the implementations of optimizations in a compiler like LLVM, or implementing optimizations with a goal of obtaining performance/scalability improvements.

Lecture Schedule

In Google Drive.

Book References:

[Text Book] Compilers: Principles, Techniques, and Tools ("Dragon book") by Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, 2006
[Text Book] Advanced Compiler Design and Implementation by Steven Muchnick, 1997
[Text Book] Optimizing Compilers for Modern Architectures: A Dependence-based Approach by Randy Allen, Ken Kennedy, 2001
[Ref. Book] Compiler Design "Syntactic and Semantic Analysis" by Reinhard Wilhelm, Helmut Seidl and Sebastian Hack, 2013
[Ref. Book] Matthew S. Hecht. 1977. Flow Analysis of Computer Programs. Elsevier Science Inc., New York, NY, USA.
[Ref. Book] Uday Khedker, Amitabha Sanyal, and Bageshri Karkare. 2009. Data Flow Analysis: Theory and Practice (1st ed.). CRC Press, Inc., Boca Raton, FL, USA. IITB link
[Ref. Book] Handbook of Compiler Optimizations by Priti Shankar and Y.N. Srikant
[Ref. Book] Introductory Tutorials to Polyhedral Compilation by Alain Darte (2000), Martin Griebl (2001), Sanjay Rajopadhye (2002).
[NPTEL] NPTEL course on Principles of Compiler Design by Prof. Y.N. Srikant from Indian Institute of Science, 2012-2014 IITM Link
.....

Grading (Tentative)