MPCS 51300 Compilers (Autumn 2021)

Course Description

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.

 

Course Organization

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.


 

Book

Keith Cooper and Linda Torczon. “Engineering a Compiler.” Elsevier, 2011.

Grading

The final grade will be based on the following:

• Exercises: 15%
• Programming assignments: 50%
• Midterm Exam (project presentation): 10%
• Final Exam: 25%

 

Exercises

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.

 

Late Submission

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.

 

Exam 

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.

 

Course Contents

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

We'll discuss virtual machines, garbage collection, and related topics. Essentially, you'll learn how the Javascript engine inside your web browser works.
 

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)

95-100: A

90-95: A-

85-90: B+

80-85: B

75-80: B-

70-75: C+

< 70: Dealt on a case-by-case basis

Core Programming (completed or concurrently enrolled). New students who are taking Compilers along with Core Programming must have received a High Pass on the programming placement exam).

Not approved for CAPP or MACS students.

This course requires competency in Unix and Linux. Please plan to attend the MPCS Unix Bootcamp (https://masters.cs.uchicago.edu/page/mpcs-unix-bootcamp) or take the online MPCS Unix Bootcamp Course on Canvas.

This class is scheduled at a time that does not conflict with any other classes this quarter.

Masters Program in Computer Science MS in Computational Analysis in Public Policy (Year 2) MA in Computational Social Science (Year 2) Bx/MS in Computer Science (Option 2: Professionally-oriented - CS Majors) Bx/MS in Computer Science (Option 3: Profesionally-oriented - Non-CS Majors)