Skip to content

v0.1.0 — 602,008 Z80 optimizations found

Choose a tag to compare

View all tags
@oisee oisee released this 28 Feb 15:24
· 255 commits to main since this release
v0.1.0
0b2de25

What is this?

A brute-force superoptimizer for the Zilog Z80 processor.

Given any sequence of Z80 instructions, it exhaustively searches for a shorter equivalent — one that produces identical register and flag state for every possible input. No heuristics, no pattern databases, just brute force with smart pruning.

First run results

602,008 provably correct optimizations found from 8.4M length-2 target sequences.

  • 34.7 billion comparisons checked
  • 3 hours 16 minutes on Apple M2
  • 83 unique transformation patterns discovered
  • Results: rules.json.gz (3.4MB compressed, 102MB uncompressed)

Highlights

Original Replacement Savings Insight
SLA A : RR A OR A -3B, -12T Shift left then rotate right = identity + flag set
SRL A : RL A OR A -3B, -12T Shift right then rotate left = identity + flag set
AND 00h : NEG SUB A -3B, -11T Zero then negate = zero with subtract flags
LD A, 00h : SLA A XOR A -3B, -11T Load zero then shift = zero with logic flags
ADD A, A : RR A OR A -2B, -8T Double then halve = identity + flag set
SRL A : SLL A OR 01h -2B, -9T Shift right then undoc-shift-left = set bit 0
XOR 0FFh : NEG SUB 0FFh -2B, -8T Complement then negate
CPL : NEG SUB 0FFh -1B, -5T Complement then negate = increment with sub flags
XOR 0FFh : SBC A, 0FFh NEG -2B, -6T Complement + subtract-with-borrow = negate
SCF : RL A SLL A -1B, -4T Set carry then rotate-through-carry = undoc shift
SCF : ADC A, 00h ADD A, 01h -1B, -4T Set carry then add-with-carry zero = add 1
SET 0, L : DEC HL RES 0, L -1B, -6T Set bit then decrement = just clear the bit
RES 0, L : INC HL SET 0, L -1B, -6T Clear bit then increment = just set the bit
ADD A, 80h : OR A XOR 80h -1B, -4T Flip sign bit with correct flag behavior
ADD A, 00h : RL A SLA A -2B, -7T Clear carry then rotate = shift left
AND 0FFh : RR A SRL A -2B, -7T Clear carry via AND then rotate = shift right

Breakdown by savings

Bytes saved Count
3 bytes 1,212
2 bytes 580,937
1 byte 19,859

Note: it correctly rejects false optimizations like LD A, 0 → XOR A because XOR A modifies flags while LD A, 0 does not. Every rule is verified against all possible inputs.

What's included

406 Z80 opcodes covering all register-only operations:

  • 8-bit loads, arithmetic, logic (ADD, ADC, SUB, SBC, AND, OR, XOR, CP)
  • All CB-prefix shifts and rotates (RLC, RRC, RL, RR, SLA, SRA, SRL, SLL)
  • BIT/RES/SET n, r — all 168 register variants
  • 16-bit pair ops (INC/DEC rr, ADD HL, EX DE,HL, LD SP,HL)
  • 16-bit immediate loads (LD BC/DE/HL/SP, nn)
  • ED-prefix arithmetic (ADC HL, SBC HL)
  • Specials: DAA, CPL, NEG, SCF, CCF, NOP

Usage

go build -o z80opt ./cmd/z80opt

# Find optimal replacement for a specific sequence
./z80opt target "AND 0xFF"
# → Replacement: AND A (-1 bytes, -3 cycles)

./z80opt target "SLA A : RR A"
# → Replacement: OR A (-3 bytes, -12 cycles)

# Run full enumeration
./z80opt enumerate --max-target 2 --output rules.json -v

Roadmap

See docs/GenPlan.md for the full implementation plan.

Next phases:

  • STOKE stochastic search — MCMC random mutations for length 5-10+ sequences
  • CUDA brute force — GPU-accelerated length-3 complete search (~20 min on 2× RTX 4060 Ti)
  • Reordering optimizer — dependency DAG analysis to apply rules to real code with interleaved instructions
  • More opcodes — (HL) memory ops, PUSH/POP, IX/IY indexed addressing
Assets 3
Loading