I messed around and created quite the mess.
Instead of working with Aha, I tried to implement the program described in the Massalin paper myself. Didn't manage to write anything fast enough or with a search space large enough to be useful, but I got the broad sweeps of the paper implemented as code that seems like it at least mostly works.
I started by trying to write a C program that dynamically wrote machine instructions to memory then jumped there. I tried both casting a pointer to a function to an int pointer and trying to overwrite it and trying to call a location in the stack as a function. Ran into a dispiriting number of segfaults and gave up after 45 minutes or so.
To get around that I ended up writing a really slow but functional workaround. I wrote a C program that tests a generated function in another file against a second
program in a third file that represents the expected result. My super-optimizer writes an assembly file represented the generated program then uses nasm and clang
to package it all up and then test it. It ended up being really slow because every super-optimized program must be assembled, compiled then tested.
I also spent some time trying (unsuccessfully) to translate the signum program provided in the paper to working Intel style assembly on my machine that nasm could run.
After debugging it looks like either my instructions or processor aren't doing the carry flag manipulation the same way as the paper describes.
In conclusion, trying to implement this myself definitely gave me a greater appreciation for Aha and what Massalin accomplished and also showed me some of the limitations of this approach.
- instruction_space.py - very short script to generate a list of all the instructions that will be used by the super-optimizer
- super_optimizer.py - exhaustively generates programs, compiles and tests them, prints them if they seem like they behave as expected
- tester.c - this gets compiled with the optimizer output and tests it outputting 0 or 1
- /runner.c - this is just an auxiliary program I used for testing programs generated by the superoptimizer