Course Information for G22.3130, Honors Compilers

Instructor:

Suresh Jagannathan
Programming Languages and Systems
NEC Research Institute

Office: (609) 951-2744
FAX: (609) 951-2488
EMAIL: suresh@research.nj.nec.com
WWW: http://www.neci.nj.nec.com/homepages/jagannathan.html
SNAIL: NEC Research Institute, 4 Independence Way, Princeton, NJ 08540

NYU Office Location: Room 424 WWH
Office Hours: 4-5pm, Thursdays

Overview

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:

Midterm: 15%
Final: 15%
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.)
Project: 55%

Project

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 here.

Syllabus

January 23

  • 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.
  • January 30

  • Lecture 3: Continuation-Passing Style.
  • Lecture 4: More on intermediate representations. Translation algorithm. A-normal form.
  • February 6
  • 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.
  • February 13

  • Lecture 7: More on Implementation. Tradeoffs. Complexity measures.
  • Lecture 8: Runtime-check elimination.
  • February 20

  • Lecture 9: Introduction to Inlining.
  • Lecture 10: Flow-directed Inlining.
  • February 27

  • Lecture 11: Closure Conversion. Closure Representations.
  • Lecture 12: More on Closure Conversion.
  • March 6

  • Lecture 14: Mid-Term Exam.
  • March 13

  • Lecture 15: Review of Mid-Term Exam.
  • Lecture 16: Loop Hoisting.
  • March 27

  • Lecture 17: Closure Representations.
  • Lecture 18: Code Generation.
  • April 3

  • Lecture 19: Code Generation.
  • Lecture 20: Register Allocation.
  • April 10:

  • Lecture 22: Parsing.
  • Lecture 23: Parsing.
  • April 17

  • Lecture 24:More on Register allocation.
  • Lecture 25:Instruction Scheduling.
  • April 24:

  • Lecture 26:More on Code Generation.
  • Lecture 27:Garbage Collection.
  • May 1:

  • Lecture 28:Future directions.
  • Lecture 29:Summary.