15-745 Spring '03
Syllabus

Course Details at a Glance

Lectures: Mondays and Wednesdays, 1:30-2:50 p.m., WeH 4615A
Instructor: Todd C. Mowry, WeH 8123, 268-3725, tcm@cs.cmu.edu
TA: Pedro Artigas, WeH 4112, 268-3047, artigas@cs.cmu.edu
Class Administrator: Jennifer Landefeld, WeH 8124, 268-4740, jennsbl@cs.cmu.edu
Web Page: www.cs.cmu.edu/afs/cs/academic/class/15745-s03/www/
Newsgroup: cmu.cs.class.cs745
Course Materials: /afs/cs.cmu.edu/academic/class/15745-s03/public

Textbook

Muchnick, Steven S., Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.

Course Overview and Objectives

Theoretical and practical aspects of building optimizing compilers that effectively exploit modern architectures. The course will begin with the fundamentals of compiler optimization, and will 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, and dynamic optimizations. Students will implement significant optimizations within the framework of a modern research compiler.

Prerequisites

This course is not intended to be your first compilers course; it is geared toward students who have already had such a course as undergraduates. For example, we expect that people are already at least somewhat familiar with basic blocks, control flow graphs, activation frames, etc. Furthermore, some familiarity with the features of modern processor architectures (e.g., the memory hierarchy, pipelining, branch prediction, and instruction issue mechanisms) will be extremely helpful. If you have not had such a course already, then it is still possible to take this course provided that you are willing to spend some additional time catching up on your own. If you feel uncertain about whether you have adequate preparation, please discuss this with the instructor.

If You Are Not a CS or ECE PhD Student

If you are not a graduate student in either the CS or ECE PhD 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.

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 homeworks, a research project, an exam, and class participation.

Homeworks:
There will be roughly three homework assignments. Each assignment involves a non-trivial amount of programming. Please work in groups of two on the assignments. (If you have difficulty finding a partner, please let us know, and we will help you find someone.) Turn in a single writeup per group.

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 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!

Exams:
There will be one exam covering the earlier (and more fundamental) portion of the course material. The exam will be closed book, closed notes.

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. Three classes are set aside entirely for student-led in-class discussions on active areas of research and innovation in compiler optimization. All students are expected to lead one of these discussions.

Grading Policy

To pass this course, you are expected to demonstrate competence in the major topics covered in the course. Your overall grade is determined as follows:

Exam: 35%
Homework: 20%
Project: 35%
Class Participation: 10%

Late assignments will not be accepted without prior arrangement.

Schedule

Table 1 shows the tentative schedule. There might be some variations.


  
Table 1: 15-745, Spring 2003, Tentative Schedule.
Class Date Day Topic Reading Assignments
1 1/13 Mon Overview of Optimizations 1.3-5, 2.1-9  
2 1/15 Wed Programming in SUIF 4.1-6, 4.9-10 #1 Out
  1/20 Mon No Class (MLK Day)
3 1/22 Wed Control Flow Analysis 7,7.1-4,18.1-3  
4 1/27 Mon Data Flow Analysis: Examples 8.1, 14.1.13  
5 1/29 Wed Data Flow Analysis: Theory 8.2-5 #1 Due, #2 Out
6 2/3 Mon Global Common Subexpr. Elimination 13.1  
7 2/5 Wed Loop Invariant Code Motion 13.2  
8 2/10 Mon Induction Variables, Strength Reduction 14.1  
9 2/12 Wed Partial Redundancy Elimination 13.3 #2 Due, #3 Out
10 2/17 Mon Static Single Assignment 8.10-11,12.6  
11 2/19 Wed Interval Analysis 7.5-7, 8.8  
12 2/24 Mon Recent Research on Optimization I handouts  
13 2/26 Wed Recent Research on Optimization II handouts  
14 3/3 Mon Recent Research on Optimization III handouts  
15 3/5 Wed Register Allocation: Coloring 16.1-3 #3 Due
16 3/10 Mon Register Allocation: Spilling & IPA 16.3.10, 16.3.12  
17 3/12 Wed Instruction Scheduling 17.1, 17.4.3, 17.5  
18 3/17 Mon Software Pipelining 20.3, 17.4 Project Proposal
  3/19 Wed Exam
Spring Break (3/24-3/28)
19 3/31 Mon Speculation & Predication 17.2.3  
20 4/2 Wed Memory Hierarchy Optimizations 20.1-6  
21 4/7 Mon Prefetching 20.4.4  
22 4/9 Wed Interprocedural Analysis 19.1-5  
23 4/14 Mon Pointer Analysis 8.12, 10 Project Milestone
24 4/16 Wed Dynamic Code Optimizations    
25 4/21 Mon Automatic Parallelization I 9.3-7  
26 4/23 Wed Automatic Parallelization II    
27 4/28 Mon Case Studies   Project Due
  4/30 Wed Project Poster Session

Back to CS745 home page.