Modern compiler optimization can take almost any code and produce a reasonably efficient binary at the end. However compiler "optimization" doesn't make your code "optimal", just better.
In contrast, superoptimization can produce perfect code - the fastest, the smallest or the most energy efficient code. The technique, first introduced in the late 80s found in some cases it could do 25% better than the best assembly programmer, and 40% better than the best compiler at the time.
Free software has always played a central role in superoptimization research, with the GNU Superoptimizer being one of the very first tools constructed.
However there is a downside. Superoptimization today is incredibly demanding of compute time, so currently it is limited to short instruction sequences. At present it is most valuable in optimizing code hotspots and key library routines, and can also be a valuable aid to the compiler writer for peephole optimization. Recent research has developed new techniques that can make superoptimization more applicable to general code.
In this talk I will introduce superoptimization and give some examples of the weird and wonderfully short sequences of code it produces. I will introduce the GNU superoptimizer and show how it is used, including some of the recent improvements I have contributed. The final part of my talk will look at the latest research including machine learning and constraint solving, and show how in future superoptimizers may be able to optimize much larger programs.
