omarandlorraine / strop Goto Github PK
View Code? Open in Web Editor NEWStochastically generates machine code
License: MIT License
Stochastically generates machine code
License: MIT License
It says in the README that the user can supply a set of test cases, but that is not true (yet).
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
.
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
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.
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.
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.
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.
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?
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.
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
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:
txa; sec
is equivalent to sec; txa
.clc; sec
, which is the same as sec; sec
, or nop; sec
, or sec
n<<1
might be equivalent to n+n
(depending of course, on specifics like what flags are updated and how, etc)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.
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.
Failings:
Needs:
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!
brainfuck is a minimalistic programming language. Tons of interpreters, compilers and transpilers have been implemented for it.
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.
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.
Слава Україні!
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.
It's already one of the best-working instruction sets after the newly-added stm8;
may as well include support for it
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.