Course Information for G22.3130, Honors Compilers
Programming Languages and Systems
NEC Research Institute
Office: (609) 951-2744
FAX: (609) 951-2488
SNAIL: NEC Research Institute, 4 Independence Way, Princeton,
NYU Office Location: Room 424 WWH
Office Hours: 4-5pm, Thursdays
This course will focus on designing and implementing compilers for advanced programming
languages. We will concentrate primarily on implementation techniques for mostly functional
languages such as Scheme or ML.
We will look at recent approaches to building optimizing compilers that draw from techniques
used in real compilers. Roughly speaking, the course will have four basic parts:
Intermediate Representations: We will investigate continuation-passing style (CPS), A-normal
form, and other related high-level intermediate representations.
Control-flow Analysis: We will study the control-flow analysis problem for higher-order
languages. We will cover classical monovariant analyses, and more advanced polyvariant analyses.
Optimizations: We will study how to derive optimizations using information gleaned from control-flow
analysis. In particular, we will study runtime-check elimination, inlining, and hopefully unboxing,
time-permitting. I also would like to revisit classical loop optimizations in the context of an
interprocedural flow analysis.
Virtual Machine Implementation: We will look at the design of virtual machines, low-level optimizations
on such machines, register allocation, and code generation.
The grading for the course will be broken down roughly as follows:
Notes: 15% (Every student is expected to serve as a scribe for at least one lecture. The responsibility of
the student is to construct an html page that not only provides a detailed summary of the lecture, but also
provides references to the literature, a transcript of questions and answers raised during the lecture, etc.)
The class project will be to implement an optimizing compiler for a language similar to Scheme. In this
sense, the language will be dynamically-typed, support first-class lexically-scoped procedures, have data
structures (lists), and cells (mutable objects).
The implementation language will be in Standard ML of New Jersey. Look
here for details on SML.
You will also find much useful information on libraries and interfaces
here. I will
be providing details on the project such as the specification of interfaces and signatures
Lecture 1: Introduction, Administrative. Background and definitions.
The source language. The implementation.
Overview of the course.
Lecture 2: Introduction to CPS. Structure of a node tree.
Lecture 3: Continuation-Passing Style.
More on intermediate representations. Translation algorithm. A-normal form.
Lecture 5: Introduction to inter-procedural flow
analysis. Classical control-flow analysis and its use in optimization.
Lecture 6: An introduction to inter-procedural flow analysis for
higher-order languages. Specification of a monovariant analysis.
Lecture 7: More on Implementation. Tradeoffs. Complexity measures.
Lecture 8: Runtime-check elimination.
Lecture 9: Introduction to Inlining.
Lecture 10: Flow-directed Inlining.
Lecture 11: Closure Conversion. Closure Representations.
Lecture 12: More on Closure Conversion.
Lecture 14: Mid-Term Exam.
Lecture 15: Review of Mid-Term Exam.
Lecture 16: Loop Hoisting.
Lecture 17: Closure Representations.
Lecture 18: Code Generation.
Lecture 19: Code Generation.
Lecture 20: Register Allocation.
Lecture 22: Parsing.
Lecture 23: Parsing.
Lecture 24:More on Register allocation.
Lecture 25:Instruction Scheduling.
Lecture 26:More on Code Generation.
Lecture 27:Garbage Collection.
Lecture 28:Future directions.