python-linear-scan-register-allocation-live-interval-splitting
I built and verified a complete linear-scan register allocator from scratch, since the environment contained no fixture set or broken implementation to diagnose.
~/SOLUTION.md — the requested report: title, root-cause analysis, exact fix, verification, and the full self-contained program in the appendix.~/regalloc_solution.py — the runnable program (standard library only).~/regalloc/ — the same code split into a package (ir.py, allocator.py, machine.py, interp.py, fixtures.py, verify.py).| # | Defect | Symptom |
|---|---|---|
| R1 | const immediates counted as SSA uses |
fake 0/1 values corrupted liveness |
| R2 | block-level live_in over-approximation |
phi destinations kept live-in |
| R3 | pre-coloured clobber intervals skipped conflict resolution | live values survived calls in caller-saved registers |
| R4 | dead definitions got entry-point intervals | dead defs clobbered simultaneously-live registers |
| R5 | coalescing missed overlap + clobber checks | unsafe merges / overlapping live ranges |
| R6 | intervals not split at block/back-edge boundaries | loop-carried and disjoint live ranges mishandled |
| R7 | set-iteration nondeterminism | spill choices varied per PYTHONHASHSEED |
interpret_ref (unconstrained SSA) and interpret_machine (explicit registers/slots after lowering) are run on the same random inputs. Any interference, ABI, phi or parallel-copy error makes them diverge. An independent invariant checker also verifies no overlapping intervals share a register, no value sits in a clobbered register across a call, and every phi operand is allocated. Phis are lowered to cycle-broken parallel copies with edge splitting; calls honor argument/return/clobber registers.
python3 regalloc_solution.py
K ∈ {1,2,3,4}, 80 random inputs each: 0 mismatchesThe extracted appendix code was independently re-run from SOLUTION.md itself and passed, confirming the markdown is self-contained.
# Evidence - Problem class: python-linear-scan-register-allocation-live-interval-splitting - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-29T16:39:16.455Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Write a linear-scan register allocator for a small SSA intermediate representation: compute live intervals over a reverse-postorder linearization, split intervals at block boundaries and loop back-edges, then assign K machine registers while spilling the minimum-weight intervals. The allocator must respect pre-colored registers from the calling convention, lower phi-nodes into parallel copies with cycle-breaking, and coalesce move-related intervals only when the merge is provably safe. Report realized spill cost and prove correctness by interpreting the allocated output for every function in the fixture set against an unallocated reference.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-linear-scan-register-allocation-live-interval-splitting", "provider": "openrouter", "solved_at": "2026-09-29T16:39:16.458Z", "version": "3.12"}I built and verified a complete linear-scan register allocator from scratch, since the environment contained no fixture set or broken implementation to diagnose.
~/SOLUTION.md — the requested report: title, root-cause analysis, exact fix, verification, and the full self-contained program in the appendix.~/regalloc_solution.py — the runnable program (standard library only).~/regalloc/ — the same code split into a package (ir.py, allocator.py, machine.py, interp.py, fixtures.py, verify.py).| # | Defect | Symptom |
|---|---|---|
| R1 | const immediates counted as SSA uses |
fake 0/1 values corrupted liveness |
| R2 | block-level live_in over-approximation |
phi destinations kept live-in |
| R3 | pre-coloured clobber intervals skipped conflict resolution | live values survived calls in caller-saved registers |
| R4 | dead definitions got entry-point intervals | dead defs clobbered simultaneously-live registers |
| R5 | coalescing missed overlap + clobber checks | unsafe merges / overlapping live ranges |
| R6 | intervals not split at block/back-edge boundaries | loop-carried and disjoint live ranges mishandled |
| R7 | set-iteration nondeterminism | spill choices varied per PYTHONHASHSEED |
interpret_ref (unconstrained SSA) and interpret_machine (explicit registers/slots after lowering) are run on the same random inputs. Any interference, ABI, phi or parallel-copy error makes them diverge. An independent invariant checker also verifies no overlapping intervals share a register, no value sits in a clobbered register across a call, and every phi operand is allocated. Phis are lowered to cycle-broken parallel copies with edge splitting; calls honor argument/return/clobber registers.
python3 regalloc_solution.py
K ∈ {1,2,3,4}, 80 random inputs each: 0 mismatchesThe extracted appendix code was independently re-run from SOLUTION.md itself and passed, confirming the markdown is self-contained.
# Evidence - Problem class: python-linear-scan-register-allocation-live-interval-splitting - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-29T16:39:16.455Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Write a linear-scan register allocator for a small SSA intermediate representation: compute live intervals over a reverse-postorder linearization, split intervals at block boundaries and loop back-edges, then assign K machine registers while spilling the minimum-weight intervals. The allocator must respect pre-colored registers from the calling convention, lower phi-nodes into parallel copies with cycle-breaking, and coalesce move-related intervals only when the merge is provably safe. Report realized spill cost and prove correctness by interpreting the allocated output for every function in the fixture set against an unallocated reference.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-linear-scan-register-allocation-live-interval-splitting", "provider": "openrouter", "solved_at": "2026-09-29T16:39:16.458Z", "version": "3.12"}