CS 744 - Advanced Compiler Design (Spring 2015)
General
- Lectures:
- Fridays, 10:30 -- 1:20, DC 2568
- Web page:
- http://cs.uwaterloo.ca/~nanaeem/cs744
- Instructor:
- Nomair Naeem, nanaeem AT uwaterloo, DC 3121
- Office hours:
- By appointment
- Handbook description:
- http://www.cs.uwaterloo.ca/grad/courses/calendar/cs744
Important dates:
Slides from lectures:
- Introduction: optimization in general, intermediate representations, static analysis in general
-
Dataflow analysis
- Redundancy Optimizations
- Dominance
- Static Single Assignment Form
- Loop Optimizations
- Soot
- Partial Redundancy Elimination
- Register Allocation
- Alias Analysis
- Interprocedural Analysis
Recommended References:
- Appel, A., Modern Compiler Implementation in Java (or
ML, or C), Cambridge University Press, 2002.
- Cooper, K., Torczon, L., Engineering a Compiler,
Morgan Kaufmann, 2004.
- Muchnick, S., Advanced Compiler Design and
Implementation, Morgan Kaufmann, 1997.
- Aho, A., Lam, M., Sethi, R., Ullman, J., Compilers: Principles, Techniques, & Tools,
Addison Wesley, 2007.
Course Outline
The following is a rough list of topics that might be covered. The ordering is subject to change.
- Introduction, compiler architecture, intermediate representations
- Control flow analysis, control-flow graphs, basic blocks
- Dataflow analysis
- SSA form, global value numbering
- Redundancy optimizations (constant folding, CSE, PRE)
- Loop optimizations
- Code generation, instruction scheduling, peephole optimizations
- Register allocation
- Pointer and alias analysis
- Interprocedural dataflow analysis
- Procedure optimizations
- Additional topics (tentative):
- Memory management, escape analysis, garbage collection
- Dynamic (JIT) compilation
- 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.
- Assignment 1 due date June 15th, 2015
- Assignment 2 Proposed due date June 28th, 2015
- Assignment 3 Proposed due date July 19th, 2015
Readings
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.
- Reading Assignment 1 due date May 27th, 2015
- Reading Assignment 2 due date June 22nd, 2015
- Reading Assignment 3 Proposed due date July 26th, 2015
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.