CS 744 - Advanced Compiler Design (Spring 2015)


Fridays, 10:30 -- 1:20, DC 2568
Web page:
Nomair Naeem, nanaeem AT uwaterloo, DC 3121
Office hours:
By appointment
Handbook description:

Important dates:

Slides from lectures:

  1. Introduction: optimization in general, intermediate representations, static analysis in general
  2. Dataflow analysis
  3. Redundancy Optimizations
  4. Dominance
  5. Static Single Assignment Form
  6. Loop Optimizations
  7. Soot
  8. Partial Redundancy Elimination
  9. Register Allocation
  10. Alias Analysis
  11. Interprocedural Analysis

Recommended References:

Course Outline

The following is a rough list of topics that might be covered. The ordering is subject to change.
  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


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


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.


Throughout the course, I will assign several research papers for you to read. For each paper, you will submit a brief summary 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

The presentations for the projects will be in the last two weeks of lectures.