15-745 Optimizing Compilers
Spring 2006 Project Web Pages
- Extended Static
Checking for L3, by Kumar Avijit and Swapnil V. Patil.
- Cache-sensitive Optimization of Immutable Graph Traversals,
by Uri Dekel and Brett Meyer.
- Incremental Path
Profiling, by Kevin Bierhoff and Laura Hiatt.
Allocation via Chordal Graph Coloring in a HOT Compiler, by Daniel Lee and Bryan Mills.
- Effect Profiling, by Katrina Ligett and Noam Zeilberger.
- Static Garbage Collection for L3, by Neelakantan Krishnaswami
and William Lovas.
- Static Reference Counting, by Todd Phillips and Mugizi
- Escape Analysis, by Paul Reitsma, Khalid El-Arini, and Andrew
- Program Dependence Graph Construction, by Michael Carl
Effects of Simple and Extended May-Alias Analysis, by David
Abraham, Liz Crawford, Sue Ann Hong, and Virginia Vassilevska.
There are many compiler infrastructures used by researchers today. You are
welcome (even encouraged) to use the L3 infrastructure. By now you should
be quite familiar with it and the intermediate language provides many
opportunities for further analysis and optimization on a realistic scale.
You might also be interested in choosing an alternative compiler
infrastructure for your project. There are various reasons for this. Most
real compiler infrastructures are much larger and support real-world
programming languages, like C or ML. This makes your project more "real",
at the expense of a lot of extra implementation detail. Also, other
infrastructures are not tied to the x86 target architecture, but may
support machines such as the Itanium. Finally, you might be planning to
devote much of your graduate studies to compiler development. In that
case, a more comprehensive infrastructure might be very useful for you, in
the long run.
In general, you are advised to use the infrastructure that most directly
allows you to address the problem or idea you are working on.
Here are some links:
- The SUIF 2
Compiler System. This is perhaps the major research compiler
infrastructure in use today. It supports a great many basic and exotic
data structures and provides a large assortment of tools and hooks for
adding your own analyses and optimizations. A full-blown C front end
is also provided.
SUIF (machsuif). MachSUIF is an off-shoot of SUIF that focues
primarily on code-level (machine-specific) analyses and
optimizations. Support for the Itanium processor is one of the most
important features for many researchers.
- Trimaran. This in frastructure
focuses on compiling for instruction-level parallelism, targeting
specifically EPIC-style instruction sets (which are described in one of
- MLton. This is an increasingly
important research compiler infrastructure for the Standard ML language.
It is convenient for its relatively clean construction and the fact that
it uses whole-program optimization.
Research Virtual Machine. This is perhaps the most important
framework for research in Java compilation (formerly known as
Jalapeno). This has been a particularly important research vehicle for
exploring issues in dynamic compilation and garbage collection.
- Soot. This is an
alternative research Java compiler from McGill University. It is much
simpler than Jikes and thus easier in many ways to modify.
- GCC. A highly portable C compiler,
gcc continues to be one of the most popular choices by researchers.
Project Proposal Guidelines
Your project proposal should be roughly two pages long. You are strongly
encouraged to discuss in person or send email with your idea to Peter Lee
before getting too far into writing. Feel free to see me during office
hours or by appointment.
Your proposal should include the following information:
- Team information. The names and email addresses of each group
member. Each team should have two people, though in exceptional cases we
may allow a group of three.
- Project web page. Please set up a simple web site for your
project. This web site should contain, initially, your proposal and then
later your final results. We will provide links to your web sites from
the main course web site.
- Project Description. Briefly describe the following aspects of
- Goal. What is the problem or question you are trying
to address with this project? You can try to choose a problem or
question that is related to some contemporary idea or research in
modern compilers. Alternatively, you might think of a new approach to
an existing problem.
- Background. What are some of the relevant papers and other
background materials that are relevant to your project? Are you
missing anything? Please provide a small bibliography.
- Approach. How will you go about completing your project?
Will you implement something? If so, what? What experiments will you
conduct? What metrics will be used to evaluate the success of your
- Plan. This is a very short project, and so a schedule is not
really needed. However, you should describe what resources you will
need (for example, what software will be used) and what machines or other
hardware will be needed. If there are significant milestones, please
describe them here. Also, please consider a fall-back plan, in case
your progress is not as good as expected or if some aspect of the
implementation or experimentation fails to produce the expected results.
Please put a copy of your proposal on your web site, and turn in (by
email) your URL to Mike by the due date of April 3, 2006.
Project Ideas and Requirements
Your projects are not expected to produce ground-breaking research
results. However, they are expected to go beyond an
undergraduate-level compiler project, in the sense that they should address
concepts and problems that are relevant to today's research. We also
expect your project to have an experimental component, which typically
means doing at least some (and in many cases, a large amount) of
In the end, your final results will be presented by a combination of
text+pictures on your project web site, plus a poster presentation. We'll
have a small poster session (date and time TBD) during the finals week.
Here are some ideas (not all of them carefully thought through, so please
be careful!), to help you get started with brainstorming.
- SSA-based register allocation. One of our readings and David
Koes' lecture discuss the possible benefits of performing graph
coloring-based register allocation on an SSA form. These benefits
include a simplified implementation and better allocation results. Are
these claims valid?
- Scheduling and allocation. The L3 compiler we have supplied
does not perform instruction scheduling, nor does it seem all that
profitable, given that it targets the x86 architecture (which, in the
Pentium4 implementation, provides OOOE). But even with OOOE it is
possible that large movements of instructions may yield benefits. One
approach to enabling large movements of code is to identify long
traces, create new large basic blocks from those traces, and then
perform scheduling (e.g., list scheduling) before register allocation.
Does this provide a benefit on a machine with OOOE?
- Escape analysis. By default, the L3 compiler allocates all
"large" data objects in the garbage-collected heap. This is true for
most compilers for languages that allow functions to dynamically
allocate such objects and then return them as results. (Can you see
why?) But in some cases, heap allocation isn't necessary. Is there a
performance gain by stack-allocating large objects whenever possible?
- Static reference counting. At the moment, all of the
storage for dynamically allocated data is reclaimed by a conservative
garbage collector. In fact, the run-time system for L3 doesn't even
provide a "free()" primitive. But it is sometimes possible to detect
statically when a structure is no longer useful, and therefore reclaim
its storage immediately (and thereby delay the need for automatic
garbage collection). This is often referred to as static reference
counting. What is the impact of this approach?
- First-class (and nested) procedures. What is the impact of
having higher-order functions on optimization? Does it make a
difference whether or not nested function definitions are allowed?
- Cache locality optimizations. We have seen in class and in
readings the importance of cache optimizations for certain kinds of
programs. But the precise optimization performed depends on
machine-specific details, such as cache line size. How would one
organize a compiler to be smart about these sorts of issues?
- Cache optimizations, 2. How feasible is it to go beyond
array-based codes for cache optimizations? Is it possible to analyze,
say, tree-based programs (perhaps with programmer-supplied annotations)
and choose data layouts that improve memory performance?
- Alias analysis. The possibility of aliasing blocks many
optimizations. What is the performance impact of simple may-alias
information in a compiler?
- Limited run-time optimization. Full-blown run-time
optimization can be quite hard to implement. But some limited forms
are easier and still potentially beneficial. For example, there may be
relatively easy run-time optimization opportunities in knowing (at
run-time) that two arrays are the same length, or that one integer
variable is smaller than another. How could such run-time information
ideas from the Spring'05 course. Many of these suggestions
are Pegasus-specific. (Pegasus is Seth Goldstein's research
compiler infrastructure.) Still, there are some nice ideas here.