Superoptimization

From Wikipedia, the free encyclopedia

Superoptimization is the technique to find the optimal code sequence for a single, loop-free assembly sequence of instructions. While a garden variety code optimizer really just improves code (and it is an accident if it produces optimal code), a superoptimizer's goal is to find the optimal sequence at the very outset.

The term superoptimization was first coined by Henry Massalin in his 1987 paper. Subsequently, only three more papers have developed this idea (1992, 2001, 2006).

Typically superoptimization is performed through an exhaustive search in the space of valid instruction sequences. While this is an expensive technique, it has been shown to be useful in optimizing performance critical inner loops. Recent work used superoptimization to automatically generate general purpose peephole optimizers BA06.

[edit] External links

[edit] Publicly available code superoptimizers:

• Stanford's Superoptimizer 2006 (information)
• GNU Superoptimizer 1992
• The Aha! (A Hacker's Assistant) Superoptimizer 2006