CSCI 7135: Topics in programming languages

This seminar course will explore the state of the art in program analysis (compile-time and run-time) and its applications.  A compile-time program analysis examines all or part of a program text in order to discover interesting properties about the program.  A run-time program analysis examines a program run in order to discover interesting properties about a program run.  Both run-time and compile time analyses have many applications such as:
  1. Improving the performance of programs
  2. Smart software engineering tools (safety checkers etc.)
  3. Performance debugging
In this seminar we will read and discuss a collection of recent papers on program analysis and their applications.
 

Project stages

 Stage 1

 Stage2

 Final

Resources for project

 SUIF documentation

Class requirements

In addition to reading and presenting papers there will be an implementation project.  The implementation will be done in the context of the SUIF-1 Compiler infrastructure.  I will put more information about the project on this page during the first week of classes.

Class mailing list

To get on the class mailing list, send an email to majordomo@cs.colorado.edu with the following message body:
  subscribe csci7135
Soon after you send this message, you will receive a message that will ask you to send a confirmation message.  Sending the confirmation message subscribes you to  the list.
 

Class format

In each class one student will be responsible for presenting the key ideas in the papers assigned to that class.  The presenter should schedule an appointment with Professor Diwan to discuss the assigned papers at least two days before the class.  The presenter should of course, carefully and thoroughly read the papers for the class.  In addition, if necessary, the presenter is responsible for reading other papers that may shed some light on the assigned papers.  If there is more than one papers assigned on a particular day then the presenter must give a single talk that integrates the ideas of all the papers.  All students are required to read the assigned papers before the class.
A presentation must contain the following:
  1. A summary of the ideas in the assigned papers.  Note that since everyone will have read the papers, the presenter need not present all the elementary ideas in the paper, just the main concepts.  However, she/he should be prepared to discuss details of the paper in response to questions by the students or the instructor.  Unless the paper is a very difficult one, you should plan to spend no more than half the class on this part of the presentation (if you are in doubt about this, it is a good thing to discuss with the instructor in your one-to-one meeting).
  2. Discussion of any additional papers that you read on the topic.  Since other students will not have read these papers you need to be more pedantic about these papers.
  3. A discussion of how the ideas in the paper fit in with the other papers we have discussed in the term
  4. A critique of the paper.  Do the papers present useful ideas?  Is the research in the papers thorough?  Was the writing clear?  Was the evaluation in the paper (if any) convincing? Do the ideas work for real programs on real machines?
  5. Any interesting research ideas that you got from reading the paper.  If the paper already has a future works section then you may discuss interesting ideas there as well.
  6. Are there other areas where you can imagine using the ideas in the paper?
The bottom line is that I want you to spend more of your presentation analyzing the ideas in the paper rather than simply presenting the ideas.

The presenter has five working days after the presentation to submit a write-up on the paper.  These write-ups will be available from the class web page for the benefit of all the students.

Guidelines for giving a talk

Like all courses, this course too relies heavily on the quality of presentations and class participation.  A badly given presentation can render even the simplest topic incomprehensible.  A good presentation can inspire!  Here are some general guidelines that I would like you to follow:
  1. Minimize the amount of text on a slide.  A slide should typically contain just a few bullets (3-5) or a figure/table and a sentence or two.  Each bullet should be short--you should strive to contain each bullet to a line.  A slide is not the place to write out long definitions, complex formulas, long algorithms, etc.  If you want to describe an algorithm, use the slides to get the intuition across (hopefully using figures).  Be prepared to answer detailed questions however.  If the paper contains complex algorithms, it may be helpful to have optional slides containing the algorithm.  These slides would be used only in response to questions requiring the details.
  2. Use figures instead of text when possible.  A figure may not be as unambiguous or precise as a mathematical formula or an algorithm, but that is fine: more details can always be brought up in the discussion period.
  3. Allocate 2-3 minutes for a slide.  For a 1 hour presentation, it means no more than 20-30 slides.
  4. Use large font sizes (18 points or bigger).
  5. Use colors judiciously.  Some colors, such as green and yellow are not too visible on an overhead.
  6. Make an outline of a talk before you start preparing the slides.  It will help you prepare a talk that feels smooth and continuous rather than fragmented.
  7. For each slide try to think of a one-liner take home message from that slide.  If there are more than one "one-liners" then maybe you need to break your slide down.

List of papers

Following is the tentative list of topics we will cover in the class along with the readings for that topic.  For many of the classes, there will be "supplimental" reading in addition to the main reading.  I will fill in supplimental readings for the topics as the class progresses.
 
Class Topic and readings Presenter and notes
1 Introduction to data flow analysis
Readings: Data-flow analysis in favorite compiler text
(e.g., Aho, Sethi, and Ullman Sections 10.1 to 10.6; or Muchnick Sections 8.1 to 8.4)
Diwan DFA lecture , SUIF lecture
2 A selection of data-flow problems
Readings: Same as previous lecture
Diwan
3 Static-single assignment form
ReadingsCytron et al. (TOPLAS Oct 91)
Supplimental readingsBrandis and Mossenbock  (TOPLAS Nov 94),  Knobe and Sarkar (POPL98)
Stevens ( notes )
4 Applications of SSA form
ReadingsKennedy et al.(PLDI 1997)
Levis ( notes )
5 Demand driven analysis
ReadingsDuesterwald et al.  (TOPLAS Nov 1997)
Hirzel ( notes )
6 Demand driven analysis via graph reachability
ReadingsHorwitz et al.  (SIGSOFT 95)
Supplimentary readings: Reps et al. (POPL 95)
Lin Xia ( notes )
7 Set constraint-based program analysis
ReadingsAiken (Science of computer programming, to appear)
Soukup ( notes )
8 Flow insensitive pointer analysis 1
ReadingsSteensgaard (POPL96), Steensgaard with structures (International conference on compiler construction 1996)
Lewis ( notes )
9 Flow insensitive pointer analysis 2
ReadingsShapiro and Horwitz (POPL 97)
Casmira ( notes )
10 Flow insensitive pointer analyses 3
ReadingsAiken and Faehndrich (SAS 97)
Lee ( notes )
11 Speeding up pointer analyses
Readings:    Fahndrich et al.  (PLDI 98)
Casmira ( notes )
12 Flow and context-sensitive pointer analysis 1
Readings: Emami and Hendren (PLDI 94)
Levis ( notes )
13 Flow and context-sensitive pointer analysis 2
Readings: Wilson and Lam (PLDI 95)
Hirzel ( notes )
14 Flow and context-sensitive pointer analysis 3
ReadingsChatterjee et al. (POPL 99)
Xia ( notes )
15 Using pointer analysis 1
ReadingsGhiya and Hendren (POPL 98)
Lee ( notes )
16 Using pointer analysis 2
Readings: Diwan et al. (Submitted for publication)
Hirzel ( notes )
17 Simple heap analysis
ReadingsGhiya and Hendren (IJPP 96)
Soukup ( notes )
18 Shape analysis 1
ReadingsSagiv et al. (TOPLAS Jan 1998)
Lewis ( notes )
19 Shape analysis 2
ReadingsSagiv et al. (POPL 99)
Brinkman-Davis ( notes )
20 Escape analysis 
ReadingsChoi et al.
Diwan
21 Path profiling
ReadingsBall and Larus (International symposium on microarchitecture 1996),  Ammons and Larus (PLDI 1998)
Lee
22 Continuous profiling
ReadingsAnderson et al. (TOCS 1997)
Soukup
23 Reverse execution
ReadingsNetzer and Weaver (PLDI 1994)
Xia ( notes )
24 Reverse execution in functional languages
Readings: Tolmach and Appel (Journal of functional programming Apr 1995)
Deleted
25 Memory system optimizations
Readings:   Roth et al.  (ASPLOS 98)
Diwan
26 More memory system optimizations
 Luk and Mowry (ISCA 99)
Lewis ( notes )
27 Simultaneous multithreading
ReadingsTullsen et al. (ISCA 95),  Lo et al.
Levis ( notes )
28 Low-power computing
ReadingsBellas et al.
Casmira