# strop
Superoptimizer written in Rust
I made the decision to abandon [stoc](https://github.com/omarandlorraine/stoc)
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 architectures:
Not much here (yet). There are a few placeholders for miscellaneous
architectures, and some of the instructions have been implemented for some of
them. But I don't want to say they're *supported* as such yet. Probably the
best ones are:
- *pic12*, precursor to the '14
- *pic14*, because I use these in my day job
- *mos6502*, because why not
- *mos65c02*, which has all the same instructions as mos6502 plus some extras
- *motorola6800*, it's related to the 6502s but has an extra register and some
other goodies
I've tried to pick ones I use or like, and then I've added the low-hanging
fruit like their relatives and so on. I've also tried to make this extensible,
and easy to add whatever architectures in the future.
### 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 slower in the general case, so long as
it's faster for these specific test cases."
(The last two 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 it's a good program. 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.
### Some example runs
What if we want to multiply some number by a constant? For this example, the
number is in register B, the constant is 15, and the output is in register A.
So you'd run:
strop --arch motorola6800 --function mult15 --search exh --in b --out a
More than 7 hours later, the program outputs:
tba
aba
aba
asla
aba
asla
aba
It took too long, so of course we can now run a random search instead of an
exhaustive search:
strop --arch motorola6800 --function mult15 --search stoc --in b --out a
And six seconds later, the program outputs:
tba
aba
rol
aba
tab
rol
aba
On some architectures, such as the 6502, the equivalent of the above code would
require a store instruction, and absolute add. This is because the 6502 lacks a
any register-to-register add instruction. I find that the current iteration of
the search algorithm, doesn't seem to come across the appropriate instruction
mix. For this reason, the exhaustive search is usually better than the
stochastic one for the 6502. At least, for now!
You might need something other than the miscellaneous built-in functions that
I've decided to put in. You might want to define your own functions. If you can
generate an appropriate JSON file, you can pass it to strop and have strop
generate the code that satisfies all test cases in the file. See the
`examples/` folder for examples.
strop --search exh -m motorola6800 -f examples/decimal_adjust.json
produces the following code,
add #0
daa
As to why the `add #0` was generated, my guess is that `daa` depends on the
state of certain flags, and `add #0` sets these flags right.