Learning Objectives:
The objective of the course is to give students a deeper perspective into the internals of a compiler. The course equips students with the fundamentals in the theory of program analysis and machine independent code optimizations. The programming assignment in the course will make them expert practitioners of theory thus introduced. The program analysis theory covered in the course is useful in exploring research areas like language-based security, and program correctness.
Learning Outcomes:
At the end of the course, students will be able to identify opportunities for optimizing the programs given as input to the compiler, devise strategies to exploit them. The programming assignment focus on implementing program analysis and optimization passes in the Low Level Virtual Machine (LLVM) framework. The code optimization and code generation methods covered in the class will help students implement compiler passes to achieve superior performance on a given hardware.
Course Contents
-
Introduction: Intermediate Codes, Static Single Assignment (SSA) form, Control Flow Graph, Dominator Tree, Lattices, Partially Ordered Set, Monotonic Functions, Data Flow Analysis theory, Low Level Virtual Machine (LLVM) programming. (11 Lectures)
-
Program Analysis: Control Flow Analysis, Data Flow Analysis, Reaching Definitions, Use-Def chain, Available Expression, Live Variable Analysis, Symbolic Execution, Interprocedural Analysis (10 lectures)
-
Machine Independent Code Optimizations: Common Expression Elimination, Partial Redundancy Elimination, Local Value Numbering, Instruction Level Parallelism, Introduction to polyhedral optimizations, Optimization for Cache Locality (11 Lectures)
-
Code Generation and Runtime Systems: Global Register Allocation, Instruction Selection by Tree Rewriting, Run-time Enviornments (6 lectures)
Textbooks
-
Compilers: Principles, Techniques, and Tools, Alfred Aho, Monica Lam, Ravi Sethi, Jeffrey D. Ullman, Addison-Wesley; Second Edition, 2006, ISBN-13: 978-0321486813
-
Compiler Construction: Principles and Practice, Kenneth C. Louden, Cengage Learning; First edition (January 24, 1997), ISBN-13: 978-0534939724
References
-
Engineering a Compiler, K.D. Cooper, and L. Torczon, Elsevier, 2004.
-
Data Flow Analysis: Theory and Practice, Uday P. Khedker, Amitabha Sanyal, and Bageshri Karkare, CRC Press, USA (2009).
Past Offerings
- Offered in Jan-May, 2024 by Unnikrishnan Cheramangalath
- Offered in Jul-Dec, 2021 by Unnikrishnan
- Offered in July-Dec, 2019 by Unnikrishnan
Course Metadata
| Item | Details |
|---|---|
| Course Title | Compiler Optimizations and Program Analysis |
| Course Code | CS5510 |
| Course Credits | 3-0-0-3 |
| Course Category | ERC |
| Proposing Faculty | Unnikrishnan C |
| Approved on | Senate 8 of IIT Palakkad |
| Course prerequisites | Compiler Design |
| Course status | New |