15-745 Optimizing Compilers

Spring 2006

Taking Baby Steps

The tasks for this course involve making modifications to an L3 compiler. The L3 compilers we have provided are, relatively speaking, very small and simple, but nevertheless they are real compilers, and real compilers are always big and complicated. Getting started with adding optimizations can be intimidating.

If you are feeling intimidated, here are some simple tips to help you get started.

  • Focus on the IR. Make sure to read the documentation on L3 compiler internals and try to familiarize yourself with the classes/modules described there. It is important to keep in mind that you do not have to understand the whole compiler. For very good engineering reasons, intermediate representations (IRs) are designed to be fairly self-contained, and so for the most part you can focus your attention completely on the IR. Try to trust what the rest of the compiler is doing.

  • Sneak up on it. As a way of dipping your toe in the water, try writing a simple function that scans the IR, looking for definitions of temps. Add some debugging code to print out the number of such definitions found. While this seems simple, it will give you the experience of handling the IR and hooking a simple analyzer into the compiler.

  • Start together, then split the work. Work with your partner on an implementation of reaching definitions analysis. Make sure to implement some kind of debugging output as well, and then hook this into the compiler to see how it works. Once you have this in hand, you and your partner can start to divide the work, with one person implementing simple constant propagation, another implementing liveness analysis, etc. You might consider starting at first with a reaching definitions that operates on every statement, and once that is well in hand, consider changing this to work on basic blocks instead. Note, however, that basic blocks analysis is probably not critical for Task 1, though certainly it will provide a useful speedup for your compiler.

  • Keep the goal in mind. All three dataflow analyses you need for Task 1 (reaching definitions, liveness analysis, and available expressions) are simple in structure (working over BVn) and similar in implementation. You can simply do a kind of copy-and-paste for each dataflow analysis, or try to be smarter and go for a more generic implementation that can be reused. But note that we will not be grading you on how good your code is, so don't worry a huge amount of you end up repeating code for no good reason...

  • KISS. Keep your transformations simple! You will be tempted at times to be "fancy" with your code transformations. Don't do this! It is standard advice in compiler construction to keep each transformation simple, and instead try to use all of the simple transformations together (perhaps iteratively) to make the code improvements. Implementing code transformations is surprisingly hard and error prone. Don't fall into the trap of doing more in any single transformation than is needed.

  • Most of all, DON'T PANIC! Mike and I will be assessing you based on how many programs in the test suite you improve. We are asking you to do this via four classical optimizations, but it is perhaps possible to get wide improvement with fewer optimizations. So, don't panic if you run out of time. You are on your honor to complete the tasks as specified, but ultimately the only thing that counts is how well you improve run-time perrformance.