COMP 512 examines a variety of topics that arise in the design and
implementation of an optimizing compiler.
In previous years, it has been taught as a lecture course.
See, for example, the lecture notes
from last year for a impression of its breadth and scope.
(Last year's web site is at the bottom of this page.)
In the Fall of 2007, COMP 512 is being taught as a readings course.
We will meet on Mondays to discuss one or more papers.
In addition to the readings, each student will
select an optimization, research the algorithms, and implement
that technique in the LLVM compiler system.
Students will be do an oral presentation on their project and
present numbers showing improvement from applying their optimization
to suitable benchmarks.
We will meet some Wednesdays to
discuss the lab projects.
The papers that we read, along with many others, are posted on a
web page
that is accessible only from computers on the Rice campus.
Second reading: Read Kennedy's "A Survey of Data-flow Analysis
Techniques" (17 on the readings page).
You may also find Sections 8.6 and 9.2 of Engineering a Compiler and
lectures 4, 5, and 7 from last year useful in understanding the material.
Third reading: Read Cytron et al. "Efficiently Computing Static
Single Assignment Form and the Control Dependence Graph"
(5 on the readings page) and
Briggs et al., "Practical Improvements to the Construction and Destruction
of Static Single Assignment Form"
(18 on the readings page).
Lecture notes from last year on SSA may be helpful; Chapter 9 of
Engineering a Compiler may also be of help.
Fourth Reading: Constant Propagation.
Read Wegman and Zadeck's paper "Constant Propagation with Conditional
Branches" (number 19 on the readings page).
Re-read the section on constant propagation in Ken's survey paper,
page number 45 and following in the published version (number 17 on
the readings page).
If you are still curious, read "A unified approach to global program
optimization" by Gary Kildall (number 61 on the readings page).
The first couple of pages lay out his approach to constant propagation
(This paper is among the most mis-cited papers I know; people credit
this paper with developing the full theory of lattice-based data-flow
analysis.)
Fifth Reading: Global Value Numbering.
Read Karthik Gargi's Paper, "A Sparse Algorithm for Predicated
Global Value Numbering" (number 62 on the readings page).
It derives, in part, from Simpson's "SCC-Based Value Numbering"
(number 63 on the readings page). You should pay attention to the
material on rewriting the code in this paper, as Gargi's paper
fails to cover this part of the process.
For additional insight, read Alpern, Wegman, and Zadeck's "Detecting
Equality of Variables in Programs" (number 31 on the readings page).
Last Year's Site
The book will use several chapters from the book
Engineering a Compiler.
If needed, we will put a copy or two on reserve in the library.
As in past years, we will also use a large collection of papers.
Citations for these papers will appear on the web site as the
course progresses.
Most of them should be available in Fondren Library. If not, I will
make them available.
COMP 512 does not cover automatic detection of
parallelism; for that material,
take COMP 515.
Requirements
This will be a lecture-format class.
It will have a mid-term exam and a final exam.
It will have three laboratory exercises; the details
will depend on enrollment.
Lecture Notes
I will post PDF-format copies of the slides used in class as
they become available.
The SSA lecture is here. The dead/cprop lecture
is here.
The minimalistic page to get the homework handouts is here.
Reading
The syllabus will be similar to earlier years.
We will use material drawn from Chapters 8, 9, \& 10 of
Engineering a Compiler by Cooper & Torczon, as well as many
papers and technical reports.
When possible, the reading material will be made available online.
For a variety of reasons, it must be posted
on a page that is accessible only to the
Rice community.
Some of these documents are works in progress and not intended
for distribution to a wider audience.
This site is maintained by Keith D. Cooper.
He is a terrible e-mail correspondent.
