15-745 Optimizing Compilers

Spring 2006

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.

• Register 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 Rwebangira.

• Escape Analysis, by Paul Reitsma, Khalid El-Arini, and Andrew Cove.

• Program Dependence Graph Construction, by Michael Carl Tschantz.

• The Effects of Simple and Extended May-Alias Analysis, by David Abraham, Liz Crawford, Sue Ann Hong, and Virginia Vassilevska.

Project Resources

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.

• Machine 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 our readings).

• 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.

• Jikes 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 your project.

  • 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 project?

  • 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 implementation work.

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 be exploited?

• Project 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.

Past Projects

• Projects from the Spring'03 course.

• Projects from the Fall'03 course.