CS4410/6410: Compilers

Fall 2019

Contact information

Office email Office hours
Olin Shivers WVH 318 shivers@ccs Tuesday 3:00–4:00 & by appt
Artem Pelenitsyn WVH 330 a.pelenitsyn@gmail.com Wednesday 11:00–12:00 & by appt


Tuesday 11:45–1:25 Snell 005
Thursday 2:50–4:30 Snell 005


Course schedule (lectures, projects, exams) (This is the central file for course-related information.)

Piazza: https://piazza.com/class/jzsj16sla6p4ni

Slides for intro-to-SML lecture.


  1. Lexer (due Thu 9/19 10:00 pm)
  2. Parser (due Tue 10/1 10:00 pm)
  3. Static semantics (due Tue 10/15 10:00 pm)
  4. Frame analysis (due Tue 10/22 10:00 pm)
  5. Translation to IR (due Tue 11/5 10:00 pm)
  6. Instruction selection (due Tue 11/12 10:00 pm)
  7. Live-variable Data-flow analyser (due Tue 11/19 10:00 pm)
  8. Register allocation (due Thu 12/5 10:00 pm)
  9. Integration (due Thu 12/12 10:00 pm)




SPIM is a simulator written by James Larus for the MIPS-II ISA, a real-world processor architecture that is a very clean RISC design.


Improved Canonicaliser

Appel provides a module of code for the Tiger-compiler project called the "canonicaliser," which lowers a program in the IR language to a form closer to machine code. This code is hard to read, as the invariants of the lowered/canonicalised form are not expressed in the type of the result form. Well, and the code isn't commented, either.

I rewrote this code using a target data type that makes the new form explicit in the type structure. It is much clearer (as well as voluminously commented). It also has a better commutativity analysis.

The code comes in two forms. The first version is exactly as described above. Then I took that, and converted the improved code to use the original IR data type for the target, producing a version that is a drop-in replacement for Appel's code.

So, read the first version but use the second.