Resources

This page contains a number of useful and/or interesting references selected by the staff. You are not expected to know most of the material on this page for the class; however, you may find it interesting and helpful. We had a lot of fun curating this!

Table of contents
  1. References
  2. Related compiler courses
  3. Toolings
  4. Recommended textbooks
  5. Other sources of inspiration

References

You will find these references useful in writing your compiler.

  1. The complete Intel x64 manual — official PDFs with all the gory details
  2. x86 and amd64 instruction reference — navigable reference by Félix Cloutier derived from the Intel manual
  3. x86 wiki — good primer on how x86 instructions work
  4. x64 cheat sheet — lists and tables detailing registers and assembly commands from Brown University’s CS033
  5. Agner Fog’s optimization page — this is a very useful reference page with manuals on how to optimize code for x86-64. In particular, take a look at the latency tables.
  6. Godbolt — allows you to input C code and gives you line-by-line assembly output of various compilers (such as gcc and clang), very useful for figuring out how to translate certain operations to assembly.

If you find interesting resources you think other students could benefit from, please consider sharing them on Piazza!

You might find lecture slides/notes from other publicly available courses useful, especially as you get into the later phases of the project:

  1. Carnegie Mellon’s 15-411 Compiler Design course.
  2. Harvard’s CS153 Compilers class.

If you are hungry for more advanced material, take a look at this:

  1. Cornell’s self-guided, online Advanced Compilers course.

Of course, do not forget this class’s cousin in the fall semester: 6.1120[6.818] Dynamic Computer Language Engineering.

For more theoretical approaches to programming language design, theory, and implementation, look into these classes:

  1. 6.S050 Programming Language Design (Spring 2023)
  2. 6.5110[6.820] Foundations of Program Analysis
  3. 6.5120[6.822] Formal Reasoning About Programs

Toolings

Although we would like to focus on ideas, not specific tools, it is important for you to gain fluency in whatever it is that you choose to use. Minutes spent familiarizing yourself with common tools and frameworks will save you hours or days in the long run.

  1. Shell
    1. The Missing Semester of Your CS Education — Learn about the shell and the terminal, then you look like a pro.
  2. Scala
    1. Tour of Scala
    2. Scala Book
    3. Scala Patterns for Compiler Design

There is no required textbook for this class, but if you insist, we think this is a good reference textbook to have:

  1. Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, 3rd ed., Morgan Kaufmann, 2022.
    • A new reference textbook for understanding modern compilers. Covers many optimizations seen in this course (e.g. data-flow, instruction scheduling, register allocation) plus a few advanced ones found in modern compilers (e.g. static single-assignment (SSA)).
    • The 3rd edition is more up to date, but the 2nd edition (2012) is available online through MIT Libraries. In supplemental readings, we will list the pages for both editions.

Other compiler textbooks you may be interested in:

  1. Robert Nystrom, Crafting Interpreters. Genever Benning, 2021.
    • Our default recommendation for people who want to learn about compilers in general (i.e. outside of this course).
    • This is an amazing introduction to implementing a parser, an interpreter, and a bytecode virtual machine in Java and C.
    • The section on parsers may be useful for phase 1 of the project.
    • The rest of the book is arguably more relevant to 6.1120[6.818] Dynamic Computer Language Engineering.
  2. A. W. Appel and J. Palsberg, Modern Compiler Implementation in Java. Cambridge University Press, 2002.
    • A classic book. Guides you through a compiler project with thoughtful code organization. Otherwise similar to Cooper et al. in content.
    • Called the “tiger book”. Also has a C version and ML version.
  3. Aho, Alfred V., et al., Compilers: Principles, Techniques, & Tools, 2nd ed. Pearson Addison-Wesley, 2007.
    • A very, very, thick, classic reference on writing an optimizing compiler for C-like languages (e.g. Decaf).
    • Also called the “dragon book.” Everyone has heard of this.
  4. Steven Muchnick, Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.
    • The “whale book.” A comprehensive coverage of advanced compiler optimizations.
  5. Queinnec, C., and Callaway K., Lisp in Small Pieces. Cambridge University Press, 1996.
    • A very cool book that builds multiple interpreters from scratch to demonstrate how language design choices interact.

Many of these textbooks are available online through MIT Libraries. (For some books, you can borrow physical copies!) You can purchase the textbooks through traditional means (e.g. Amazon) or ask the TAs for advice on acquiring the textbooks.

Other sources of inspiration

  1. Overviews
    1. LLVM compiler architecture
    2. GCC compiler architecture
  2. Blogs
    1. Russ Cox’s Blog — Russ is one of the developers of Go, a popular language.
    2. Matt Might’s Blog — Matt is a professor at the University of Utah and has written some very interesting articles (e.g. “Yacc is dead”)
    3. Ralf’s Ramblings — Ralf wrote a lot of popular blog posts exploring the complexity behind systems languages like C++ and Rust.
    4. Embedded in Academia — Ditto.
  3. Papers
    1. Register Allocation & Spilling via Graph Coloring — G.J. Chaitin / 1982. Great (short) paper on simple register allocation.
    2. Linear Scan Register Allocation
    3. Iterated Register Coalescing — Lal George / 1996. Presents improvements/alternative to Chaitin’s design. If Chaitin-style (+/-Briggs) register allocation isn’t enough for you, this paper is a good read - actually, it’s a good read anyway, to understand the tradeoffs
    4. Superword Level Parallelism combined with loop unrolling, a simple way to implement a vectorizing compiler
  4. Theory
    1. Order Theory for Computer Scientists — Matt Might’s summary on the foundations of data-flow analysis.
    2. Davey, B. A., and H. A. Priestley, Introduction to Lattices and Order, 2nd ed. Cambridge University Press, 2002.