CSE 231: Advanced Compilers

Implementation Projects

Take heed:   All these project are awesome, but they're also challenging. Start early, ask lots of questions, and keep us posted on your progress.

Finding Bugs in Language Implementations

Our friends at Utah created CSmith, a tool that uses "differential random testing" to find both crash bugs (annoying) silent optimization errors (terrifying!) in C compilers. Using their technique, they've found hundreds of bugs in mature, widely deployed C compilers. For example, they found multiple bugs in LLVM, GCC, and ICC, and these are the compilers you use every day, the compilers that most *nix software is built with! Your project will be to adapt the ideas from CSmith to another language implementation, e.g. Python or JavaScript, hopefully finding major bugs along the way.

Code Perforation

Want your code to run 2x or 3x faster and use less power? Just skip a few loop iterations here and there! Perhaps this sounds crazy (that's why we call it research), but it turns out out that for many programs you can just jump over parts of the code without totally destroying the computation. This technique, called Code Perforation, can improve performance, save power, and make programs more robust in the face of errors. Your project will be to explore existing code perforation techniqes, measure them on various benchmarks, and then cook up your own code perferation analysis to determine where and when computations can be dropped.

Parallelizing Transformations

Your goal will be to explore some parallelizing transformations/optimizations. There are many possibilities here, including exploring topics related to Mapreduce optimizations (for example, see the FlumeJava paper). More details to come.

Compiling a Domain Specific Language

Pick a Domain Specific Language and/or some specialized hardware, and write a compiler for such a language. As an example, in a previous quarter, a group built a compiler that takes musical score descriptions, and compiles them down to a board that plays the music. Another group designed a Domain Specific Language for controlling LED light signals, and used it to program the big-toe LEDs.


Ironically, there's rarely anything optimal about the code produced by a compiler's optimizer. However, when it comes to superoptimizer, it's a different story all together. Unlike traditional optimizers, superoptimizers produce code that is guaranteed optimal for certain parts of programs. The Stanford Superoptimizer in particular has been shown to provide up to 10x speedups for compute intensive kernels on x86! However, there are still plenty of challenges left before superoptimization becomes mainstream. One issue is that determining when one program fragment is better than another, i.e. the cost of a program, can be extremely difficult. Another, related issue, is that optimizations that help tremendously on one machine make almost no difference on the next machine. Your project will be to replicate the results from the Stanford SO project and then attempt to improve on them by developing a refined cost model for programs, preferably informed by some form of profiling.

Finding Bugs in Applications

Over the past decade there's been steady progress in automatic test generation. Current techniques can often far outperform human-written test suites, often achieving extremely high coverage in terms of lines of code exercised. In fact, one tool even found 3 serious bugs in GNU Coreutils, the main suite of programs powering many, many of today's *nix machines. This is surprising, as GNU Coreutils is one of the most widely used pieces of open source software, and yet these bugs remained undetected for nearly 15 years. Another example, the following paper found energy bugs in Android applications. Some of these bug finders and test generators take advantage of domain specific information while others are general purpose. Your project will be to implement a bug finding tool for a class of applications of your choice and attempt to uncover subtle programs errors that would elude testing or inspection by mere humans.