*This course will be conducted remotely and will be online only for Autumn 2020*
At a high level, students should come out of the class with an understanding of:
- Parts of compiler technology that are useful in general (i.e., scanning/regexes/parsing) and algorithmic ideas that come up in other contexts (e.g., graph algorithms - dominance and coloring, for example - and lattice algorithms).
- Why some aspects of optimization are hard, both in terms of algorithmic complexity and practical concerns (e.g., supporting separate compilation), and how choices made about the language semantics can make this harder or easier.
- How compile time vs. expected performance gain affects the design of compilers, especially JIT compilers.
This course meets once a week for lectures and once a week for an optional TA session. Even if not recorded, attendance in class is strongly encouraged. Most of the coursework revolves around 4 homework assignments, as the primary focus will be for students to code. There will be one presentation (Week 6) and one Final Exam (Week 11). The course calendar, including the contents of each lecture and programming assignment due dates, is shown at the end of this page.
Keith Cooper and Linda Torczon. “Engineering a Compiler.” Elsevier, 2011.
The final grade will be based on the following:
- Exercises: 15%
- Programming assignments: 50%
- Midterm Exam (project presentation): 10%
- Final Exam: 25%
Three individual exercises will be assigned during the quarter. They will constitute 15% of the course grade.
Compiler Programming Project
We will assign six programming assignments over the course of the term. You can choose to work on the programming assignment alone, however, it is strongly recommended to work by group of 2 people. You will need to inform us of your choice by Week 2. The goal of this assignment will be to make you create your own compiler.
The assignments will be interconnected; they will guide you to the creation of your own compiler. They will constitute 50% of the course grade.
The assignments will be due on weeks 3, 5, 7, 8, 9, and 10.
Week 6: A presentation of your work on your own compiler. This presentation will not be longer than 10 minutes The grade of this presentation will constitute 10% of the course grade.
Prorated points will be applied according to the number of late days.
- 1 day late: 75% of the grade will be considered.
- 2 days late: 50% of the grade will be considered.
- 3 days late: 25% of the grade will be considered.
- After 3 days, no assignment will be accepted.
We will be giving a final exam during at Week 11. The final exam is worth 25% of the grade.
The final exam will be an open-book written exam on the whole content of the class.
The questions of this exam will be on the content of the lecture and the compiler project.
Week 1: General introduction to compiler structure
What is a compiler (e.g., GCC, MSVC)? How does source code get transformed into instructions that a processor or virtual machine can execute? We'll cover the basics of compiler structure and review relevant aspects of computer architecture.
Week 2: Lexical analysis and parsing
We'll cover how a textual programming language is processed and introduce tools that make this job easier.
Week 3: Intermediate representations
We'll cover control flow, dominance, intermediate representations, and related topics to understand how a program is represented inside of the compiler.
Week 4: LLVM
We'll discuss LLVM in particular to give you enough practical background to use LLVM to create a compiler.
Week 5: Pointers and optimizations
We'll discuss pointers and data-flow/lattice algorithms, plus function inlining and peephole optimizations.
Week 6: Mid-term presentations
All members of the class will present their current work. As time allows, we'll cover exception handling and co-routines.
Week 7: Loop optimizations and more
We'll continue discussing peephole optimizations and discuss the topic of undefined behavior. We'll then talk about loop optimizations.
Week 8: Lower-level things
We'll discuss vectorization, instruction selection, and register allocation.
Week 9: Virtual machines
Week 10: Debugging
We'll discuss debugging technology, including instrumentation-based debugging (e.g., LLVM sanitizers). We'll also review for the final exam.
Week 11: Final Exam
Grading Group (% of the whole grade)
< 70: Dealt on a case-by-case basis