strop

Superoptimizer written in Rust

This program stochastically generates assembly language programs that compute a given function. The idea is you give it a function to compute and specify which registers and things to use, and strop will generate and output a pretty good program which does the specified thing.

I abandoned stoc, a similar thing done in C, when I realized it was simply too unwieldly to work with. I needed an excuse to learn Rust, plus I wanted a superoptimizer that could target things other than the 6502, So, strop was born, the stochastic optimizer, written in Rust.

Supported instruction sets:

Strop's repertoire of instructions include mathematical operations such as boolean AND, OR, etc., addition & subtraction, comparisons, load/store instructions, conditional and unconditional jumps, etc. Certain operations are not included, because I anticipate that end-users will use strop mostly for generation of computationally intense things like inner loops and perhaps bodies of functions. This means that I don't intend for strop to generate things like push/pops, returns from interrupts, and this kind of thing.

Strop currently supports these instruction sets, as indicated by the status of the badges:

• stm8
• 6502 65n02 65c02
• kr580vm1

Theory of operation

The basic idea is to generate code better than what traditional optimising compilers can do. A few of the reasons why that's possible:

• we can do an exhaustive search, while optimizing compilers generally do a greedy ascent. That means strop will find a global maximum, instead of a local maximum.

• we can put things like error margins, and don't-care bits on output variables, which can yield more opportunity for code optimization. That's like saying, "oh I don't care if the program computes things 100% correctly, so long as it's much faster", which I bet could have some utility.

• we can add different weights to each test case. That would be like saying, "oh, I don't care if the program is suboptimal in the general case, so long as it's more optimal for these specific test cases."

• having run all the test cases, we can take some measurements such as branch predictability and such likes, and optimize for the same.

(The last three are not implemented yet, but something I want to do eventually)

How are we going to do this? The way strop generates code is by running a code sequence against a set of test cases (these may be generated by strop itself or supplied by the user). The code is mutated and run against the test cases over and over again. When the test cases all pass, we know the program is good. As the code is run, we can analyse it for characteristics like speed and size, and this information can be fed into the way we mutate or select the code sequence.