DeiMOS – A Superoptimizer for the MOS 6502
9 hours ago
- #code-generation
- #MOS6502
- #superoptimizer
- A superoptimizer exhaustively searches instruction sequences to find optimal code, unlike traditional compilers.
- DeiMOS targets the MOS 6502 due to its simplicity and small instruction set, enabling efficient exhaustive search.
- Test generation verifies correctness by running candidate programs against all possible inputs (up to 256 values).
- Initial naive methods are slow; optimizations include pruning invalid instructions and using multithreading across cores.
- Users can restrict instruction generation (e.g., memory addresses, instruction classes) to narrow the search space.
- Checkpointable emulation caches CPU/memory states to avoid re-executing unchanged program segments.
- Pruning branches discards programs operating on undefined data or overwriting inputs to accelerate search.
- Warp emulation runs multiple test cases in parallel, merging identical states and pruning when outputs conflict.
- Shadow instructions allow opcode arguments to serve as valid instructions, reducing program size via dual-purpose bytes.
- Branch templates predefine control flow patterns to detect invalid branch targets early during generation.
- Degenerate sequences (e.g., redundant operations) are eliminated using predefined optimization rules.
- Unofficial 6502 instructions are optionally supported, though often avoided due to reliability and portability concerns.
- Example optimizations include a 7-byte multiplication by 10 using RRA and shadow instructions for max(A,X).
- DeiMOS is written in Zig for performance and compile-time customization, generating sequences up to ~11 bytes in reasonable time.