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.

  1. Superoptimization using heuristic exhaustive searching is a viable optimization technique for small code blocks which form the core of performance-critical software applications;
  2. Within the compiler, superoptimization provides an effective technology for creating target specific peephole optimization passes; and
  3. 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.

Pages in this section

Research

SECURE

2017-. The compiler is ideally placed to help the user write secure code. The SECURE project is applying the latest academic research in this area to production GCC and LLVM compilers.

Research

AAP

2015-. An Altruistic Processor (AAP) was created to advance compiler technology for deeply embedded processors with a restricted register set and complex memory structures.

Research

GSO 2.0

2015-. GSO 2.0 is a tool kit under development by Embecosm, allowing multiple approaches to superoptimization to be used.

Research

TSERO

2015-2017. TSERO was a follow on project to the MAGEEC and Superoptimization projects looking at compiling energy efficient code for high performance computing systems and data centers.

Research

Superoptimization

2014. This feasibility study established the feasibility of using superoptimization to improve performance of critical code sections and to create new machine dependent peephole optimization passes for compilers

Research

MAGEEC

2013-2014. The MAGEEC research project aimed make machine learning feasible in commercial compilers, specifically for generating energy efficient code on deeply embedded systems.