15-745 Optimizing Compilers

Spring 2006

Course Syllabus

The Course at a Glance

Lectures: Tuesdays and Thursdays, 10:30am-11:50am, WeH 5409 Instructor: Peter Lee, x-3049, email to "petel" Office hours Wed. 11am-noon or by appt., WeH 8216 TA: Mike DeRosa, WeH 8121, x-5943, email to "mderosa" Office hours TBA, WeH 8121 Class Admin: Angie Miller, x8-6645, WeH 8215, email to "amiller" Web Page: http://www.cs.cmu.edu/afs/cs/academic/class/15745-s06/web Textbook: Muchnick, Steven S., Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.

Course Objectives

This course explores the foundations and practical aspects of modern optimizing compilers. The course begins with the fundamentals of compiler optimization as currently practiced, and will then build upon these fundamentals to address issues in state-of-the-art commercial and research machines. Topics include: intermediate representations, basic blocks and flow graphs, data flow analysis, partial evaluation and redundancy elimination, loop optimizations, register allocation, instruction scheduling, interprocedural analysis, memory hierarchy optimizations, extracting parallelism, dynamic optimizations, and run-time. Students will design, implement, and evaluate significant optimizations within the framework of a realistic compiler.

Prerequisites

This course is not intended to be your first course on compiler construction or computer architecture. It is design for students who have already completed undergraduate-level courses on these topics. If you have not taken compiler and architecture courses already, it is still possible to take this course provided that you are willing to spend some additional time catching up on your own. It will also be helpful if you have some familiarity with the features of modern processor architectures (e.g., the memory hierarchy, pipelining, branch prediction, and instruction issue mechanisms) as well as strong programming proficiency in either Standard ML, Java, or Objective CAML. If you feel uncertain about whether you are adequately prepared to take this class, please discuss this with the instructor.

If You Are Not a CS or ECE Ph.D. Student

If you are not a graduate student in either the CS or ECE Ph.D. program, you need permission to take this class. If you have not already done so, send a message to the instructor stating your status, why you want to take the class, and if you want to take the class for credit or as an auditor. At the moment, all such students are on the course waiting list. The waiting list will be cleared upon receipt of your email.

Placing Out

Students who have already taken a graduate-level course in compiler optimization may find that some of this course material is familiar. It is likely that the focus and style of this course will be different from what you have experienced before, and that the pace will be fast enough that you will not be bored. However, if you feel strongly that you should be able to "place out" of all or part of this course, please discuss this with the instructor.

Course Work

Grades will be based on implementation tasks, a research project, a take-home worksheet, and class participation. Tasks: There will be roughly three implementation tasks. The goal of each task is to ensure that students gain hands-on experience with classic, fundamental concepts in compiler optimizations. Each task involves a non-trivial amount of programming. Please work in groups of two. (If you have difficulty finding a partner, please let us know, and we will help you find someone.) You will grade your own tasks by evaluating the performance of your generated target code and then submitting the results to us. Project: A major focus of this course is the project. We prefer that you work in groups of two on the project, although groups of up to three may be permitted depending on the scale of project (ask the instructor for permission before forming a group of three). The project is intended to be a scaled-down version of a real research project. The project must involve an experimental component--i.e. it is not simply a paper and pencil exercise. We encourage you to come up with your own topic for your project, although we will be posting suggested projects to the class web page at a future date. You will have at least six weeks to work on the project. You will present your findings in a written report (the collected reports may be published as a technical report at the end of the semester), and also during a poster session during the last day of class. Start thinking about potential project ideas soon! Worksheet: There will be a take-home worksheet covering the earlier (and more fundamental) portion of the course material. You will be required to complete all of the problems perfectly in order to get credit. The credit is all-or-nothing, so handing in early so that mistakes can be found and corrected is a very good idea. Class Participation: In general, we would like everyone to do their part to make this an enjoyable interactive experience (one-way communication is no fun). Hence in addition to attending class, we would like you to actively participate by asking questions, joining in our discussions, etc. Quite a few class periods are set aside entirely for student-led discussions on project proposals and active areas of research in compiler optimization. All students are expected to lead one of these discussions.

Grading Policy

This is a (very) tentative breakdown of the grading for this course. Tasks: 30% Project: 30% Worksheet: 20% Class Participation: 20% Late assignments will not be accepted without prior arrangement.

Course Schedule

Please see the course schedule here.