Phi resolution in ir_lower: the parallel copy and its scratch word

Scope: the "phi web on a CFG edge is a parallel copy" item of the C2 review, as it lands in the optimizing backend.

Subject: jit/src/ir_lower.rs — Lowerer::emit_phi_copies, Lowerer::emit_copy_op, phi_copy_sequence, frame_word_loc / frame_word_off, and the frame reservation in Lowerer::new. Companion to docs/jit/linear-scan-regalloc.md, which owns the algorithm (regalloc::resolve_parallel_copy) and its CopyOp vocabulary.

---

0. Status in one paragraph

ir_lower now routes every edge's phi copies through regalloc::resolve_parallel_copy and emits the resulting Move / Save / Restore sequence. Cycles — the swap loop, and every other permutation of loop-carried values — are broken with one reserved frame word, Lowerer::phi_copy_scratch_slot_off, because RAX is already the move temporary and cannot also be the cycle parking spot. The intermediate UnsupportedShape("cyclic phi parallel copy") refusal is gone: a swap-shaped loop compiles, and compiles correctly, instead of dropping a tier.

---

1. What was wrong

prealloc_phi_slots gives every Op::Phi its own frame word. The copies one predecessor performs on its outgoing edge are therefore an assignment over distinct words, and — this is the part that was missed — a simultaneous one: every source must be read as it was before any destination is written.

A loop that swaps two locals makes each header phi the other's back-edge value:

for (…) { int t = a; a = b; b = t; }        // or, with no temp at all:
                                            // iload_1; iload_0; istore_1; istore_0

slot(a') ← slot(b)
slot(b') ← slot(a)

Emitted in gather order through RAX, the second copy reads the word the first just overwrote and both locals end up holding b. That is wrong code, not a missed optimisation, and it is invisible to any assertion about the copy list — only executing the emitted bytes shows it.

An intermediate state of the fix ordered the copies topologically (readers first) and, when only cycles remained, refused the compile with BailoutReason::UnsupportedShape("cyclic phi parallel copy"). Correct, but it dropped every swap-shaped loop to a lower tier.

2. The scratch word

Lowerer::new reserves five bookkeeping words between the locals (plus the optional context slot) and the spill band, at [rbp - (base + k) * 8]:

first_spill is (base + 5) * 8, one word higher than it used to be. Three properties follow, and all three are asserted in the_phi_scratch_word_is_reserved_below_the_spill_band:

• No collision with a coloured slot. alloc_slot_checked places a value at first_spill + colour * 8; the scratch is strictly below first_spill, so no colour plan_slots hands out can land on it. verify_slot_colouring and verify_data_locations see an unchanged spill band, and the published FrameLayout (locals_hi / spill_lo = first_spill) simply counts the scratch as one more reserved local word, exactly as it counts the other four.
• estimate_frame_bytes still equals the frame that gets built. Lowerer::new sizes the frame by calling estimate_frame_bytes, so the two cannot drift; the debug_assert_eq! against the hand-written layout sum is what pins the mirror, and its bookkeeping_size term moved from 8 * 4 to 8 * 5 in lockstep with the estimator's bookkeeping. The frame grows by 8 bytes (16 after alignment, half the time) per compiled method.
• The spill band still fits. The highest spill offset is first_spill + (slots - 1) * 8; the cap is frame_size - shadow - reserve - args. Both moved by the same 8 bytes, so the margin is what it always was.

Why not a register, and why not zeroed

RAX is the move temporary — every Move is load_to_rax; store_rax, so RAX is dead the instant the next move begins. Breaking a cycle needs a location that survives an intervening move. A second scratch register would work but this backend deliberately keeps every value in a frame word and reserves no register across an edge; one frame word is the cheap, local answer.

The word is not zeroed in the prologue and is never named by an oop map. A Save always precedes its matching Restore inside one straight-line copy sequence — no branch, no call, no safepoint in between — so it is never read before it is written, and never holds a live reference across a point the collector can observe. (Contrast shadow_thread_slot_off, which is zeroed, because its consumers are null-guarded on a value the prologue may skip writing.)

3. The ValueLoc view

resolve_parallel_copy speaks regalloc::ValueLoc. This backend's locations are rbp-relative byte offsets, so frame_word_loc / frame_word_off convert:

ValueLoc::Slot(off as u32)          // off is the offset, NOT off / 8

The resolver only ever compares locations — it never dereferences one, and the scratch is deliberately unnamed in CopyOp — so the payload has to be an injective token for "this frame word" and nothing more. The byte offset is exactly that. Dividing by 8 would be a hazard rather than a tidiness: it maps two distinct offsets onto one location the moment the offsets ever stop being 8-aligned, and resolve_parallel_copy drops a copy whose destination and source are the same location — so the aliasing would silently delete a real move, the same class of wrong-code bug this change removes.

ValueLoc::Reg is unreachable here and is refused (BailoutReason::Internal) rather than mis-emitted as an offset.

4. Cost

The acyclic majority — every merge that is not a permutation of live values — pays exactly the one load + one store per copy it always paid.

One word is enough for any number of cycles. resolve_parallel_copy prefers a ready destination on every pass, and breaking a cycle immediately makes one entry ready, so the Restore of cycle i is always emitted before the Save of cycle i + 1. That is an invariant of the resolver, but the frame reservation here is what depends on it, so disjoint_phi_cycles_never_nest_their_saves pins it from this side.

5. Behaviour change to be aware of

resolve_parallel_copy rejects a web that writes one destination twice with two different sources (BailoutReason::Internal, "a parallel copy writes one destination twice"). The old sequential emitter accepted that shape and let the last write win — which is wrong whenever the two entries came from two different edges of the same predecessor, since the edge actually taken decides the value. The new behaviour is a refused compile (fall back a tier), i.e. fail-closed. An identical pair listed twice is idempotent and is still accepted.

6. Tests

jit/src/ir_lower.rs, mod tests, section "Phi parallel copy".

The cycle cases execute the emitted bytes: parallel_copy_harness builds a real Lowerer frame (so the offsets, the scratch reservation and frame_size are production's), hand-rolls a minimal prologue/epilogue around the real sequencer and the real emitter, seeds the named words plus the scratch with a sentinel, and runs the result.

• a_two_element_phi_cycle_really_swaps_the_two_frame_words — the wrong-code witness; the old emitter left b in both words.
• a_three_element_phi_cycle_rotates_the_frame_words — 4 ops.
• an_acyclic_phi_chain_emits_the_minimal_moves_and_no_scratch — exact op list, and the scratch still holds its sentinel afterwards.
• a_self_copy_emits_nothing.
• disjoint_phi_cycles_never_nest_their_saves — the one-word invariant.
• a_register_location_is_refused_rather_than_emitted_as_an_offset.
• the_phi_scratch_word_is_reserved_below_the_spill_band — the five words are contiguous, no colour collides, and estimate_frame_bytes still equals the built frame_size (asserted in release too, not only via the debug_assert_eq!).
• the_swap_loop_compiles_and_swaps — end to end from bytecode. Returns a - b, so 0 is the readout for either duplication bug and a None compile is the readout for the refusal coming back.

7. Reconcile

Both items below are done (checked 2026-09-18, r9). Kept for the record.

docs/jit/linear-scan-regalloc.md carries a block titled "Reconcile — this is a live bug in ir_lower.rs" — gone; that file's Phi resolution is a parallel copy section now says "Two callers now, not one" and points at the consumer.

regalloc::ValueLoc::Slot's doc says the payload is "an 8-byte word index, as SlotPlan::node_color numbers them" — relaxed in R7: the doc now says whose numbering a Slot is in (the Allocation's, or the consumer's after Allocation::adopt_home_colouring) and that a backend building ValueLocs itself may use any injective per-word token, which is what §3's byte offset is.

8. What the same sequencer must NOT be asked to do (r9)

resolve_parallel_copy orders ONE simultaneous copy. It is not an edge resolver: the linear-scan allocation it is fed from is a timeline in block LAYOUT order, and when the scan splits a value the location at the top of a block is only right for the fall-through edge. The phi copies are safe from that because every phi source is read at the predecessor's own edge position (phi_edge_copies, ir_lower::emit_phi_copies). Split residency's per-position transitions are not — see docs/internal/fixed-bugs/linear-scan-split-timeline-has-no-edge-resolution-FIXED-20260918.md and regalloc::split_edge_conflicts.

r9 wave 2: the edge resolver now exists as its own function, regalloc::split_edge_resolution, and it FEEDS this sequencer rather than replacing it: its per-edge copies use the same (destination, source) convention as phi_edge_copies, so a consumer appends them to the edge's phi copies and sequences both through one resolve_parallel_copy call — which is required, not optional, because a phi copy can read a register a resolution copy writes (and the reverse). The duplicate-destination refusal still holds across the union: a resolution destination is always a register the target block's code reads a live-in value from, and a phi is never live into its own block, so a collision there is a malformed plan, not a sequencing problem.