DeiMOS – A Superoptimizer for the MOS 6502
by Aransentin on 4/7/2026, 11:10:22 AM
https://aransentin.github.io/deimos/
Comments
by: russellsprouts
Very cool!<p>I did something related in the past: <a href="https://github.com/RussellSprouts/6502-enumerator" rel="nofollow">https://github.com/RussellSprouts/6502-enumerator</a>. It uses C++ templates to share an emulator implementation between z3-powered symbolic execution and actual execution. It was meant to find equivalence between random instruction sequences for peephole optimization, rather than optimizing a specific input sequence.<p>Shadow instructions are very interesting and cursed. I've seen them used in very limited circumstances for NOP-slides for timing code: <a href="https://www.pagetable.com/?p=669" rel="nofollow">https://www.pagetable.com/?p=669</a>. It would be fun to see it applied in otherwise normal code. My enumerator wouldn't support this -- it didn't execute actual 6502 instructions from bytes -- it had its own internal representation for `the first arbitrary absolute pointer` or `the second arbitrary immediate constant`. These would either be initialized with random concrete values or z3 variables.
4/7/2026, 3:09:45 PM
by: rbanffy
Interesting and fun read - we are well into the terrain of what was completely impossible to do back then. Now I can't wait to see a faster AppleSoft ROM ;-)
4/7/2026, 2:29:27 PM
by: HarHarVeryFunny
If you assume that A * 10 isn't going to overflow, so that ASL A moves 0 into the carry flag (so no need for CLC), then instead of using the undocumented RRA opcode, you can just do:<p>sta $00<p>asl a<p>asl a<p>adc $00<p>asl a<p>This is also 7 bytes, but is faster since adc $00 is 3 cycles, vs rra $00 being 5 cycles.<p>The A = max(A, X) example is certainly interesting, but not very useful since it loops through the code twice (very slow) and assumes that $8a is available. The much faster obvious version only adds one byte:<p>stx $00<p>cmp $00<p>bcs done<p>txa<p>done:
4/7/2026, 1:33:59 PM
by: kstrauser
That’s incredibly clever and a fun read. Well done!<p>I imagine lots of demo coders glancing back and forth between that writeup and their own carefully hand-tuned assembly.
4/7/2026, 1:09:01 PM
by: potus_kushner
reminds me a bit of <a href="https://pubby.games/codegen.html" rel="nofollow">https://pubby.games/codegen.html</a> just that its approach seems way more refined and useful.
4/7/2026, 2:47:37 PM
by: vibecoderking93
Great
4/7/2026, 1:40:01 PM