[Model] FeasibleRegisterAssignment

[isPANN]

Motivation

FEASIBLE REGISTER ASSIGNMENT (P294) from Garey & Johnson, A11 PO2. Given an expression DAG and a fixed assignment of registers to vertices, determine whether there exists a computation order that respects the assignment. This extends RegisterSufficiency (P293) by adding a constraint: not only must K registers suffice, but each vertex must use a specific pre-assigned register. Arises in compilers when register preferences are dictated by calling conventions or hardware constraints.

Associated reduction rules:

• As source: (none in G&J)
• As target: [Rule] 3-SATISFIABILITY to FEASIBLE REGISTER ASSIGNMENT #905 (3-SATISFIABILITY → FeasibleRegisterAssignment)
• Connections (beyond G&J):
  • Extends RegisterSufficiency (P293/R225): if the register assignment is not fixed, we get the simpler sufficiency question
  • Related to graph coloring: a register assignment is essentially a coloring of the interference graph, and feasibility asks if that coloring is realizable under evaluation order constraints
  • Applications: compiler backends with ABI register constraints, hardware with dedicated register roles

Definition

Name: FeasibleRegisterAssignment

Reference: Garey & Johnson, Computers and Intractability, A11 PO2

Mathematical definition:

INSTANCE: Directed acyclic graph G = (V, A), positive integer K, a register assignment function f: V → {R₁, R₂, ..., Rₖ}.
QUESTION: Is there a computation for G (an ordering of the vertices respecting the DAG dependencies) such that at each step, when a vertex v is computed, register f(v) is available (not holding a live value needed later)?

Semantics:
A "computation" is a topological ordering π of the vertices (from leaves to roots). At step i, vertex π(i) is evaluated and its result is placed in register f(π(i)). A register Rⱼ is "available" at step i if no previously computed vertex u with f(u) = Rⱼ still has a descendant that has not yet been computed. In other words, the value in Rⱼ can be overwritten only if it is no longer needed.

The question is whether the DAG can be evaluated in some topological order such the fixed register assignment f never causes a conflict (needing to store a live value and a new value in the same register simultaneously).

Variables

• Count: The configuration space is the set of valid topological orderings of G.
• Per-variable domain: For brute-force binary encoding, one can assign each vertex a time slot (integer in [0, |V|-1]).
• Meaning: A valid computation is a topological ordering π such that for all i, register f(π(i)) does not hold a value still needed by an uncomputed vertex.

Schema (data type)

Type name: FeasibleRegisterAssignment
Variants: (none)

Field	Type	Description
num_vertices	usize	Number of vertices n = |V|
arcs	Vec<(usize, usize)>	Directed arcs (v, u) meaning v depends on u
num_registers	usize	Number of registers K
assignment	Vec<usize>	Register assignment f: vertex index → register index (0-based)

Notes:

• This is a decision (feasibility) problem: does a valid computation order exist?
• assignment[v] gives the register index assigned to vertex v, with values in 0..num_registers.
• Schema follows the same pattern as RegisterSufficiency (flat fields, no graph wrapper type).
• Key getter methods: num_vertices() (= number of vertices), num_arcs() (= number of arcs), num_registers() (= K).

Complexity

• Decision complexity: NP-complete (Sethi, 1975; transformation from 3SAT).
• Restrictions: NP-complete even with max out-degree 2.
• Best known exact algorithm: Brute-force over topological orderings with per-step register check.
• Complexity expression for declare_variants!: num_vertices ^ 2 * 2 ^ num_vertices (same bound as RegisterSufficiency; the additional assignment check is O(1) per step).
• References:
  • R. Sethi (1975). "Complete Register Allocation Problems." SIAM Journal on Computing, 4(3), pp. 226–248. Original NP-completeness proof and relationship to register sufficiency.

Specialization

• This is a special case of: General register allocation (where both assignment and sufficiency are free)
• Generalizes: RegisterSufficiency (P293) — if we existentially quantify over f, we get register sufficiency
• Known special cases: Trees (polynomial — Sethi-Ullman techniques apply)

Extra Remark

Full book text:

INSTANCE: Directed acyclic graph G = (V, A), positive integer K, register assignment f: V → {R₁, R₂, ..., Rₖ}.
QUESTION: Is there a computation for G that respects the register assignment f?
Reference: [Sethi, 1975]. Transformation from 3-SATISFIABILITY.
Comment: NP-complete even with maximum out-degree 2.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all topological orderings of the DAG and check if any respects the register assignment constraints.
• It can be solved by reducing to integer programming. (Possible via scheduling-style ILP with register liveness constraints.)
• Other: Polynomial for expression trees.

Example Instance

Expression DAG G with 4 vertices {0, 1, 2, 3}, K = 2 registers {R₀, R₁}:

• Leaves: {2, 3} (no dependencies)
• Internal: {1} depends on {3}
• Root: {0} depends on {1, 2}
• Arcs: (0→1), (0→2), (1→3)

Register assignment: f(0) = R₀, f(1) = R₁, f(2) = R₀, f(3) = R₀

Answer: YES — a feasible computation order exists.

Valid computation order: 3 → 1 → 2 → 0

• Step 1: Compute v3, place in R₀. (R₀ = v3, live — needed by v1)
• Step 2: Compute v1 = op(v3), place in R₁. v3 has no remaining dependents, so R₀ is now free. (R₁ = v1, live — needed by v0)
• Step 3: Compute v2 (leaf), place in R₀. (R₀ = v2, live — needed by v0; R₁ = v1, live — needed by v0)
• Step 4: Compute v0 = op(v1, v2), place in R₀. Reads v1 from R₁ and v2 from R₀, then overwrites R₀ with result. Done.

No register conflicts occur: each time a vertex is computed, its assigned register either was free or held a value no longer needed.

Infeasible variant (same DAG, K = 1, all vertices assigned to R₀):

• f(0) = R₀, f(1) = R₀, f(2) = R₀, f(3) = R₀
• Any valid topological order requires v3 before v1, and both v1 and v2 before v0.
• After computing v3 (R₀ = v3), computing v2 overwrites R₀ — but v1 still needs v3. Alternatively, computing v1 next overwrites R₀ — but v0 still needs v2. With only one register and fan-in 2 at the root, no order avoids a conflict.
• Answer: NO — no feasible computation order exists.

Validation script

#!/usr/bin/env python3
"""Validate FeasibleRegisterAssignment examples."""
from itertools import permutations

def is_topo_order(order, arcs, n):
    pos = [0] * n
    for i, v in enumerate(order):
        pos[v] = i
    return all(pos[u] < pos[v] for (v, u) in arcs)

def is_feasible(order, arcs, n, assignment):
    dependents = {v: [] for v in range(n)}
    for (v, u) in arcs:
        dependents[u].append(v)
    computed = set()
    for v in order:
        reg = assignment[v]
        for w in computed:
            if assignment[w] == reg:
                if any(d not in computed and d != v for d in dependents[w]):
                    return False
        computed.add(v)
    return True

def solve(n, arcs, assignment):
    return [list(p) for p in permutations(range(n))
            if is_topo_order(p, arcs, n) and is_feasible(p, arcs, n, assignment)]

# Feasible: 4 vertices, arcs (0,1),(0,2),(1,3), K=2, assignment [0,1,0,0]
r1 = solve(4, [(0,1),(0,2),(1,3)], [0,1,0,0])
assert len(r1) == 1 and r1[0] == [3,1,2,0], f"Expected [[3,1,2,0]], got {r1}"
print("Feasible example: PASS")

# Infeasible: same DAG, K=1, assignment [0,0,0,0]
r2 = solve(4, [(0,1),(0,2),(1,3)], [0,0,0,0])
assert len(r2) == 0, f"Expected [], got {r2}"
print("Infeasible example: PASS")

References

• [Sethi, 1975]: R. Sethi (1975). "Complete Register Allocation Problems." SIAM Journal on Computing, 4(3), pp. 226–248.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; planned 3SAT reduction provides connectivity
Non-trivial	✅ Pass	Distinct from RegisterSufficiency — adds fixed assignment constraint f: V → {R₁,...,Rₖ}
Correctness	✅ Pass	Sethi 1975 reference verified; NP-completeness claim consistent with G&J A11 PO2
Well-written	❌ Fail	Multiple issues: broken example, missing expected outcome, nonexistent data type

Overall: 3 passed, 0 warnings, 1 failed

---

Usefulness

Pass. FeasibleRegisterAssignment does not exist in the codebase. The issue mentions a concrete reduction from 3-SATISFIABILITY (G&J R311) and a relationship to the existing RegisterSufficiency model. The motivation (compiler backends with ABI register constraints, hardware with dedicated register roles) is concrete and well-justified.

The "How to solve" section checks brute-force and notes polynomial solvability for trees. ILP is not claimed as a direct solver path, so no companion [Rule] issue is required.

Non-trivial

Pass. RegisterSufficiency asks whether K registers suffice for a DAG computation, with freedom to assign any register to any vertex. FeasibleRegisterAssignment fixes the register assignment f and asks whether a valid evaluation order exists that respects it. The fixed assignment constraint is a genuinely different feasibility condition — not a variant or renaming of an existing problem.

Correctness

Pass. The cited reference — R. Sethi (1975), "Complete Register Allocation Problems," SIAM Journal on Computing 4(3), pp. 226–248 — is confirmed real and already present in the project bibliography (docs/paper/references.bib as sethi1975). The DOI (10.1137/0204020) matches. The NP-completeness claim via transformation from 3-SAT is consistent with Garey & Johnson A11 PO2.

The complexity bound "O*(2^n) brute-force over topological orderings" is generic rather than a specialized algorithm. This is acceptable for NP-complete problems without known improved exact algorithms, though the actual number of topological orderings can be much smaller than 2^n.

Well-written

Fail. Several issues need to be addressed:

4a: Missing/Incomplete Sections

1. Missing Expected Outcome. The example does not provide a definitive answer. The issue's own walkthrough of the order 3 → 4 → 1 → 2 → 0 identifies a potential conflict at step 4 but then does not resolve whether the instance is feasible or infeasible. A model issue must state: either a concrete valid computation order (with step-by-step register state verification), or an explicit statement of infeasibility with justification.

2. Missing concrete complexity expression. The complexity section says "O*(2^n) brute-force" but does not give a complexity expression in terms of problem parameters (e.g., 2^num_vertices). The declare_variants! macro requires a concrete expression string.

4b: Schema Issues

3. Nonexistent data type DirectedAcyclicGraph. The schema proposes a field dag of type DirectedAcyclicGraph, but this type does not exist in the codebase. The existing RegisterSufficiency model (which has an almost identical input structure) uses num_vertices: usize and arcs: Vec<(usize, usize)> instead. The schema should follow the same pattern for consistency and implementability.

4d: Example Quality

4. Example is broken/inconclusive. The worked example traces order 3 → 4 → 1 → 2 → 0 but then questions its own validity ("conflict? v3 was consumed by step 3, and step 4 also needs v3"). An example must either demonstrate a valid solution or prove infeasibility — it cannot end with an open question. The example should have multiple feasible configurations with different feasibility outcomes to meaningfully test correctness.

5. Example lacks round-trip testability. For a feasibility problem, the example needs a mix of satisfying and non-satisfying configurations. The current example does not even resolve the feasibility of the single order it considers.

Recommendations

• Model the schema after RegisterSufficiency: use num_vertices, arcs, num_registers, and assignment fields (no DirectedAcyclicGraph type).
• Provide a small but complete example (5-6 vertices) with: (a) one valid computation order with step-by-step register state, and (b) at least one invalid order showing why it fails.
• Add a complexity expression like num_vertices ^ 2 * 2 ^ num_vertices (matching RegisterSufficiency's bound, since the additional assignment check is O(1) per step).

[isPANN]

Changelog — Issue Quality Fix

Addressed all failures from the check-issue report:

Fixed

1. Linked associated rule: Changed R311 (3-SATISFIABILITY →) to #905 (3-SATISFIABILITY → FeasibleRegisterAssignment) with GitHub issue cross-reference.
2. Added concrete complexity expression: num_vertices ^ 2 * 2 ^ num_vertices for declare_variants! (matches RegisterSufficiency's bound — the additional per-step assignment check is O(1)).
3. Fixed schema — removed nonexistent DirectedAcyclicGraph type: Replaced with num_vertices: usize + arcs: Vec<(usize, usize)>, matching the RegisterSufficiency pattern.
4. Added getter methods to Schema notes: num_vertices(), num_arcs(), num_registers().
5. Replaced broken example with a verified one: 4-vertex DAG with K=2 (feasible, one valid order [3,1,2,0] with step-by-step register state trace) and K=1 all-same-register variant (infeasible with justification).
6. Added Python validation script in a <details> block confirming both examples.
7. Removed all ⚠️ Unverified markers — content has been reviewed and validated.

[isPANN]

Please kindly check the following items (PR #960):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.