[Model] MinimumCodeGenerationOneRegister

[isPANN]

Motivation

MINIMUM CODE GENERATION ON A ONE-REGISTER MACHINE (P296) from Garey & Johnson, A11 PO4. A fundamental compiler optimization problem: given an expression DAG, find the minimum number of instructions needed to evaluate all root values on a machine with a single accumulator register (supporting LOAD, STORE, and OP instructions). This models the instruction selection and scheduling phase of code generation for simple architectures.

Associated reduction rules:

• As target: R308 (3-SATISFIABILITY →)
• Connections (beyond G&J):
  • Generalizes the Sethi-Ullman numbering problem for expression trees (which is polynomial)
  • Related to RegisterSufficiency (P293): both concern register allocation, but this problem fixes the register count to 1 and asks about instruction count

Definition

Name: MinimumCodeGenerationOneRegister
Reference: Garey & Johnson, Computers and Intractability, A11 PO4

Mathematical definition:

INSTANCE: Directed acyclic graph G = (V, A) with max out-degree 2. Leaf vertices (out-degree 0) represent input values stored in memory. Internal vertices represent operations. Root vertices (in-degree 0) are the values to compute.
OBJECTIVE: Find a program of minimum number of instructions for a one-register machine that computes all root vertices.

Instruction semantics:

• LOAD v: Load the value of vertex v from memory into the register. For leaves, the value is the input; for internal vertices, the value must have been previously STOREd.
• STORE v: Save the current register value into memory as the computed value of vertex v.
• OP v: Compute vertex v by applying its operation to two operands: one must be in the register and the other must be in memory. The result is placed in the register. For unary operations (out-degree 1), only the register operand is used.

A valid program respects data dependencies: all children of v must be computed before OP v is executed.

Variables

• Count: n = |V| (one variable per vertex representing its position in the instruction schedule)
• Per-variable domain: {0, 1, ..., 3n-1} (time step at which the vertex's instruction is executed; upper bound since at most 3 instructions per vertex: LOAD/STORE/OP)
• Meaning: A valid program is a sequence of LOAD, STORE, and OP instructions that respects DAG dependencies and computes all root vertices. The objective minimizes the total instruction count.

Schema (data type)

Type name: MinimumCodeGenerationOneRegister
Variants: (none — fixed to DAGs)

Field	Type	Description
num_vertices	usize	Number of vertices
edges	Vec<(usize, usize)>	Directed arcs (parent, child) in the expression DAG
num_leaves	usize	Number of leaf vertices (out-degree 0)

Complexity

• Decision complexity: NP-complete (Bruno and Sethi, 1976; transformation from 3SAT).
• Best known exact algorithm: O*(2^num_vertices) brute-force over instruction orderings. No sub-exponential exact algorithm is known.
• Restrictions: NP-complete even when vertices with in-degree > 1 have arcs only to leaves. Polynomial-time solvable for directed forests (trees) — the classical Sethi-Ullman algorithm gives an optimal instruction sequence for expression trees in O(n) time.
• References:
  • J. Bruno, R. Sethi (1976). "Code Generation for a One-Register Machine." Journal of the ACM, 23(3), pp. 502–510.
  • R. Sethi, J.D. Ullman (1970). "The Generation of Optimal Code for Arithmetic Expressions." Journal of the ACM, 17(4), pp. 715–728.

Extra Remark

Full book text:

INSTANCE: Directed acyclic graph G = (V, A) with maximum out-degree 2, positive integer K.
QUESTION: Is there a program of K or fewer instructions for a one-register machine that computes all the root (in-degree 0) vertices of G?
Reference: [Bruno and Sethi, 1976]. Transformation from 3-SATISFIABILITY.
Comment: NP-complete even if the only vertices having in-degree greater than 1 have arcs only to leaves [Bruno and Sethi, 1976]. Solvable in polynomial time for directed forests [Sethi and Ullman, 1970].

Note: The original G&J formulation is a decision problem with threshold K. We use the equivalent optimization formulation: minimize the number of instructions.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all valid instruction sequences respecting DAG dependencies; return the one with minimum length that computes all roots.)
• It can be solved by reducing to integer programming.
• Other: Sethi-Ullman algorithm for the tree/forest case (polynomial).

Example Instance

Expression DAG G with 7 vertices {v0, v1, v2, v3, v4, v5, v6}:

Leaves (out-degree 0, inputs in memory): {v4, v5, v6}
Internal nodes (binary operations):

• v3 = op(v5, v6)
• v1 = op(v3, v4)
• v2 = op(v3, v5) — note: v3 has in-degree 2 (shared subexpression)
• v0 = op(v1, v2) — root (in-degree 0)

Arcs: (v0→v1), (v0→v2), (v1→v3), (v1→v4), (v2→v3), (v2→v5), (v3→v5), (v3→v6)

Optimal program (8 instructions):
Leaves v4, v5, v6 are pre-loaded in memory as inputs.

1. LOAD v5 — reg = v5
2. OP v3 — reg = op(v5, mem[v6]) = v3; v6 is a leaf already in memory
3. STORE v3 — mem[v3] = v3 (shared subexpression, needed by both v1 and v2)
4. OP v2 — reg = op(v3, mem[v5]) = v2; v5 is a leaf still in memory
5. STORE v2 — mem[v2] = v2
6. LOAD v4 — reg = v4
7. OP v1 — reg = op(v4, mem[v3]) = v1
8. OP v0 — reg = op(v1, mem[v2]) = v0 ✓

Key insight: By computing v2 immediately after v3 (while v3 is still in the register), we avoid an extra LOAD. The shared subexpression v3 forces one STORE, and v2 forces another STORE to free the register for computing v1.

Suboptimal program (10 instructions): Computing v1 before v2 requires an extra LOAD v5 and STORE v1, totaling 10 instructions.

Expected Outcome

Optimal value: Min(8) — the minimum number of instructions to compute the root v0. Breakdown: 2 LOADs + 2 STOREs + 4 OPs = 8. The shared subexpression v3 (in-degree 2) is the source of complexity; without sharing, the tree case would be solvable by Sethi-Ullman in fewer steps.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; not yet in reduction graph; planned 3SAT reduction
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	References verified; optimality claim in example unsubstantiated
Well-written	❌ Fail	Multiple template issues: vague Variables section, missing Expected Outcome, unverified optimality claim, no concrete complexity expression

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. CodeGenerationOneRegister does not exist in the codebase. The problem is distinct from the existing RegisterSufficiency (which concerns the number of registers needed, not instruction count with a fixed single register). The issue identifies a concrete planned reduction: 3-SATISFIABILITY → CodeGenerationOneRegister (R308 per G&J), connecting it to the existing reduction graph. Brute-force solving is claimed and feasible.

Non-trivial

Pass. This problem has genuinely different feasibility constraints from all existing problems. It combines a DAG-based expression structure with instruction sequencing under a single-register constraint. It is not a variant of RegisterSufficiency — the two problems ask fundamentally different questions (instruction count vs. register count). No existing problem in the codebase captures this.

Correctness

Warn. The two cited references are verified:

1. Bruno & Sethi (1976) — "Code Generation for a One-Register Machine," Journal of the ACM, 23(3), pp. 502–510. Confirmed to exist; NP-completeness result confirmed. The Sethi-Ullman 1970 paper (sethiUllman1970) is already in the project bibliography.

2. Sethi & Ullman (1970) — "The Generation of Optimal Code for Arithmetic Expressions," Journal of the ACM, 17(4), pp. 715–728. Confirmed. Polynomial algorithm for expression trees.

However, there are two concerns:

• The issue claims the G&J reduction is "from 3-SATISFIABILITY" (matching the book text), but then also says "R308 (3-SATISFIABILITY →)" in the associated reduction rules. The G&J book text itself says "Transformation from 3-SATISFIABILITY," which is consistent. However, the Bruno & Sethi 1976 paper is the original source, and whether they reduce from 3-SAT specifically (vs. general SAT) should be verified from the paper itself. The G&J book says 3-SAT, so this is likely correct.

• The example claims K=10 is infeasible ("answer is NO") without any justification. This is an unsubstantiated optimality claim — the issue does not prove or explain why 11 is the minimum instruction count for this DAG.

Well-written

Fail. Several template requirements are not met:

1. Variables section is vague. The section says "a permutation of operations" and "binary encoding can assign each vertex a time step" but does not provide a concrete variable count, per-variable domain, or clear encoding. For implementation, the programmer needs to know exactly how configurations map to instruction sequences. This section needs a precise encoding (e.g., "one variable per instruction slot, domain = {LOAD_v, STORE_v, OP_v}" with a count formula).

2. Missing Expected Outcome section. The template requires a clear "Expected Outcome" with a concrete valid solution and justification. The example provides a worked program but does not have a separate Expected Outcome section stating the answer (YES/NO) and why it is correct.

3. Unverified optimality claim in example. The example asserts "K = 10 → answer is NO" without justification. For the example to be useful for testing, the optimal instruction count must be verified (e.g., by exhaustive enumeration on this small instance or by a lower-bound argument). Without this, the example cannot be used for round-trip testing.

4. Missing concrete complexity expression. The Complexity section says "O*(2^n) brute-force over instruction orderings" but no specific best-known algorithm with a concrete complexity expression in terms of problem parameters is given (e.g., 2^num_vertices). For declare_variants!, a concrete expression string is required.

5. Schema proposes DirectedAcyclicGraph type which does not exist in the codebase. The issue should acknowledge this gap or propose how it will be represented (e.g., using an adjacency list, or extending existing graph types).

6. Example round-trip quality is uncertain. The example has 7 vertices with a shared subexpression, which is structurally interesting. However, because the optimality of K=11 is unverified, the example cannot be used for meaningful round-trip testing — we cannot confirm that K=11 is the minimum, so we cannot validate that a solver returns the correct answer.

Recommendations

• Verify the minimum instruction count for the example DAG (either by hand enumeration or a reference), or choose a simpler example where optimality can be easily demonstrated.
• Provide a concrete variable encoding with explicit count and domain for the brute-force solver.
• Add an Expected Outcome section.
• Note that DirectedAcyclicGraph is a new type that needs implementation, or propose an alternative representation using existing codebase primitives.
• Consider providing a complexity expression like "2^num_vertices" or a tighter bound if one exists in the literature.

[isPANN]

Converted from decision to optimization framing: removed bound K, now asks for minimum instruction count. Renamed to MinimumCodeGenerationOneRegister. Removed PoorWritten label. Companion rule issue: #949 (Satisfiability -> MinimumCodeGenerationOneRegister, G&J R308).

[isPANN]

Fix-issue changelog

• Variables: replaced vague "scheduling/sequencing problem" with concrete encoding (n variables, time-step domain)
• Schema: added explicit num_vertices, edges, num_leaves fields instead of abstract DirectedAcyclicGraph type
• Example: fixed optimality — original 11-instruction program was suboptimal; found 8-instruction program by computing v2 immediately after v3 (avoids extra LOAD). Verified by simulation.
• Expected Outcome: added section with Min(8) and instruction breakdown
• Definition: clarified instruction semantics (leaves are pre-loaded in memory as inputs)

Applied by /fix-issue.