CS6250: Advanced Compiler Optimizations

January 2015 - May 2015

Instructor: Ramakrishna Upadrasta (U. Ramakrishna)
Email: Ramakrishna AT iith DOT ac DOT in

Discussion Google-group: IITH-CompilerOpt-Jan15 AT googlegroups DOT com Join Group (only with IITH email-IDs)
Classes: Tue: 10:00am-11:30am, Fri: 8:30am-10:00am (D slot); Room: SSRL Lab conf. room

Credits: CS6250 3:0;
Prerequisites: CS6250: A grade of "A" in CS3020 and CS3021 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 (CS6250)

The objective of this course is to learn basic and advanced compiler optimization techniques, either traditional or modern in their scope, or scalar-variable based or loop-optimization based in their application or machine independent or dependent in their variety.

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 more high-level optimizations that are based on the static single assignment intermediate representation as well as low-level optimizations like register allocation, instruction scheduling and software pipelining.

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 or GPU 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 advanced 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

2nd-Jan-2015 Organization & Logistics,
An Overview of Compiler Optimizations
Introduction to Control-Flow Analysis
Dominators, Back Edges, Natural Loops, Interval analysis, T1-T2 analysis,
Reducibility (using back edges, Interval analysis and T1-T2 analysis). PDF

6th-Jan-2015 Control Flow Analysis (contd.) PDF

Readings (All)
6th-Jan-2015 Control Flow Analysis (contd.) PDF

Readings (All)
No classes.
Instructor at TIFR, Mumbai to attend POPL-2015 conference.

Readings (All): Projects document in the Google-drive folder
20th-Jan-2015 Discussions about projects
Readings (All): Projects document in the Google-drive folder
27th-Feb-2015 Control Dependence by Ferrante PDF
Control Dependence by Pingali-Bilardi PDF
Slides by Keshav Pingali PDF
30th-Jan-2015 Alias Analysis in LLVM by Utpal.
Basic-AA vs. no-alias vs. type based AA vs. global/mod ref vs. CFL-AA

Readings (All)
3rd-Feb-2015 Alias Analysis by Utpal (contd.)
Scalar Evolution by Aditya.

Readings (All)

Book References:

Some Class Links:

Suggested readings:

Grading (CS6250)

Activity Weight
Class Participation 10%
Written Assignments (scribes, paper summaries etc.) 15%
Mini Prog. Assignments 10%
Paper Presentations (in class) 10%
Mid Term Exam 20%
Project (Proposal+Writeup+Presentation+Impact) 35%