# strop
[![Build Status](https://github.com/omarandlorraine/strop/workflows/Rust/badge.svg)](https://github.com/omarandlorraine/strop/actions?workflow=Rust)
[![crates.io](https://img.shields.io/crates/v/strop)](https://crates.io/crates/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](https://github.com/omarandlorraine/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 *st*ochastic *op*timizer,
written in *R*ust.

### 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:

 * [![Build Status](https://github.com/omarandlorraine/strop/workflows/stm8/badge.svg)](https://github.com/omarandlorraine/strop/actions?workflow=stm8) stm8
 * [![Build Status](https://github.com/omarandlorraine/strop/workflows/mos6502/badge.svg)](https://github.com/omarandlorraine/strop/actions?workflow=mos6502) 6502 65n02 65c02
 * [![Build Status](https://github.com/omarandlorraine/strop/workflows/x80/badge.svg)](https://github.com/omarandlorraine/strop/actions?workflow=x80) 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.