Lectures: | MW 3:00pm-4:20pm, F 10:30am-11:50am, WeH 4615A |
Instructor: | Todd C. Mowry, WeH 8123, 268-3725, tcm@cs.cmu.edu |
TA: | Dave Koes, WeH 3723, 268-1685, dkoes@cs.cmu.edu |
Class Admin: | Jennifer Landefeld, WeH 8124, 268-4740, jennsbl@cs.cmu.edu |
Web Page: | http://www.cs.cmu.edu/afs/cs/academic/class/15745-f03/www/ |
Newsgroup: | cmu.cs.class.cs745 |
Handouts: | Electronic: /afs/cs.cmu.edu/academic/class/15745-f03/public |
Hardcopies: In bins outside WeH 8124. |
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. If you have not taken a compilers course 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). If you feel uncertain about whether you are adequately prepared to take this class, 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 | Who |
1 | 9/12 | Fri | Overview of Optimizations | 1.3-5, 2.1-9 | #1 Out | TCM |
2 | 9/15 | Mon | Programming in SUIF | 4.1-6, 4.9-10 | TCM | |
3 | 9/17 | Wed | Local Optimizations | 7,7.1-4,18.1-3 | TCM | |
4 | 9/19 | Fri | Data Flow Analysis: Examples | 8.1, 14.1.13 | TCM | |
5 | 9/22 | Mon | Data Flow Analysis: Theory | 8.2-5 | #1 Due, #2 Out | TCM |
6 | 9/24 | Wed | Global Common Subexpr. Elimination | 13.1 | TCM | |
7 | 9/26 | Fri | Loop Invariant Code Motion | 13.2 | TCM | |
8 | 9/29 | Mon | Induction Variables, Strength Reduction | 14.1 | TCM | |
9 | 10/1 | Wed | Partial Redundancy Elimination | 13.3 | TCM | |
10 | 10/3 | Fri | Interval Analysis | 7.5-7, 8.8 | TCM | |
11 | 10/6 | Mon | Intro to Static Single Assignment (SSA) | 8.10-11,12.6 | #2 Due, #3 Out | TCM |
12 | 10/8 | Wed | SSA-Style Optimizations | TCM | ||
13 | 10/10 | Fri | Recent Research on Optimization I | handouts | N/A | |
14 | 10/13 | Mon | Recent Research on Optimization II | handouts | N/A | |
15 | 10/15 | Wed | Recent Research on Optimization III | handouts | N/A | |
10/17 | Fri | No Class (Mid-Semester Break) | ||||
16 | 10/20 | Mon | Register Allocation: Coloring | 16.1-3 | #3 Due | DK |
17 | 10/22 | Wed | Register Allocation: Spilling | 16.3.10, 16.3.12 | DK | |
18 | 10/24 | Fri | Instr Scheduling: List Scheduling | 17.1, 17.4.3, 17.5 | Project Proposal | TCM |
19 | 10/27 | Mon | Instr Scheduling: Speculation | 17.2.3 | TCM | |
20 | 10/29 | Wed | Instr Scheduling: Software Pipelining | 20.3, 17.4 | TCM | |
10/31 | Fri | Exam | ||||
21 | 11/3 | Mon | Memory Hierarchy Optimizations | 20.1-6 | TCM | |
22 | 11/5 | Wed | Prefetching | 20.4.4 | TCM | |
23 | 11/7 | Fri | Automatic Parallelization I | 9.3-7 | TCM | |
24 | 11/10 | Mon | Automatic Parallelization II | TCM | ||
25 | 11/12 | Wed | Dynamic Code Optimizations | TCM | ||
26 | 11/14 | Fri | Case Studies, Embedded Systems | DK | ||
11/19 | Wed | Project Milestone | TCM | |||
12/3 | Wed | Project Due | TCM | |||
12/5 | Fri | Project Poster Session |
Back to CS745 home page.