GNU Superoptimizer - Summary

This software is part of the GNU Project.

The superoptimizer is a function sequence generator that uses an exhaustive generate-and-test approach to finding the shortest instruction sequence for a given function.  You have to tell the superoptimizer which function and which CPU you want to generate code for, and how many instructions you can accept.

The superoptimizer can't generate very long sequences, unless you have a very fast computer or very much spare time.  The time complexity of the used algorithm is approximately: O (m n ^(2n)), where m is the number of available instructions on the architecture and n is the shortest sequence for the goal function.  The practical sequence length limit depends on the target architecture and goal function arity; In most cases it is about 5, but for a rich instruction set as the HPPA it is just 4.  The longest sequence ever generated was for the MC68020 and 7 instructions long.  It took several weeks to generate it...

Registration Date: Tue 20 Oct 2020 06:31:07 PM UTC
License: GNU General Public License v3 or later
Development Status: 4 - Beta