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 |
Muchnick, Steven S., Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.
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.
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.
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.
Grades will be based on homeworks, a research project, an exam, and class participation.
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.
Table 1 shows the tentative schedule. There might be some variations.
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.