• Course Description
• Logistics
• Syllabus

CS 343

Advanced Topics in Compilers - Spring 2012

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.

Previous offerings:

• Spring 2011
• Spring 2010

Logistics

Class

• Lectures: Tuesday, Thursday, 2:15 to 3:30 in Gates 200
• Prerequisites: cs243, or permission from instructor

Instructor

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

TA

• Philip Guo
• Email:
• Website: http://www.pgbovine.net/
• Office: Gates 326
• Office hours: By appointment

Syllabus

Static Bugfinding

April 3 (Tue)

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

April 5 (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

Guest Lecture (Prof. Philip Levis)

April 10 (Tue)

• Surviving Sensor Network Software Faults, Yang Chen, Omprakash Gnawali, Maria Kazandjieva, Philip Levis, and John Regehr

Dynamic Analysis

April 12 (Thu)

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

April 17 (Tue)

• Atom: A System for Building Customized Program Analysis Tools, Amitabh Srivastava and Alan Eustace [Annotated PDF]
• ATOM Source Files readable PDF (pretty-printed using a2ps *.c -A fill -o atom-examples.ps -Mletter)
• Optional: ATOM Source Files (complete tarball)
• Optional: A Practical System for Intermodule Code Optimization at Link-Time

April 19 (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 [Annotated PDF]
• Example PIN tool: cache simulator (dcache.cpp, dcache.H)
• Optional: Pin User Manual
• 
  
• Comment: much, much simpler to write tools than Valgrind, but handles fewer corner cases.

Optimizing JITs

April 24 (Tue)

• Dynamo: A Transparent Dynamic Optimization System, Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia [Annotated PDF]

April 26 (Thu)

• KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs, Cristian Cadar, Daniel Dunbar, and Dawson Engler

May 1 (Tue)

• Using Valgrind to detect undefined value errors with bit-precision, Julian Seward and Nicholas Nethercote
• How to Shadow Every Byte of Memory Used by a Program, Nicholas Nethercote and Julian Seward

May 3 (Thu) - Midterm Exam

• The midterm exam covers all papers up until today except for the guest lecture paper (Surviving Sensor Network Software Faults)
• Midterm from Spring 2011

May 8 (Tue)

• Efficient Implementation of the Smalltalk-80 System, L. Peter Deutsch and Allan M. Schiffman
• The Technology Behind Crusoe(tm) Processors, Alexander Klaiber

Dynamic Code Generation

May 10 (Thu)

• DPF: Fast, Flexible Message Demultiplexing using Dynamic Code Generation, Dawson R. Engler and M. Frans Kaashoek


• VCODE: A Retargetable, Extensible, Very Fast Dynamic Code Generation System, Dawson R. Engler
• Annotated copy.
• Slides
• Example: generating machine code

Cool Hacks

May 15 (Tue)

• Superoptimizer -- A Look at the Smallest Program, Henry Massalin
• Annotated copy.


• Reflections on Trusting Trust, Ken Thompson
• Annotated copy.
• Source code: replicate.c, identity-cc.c, trojan-attempt1.c, trojan-attempt2.c

May 17 (Thu) - Informal project progress presentations (you can just doodle on whiteboard)

May 22 (Tue) - Informal project progress presentations (continued)

May 24 (Thu)

• Enhancing Server Availability and Security Through Failure-Oblivious Computing, Martin Rinard, Cristian Cadar, Daniel Dumitran, Daniel M. Roy, Tudor Leu, and William S. Beebee, Jr.

May 29 (Tue)

• Reverse Interpretation + Mutation Analysis = Automatic Retargeting, Christian S. Collberg.
• Annotated copy.
• Optional: Longer journal article.

May 31 (Thu)

• Finding and Understanding Bugs in C Compilers, Xuejun Yang, Yang Chen, Eric Eide, and John Regehr
• Annotated copy.
• Optional: Interesting author discussion on undefined behavior

June 11 (Mon) - Final Project Presentations - 5:30pm to 8:30pm in Gates 104

• Please bring to class a 1-2 page written report summarizing your project's main ideas and results.