CS4410/6410: Compilers

Fall 2021

Contact information

Lectures

Other

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

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

Handin server: https://handins.ccs.neu.edu/courses/161

Assignments

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

Resources

Books

• The course textbook is Modern Compiler Implementation in ML, by Andrew Appel. Try to get the edition that says "Reprinted with corrections, 1999" on page iv; previous editions had lots of errors. (This is, of course, not an issue in 2017 unless you're buying a very old, used copy.) You can order the book from Barnes & Noble or Amazon.

  Appel's text comes in multiple versions: one for C, Java and ML. Make sure you get the ML version.

  Appel maintains a web page for the text book, which includes various files to begin your compiler with, and a a list of errata for the different editions of the book. It will save you confusion later if you take 15 minutes and go through the errata, applying them to your copy.

• If you are not an experienced SML programmer, then you will almost certainly need to get an introductory text on SML. I recommend Larry Paulson's ML for the Working Programmer.

  You can also find some useful tutorials on the Net. Several are listed below.

MIPS and SPIM

• James Larus's Assemblers, Linkers, and the SPIM simulator . This is Appendix B of Hennessy & Patterson's standard architecture textbook Computer Organization and Design: The Hardware/Software Interface, published by Morgan Kaufman. (It's appendix A of older versions of the book). It includes documentation on the MIPS R2000, its assembly code, and the SPIM simulator.
• SPIM documentation, in PostScript and PDF format. NOTE: the description of MIPS calling conventions in here is older than that in the Hennessy & Patterson book.
• The SPIM simulator runs on Windows, Macs and Linux. It has its own wikipedia page, which provides links to places you can obtain it. But most linux distros provide it as a package.
• Tiger Runtime System -- needed to actually run your programs.

ML

• Other ML tutorials
• Standard ML of New Jersey home page
• SML/NJ "Basis" Library documentation
• SML/NJ Library Manual
• User Manual for CM , an SML/NJ Configuration Manager
• User Manual for ML-Lex, a lexical analyzer generator for ML
• User Manual for ML-Yacc, a parser generator for ML
• You are strongly encouraged to develop and debug SML using emacs. In particular, emacs comes with two special modes: one for editting sml source code, and one for running an sml process inside emacs.

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.