DeiMOS – A Superoptimizer for the MOS 6502 (aransentin.github.io)

DeiMOS is a “superoptimizer” that searches exhaustively for the smallest/fastest machine-code sequences for the MOS 6502 by generating candidate instruction streams and verifying them against a user-supplied spec across all 8-bit inputs. The article outlines why the 6502 is a practical target (small, well-defined instruction set) and describes several accelerations, including early rejection of crashing/invalid candidates, multithreaded/process-based distributed search, restricted instruction/address generation, checkpointable emulation, and branch pruning based on undefined data and input overwrites using “warp” multi-input emulation. It also discusses additional techniques like “shadow instructions” that exploit the way branches can land in the middle of variable-length instructions.