Guaranteed optimization: Proving nullspace properties of compilers

Abstract. Writing performance-critical programs can be frustrating be-cause optimizing compilers for imperative languages tend to be unpre-dictable. For a subset of optimizations – those that simplify rather than reorder code – it would be useful to prove that a compiler reliably per-forms optimizations. We show that adopting a “superanalysis ” approach to optimization enables such a proof. By analogy with linear algebra, we define the nullspace of an optimizer as those programs it reduces to the empty program. To span the nullspace, we define rewrite rules that de-optimize programs by introducing abstraction. For a model compiler we prove that any sequence of de-optimizing rewrite rule applications is undone by the optimizer. Thus, we are able to give programmers a clear mental model of what simplifications the compiler is guaranteed to perform, and make progress on the problem of “abstraction penalty ” in imperative languages.