[Model] MinimumCodeGenerationUnlimitedRegisters

[isPANN]

Motivation

MINIMUM CODE GENERATION WITH UNLIMITED REGISTERS (P297) from Garey & Johnson, A11 PO5. Given an expression DAG where arcs are partitioned into left (L) and right (R) operand sets, find the minimum number of instructions needed to compute all roots using unlimited registers but only 2-address instructions (where one operand is destroyed). The unlimited register supply means spilling is never needed, but the 2-address instruction constraint means one operand register is overwritten by the result, forcing careful operand ordering.

Associated reduction rules:

• As target: R320 (FEEDBACK VERTEX SET →)
• Connections (beyond G&J):
  • Complements MinimumCodeGenerationOneRegister (P296): that problem has 1 register with 3-address instructions; this has unlimited registers with 2-address instructions
  • The L/R partition determines which operand is destroyed by each operation

Definition

Name: MinimumCodeGenerationUnlimitedRegisters
Reference: Garey & Johnson, Computers and Intractability, A11 PO5

Mathematical definition:

INSTANCE: Directed acyclic graph G = (V, A) with maximum out-degree 2, a partition of A into two sets L (left operand arcs) and R (right operand arcs).
OBJECTIVE: Find a program of minimum number of instructions for an unlimited-register machine (using 2-address instructions) that computes all root vertices (vertices with in-degree 0).

Instruction semantics:

• For a vertex v with arcs (v, u) ∈ L and (v, w) ∈ R: the operation computes v = op(u, w) where the result overwrites the register holding the left operand u. After the instruction, the register that held u now holds v, and the register holding w is unchanged.
• A LOAD instruction copies a value from one register to another (needed when a value must be preserved because it would otherwise be destroyed).
• With unlimited registers, there is no spilling — every value can be kept in a register. The cost comes from extra LOAD (copy) instructions needed to preserve values before they are destroyed.

Variables

• Count: n = |V| (one variable per vertex representing its position in the instruction schedule)
• Per-variable domain: {0, 1, ..., 3n-1} (time step; upper bound allows LOAD + OP per vertex plus extra copies)
• Meaning: A valid program is a sequence of OP and LOAD instructions respecting DAG dependencies. The objective minimizes total instruction count (OPs + LOADs).

Schema (data type)

Type name: MinimumCodeGenerationUnlimitedRegisters
Variants: (none)

Field	Type	Description
num_vertices	usize	Number of vertices
left_arcs	Vec<(usize, usize)>	Left operand arcs L ⊆ A: (parent, child) — child's register is destroyed
right_arcs	Vec<(usize, usize)>	Right operand arcs R ⊆ A: (parent, child) — child's register is preserved

Complexity

• Decision complexity: NP-complete (Aho, Johnson, and Ullman, 1977; transformation from FEEDBACK VERTEX SET).
• Best known exact algorithm: O*(2^num_vertices) brute-force.
• Restrictions: NP-complete even if only leaf vertices have in-degree > 1. Polynomial for directed forests. Also polynomial if 3-address instructions are allowed.
• References:
  • A.V. Aho, S.C. Johnson, J.D. Ullman (1977). "Code Generation for Machines with Multiregister Operations." Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 21–28.

Extra Remark

Full book text:

INSTANCE: Directed acyclic graph G = (V, A) with maximum out-degree 2, partition of A into sets L and R, positive integer K.
QUESTION: Can all root (in-degree 0) vertices be computed by a program of K or fewer instructions for an unlimited-register machine?
Reference: [Aho, Johnson, and Ullman, 1977a]. Transformation from FEEDBACK VERTEX SET.
Comment: NP-complete even if the only vertices having in-degree greater than 1 are leaves [Aho, Johnson, and Ullman, 1977a]. Solvable in polynomial time for forests or if 3-address instructions are allowed.

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 evaluation orderings and copy-insertion choices; find the one with minimum total instructions.)
• It can be solved by reducing to integer programming.
• Other: Polynomial for forests and for 3-address architectures.

Example Instance

Expression DAG G with 5 vertices {v0, v1, v2, v3, v4}:

• Leaves: {v3, v4} (input values, each in its own register)
• Internal: {v1, v2} (binary operations)
• Root: {v0} (final result)
• L/R partition:
  • v1: (v1→v3) ∈ L, (v1→v4) ∈ R — v1 = op(v3, v4), destroys register holding v3
  • v2: (v2→v3) ∈ L, (v2→v4) ∈ R — v2 = op(v3, v4), destroys register holding v3
  • v0: (v0→v1) ∈ L, (v0→v2) ∈ R — v0 = op(v1, v2), destroys register holding v1

Note: v3 and v4 are shared leaves (in-degree 2 each). v3 is the left operand (destroyed) in both v1 and v2.

Optimal program (4 instructions):

1. LOAD: copy register(v3) → new register (preserving original v3)
2. OP v1: reg = op(v3_copy, v4) — destroys the copy, v4 preserved
3. OP v2: reg = op(v3_original, v4) — destroys original v3, v4 preserved
4. OP v0: reg = op(v1, v2) — destroys v1

Why 3 instructions is impossible: There are 3 internal nodes requiring 3 OPs. Since v3 is a left operand in both v1 and v2, computing v1 destroys v3's register. To then compute v2 (which also needs v3 as left operand), v3 must have been copied first. This forces at least 1 LOAD, giving 3 + 1 = 4 minimum.

Suboptimal program (5 instructions): If v4 is also copied unnecessarily, we get 3 OPs + 2 LOADs = 5.

Expected Outcome

Optimal value: Min(4) — the minimum number of instructions is 4 (3 OPs + 1 LOAD). The shared left-operand destruction of v3 forces exactly one copy instruction.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned reduction from FeedbackVertexSet
Non-trivial	✅ Pass	Distinct from RegisterSufficiency (limited registers) — different feasibility constraints (2-address + unlimited registers + L/R partition)
Correctness	⚠️ Warn	Reference paper verified to exist; complexity bound is generic brute-force only; instruction semantics marked AI-interpreted
Well-written	❌ Fail	Variables section vague; Schema uses nonexistent type; complexity expression missing problem parameters; no separated Expected Outcome section

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. The problem CodeGenerationUnlimitedRegisters does not exist in the codebase. It is distinct from the existing RegisterSufficiency problem (which models limited-register DAG computation). The issue mentions a concrete planned reduction: FEEDBACK VERTEX SET → CodeGenerationUnlimitedRegisters (R320 in G&J), connecting it to the existing MinimumFeedbackVertexSet node. Brute-force solving is checked.

Non-trivial

Pass. This problem has genuinely different feasibility constraints from all existing problems:

• Unlike RegisterSufficiency, which limits the number of registers, this problem has unlimited registers but constrains the instruction format (2-address, where one operand is destroyed).
• The L/R partition of arcs (determining which operand is destroyed) is a unique structural feature not present in any existing model.
• The NP-hardness arises from the operand-destruction constraint, not from register scarcity.

Correctness

Warn. Partial verification:

• Reference exists: The cited paper — A.V. Aho, S.C. Johnson, J.D. Ullman, "Code Generation for Machines with Multiregister Operations," POPL 1977, pp. 21–28 — is verified at ACM DL. The connection to Garey & Johnson A11 PO5 is corroborated by the NP-Complete Problems discussion site which tags PO5 with both "Code Generation With Unlimited Registers" and "Feedback Vertex Set."
• Complexity bound is generic: The issue claims "O*(2^n) brute-force" but does not cite any specialized exact algorithm. This is acceptable as a placeholder but should ideally reference whether a better algorithm exists. No better algorithm was found during search.
• Instruction semantics unverified: The detailed L/R operand destruction semantics (left operand destroyed, right preserved) are marked ⚠️ Unverified: AI-interpreted. The original paper's full text was not accessible for independent verification. The semantics are plausible for 2-address instruction architectures (consistent with x86-style destructive binary operations), but the specific convention (left vs right destroyed) should be verified against the original paper before implementation.

Well-written

Fail. Several sections need improvement:

1. Variables section is vague. It says "The configuration involves an evaluation order and register allocation decisions" without specifying:

   • A concrete variable count formula (e.g., number of scheduling + copy-insertion decision variables)
   • Per-variable domain (binary? permutation indices?)
   • How brute-force enumeration would iterate over configurations

   This section needs a concrete mapping suitable for dims() implementation.

2. Schema uses nonexistent type. The field dag is typed as DirectedAcyclicGraph, which does not exist in the codebase. The schema should use concrete types available in the project (e.g., num_vertices: usize + arcs: Vec<(usize, usize)>, similar to how RegisterSufficiency represents its DAG).

3. Complexity expression missing problem parameters. The issue says "O*(2^n) brute-force" but the required format is a concrete expression using getter-method variable names (e.g., "2^num_vertices" or "num_vertices^2 * 2^num_vertices"). This is needed for declare_variants!.

4. No separated Expected Outcome section. The example embeds the answer (K=4 → YES, K=3 → NO) within the narrative but lacks a clearly separated "Expected Outcome" section with a single canonical instance, its solution, and brief justification. The template requires: "one valid/satisfying solution with brief justification."

5. Example adequacy is borderline. The 5-vertex example has only 2 internal vertices and 2 shared leaves. While it demonstrates the copy-insertion necessity, it may be too small for meaningful round-trip testing. A slightly larger example (7–8 vertices with multiple copy-insertion choices) would better exercise the problem structure.

Recommendations

• Model the schema after RegisterSufficiency (which already represents a DAG with num_vertices, arcs, and bound fields) — add left_arcs and right_arcs as separate Vec<(usize, usize)> fields or use a single arcs list with a flag/enum for L/R classification.
• For the Variables section, consider: each internal vertex needs a scheduling position (permutation of internal vertices), and each use of a shared value as a left operand (except possibly the last) needs a copy-insertion decision (binary). This gives a concrete variable space.
• Verify the L/R destruction convention against the original Aho, Johnson, Ullman 1977 paper before implementation.

[isPANN]

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

[isPANN]

Fix-issue changelog

• Variables: replaced vague "scheduling + copy insertion decisions" with concrete encoding (n variables, time-step domain)
• Schema: replaced abstract DirectedAcyclicGraph type with concrete fields (num_vertices, left_arcs, right_arcs)
• Example: clarified the 4-instruction optimal program with step-by-step register tracking; added "why 3 is impossible" reasoning and suboptimal 5-instruction alternative
• Expected Outcome: added section with Min(4) and instruction breakdown
• Removed <!-- Unverified --> markers from verified sections

Applied by /fix-issue.