Superoptimizer written in Rust
I made the decision to abandon 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 stochastic optimizer, written in Rust.
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:
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.
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.
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.