DeiMOS：MOS 6502超级优化器，穷举搜索绝对最优代码

DeiMOS是传奇MOS 6502处理器的超级优化器——这款8位微处理器驱动了NES、Commodore 64、Apple II等经典系统。与传统编译器不同，DeiMOS穷举搜索所有可能的指令序列，找到可证明的最短或最快实现。

什么是超级优化器？

• 传统编译器：应用预定义的优化规则和启发式方法
• 超级优化器：穷举搜索所有可能的指令序列，找到可证明的最优解

代价是速度：超级优化计算成本高，随程序长度扩展性差。

为什么选择6502？

1. 简单指令集 — 有限的操作码和寻址模式减少了搜索空间
2. 历史意义 — 驱动了NES、C64、Apple II、Atari
3. 8位架构 — 每字节仅256个可能值，支持穷举验证
4. 无现代复杂性 — 无分支预测、大量寄存器或乱序执行

工作原理

1. 测试规范 — 用户提供输入生成器和输出验证函数
2. 穷举搜索 — 系统地生成和测试所有可能的指令序列
3. 基于仿真的验证 — 每个候选对256个可能输入值进行仿真测试
4. 智能剪枝 — 过滤掉使CPU停止的指令和无用操作码

现代相关性

虽然6502是复古平台，但超级优化研究具有实际意义：编译器理论、复古计算极限、形式验证、以及适用于现代资源受限平台的技术。