CSE 231

CSE 231 -Advanced Compiler Design

Description

This course focuses on the analysis and optimization techniques needed to obtain high performance on current computer architectures.

Prerequisites

CSE 131A and B or equivalent, or consent of the instructor.

Class Times and Location

Tuesday & Thursday 3:55 to 5:20 pm
First class (Tues Mar 31): University Center 413 room 1
After the first class: APM 5402
Extra class: Fri May 15 3 pm in 4301: Special presentation by new faculty Andrew Chien
No class Thurs May 21

Staff

Name	Office	telephone	Office Hours	Email
Jeanne Ferrante	APM 4151	534-8406	By appt.	ferrante@cs.ucsd.edu
Nick Mitchell	APM 4338	534-5913	Project questions, by appt.	mitchell@cs.ucsd.edu

Course Text

Steve Muchnick, Advanced Compiler Design & Implementation. (The book's web page contains an errata for the text.)
Selected Papers

Syllabus

Ch 1-2 Overview of optimizing compilers
Ch 7 Graph structures for control flow analysis of programs
Ch 8 Data flow analysis of programs, Static Single Assignment form
Ch 9 Data Dependence of programs, Program Dependence Graph
Ch 11-12 Scalar Optimizations, Optimization based on Static Single Assignment
Ch 13 Redundancy Elimination
Ch 14 Loop Optimizations
Ch 5-6 Run-time support, Automatic Code Generators
Ch 16-17 Register Allocation, Instruction Scheduling
Ch 21 Case studies of compilers and future trends
Selected papers from the literature

Grading

1/3 - Project
1/3 - Homeworks
1/3 - Midterm ***Tues April 28, in-class, closed-book exam**** Exam solutions

Course Outline

Outline

Lectures

Lecture 1 --- Tues Mar 31
Lecture 2 --- Thurs Apr 2
Lecture 3 --- Tues Apr 7
Lecture 4 --- Thurs Apr 9
Lecture 5 --- Tues Apr 14
Lecture 6 --- Thurs Apr 16
Lecture 7 --- Tues Apr 21
Lecture 8 --- Thurs Apr 23
Lecture 9 --- Thurs Apr 30
Lecture 10 --- Tues May 5
Lecture 11 --- Thurs May 7
Lecture 12 --- Tues May 12
Lecture 13 --- Thurs May 14
Lecture 16 --- Tues Jun 2

Homework

Homework 1 --- Due Tues April 7 Solution
Homework 2 --- Due Thurs April 23 Solution
Extra Credit Homework --- Due Tues May 19
Homework 3 --- Due Tues May 26 Solution

Important Information: Homework Guidelines

Please read this.

Reading Assignments

Week 1: Ch. 1, 2, 7.
Week 2: Ch. 8.
Week 3: Efficiently Computing SSA and the Control Dependence Graph by Cytron, Ferrante, Rosen, Wegman and Zadeck, ACM Transactions on Programming Languages and Systems, Vol 13, No 4, Oct. 1991, pp. 451-490, and Ch. 9 (except for 9.2).
Week 4: 10.1, 11, 12.1-12.3, 12.4.1, 12.5, 13.1, 13.2
Week 5: 13.3-13.6
Week 6: 12.4.2, 12.6
Week 7: Ch 16, 9.2, 17.1
Week 9: Dynamic Pointer Alignment: Tiling and Communication Optimizations for Parallel Pointer-Based Computations, X. Zhang and A. Chien, 1997 PLDI.
Tuning Compiler Optimizations for Simultaneous Multithreading Lo, Eggers, Levy Parekh and Tullsen, 1997 Micro.
Week 10: Ch 21

Project

Part I: Control Flow Graphs and Loop Structure --- Due TUES April 21
Part II: Constructing SSA Form --- Due THURS May 14
Part III: Optimization Using SSA Form --- Due Tues Jun 9

Important Information: Project Guidelines

Please read this.

Important Information: Project Turnin

Please read and follow carefully!

Frequently Asked Questions on the Project:

Check here first!

Getting Started with Simple Suif

Introduction to Simple Suif

Here are some SUIF pointers.