8.2

EECS 483: Compiler Construction

Syllabus --Fall 2021

Meeting places & times

Course staff & office hours

Instructor

  

Max New

  

maxsnew@umich

  

Beyster 4640 & Zoom

  

Mon & Thu 4-5:30pm,
and by appointment

IAs:

  

Ramchandra Apte

  

ramkapte@umich

  

Beyster 1695 & Zoom

  

Tuesday 2:30-3:30pm

  

Sathvik Koneru

  

sathvikk@umich

  

Zoom

  

Thu 5:30-6:30pm

Max New
Max New

Ramchandra Apte
Ramchandra Apte

Sathvik Koneru
Sathvik Koneru


General information

EECS 483 covers the implementation of efficient compilers for programming languages. The course focuses on the connections between language features and the impact they have on the design of a compilier, including any associated algorithms and pragmatic issues, and practical applications including those outside of programming languages proper. Participants build a working compiler including lexical analysis, parsing, register allocation and code generation. As a secondary emphasis, the course exposes students to run-time issues and optimization.

Exams

At the moment, I am not planning on giving formal exams. However, we will likely have two or three written assignments (as opposed to the project assignments) that will serve a similar purpose. There is a final exam time scheduled for this course, but we may not use it. We will likely have project presentations due during exam week, so don’t assume the course is over before then.


External Links

This is the main website for this course. We will also use the following sites:


Materials

Software

Programming assignments will use several pieces of software:

Rust is supported by many editors you may use any editor you wish.

Compilers written in the class will be graded on Linux, and code is not cross-platform. I will provide pointers to how Mac users can easily make their code work on Linux, but Windows users are recommended to install a Linux distribution using WSL for testing. Instructions are provided here.

Books

There is no required textbook, but you may find these books useful.


Andrew Appel, Modern Compiler Implementation in ML, Cambridge University Press, 1998.

  


Keith D. Cooper and Linda Torczon, Engineering a Compiler, 2nd Ed., Morgan Kaufmann, 2004.

  


Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Pearson Education Inc, 2006.

Online resources

Rust Resources

X86 Resources

X64 Resources

(I will add to this list over the semester as I find useful guides. Email me if you have suggestions.)


Lectures

This table specifies the lecture schedule; topics are tentative.

I will be publishing lectures notes somewhat on-demand, as I update them for Rust. In the meantime I’m leaving them private, so they are not needlessly confusing.

Date

 

Topics (tentative and approximate)

 

Materials

8/30 M

 

Introduction to compilers, course overview

 

Reading: Rust book chapters 1-4 and notes

9/01 W

 

Rust practice, trees

 

Reading: Rust book chapters 6.2, 8.1,8.2, 9, 10.3, 11, Rust live code and slides

9/06 M

 

No class: Labor Day

 

9/08 W

 

Tiny compiler: grammar, abstract syntax, and instructions

 

notes and live code

9/13 M

 

Names, scope and (simple) stacks

 

notes

9/15 W

 

Conditionals

 

notes

9/20 M

 

Sequential Form

 

notes

9/22 W

 

Multiple data types and tagging values

 

notes

9/27 M

 

Calling conventions

 

slides

9/29 W

 

Errors, Calling into Rust

 

notes, demo stub.rs and demo compiled_code.s

10/04 M

 

Function Calls and Definitions

 

notes, live code assembly and live code fundef

10/06 W

 

More Fun calls and definitions

 

10/11 M

 

Tail Calls

 

notes, slides, asm tail call and rust tail call

10/13 W

 

Register Allocation 1: Liveness/Conflict Analysis

 

slides

10/18 M

 

No class: Fall Study Break

 

10/20 W

 

Register Allocation 2: Graph Coloring

 

slides

10/25 M

 

Heap allocation and pairs

 

notes

10/27 W

 

Mutable Arrays and Desugaring

 

notes

11/01 M

 

First-class functions/Closures

 

notes

11/03 W

 

More closures

 

11/08 M

 

Closure Code

 

example code, example compilation and example runtime

11/10 W

 

Recursion and Objects

 

11/15 M

 

Garbage Collection

 

slides

11/17 W

 

Stack Walking

 

11/22 M

 

Optimization

 

11/24 W

 

No class: Thanksgiving

 

11/26 F

 

No class: Thanksgiving

 

11/29 M

 

Exceptions

 

12/01 W

 

(Canceled)

 

12/06 M

 

Lexing/Parsing: Theory

 

12/08 W

 

Lexing/Parsing: Practice

 


Testing

Testing your code is sufficiently important that we’ve devoted an entire page to it. Please read these notes, for each and every assignment you work on.


Homework schedule

Homework will usually be due at 8:59 PM; the day of the week varies, so you should check each individual assignment to be sure. General homework policies are here.

This homework schedule is tentative and subject to change at the instructor’s discretion.

Link

  

Assigned

  

Due

Assignment 0: Rust warmup, part 1: basics

  

Mon 08/30

  

Thu 09/02

Assignment 1: Rust warmup, part 2: trees

  

Fri 09/03

  

Thu 09/09

Assignment 2: Adder: A starter language

  

Tue 09/14

  

Tue 09/21

Assignment 3: Boa: Adding new operators

  

Tue 09/21

  

Thu 09/30

Assignment 4: Cobra: Multiple types of values

  

Thu 09/30

  

Tue 10/12

Assignment 5: Diamondback: Defining functions

  

Thu 10/14

  

Tue 10/26

Assignment 6: Written 1: Adding new data types

  

Wed 10/27

  

Thu 11/04

Assignment 7: Hundred-pacer: Register Allocation

  

Tue 11/09

  

Thu 11/18

Assignment 8: Egg-eater: Arrays

  

Thu 11/18

  

Thu 12/02

Assignment 9: Fer-de-lance: Anonymous, first-class functions

  

Thu 12/02

  

Wed 12/15


Course policies

Collaboration and academic integrity

You may not collaborate with anyone on any of the exams. You may not use any electronic tools, including phones, tablets, netbooks, laptops, desktop computers, etc. If in doubt, ask a member of the course staff.

All homework assignments, will be completed with a partner; some may involve a larger team (TBD). You must collaborate with your assigned partner or team, as specified, on homework assignments. You may request help from any staff member on homework. (When you are working with a partner, we strongly recommend that you request help with your partner, rather than solo.) You may use the Piazza bulletin board to ask questions regarding assignments, so long as your questions (and answers) do not reveal information regarding solutions. You may not get any help from anyone else on a homework assignment; all material submitted must be your own. If in doubt, ask a member of the course staff.

Providing illicit help to another student is also cheating, and will be punished the same as receiving illicit help. It is your responsibility to safeguard your own work.

Students who cheat will be reported to the university’s office on academic integrity and penalized by the course staff, at our discretion, up to and including failing the course.

If you are unclear on any of these policies, please ask a member of the course staff.

Homework

We will be using the following gradescope page for homework submissions.

Late days & late work

Each student gets four free, no-questions-asked late days for the term. The purpose of late days is make the extension process fair and transparent by getting the instructors out of the extension-granting business entirely. Instead, when you need an extension, you can take one — provided you have a late day remaining.

Using a late day is automatic: simply submit the homework up to one day late. The server will keep track of the number of used late days. Conserve your late days carefully.

No more than one late day may be used on any one homework. Late days cannot be divided fractionally, but must be used whole. Late days cannot be transferred to or shared with a partner, so in order to take an extension both you and your partner must have sufficient late days remaining. Choose your partners carefully.

Grades

Your grade will be based on your performance on the programming assignments and written assignments. Each assignment will be given an equal weight to the final grade. There will likely be around 12 total assignments but this is subject to change based on the pace of the course.

The grades will computed on an absolute basis: there will be no overall curving. The instructor may choose to curve an individual assignment, but please do not bank on such a chance.

The estimated mapping of raw point totals to letter grades is given below. Please note that these grade boundaries may move slightly in either direction at the discretion of the instructor: if a particular breakpoint falls in the middle of a tight cluster of numeric grades, we will attempt to move the breakpoint to give that whole cluster the same letter grade. If, near the end of the semester, you are concerned that your grade is hovering near a breakpoint, see me to discuss your concerns.

Cutoff

  

93%

  

90%

  

86%

  

83%

  

80%

  

76%

  

73%

  

70%

  

66%

  

63%

  

60%

  

else

Letter grade

  

A

  

A-

  

B+

  

B

  

B-

  

C+

  

C

  

C-

  

D+

  

D

  

D-

  

F