FAQ

Here is where I put some of the questions I've been asked about this project.

whats a Stochastic superoptimiser ?

"Stochastic" basically means the same as random.

A "superoptimizer" tries to generate code that's better than what optimizing compilers come up with. While a compiler turns high-level code into low-level code by means of a series of transforms, a superoptimizer takes a different approach. A superoptimizer instead searches through possible code sequences and see if they fit some function.

Other superoptimizers are usually brute-force, exhaustive searches. They are really useful for generating compiler back-ends, and optimization passes and things like that.

But this one does not use exhaustive search. It uses a random search. It takes a code sequence, maybe an empty one to start with, and randomly changes it in some way (maybe by inserting an instruction, or changing an instruction's operand, or deleting an instruction, or reordering instructions), and then seeing if this mutation brings the resulting program closer to being "correct".

What it finds is usually the best possible sequence of instructions that computes a given function.

is it something that's ... useful?

Yes. For reasons of linguistic detail it's hard to translate from high level languages to certain instruction sets. For an example, see Why do C to Z80 compilers produce poor code?. Other examples include low-end PICs; later versions have needed to introduce new instructions specifically for compiling C.

Strop completely side-steps this issue by not trying to translate anything.