◐ Off-By-One · answer catalog

go-burs-optimal-tree-tiling-instruction-selection

1 answer(s)gogo1.26

go-burs-optimal-tree-tiling-instruction-selection

📦 Source in repository (JSON)

Answer

The solution is complete and verified. Here's a summary.

Deliverable

/workspace/SOLUTION.md — a self-contained writeup (title, root-cause analysis, exact fix with full source, verification). The runnable implementation lives in /workspace/burs/.

Diagnosis

The task is to build an optimal BURS selector from scratch. The failure modes a naive implementation hits (and which the grader catches) are:

  1. Greedy per-node matching is not optimal — tiles claim different numbers of nodes (LOAD_OFF claims load+add+const; DIVMOD claims div+mod; CMPBR claims branch+lt), so the true objective is a minimum-cost exact cover, not local choices.
  2. Commutative ADD/MUL must emit once for both operand orders.
  3. LT is not commutative — a real bug found during development: using LT_I for a constant in either position gave verified=182/200; fixed by adding a distinct LT_IR tile.
  4. Load folding must subsume the address ADD and its CONST.
  5. Register pressure must be in the cost: effCost = Cost + max(0,Regs−K)·SPILL.
  6. Ties need a total order: cost → instruction count → lexicographic rule@maxClaim.
  7. Inputs are always DAG descendants of claims, so sorting tiles by max claimed id gives a valid topological emission order.

Fix

Verification

$ cd /workspace/burs && go vet ./... && go test -v
--- all 8 tests PASS ---
$ go run .
verified=200/200

I also extracted the code blocks back out of SOLUTION.md into a clean directory and rebuilt from scratch: build + vet clean, all tests pass, verified=200/200 — proving the document is fully self-contained and directly usable.

Evidence & signatures

# Evidence
- Problem class: go-burs-optimal-tree-tiling-instruction-selection
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-28T16:16:08.261Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement optimal instruction selection for a small RISC-like target by tiling an expression DAG with a bottom-up rewrite system: compute a minimal-cost cover of every node, handle both operand orders of commutative operators without duplicating instructions, fold loads into memory operands, and emit multi-result rules (e.g. divmod, compare-and-branch) that claim more than one node at once. The cost function must include register pressure so that a tiling needing spills loses to one that does not, and rule selection must be deterministic when two rules share the minimum cost (documented tie-break). Grading runs the selector against a brute-force optimal enumerator on 200 seeded random DAGs and asserts equal total cost plus semantic equivalence of the emitted instruction traces when both runs are executed on the reference interpreter.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-burs-optimal-tree-tiling-instruction-selection", "provider": "openrouter", "solved_at": "2026-09-28T16:16:08.261Z", "version": "1.26"}
Generated from the verified corpus · MIT licensedBack to the catalog