University of Alberta CMPUT 680

Department of Computing Science
University of Alberta


Compiler: a program that captures the human intent of a program and recasts it in a way that a computer can process.

(From John Backus' obituary by Steve Lohr in New York Times, March 2007)


Fall 2006

TIME: TR 1400-1520
INSTRUCTOR: José Nelson Amaral
OFFICE HOURS: Tuesday 11-12, Thursday 1-2
EMAIL: amaral AT cs DOT ualberta DOT ca


Important Dates (tentative)
September 21 (Thursday) project assignment
October 10 (Tuesday) project interviews
October 16 (Monday) project proposal
November 14 (Tuesday) project progress report
December 05 (Tuesday) exam
December 14 (Thursday) project presentations
December 15 (Friday) final written project reports


Calendar Description

Study classical compiler optimizations and the trade-offs between hardware assisted and compiler assisted instruction level parallelism. Explore the integration of recent architectural advances with compiler design, including control and data speculation, predication, and multi-threading. Study dynamic re-compilation and feedback-directed compilation.


Students should have prior software design and implementation experience, and some knowledge of computer organization, operating systems, compilers, and computer architecture (some combination of CMPUT229, CMPUT329, CMPUT379, CMPUT415, and CMPUT 429). Students that have taken less than three of these classes, or their equivalents, should consult the instructor before registering.

Course Description and Goals

This course studies compiler design and implementation: a research discipline that seeks to reduce both the compilation time and execution time of programs. Execution time reduction is achieved through code transformations that result in better use of the resources available in a machine. A successful compiler optimization must produce a faster program, result in moderate compilation time and moderate use of storage - both for the final machine code and during the compilation process. Compiler designers must discover and implement algorithms to efficiently perform these code transformations.

Although compiler design and optimization is a research discipline on its own right, understanding compiler optimization is very important for architecture and system research. For instance, when changes to a programming model or to an instruction set architecture are proposed, the required changes to the compilation process must be taken into consideration. This course emphasizes the optimizations that take place at the "middle end" and at the "back end" of a compiler. Such optimizations are often language independent and explore the relationship between compiler optimization and architecture and system design.

In 2006 part of the focus of the course will be on reference analysis as well as on compilation for new programming language idioms, such as Aspect-Oriented Programming. We are also very interested on feedback-oriented compilation. The course projects and lab exercises for this portion of the course may use both the Jikes compiler and the McGill Tool Suite: Soot , STEP

Course Outline

Component Date Due Weight
Project December 15 40%
Exam December 05 30%
Homeworks, Class Presentations, Labs TBA 30%

Reference Books
Aho, Alfred V., Sethi, Ravi, Ullman, Jeffrey D., Compilers: Principles, Techniques and Tools, Addison-Wesley: Reading, MA, 1985. Muchnick, Steve S., Advanced Compiler Design and Implementation, Morgan Kaufmann Publishers Inc., 1997.
Morgan, Robert, Building an Optimizing Compiler, Butterworth-Heinemann, Boston, MA, 1998. Appel, Andrew W., Modern Compiler Implementation in C, Cambridge Univ. Press, 1998.
M. Wolfe, High Performance Compilers for Parallel Computing, Addison Wesley Longman, 1994. Allen, Randy, Kennedy, Ken, Optimizing Compilers for Modern Architectures: A Dependence-based Approach, Morgan Kauffman, 2001.

I am not aware of a single textbook that covers the topics taught in this class. In the first lecture I will discuss how each one of the books below cover the material and its relevance to the class. Therefore students should not buy books for this class before the term starts. Most of the topics studied in this class are presented in the textbooks below as well as in conference and journal papers.


Most Relevant Conference

This graduate class will study papers published in a number of conferences that publish compiler related research. Some of the most important conferences for this area include:

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)
International Symposium on Computer Architecture (ISCA)
International Conference on Parallel Architectures and Compilation Techniques (PACT)
Compiler Construction (CC)
International Conference on Compilers, Architectures and Synthesis for Embedded Systems (CASES)
International Workshop on Languages and Compilers for Parallel Computing (LCPC)
Languages, Compilers, and Tools for Embedded Systems (LCTES)
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)
International Workshop on Software and Compilers for Embedded Systems (SCOPES)

Class Projects: TBA
Project Team Mentor

Class Presentations: TBA

Here is the form that will be used for the presentation evaluations.

CMPUT680 Winter 2002 Mail Archive
CMPUT680 Winter 2001 Mail Archive

[University of Alberta]
University of Alberta
[Department of Computing Science]
Computing Science

"... unlike other classes where we work on illustrative problems that
everyone knows the answer before we start [in this class] we are working on
real problems that no one completely understands."

Cam Macdonell (Winter 2001)

"This is a class [in which] you will probably learn a lot. You will learn about computer architecture,
[about] things not to do when writing programs, and of course you will learn about all
sorts of different ways in which a compiler can optimize code."

Nathan Bullock (Winter 2001)

"The thing [that] I enjoyed the most was the collaboration between
everyone in the class in solving problems."

Cam Macdonell (Winter 2001)

"If you have interests in high-performance computing, this course
will help you know how to utilize the compiler to reach your goal."

Ling Zhao (Winter 2001)

"I learned that a good programmer with an understanding of compilers can write
programs that are very easy for a compiler to fully and cheaply optimize."

(Matthew McNaughton, Winter 2001)

"Before I took this class, ... I never thought that compilers could do
so many optimizations... there is so much stuff that I [now] admire... [some concepts] are
elegant, very simple, easy to understand, yet they started a new field of research."

(Ling Zhao, Winter 2001)

"Be aware that Nelson expects a lot from you. And thats a good thing :-). ... You
will build great friendships and have alot of fun as the class members work
together to learn the course material and [to] do the assignments."
(John Anvik, Winter 2001)

"Before this course, I thought that compiling was no more than some kind of translation.
[In this class] I became aware of crazy things that happen [to a program]!"

(Peng Zhao, Winter 2001)