CS 343

Advanced Topics in Compilers - Spring 2011

Course Description

Compiler research for a long time was moribund, stuck on narrow topics such as register allocation and instruction scheduling. In contrast, the last decade has seen an explosion of interesting work using compilers to accomplish something cool. This class will cover a selection of such research papers, ranging across static and dynamic bug finding, binary analysis, reverse engineering, programming via sketching, and other topics that seem worth knowing. The class is discussion oriented. You will read (typically) one paper before each class thoroughly, which will be dissected during the class period. By the end of the course you will be able to read a technical paper and extract its essence as well as noticing when the authors have sinned by omission in their experiments or wording. A good paper along these lines is here.

Papers will be somewhat bimodal. We will often start with an older one to set the stage (since they are simpler), and then a later one so you can see what the current thinking is. To see the papers that were covered last quarter, you can take a look at last year's website.

In addition, students will form groups of 1-3 and do a final project of their design which they will present. There may also be programming projects assigned to follow corresponding papers read.

Logistics

Class

Lectures: Tuesday, Thursday, 2:15 to 3:30 in 300-303
Prerequisites: cs243, or permission from instructor
Staff mailing list: cs343-spr1011-staff@lists.stanford.edu
Midterm: April 28
Project Presentations: June 3rd, 3:30-6:30, in 300-303
Final exam: Cancelled

Instructor

Dawson Engler
Office: Gates 314
Website: cs.stanford.edu/~engler
Office hours: By appointment

TA

David Goldblatt
Office: None
Office hours: By appointment

Syllabus

Static Bugfinding

March 29 (Tue)

Checking System Rules Using System-Specific Programmer-Written Compiler Extensions , Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem
Slides

March 31 (Thu)

A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World , Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, and Dawson Engler
Slides

Dynamic Analysis

April 5 (Tue)

Purify: Fast Detection of Memory Leaks and Access Errors , Reed Hastings and Bob Joyce
Optional: Purify User's Guide

April 7 (Thu)

Atom: A System for Building Customized Program Analysis Tools , Amitabh Srivastava and Alan Eustace
ATOM Source Files
Optional: A Practical System for Intermodule Code Optimization at Link-Time

April 12 (Tue)

Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation, Nicholas Nethercote and Julian Seward
Example tool: Lackey (Unfortunate that writing a trivial tool is so complicated.)

April 14 (Thu)

Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation , Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood
Optional: Pin User Manual
Example PIN tool: cache simulator dcache.cpp dcache.H
Comment: much, much simpler to write tools than Valgrind, but handles fewer corner cases.

Optimizing JITs

April 19 (Tue)

Dynamo: A Transparent Dynamic Optimization System , Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia

April 21 (Thu)

Trace-based Just-in-Time Type Specialization for Dynamic Languages , Andreas Gal, Brendan Eich, Mike Shaver, David Anderson, David Mandelin, Mohammad R. Haghighat, Blake Kaplan, Graydon Hoare, Boris Zbarsky, Jason Orendorff, Jesse Ruderman, Edwin Smith, Rick Reitmaier, Michael Bebenita, Mason Chang, and Michael Franz.
Comment: Essentially identical to Dynamo with some simple extensions to handle dynamic types.
Excellent discussion of trace-based vs method-based JITs and Tracemonkey --- it seems the Mozilla is going to use method-based as a fall-back.

Binary Translation

April 26 (Tue)

FX!32: A Profile-Directed Binary Translator, Anton Chernoff, Mark Herdeg, Ray Hookway, Chris Reeve, Norman Rubin, Tony Tye, S. Bharadwaj Yadavalli, and John Yates
The Technology Behind Crusoe(tm) Processors, Alexander Klaiber
Optional: Binary Translation, Richard L. Sites, Anton Chernoff, Matthew B. Kirk, Maurice P. Marks, and Scott G. Robinson