CS 744 - Advanced Compiler Design (Spring 2011)

General

Organizational meeting:
Tuesday, May 3rd, 2011, 1:00 -- 2:20, MC 2036A
Lectures:
Tuesdays and Thursdays, 1:00 -- 2:20, MC 2036A
Web page:
http://plg.uwaterloo.ca/~olhotak/cs744
Instructor:
Ondřej Lhoták, olhotak@plg, DC 2520
Office hours:
TuTh 2:30 -- 3:30, DC 2520, or by appointment
Handbook description:
http://www.cs.uwaterloo.ca/grad/courses/calendar/cs744

Important dates:

Slides from lectures

  1. Introduction: optimization in general, intermediate representations, static analysis in general
  2. Dataflow analysis
  3. Soot
    Liveness analysis example:
  4. Redundancy Optimizations
  5. Dominance
  6. Static Single Assignment Form
  7. Global Value Numbering
  8. Loop Optimizations
  9. Partial Redundancy Elimination
  10. Register Allocation
    Register allocation on SSA form:
  11. Instruction Scheduling

Recommended References

Course Outline

  1. Introduction, compiler architecture, intermediate representations
  2. Control flow analysis, control-flow graphs, basic blocks
  3. Dataflow analysis
  4. SSA form, global value numbering
  5. Redundancy optimizations (constant folding, CSE, PRE)
  6. Loop optimizations
  7. Code generation, instruction scheduling, peephole optimizations
  8. Register allocation
  9. Pointer and alias analysis
  10. Interprocedural dataflow analysis
  11. Procedure optimizations
  12. Additional topics (tentative):
    1. Memory management, escape analysis, garbage collection
    2. Dynamic (JIT) compilation
    3. Program analysis in software development tools

Evaluation

Assignments: 3 * 10%
Reading assignments: 10%
Course Project:
- proposal: 10%
- final report: 30%
- presentation: 20%

Assignments

There will be three short assignments to give you a chance to apply the lecture material. Assignments will have some written and some programming problems.

Readings

Throughout the course, I will assign several research papers for you to read. For each paper, you will submit a brief summary (one-page maximum) of the paper in your own words. Each reading assignment will be marked on a pass/fail basis.

Course Project

The course project gives you a chance to explore a specific area of compiler implementation in more depth. You will be required to implement some compiler feature, and perform an experimental evaluation of your implementation. You may do your implementation within any freely-available compiler infrastructure (e.g. Soot, JikesRVM, Wala, LLVM, Scala, gcc, Eclipse, abc, SUIF, etc.)

You will report on your project in a paper in the style of a PLDI research paper (approx. 10 pages), and give an overview of your project in a 21-minute presentation to the class (plus 5 minutes for questions). LaTeX and MS Word templates for the PLDI paper format are available from SIGPLAN.

Presentation Schedule