CS614: Advanced Compilers

Offering: Spring 2025

About the course

A compiler is a fundamental software necessary to translate computer programs to a form that can be executed on intended machines. Designing a compiler involves learning several aspects of computer science: logic, formalism, mathematics, data structures, algorithms, programming, and so on. This course is a deep dive into the back-end of a compiler, covering fundamentals of and advancements in compiler optimizations, code generation, parallelization, as well as an introduction to dynamic compilation. At the end of the course, students should be able to appreciate the underlying concepts in compiler design, and be motivated to master the art of analyzing and transforming programs for performance.

Contents:

• Overview of compilation. Front-end recap. AST traversal using JavaCC and JTB. Object structures. Field and method resolution. IR generation for OO languages.
  

• Intro to program optimization. Control-flow graphs. Iterative dataflow analysis. Constant propagation. SSA form. SSA-enabled optimizations: conditional constant propagation, value numbering, partial redundancy elimination.
  

• Interprocedural optimizations. Call-graph construction. Class hierarchy analysis. Rapid type analysis. Pointer analysis. Devirtualization and method inlining.
  

• Memory management. Runtime layouts. Register allocation: Liveness and graph coloring, bitwidth-awareness.

• Code generation. Instruction selection. Pipelining and instruction scheduling.
  

• Cache optimizations. Data prefetching. Layout ordering. Loop transformations.
  

• Parallelization. Memory models. Loop-dependence analysis. MHP analysis.
  

• Managed runtimes. Dynamic compilation. Speculation and deoptimization.

References:

1. Steven S. Muchnick. Advanced Compiler Design and Implementation. Harcourt Asia Private Ltd, 2000.
2. Andrew W. Appel. Modern Compiler Implementation in Java. Cambridge University press, Second Edition.
3. Y. N. Srikant and P. Shankar (Ed.) The Compiler Design Handbook: Optimizations and Machine Code Generation. CRC Press, 2002.
4. F. Nielson, H. R. Nielson and C. Hankin. Principles of Program Analysis. Springer Verlag, 1999.
5. R. Morgan. Building an Optimizing Compiler. Digital Press, 1998.
6. Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures. Morgan Kaufmann Publishers, 2002.

Logistics

• Credits: 3-0-0-6.

• Prerequisites: Exposure to a UG course on compilers. Or consent of teacher.

• Audience: Elective for UG as well as PG students.

• Instructor: Manas Thakur.

• TAs: Aditya Anand (23d0381) and Meetesh Mehta (23d0361).

• Slot: 9 (Mon and Thu, 3:30-4:55 pm).

• Classroom: CC 103.

• Office hour: Fri 4-5 pm.

Evaluation

1. Programming assignments: 45* (= 10+15+10+10)
2. Mid-sem exam: 25
3. End-sem exam: 25
4. Course participation: 5
5. Paper reading: 20*
*Paper reading option for those who score <50% in the first two programming assignments.