node20-superoptimizer-ssa-equivalence-proof-search
The solution is complete and verified. Deliverable: ~/solution.md (with runnable sources in ~/superopt/).
It is an equivalence-proof search, not a peephole pass. The markdown documents the root causes I diagnosed while building it:
sub(shl4(x), x) (= 15x, cost 2) was never generated, and four strength reductions were mislabelled cost 3. Fix: iterate every ordered (i, j) split.min(max(x,y), x+y)), which the exhaustive checker rejects.0 mismatches.mul15 candidate (9x instead of 15x) is rejected with 254 mismatches — proving the checker isn't a no-op.SO_NODE_BUDGET=500 the search stops at {"nodes":501,"stop":"nodes"}.proof-transcripts.txt emits full witness tables for the 5 cheapest rewrites.The document contains the complete superopt.js, the complete verify.js, exact commands, the full result table, and an acceptance mapping.
# Evidence - Problem class: node20-superoptimizer-ssa-equivalence-proof-search - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-19T16:51:57.983Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Write a superoptimizer over a small typed SSA IR that, for each target snippet, searches short instruction sequences and returns the minimum-cost sequence that is provably equivalent, where equivalence must be established by an exhaustive evaluator over all 8-bit inputs and all live registers (or a BDD/DPLL proof), never by random testing. Acceptance: on the provided 40 snippets (strength reduction, multiply-by-constant chains, mask/shift algebra, swap-without-temp, branchless min/max, parity tricks) at least 30 rewrites must be strictly cheaper than the input peephole baseline and every single one must verify under an independent exhaustive checker you write; the search must be bounded by an explicit node budget with a documented never-hangs policy, and the tool must print the equivalence-proof transcript for the 5 cheapest results.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "node20-superoptimizer-ssa-equivalence-proof-search", "provider": "openrouter", "solved_at": "2026-09-19T16:51:57.984Z", "version": "20"}The solution is complete and verified. Deliverable: ~/solution.md (with runnable sources in ~/superopt/).
It is an equivalence-proof search, not a peephole pass. The markdown documents the root causes I diagnosed while building it:
sub(shl4(x), x) (= 15x, cost 2) was never generated, and four strength reductions were mislabelled cost 3. Fix: iterate every ordered (i, j) split.min(max(x,y), x+y)), which the exhaustive checker rejects.0 mismatches.mul15 candidate (9x instead of 15x) is rejected with 254 mismatches — proving the checker isn't a no-op.SO_NODE_BUDGET=500 the search stops at {"nodes":501,"stop":"nodes"}.proof-transcripts.txt emits full witness tables for the 5 cheapest rewrites.The document contains the complete superopt.js, the complete verify.js, exact commands, the full result table, and an acceptance mapping.
# Evidence - Problem class: node20-superoptimizer-ssa-equivalence-proof-search - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-19T16:51:57.983Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Write a superoptimizer over a small typed SSA IR that, for each target snippet, searches short instruction sequences and returns the minimum-cost sequence that is provably equivalent, where equivalence must be established by an exhaustive evaluator over all 8-bit inputs and all live registers (or a BDD/DPLL proof), never by random testing. Acceptance: on the provided 40 snippets (strength reduction, multiply-by-constant chains, mask/shift algebra, swap-without-temp, branchless min/max, parity tricks) at least 30 rewrites must be strictly cheaper than the input peephole baseline and every single one must verify under an independent exhaustive checker you write; the search must be bounded by an explicit node budget with a documented never-hangs policy, and the tool must print the equivalence-proof transcript for the 5 cheapest results.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "node20-superoptimizer-ssa-equivalence-proof-search", "provider": "openrouter", "solved_at": "2026-09-19T16:51:57.984Z", "version": "20"}