omarandlorraine/strop

Stochastically generates machine code

strop's Issues

no way to load custom functions

It says in the README that the user can supply a set of test cases, but that is not true (yet).

No warning if value is too large for a register

Apparently the stm8 x register does not hold a 16-bit value despite having low and high registers(?). This function never results in strop halting:

{
    "tests": [
        {"steps": [{"datum": "a", "set": 255}, {"datum": "x", "diff": 65535}]}
    ]
}

but also it never raises any warning. Same for if diff is arbitrarily large but still small enough for a Rust i32.

mos6502: incorrect carry flag after SBC opcode

According to the fuzz tests (these are not run on the github workflow), the after an SBC instruction, the carry flag does not match what mre/mos6502 does.

I've not looked into what the problem is

Support the Z80

Fix the KR580VM1 backend

there is so much unnecessary code

There's tables of opcodes, and hand-coded disassemblers, and match statements spanning several screens, it's a nightmare. How about using third-party crates more.

Smaller randomize steps

Strop generated this code:

    ldw x, #5
    incw x
    incw x
    mul x, a
    ld a, xl

to multiply the accumulator by 7. What it's doing is loading X with the constant five, and incrementing it twice, leaving seven. Then it does the multiplication, and then moves the result where it should be.

It's a bit stupid

But picking a random immediate value with any of the possible values picked with a uniform distribution makes it too unattractive to the search function, and it ends up trying to use shifts and things. This is because mutating a single instruction means randomizing all of the opcode and the source and destination operands. It's too great a step.

So we should experiment with some kind of "smaller step". So maybe the mutation here should take immediates and pick one of: increment, decrement, flip-a-bit, negate, etc. In the example above, this would mean offering successively closer values for x in the first instruction, which would reduce the probability of strop inserting these pointless incw instructions.

No support for registers that aren't exactly 8 bits

This one's important. I think that this is crucial for getting any kind of support for actually useful systems like ARMs and whatever else is in use today.

Even the Z80, Intel 8080 and friends, would benefit from not everything having to be an 8 bit integer. So the register file will probably needs to be rethought.

Support for 6809

The 6809 is a (now discontinued, but still loved by enthusiasts) CPU that's not so dissimilar from the 6800 and 6801. It shouldn't be too hard to add it.

Support for "pseudo-code" output

Right now strop outputs assembly/machine code - this is OK if you're going to run it directly on some architecture, but what if you want to put the idea into code to compile it for any architecture? Every architecture has a version of some primitive operations, like bit shifting and masking, moving bytes around and so on, and of course variables/registers. For example, fast-inverse-square-root was implemented in C, not x86 raw assembly.

I think a "holy grail" of strop will be when it can come up with a fast-inverse-square-root algorithm - or even a version that's even faster - as pseudo-code, such that it's a relatively straightforward port to C or Rust. Right now, strop is compiling to one architecture, and then you have to reverse-engineer it.

To achieve the desired effects, the "pseudo-code" would have to be interpreted by strop "as if" it were compiled for some abstract machine, for the purposes of achieving the desired behavior from the pseudo-subroutine. If this is possible, strop wouldn't be useful just for generating subroutines, but for generating new algorithms that can be implemented in any programming language.

For example, I want an sRGB color blending function that doesn't use any floating-point math. It can be implemented by a couple lookup tables, but then you spend kilobytes of space (or 512 bytes if you want to completely defeat the gamma curve) for them.

Strop could generate ridiculous stuff that happens to do exactly what I want for the entire input space (all 56 bits of it), but that's no use if I can't decode the assembly (this is not a trivial algorithm).

So pseudo-code would further open up the door to use strop as a real tool for finding real performant solutions to problems that currently require verbose/expensive implementations in order to be correct. My example is approximately what strop is eventually intended to solve, right? :)

P.S. this is my first issue here, how'd I do?

Support Arm processors

Until now, strop has had a focus on supporting processors without good support from Clang or GCC.

But I think it would be good to put in Arm support as well. That would be more generally useful since more people use Arm.

Maybe we can use this emulator for fuzz testing, as on the 6502 backend.

Make the AAPCS32 search generic across more types

Right now the search done by .aapcs32(function_pointer) requires that the function takes two i32 parameters and returns an Option<i32>.

It would be way better if this could be generic and it could take an u8, i16, f32, etc and return the same

Idea for speeding up the bruteforce search

A considerable speedup could come from identifying sequences of instructions that have other representations, and skipping these instruction sequences in the bruteforce search. Some examples:

• Independent instructions may be ordered any which way round. For example, on the 6502, txa; sec is equivalent to sec; txa.
• Instructions might have no effect, or their effect might be overwritten by another instruction, such as clc; sec, which is the same as sec; sec, or nop; sec, or sec
• The 6502 has zero page addressing. Many instructions doing that also have an absolute addressing mode doing the same thing but at a greater cost
• n<<1 might be equivalent to n+n (depending of course, on specifics like what flags are updated and how, etc)
• On the Z80, there are sometimes several ways to encode the same instructions, for example with ignored prefixes

It might be a good idea to have some automatically generated peephole optimizer that can notice this kind of thing and use this knowledge to cull the search space.

ADC operations don't seem to be heeding the carry flag

Not sure why, but programs generated for the 6502 containing the adc instruction don't first clear or set the carry flag like correct programs must.

The quality of the codebase is quite poor

Failings:

• There is a lot of duplicate code here and there
• So many half-implemented bad ideas as well

Needs:

• structure
• some of the more ridiculous enums & data structures can/should be simplified
• documentation

Support for STM8?

The STM8 is a widely used embedded 8 bit mcu that is very much like an upgraded MC6800 or 6502. Please consider supporting it. Thanks!

idea: brainfuck target

brainfuck is a minimalistic programming language. Tons of interpreters, compilers and transpilers have been implemented for it.

No parallellism

The exhaustive search could be made faster by utilizing actually all the cores. Most computers these days have at least 4 cores, so there's opportunity for a 4x speedup right there.

Support for KR580VM1

This one stems from the same lineage as the Intel 8080, 8085 and Z80 line. It has another couple of registers, another address space and a few other bits and bobs.

Слава Україні!

Support the PIC14

Early versions of strop had support for the PIC14, but later versions do not have this feature.

So I think we should add it back in.

Support for 6502

It's already one of the best-working instruction sets after the newly-added stm8;

may as well include support for it