CMPUT 680 COMPILER DESIGN AND OPTIMIZATION 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)

LATEST ANNOUNCEMENT:

Fall 2006

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

Lectures

• Topic0: Introduction (HTML) ( Powerpoint)
• Topic1: Brief History of Speculation and Predication (HTML) (Powerpoint)
• Topic2: Parsing (HTML) (Powerpoint)
• Topic3: WHIRL (HTML) (Powerpoint)
• Topic4: Flow Analysis (HTML) (Powerpoint)
• Topic5: PeepHole Optimization (HTML) (Powerpoint)
• Topic6: Code Generation (HTML) (Powerpoint)
• Topic7: Register Allocation (HTML) (Powerpoint)
• Topic8: Minimum Register Instruction Sequencing (HTML) (Powerpoint)
• Topic9: Register Saturation (HTML) (Powerpoint)
• TopicA: Data Dependence in Loops (HTML) (Powerpoint)
• TopicB: Loop Restructuring (HTML) (Powerpoint)
• TopicC: Loop Fusion (HTML) (Powerpoint)
• TopicD: Index-Set Splitting (Powerpoint)
• TopicE: Software Pipelining (HTML) (Powerpoint)
• TopicF: IA-64 Hardware Support for Software Pipelining (HTML) (Powerpoint)
• TopicG: Static Single Assignment (HTML) (Powerpoint)
• TopicH: Psi-SSA (HTML) (Powerpoint)
• TopicI: Superblocks and Hyperblocks (HTML) (Powerpoint)
• TopicJ: Wavefront Scheduling (HTML) (Powerpoint)
• TopicP: Reference Analysis (HTML) (Powerpoint)
• TopicQ: Binary Decision Diagrams (HTML) (Powerpoint)

Assignments

• Homework #1: Lex and Yacc (Due: September 15)
• Homework #2: Data and Control Flow ( .ps ) ( .pdf ) (Due: October 02 2006, in class)

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.

Prerequisites

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.

Course Outline

• Motivation: Integrating Architectured Features in Compiler Design
• Fundamentals of Code Generation
• A Tour of Compiler Design
• Flow Analysis
• Peephole Optimization and Optimal Code Generation
• Basic Back-End Optimization
• Data Dependence Analysis in Loops
• Interval Graphs
• Loop Scheduling
• Hardware Assisted Software Pipelining
• An Overview of the Pro64 Compiler Infra-structure
• Static Single Assignment Form
• The Optimal Code Generation Problem

Grades
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.

Resources

• Open Research Compiler (ORC)
  • ORC Tutorial Presented at Micro-34, Austin, TX, December 2001.
  • Description of WHIRL (ORC intermediate level representation).
  • WHIRL Symbol Table Specification
  • ORC Comand Line Flags
• Jikes RVM and Compiler
  • Slides introducing Jikes RVM Presented at OOPSLA 2002.
  • Jikes RVM User's Guide.
  • Slides on Jikes Intermediate Representation Prepared by Shane Brewer.
• McGill Tool Suite:
  • Soot
  • STEP

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

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)