Superoptimization

Superoptimization is the task of finding the optimal code sequence for a single, loop-free sequence of instructions. While garden-variety compiler optimizations really just "improve" code (and it is an accident if it produces genuinely "optimal" code), a superoptimizer's goal is to find the optimal sequence at the outset.

The term superoptimization was first coined by Henry Massalin in his [http://portal.acm.org/citation.cfm?id=36194 1987 paper] and then later developed for integration within the GNU Compiler Collection ( [http://portal.acm.org/citation.cfm?id=143146 GSO] 1992). Recent work has further developed and extended this idea: ( [http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-171.html 2001] , [http://dx.doi.org/10.1007/11799573_21 2006] , [http://cs.stanford.edu/~sbansal/pubs/asplos06.pdf 2006] ).

Typically, superoptimization is performed via exhaustive search in the space of valid instruction sequences. While this is an expensive technique, and therefore impractical for general-purpose compilers, it has been shown to be useful in optimizing performance-critical inner loops. [http://cs.stanford.edu/~sbansal/pubs/asplos06.pdf Recent work] has used superoptimization to automatically generate general-purpose peephole optimizers.

External links

Publicly available superoptimizers:

* [http://ftp.gnu.org/gnu/superopt GNU Superoptimizer (GSO)] (1992)
* [http://krr.cs.bath.ac.uk/index.php/TOAST TOAST Superoptimiser] (2006)
* [http://www.hackersdelight.org/aha.zip The Aha! (A Hacker's Assistant) Superoptimizer] (2006)
* [http://theory.stanford.edu/~sbansal/superoptimizer.html Stanford's Superoptimizer] (2006)