go-linear-scan-register-allocator
Done. Complete solution in ~/regalloc/ — deliverable SOLUTION.md (self-contained: title, root-cause analysis, exact fix with code, verification) plus the runnable module (go.mod, allocator.go, allocator_test.go), all green under go vet, gofmt, go test, and -race.
spillCost/length" is an online heuristic, and weighted interval graphs defeat it: A=[0,10)@90, B=[0,5)@50, C=[5,10)@50, K=1 — greedy spills {B,C} (cost 100) while the optimum spills only A (cost 90, keeping B,C which tile the range). Measured: the faithful greedy disagrees with brute force on 1606/3000 (~54%) random instances, so no per-step rule can satisfy "oracle confirms cost-optimal spill set for N ≤ 12".end ≤ current.start) both under-uses registers (spills colorable graphs) and reuses registers of still-live intervals (overlap violations).Interval graphs are perfect ⇒ K-colorable ⇔ max pointwise overlap ≤ K. Allocate runs two phases:
- Phase 1 (optimal spill set): max-weight K-colorable subset = min-cost flow on the interval DAG (path of K tracks, intervals as −Cost chords, successive shortest paths + potentials; skipped entirely when maxOverlap ≤ K → guaranteed no-spill when colorable).
- Phase 2 (Poletto-Sarkar linear scan): kept intervals colored by start point with an active min-heap keyed on end; expire-then-assign from a K − |active| free pool. O(N log N), never reuses a live register.
11/11 tests pass (2.24 s; 9.9 s with -race): brute-force oracle matches spilled cost on 3 850 random instances N ≤ 12 (+ 320 for N = 13–16), overlap-freedom on all randomized tests, 500 colorable graphs spill nothing, the all-overlapping N=50 000 case hits the exact optimum for K=1,2,4, and 200 000 intervals, K=3 in ≈ 533 ms (proving active-list expiry, not restart). The three code blocks embedded in SOLUTION.md were verified byte-identical to the working sources.
# Evidence - Problem class: go-linear-scan-register-allocator - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-30T10:44:48.839Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement linear-scan register allocation (Poletto-Sarkar) for an interval-based IR: given N live intervals [start,end) with a spill cost and K physical registers, assign each interval a register in [0,K) or mark it spilled such that no two overlapping intervals share a register. When registers are exhausted, spill the active interval with the lowest spillCost/length ratio that keeps the remaining graph colorable, minimizing total spilled cost; the no-spill case must always succeed whenever the interval graph is K-colorable. Acceptance: randomized tests verify overlap-freedom, a brute-force oracle confirms the spill set is cost-optimal for N <= 12, and the allocator uses active-list expiry sorted by end point rather than naive restart.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-linear-scan-register-allocator", "provider": "openrouter", "solved_at": "2026-08-30T10:44:48.839Z", "version": "1.26"}Done. Complete solution in ~/regalloc/ — deliverable SOLUTION.md (self-contained: title, root-cause analysis, exact fix with code, verification) plus the runnable module (go.mod, allocator.go, allocator_test.go), all green under go vet, gofmt, go test, and -race.
spillCost/length" is an online heuristic, and weighted interval graphs defeat it: A=[0,10)@90, B=[0,5)@50, C=[5,10)@50, K=1 — greedy spills {B,C} (cost 100) while the optimum spills only A (cost 90, keeping B,C which tile the range). Measured: the faithful greedy disagrees with brute force on 1606/3000 (~54%) random instances, so no per-step rule can satisfy "oracle confirms cost-optimal spill set for N ≤ 12".end ≤ current.start) both under-uses registers (spills colorable graphs) and reuses registers of still-live intervals (overlap violations).Interval graphs are perfect ⇒ K-colorable ⇔ max pointwise overlap ≤ K. Allocate runs two phases:
- Phase 1 (optimal spill set): max-weight K-colorable subset = min-cost flow on the interval DAG (path of K tracks, intervals as −Cost chords, successive shortest paths + potentials; skipped entirely when maxOverlap ≤ K → guaranteed no-spill when colorable).
- Phase 2 (Poletto-Sarkar linear scan): kept intervals colored by start point with an active min-heap keyed on end; expire-then-assign from a K − |active| free pool. O(N log N), never reuses a live register.
11/11 tests pass (2.24 s; 9.9 s with -race): brute-force oracle matches spilled cost on 3 850 random instances N ≤ 12 (+ 320 for N = 13–16), overlap-freedom on all randomized tests, 500 colorable graphs spill nothing, the all-overlapping N=50 000 case hits the exact optimum for K=1,2,4, and 200 000 intervals, K=3 in ≈ 533 ms (proving active-list expiry, not restart). The three code blocks embedded in SOLUTION.md were verified byte-identical to the working sources.
# Evidence - Problem class: go-linear-scan-register-allocator - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-30T10:44:48.839Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement linear-scan register allocation (Poletto-Sarkar) for an interval-based IR: given N live intervals [start,end) with a spill cost and K physical registers, assign each interval a register in [0,K) or mark it spilled such that no two overlapping intervals share a register. When registers are exhausted, spill the active interval with the lowest spillCost/length ratio that keeps the remaining graph colorable, minimizing total spilled cost; the no-spill case must always succeed whenever the interval graph is K-colorable. Acceptance: randomized tests verify overlap-freedom, a brute-force oracle confirms the spill set is cost-optimal for N <= 12, and the allocator uses active-list expiry sorted by end point rather than naive restart.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-linear-scan-register-allocator", "provider": "openrouter", "solved_at": "2026-08-30T10:44:48.839Z", "version": "1.26"}