Superoptimization
Compilers translate software into code executed by actual processors, but that translation is not always as efficient as desired, even when using traditional optimization techniques are used. Superoptimization attempts to find the the theoretically best translation of a block of code (in terms of code size, execution speed and energy efficiency). The first attempts were made over 30 years ago using using exhaustive searching and were thus computationally extremely demanding. In the intervening time, significant advances have been made, both by heuristic improvements to the search algorithm and by the increase in compute power available. However it remains a technique of purely academic interest.
In the summer of 2014, Innovate UK funded Embecosm to carry out a feasibility study of commercial applications for superoptimization. The full report is available as Embecosm Application Note 15. It came up with three core recommendations.
- Superoptimization using heuristic exhaustive searching is a viable optimization technique for small code blocks which form the core of performance-critical software applications;
- Within the compiler, superoptimization provides an effective technology for creating target specific peephole optimization passes; and
- In the medium term, constraint based techniques for superoptimization have the potential to allow superoptimization of larger blocks of code.
In all three cases, the report noted that further work was needed to create practical tools. For a long time, the state-of-the-art was the GNU Superoptimizer (GSO), now a quarter of a century old. More recently a Stanford University have created STOKE, a stochastic superoptimizer, now available as an open source tool.
In the intervening time since GSO was written, computers have become more powerful, they have become multi-core, formal methods have advanced, and a large number of heuristics have been developed. What is now needed is not a single tool, but a framework for deploying a range of superoptimization techniques in a way that can take advantage of parallel computing. Only with this in place commercial superoptimization becomes practical.
Under the Innovate UK funded TSERO project, Embecosm created an initial implementation of such a framework, the GNU Superoptimizer 2.0 or GSO 2.0. Initial testing of the framework used the Atmel AVR architecture, and outperformed the best GCC results in 6 out of 10 cases , offering improvements of between 47% and 64%. Development of GSO 2.0, particularly to support constraint based superoptimization is a research priority for Embecosm.
Embecosm is currently able to use existing superoptimization technology to create peephole optimizers and to superoptimize specific applications. We also welcome partners to help develop the technology of GSO 2.0 for the future.