Project 2: Implement an Optimization

• Proposal due: October 2, 2019
• Report due: October 23, 2019

Overview

This project is about compiler optimization. You can choose any optimization you can find in the literature (except for ones we examined in detail in class). You'll implement the optimization for Bril—so in the end, your "deliverable" will be a program that reads and writes Bril programs. The output program should do the same thing as the input program but be more efficient, for some definition of "efficient."

You must design and carry out a rigorous, thorough evaluation of your optimization. You'll want to evaluate both the correctness and the efficiency. You can pick any efficiency metric you like: code size in static Bril instructions, performance in dynamic Bril instructions, performance in wall-clock time of a particular compiler or interpreter backend, notional energy for some instruction-level cost model, etc.

Ideas

Here are some compiler optimizations you might select:

• Basic block layout, guided by profiling or branch heuristics.
• Some reasonable set of peephole optimizations, especially if you have an interesting angle such as automatically generating them or verifying them.
• Vectorization, either at the "loop level" or "basic block" level ("straight-line" vectorization).
• Loop unrolling, guided by a cost model.
• Software pipelining, also guided by a cost model. See this showdown, for example.
• Loop unswitching, where you hoist top-level conditionals out of loops by creating specialized variants.
• Loop interchange, given a suitable extension for multi-dimensional arrays.
• A nontrivial, probably context-sensitive, pointer analysis. (The efficiency would have to come from downstream optimizations that use alias information.)
• More elaborate global value numbering, including constant propagation extensions. See LLVM's NewGVN for inspiration.
• Function inlining. See this context-sensitive approach, for example.
• Function outlining, especially if the goal is code size reduction.
• A fancy polyhedral loop optimization.
• Sparse conditional constant propagation.
• Tail call elimination (regardless of whether you want to call this an "optimization").
• Loop invariant code motion.
• Lazy code motion.
• Strength reduction, but certainly focusing on more interesting replacements than power-of-two multiplications and divides.
• Deforestation, given a suitable list extension to the Bril language.
• Speculative software prefetching. If you're generating code for LLVM, for example, you can use its llvm.prefetch intrinsic.
• Devirtualization, given a suitable extension for indirect jumps.
• Soundly eliminating array bounds checks, assuming a Bril extension that includes unsafe array accesses.
• Induction variable elimination.
• Register allocation via graph coloring, assuming an extension that lets you address either "real" machine registers for some target or a virtual limited register set in Bril.
• Partial redundancy elimination.

Doing the Project

To find an optimization to implement, I invite you to look around at the compilers literature and even textbooks from other courses. Once you pick one, write your proposal (see the general project instructions) and link to any sources that describe what the optimization is all about. More so than for Project 1, be sure to include a detailed plan for your evaluation.

Depending on your optimization, the base Bril language may not be rich enough and you may need to extend it. That's absolutely fine—just be sure to describe what the extension will look like in your proposal.

You can choose whether to implement your optimization in the central Bril repository or in your own repository, depending on how useful you think it will be to other projects.

In your report (see the general instructions again), be sure the describe how you bridged the gap between the "theoretical" version of the optimization that you read in the literature and your real-world implementation. Give lots of detail on your experimental setup, your benchmarking approach, and the empirical results you gathered. While writing, keep your audience in mind: you're publishing this as a public blog post, so make it accessible to the technically-sophisticated public.