# GNU Superoptimizer 2.5

GNU Superoptimizer is a project that uses an approach to finding the shortest instruction sequence for a given function.

- LICENSE TYPE:
- GPL (GNU General Public License)
- USER RATING:
- DEVELOPED BY:
**Torbjorn Granlund**- HOMEPAGE:
- ftp.gnu.org
- CATEGORY:
- ROOT \ Science and Engineering \ Mathematics

GNU Superoptimizer is a project that uses an approach to finding the shortest instruction sequence for a given function.

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

2n

O(m n )

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...

The superoptimizer can't guarantee that it finds the best possible

instruction sequences for all possible goal functions. For example, it

doesn't even try to include immediate constants (other that -1, 0, +1, and

the smallest negative and biggest positive numbers) in the sequences.

Other reasons why not optimal sequences might be found is that not all

instructions are included, not even in their register-only form. Also, some

instructions included might not be correctly simulated. If you encounter

any of these problems, please report them to the address below.

WARNING! The generated sequences might be incorrect with a very small

probability. Always make sure a sequence is correct before using it. So

far, I have never encountered any incorrect sequences. If you find one,

please let me know about it!

Having said this, note that the superoptimizer practically always finds

optimal and correct sequences for functions that depend on registers only.

· Delete unused variable tot_bits.

· Make state1 have char type.

· Use random() on alpha, since srand48 doesn't work there.

· Return small numbers with high probability.

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

2n

O(m n )

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...

The superoptimizer can't guarantee that it finds the best possible

instruction sequences for all possible goal functions. For example, it

doesn't even try to include immediate constants (other that -1, 0, +1, and

the smallest negative and biggest positive numbers) in the sequences.

Other reasons why not optimal sequences might be found is that not all

instructions are included, not even in their register-only form. Also, some

instructions included might not be correctly simulated. If you encounter

any of these problems, please report them to the address below.

WARNING! The generated sequences might be incorrect with a very small

probability. Always make sure a sequence is correct before using it. So

far, I have never encountered any incorrect sequences. If you find one,

please let me know about it!

Having said this, note that the superoptimizer practically always finds

optimal and correct sequences for functions that depend on registers only.

**What's New**in This Release:· Delete unused variable tot_bits.

· Make state1 have char type.

· Use random() on alpha, since srand48 doesn't work there.

· Return small numbers with high probability.

Last updated on February 28th, 2007

#### Add your review!

SUBMIT