CS614: Advanced Compilers
Offering: Autumn 2023
About the course
“I had a running compiler and nobody would touch it. … they carefully told me, computers could only do arithmetic; they could not do programs.”
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. Semantic analysis: Type checking. Syntax-directed translation. Intermediate representations. IR generation for OO languages.
Intro to code optimization. DFA basics. Program representations for optimization. SSA form. SSA-enabled optimizations: conditional constant propagation, value numbering, partial redundancy elimination. SSA construction and destruction algorithms.
Interprocedural optimizations. Function inlining. Polymorphism and devirtualization.
Memory management: runtime layouts. Register allocation: liveness and graph coloring, bitwidth-awareness. Code generation: instruction selection, pipelining and instruction scheduling.
Cache optimizations: data prefetching, loop transformations. Parallelization: loop parallelization, memory models, MHP analysis, vectorization.
Managed runtimes: garbage collection, dynamic compilation, speculation and deoptimization.
References:
1. Steven S. Muchnick. Advanced Compiler Design and Implementation. Harcourt Asia Private Ltd, 2000.
2. Y. N. Srikant and P. Shankar (Ed.) The Compiler Design Handbook: Optimizations and Machine Code Generation. CRC Press, 2002.
3. F. Nielson, H. R. Nielson and C. Hankin. Principles of Program Analysis. Springer Verlag, 1999.
4. R. Morgan. Building an Optimizing Compiler. Digital Press, 1998.
5. 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.
TA: Aditya Anand.
Slot: 10 (Wed and Fri, 2:00pm-3:25pm).
Classroom: CC 105.
Office hour: Mon, 11:30am-12:30pm.
Evaluation
1. Programming assignments*: 40 (= 4 * 10)
2. Paper reading*: 10 (= 1 * 10)
3. Mid-sem exam: 20
4. End-sem exam: 25
5. Course participation: 5
*Best four from 1 and 2 to be scaled to 50