DeiMOS: A Superoptimizer for the MOS 6502 That Exhaustively Finds the Fastest Possible Code

DeiMOS is a superoptimizer for the legendary MOS 6502 processor — the 8-bit microprocessor that powered the NES, Commodore 64, Apple II, and countless other classic systems. Unlike compilers that apply heuristic optimization rules, DeiMOS exhaustively searches all possible instruction sequences to find the provably shortest or fastest implementation.

What is a Superoptimizer?

A superoptimizer goes beyond traditional compilers:

• Traditional compiler: Applies predefined optimization rules and heuristics
• Superoptimizer: Exhaustively searches the entire space of possible instruction sequences to find the one that is provably optimal

The trade-off is speed: superoptimization is computationally expensive and scales poorly with program length.

Why the 6502?

The MOS 6502 (1975) is an ideal target for superoptimization:

1. Simple instruction set — Limited opcodes and addressing modes reduce search space
2. Historical significance — Powered the NES, C64, Apple II, Atari
3. 8-bit architecture — Only 256 possible values per byte, enabling exhaustive verification
4. No modern complexity — No branch prediction, extensive registers, or out-of-order execution

How DeiMOS Works

1. Test specification — User provides input generator and output verifier functions
2. Exhaustive search — Systematically generates and tests all possible instruction sequences
3. Emulation-based verification — Each candidate is emulated against all 256 possible input values
4. Smart pruning — Filters out CPU-jamming instructions and useless opcodes to reduce search space

Optimizations Over Naive Approach

The naive approach of generating all byte combinations (256^n for n-byte programs) is impossibly slow for even modest program lengths. DeiMOS uses several key optimizations:

• Dead instruction elimination — Skips bytes that would halt the CPU
• Lookup table filtering — Only generates instructions that make sense in context
• Depth tracking — Follows branch targets rather than linear byte sequences

Modern Relevance

While the 6502 is a retro platform, superoptimization research has practical implications:

• Compiler theory — Understanding optimal code generation for constrained architectures
• Retro computing — Pushing the limits of classic hardware
• Formal verification — Provably correct optimization
• Embedded systems — Techniques applicable to modern resource-constrained platforms