◐ Off-By-One

js-20261008-wasm-gc-moving-heap-stackmap-deopt

1 answer(s)jsnode20

Problem class: js-20261008-wasm-gc-moving-heap-stackmap-deopt

Answer

Sound Stack Maps for Wasm GC Across Moving-Heap Safepoints

Problem class: js-20261008-wasm-gc-moving-heap-stackmap-deopt

A complete, dependency-free Node ≥20 implementation with a behavioural test suite was built and verified at ~/wasm-stackmap/ (stackmap.js, stackmap.test.js, demo.js, SOLUTION.md). All 16 tests pass and the end-to-end relocation/resume demo passes. The full write-up is below.

1. Root-cause analysis

A moving (compacting) collector relocates objects, so between two safepoints the runtime must find every live reference to update its bit pattern. A Wasm GC stack map maps each live value at a safepoint (call, loop back-edge, deopt point) to a location (register, slot, or constant). The failure modes are asymmetric — that asymmetry is the whole problem:

Class	Example	Consequence	Reject?
Under-approximation	live `v0` in `rax`, map `{}`	object never updated → dangling pointer	yes
Stale root	map `v0→rax` but a call/def clobbered `rax`	GC relocates garbage / `v0` stays stale	yes
Precise over-approximation	dead `v1` in `rbx`, map `v1→rbx`	object kept alive one extra cycle	no (safe)
Unsafe over-approximation	map `v1→rbx` but `rbx` holds an `i32`/garbage	GC relocates an integer → corruption	yes

Naive validators go wrong in four predictable places:

They reject all extra map entries — killing safe conservative maps. The correct rule is not "exact"; it is "every extra physical root must definitely hold a movable reference or null".
They check state before a call. Caller-saved registers are destroyed by the call, so the safepoint state is before + clobbers. A root living only in rax across a call is stale.
They only look at the innermost inline frame. Inlined locals can live in the caller's registers/slots, so one safepoint has a union of obligations over the whole inline stack.
They repair greedily per safepoint. A value live across k safepoints needs one spill, not k. Minimum repair is a set cover over spill placements.

Also: i31ref/numeric types are not moved — putting one in a root list is unsafe, not redundant. And deopt metadata pins non-reference values: a missing i32 local is not a GC bug, but it is an observable behaviour bug after resume.

Soundness definition

Let live(S) be values live at safepoint S, and movable(t) true for anyref/eqref/structref/arrayref/externref/funcref/ref. Map M at S is sound iff:

Coverage. For every v ∈ live(S) with movable(type(v)), M(v)=L and L definitely holds v (must-analysis).
Root safety. Every physical entry v→L has L definitely holding a movable value (or null const). Extra dead-but-valid roots are accepted.
Resume. Every deopt binding (label→v) has a valid M(v).

Repair cost = #entries + #spills. Entry cost is a constant offset, so minimising repairs = minimising inserted spills, each spill covering every safepoint it dominates until the value is redefined.

2. Model

Function = { name, entry, blocks: Block[] }
Block    = { id, succs: string[], insts: Inst[] }
insts    = def dst,type,loc | copy dst,src,type | moveto v,loc | clobber loc
         | safepoint id,map,frames | call id,args,clobbers,dst,loc,map,frames
         | deopt id,map,frames | br target | ret value
loc      = {k:'reg',name} | {k:'slot',index} | {k:'const',value}
frame    = { id, caller, pc, deopt:boolean, values:{ label: vreg } }
map      = { vreg: loc }

3. The exact fix — `stackmap.js`

Pipeline: const { before, plan, repaired, after } = require('./stackmap').checkAndRepair(func).

Internals: (1) block liveness fixpoint where frame bindings count as uses; (2) must/may abstract interpreter — locOf[v] = locations where v is definitely present (intersection over paths), mayHold[loc] = values that may be there (union, with a GARBAGE marker); (3) dominators + RPO for legal spill anchors; (4) validation using the safepoint state (call = pre-call + clobbers); (5) repair with exact branch-and-bound set cover; (6) a relocation/resume simulator that actually moves objects at each safepoint and checks every required value and deopt local.

'use strict';

/*
 * stackmap.js
 * Validator + repair pass for WebAssembly GC stack maps across moving-GC
 * safepoints (inlined frames, register spills, deopt metadata).
 */

const MOVABLE = new Set([
  'anyref', 'eqref', 'structref', 'arrayref', 'externref', 'funcref',
  'ref', 'ref null', 'dataref',
]);
const GARBAGE = '<garbage>';
const isMovable = (t) => !!t && MOVABLE.has(t);

const locKey = (l) =>
  l.k === 'reg' ? `reg:${l.name}` : l.k === 'slot' ? `slot:${l.index}` : `const:${JSON.stringify(l.value)}`;

function emptyState() {
  return { locOf: new Map(), mayHold: new Map(), constOf: new Map() };
}
function cloneState(s) {
  const o = emptyState();
  for (const [v, set] of s.locOf) o.locOf.set(v, new Set(set));
  for (const [k, set] of s.mayHold) o.mayHold.set(k, new Set(set));
  for (const [v, val] of s.constOf) o.constOf.set(v, val);
  return o;
}

function instDefs(i) {
  if (i.op === 'def' || i.op === 'copy') return [i.dst];
  if (i.op === 'call' && i.dst) return [i.dst];
  return [];
}
function instUses(i) {
  const u = [];
  if (i.op === 'copy') u.push(i.src);
  if (i.op === 'moveto') u.push(i.v);
  if (i.op === 'call') for (const a of i.args || []) u.push(a);
  if (i.op === 'safepoint' || i.op === 'deopt' || i.op === 'call')
    for (const f of i.frames || []) for (const v of Object.values(f.values)) u.push(v);
  if (i.op === 'ret' && i.value) u.push(i.value);
  return u;
}

function removeLoc(st, key) {
  for (const set of st.locOf.values()) set.delete(key);
}
function overwriteLoc(st, key, holder) {
  removeLoc(st, key);
  st.mayHold.set(key, new Set([holder]));
}

function transfer(st, i) {
  const s = cloneState(st);
  switch (i.op) {
    case 'def': {
      if (i.loc.k === 'const') {
        s.locOf.delete(i.dst);
        s.constOf.set(i.dst, i.loc.value);
      } else {
        s.constOf.delete(i.dst);
        const key = locKey(i.loc);
        overwriteLoc(s, key, i.dst);
        s.locOf.set(i.dst, new Set([key]));
      }
      break;
    }
    case 'copy': {
      s.locOf.delete(i.dst);
      s.constOf.delete(i.dst);
      if (s.constOf.has(i.src)) s.constOf.set(i.dst, s.constOf.get(i.src));
      const srcs = s.locOf.get(i.src);
      if (srcs) {
        s.locOf.set(i.dst, new Set(srcs));
        for (const key of srcs) {
          if (!s.mayHold.has(key)) s.mayHold.set(key, new Set());
          s.mayHold.get(key).add(i.dst);
        }
      }
      break;
    }
    case 'moveto': {
      s.constOf.delete(i.v);
      const key = locKey(i.loc);
      const old = s.locOf.get(i.v) || new Set();
      for (const k of old) {
        const h = s.mayHold.get(k);
        if (h) h.delete(i.v);
      }
      overwriteLoc(s, key, i.v);
      s.locOf.set(i.v, new Set([key]));
      break;
    }
    case 'clobber': {
      const key = locKey(i.loc);
      removeLoc(s, key);
      s.mayHold.set(key, new Set([GARBAGE]));
      break;
    }
    case 'call': {
      for (const c of i.clobbers || []) {
        const key = locKey(c);
        removeLoc(s, key);
        s.mayHold.set(key, new Set([GARBAGE]));
      }
      if (i.dst && i.loc) {
        s.constOf.delete(i.dst);
        const key = locKey(i.loc);
        overwriteLoc(s, key, i.dst);
        s.locOf.set(i.dst, new Set([key]));
      }
      break;
    }
    default:
      break;
  }
  return s;
}

function mergeStates(a, b) {
  if (!a) return cloneState(b);
  if (!b) return cloneState(a);
  const out = emptyState();
  const vs = new Set([...a.locOf.keys(), ...b.locOf.keys()]);
  for (const v of vs) {
    const sa = a.locOf.get(v);
    const sb = b.locOf.get(v);
    if (!sa || !sb) continue;
    const inter = new Set([...sa].filter((x) => sb.has(x)));
    if (inter.size) out.locOf.set(v, inter);
  }
  const ls = new Set([...a.mayHold.keys(), ...b.mayHold.keys()]);
  for (const k of ls) {
    const x = a.mayHold.get(k) || new Set();
    const y = b.mayHold.get(k) || new Set();
    out.mayHold.set(k, new Set([...x, ...y]));
  }
  const cs = new Set([...a.constOf.keys(), ...b.constOf.keys()]);
  for (const v of cs) {
    if (a.constOf.has(v) && b.constOf.has(v) && a.constOf.get(v) === b.constOf.get(v))
      out.constOf.set(v, a.constOf.get(v));
  }
  return out;
}

function stateSig(s) {
  if (!s) return 'null';
  const l = [...s.locOf.entries()]
    .map(([v, set]) => `${v}=${[...set].sort().join(',')}`).sort().join('|');
  const m = [...s.mayHold.entries()]
    .map(([k, set]) => `${k}=${[...set].sort().join(',')}`).sort().join('|');
  const c = [...s.constOf.entries()].map(([v, x]) => `${v}=${x}`).sort().join('|');
  return `${l}##${m}##${c}`;
}
function setEq(a, b) {
  if (a.size !== b.size) return false;
  for (const x of a) if (!b.has(x)) return false;
  return true;
}

/* Analysis: liveness, must/may location state, dominators, RPO order */
function analyze(func) {
  const blocks = new Map(func.blocks.map((b) => [b.id, b]));
  const entry = func.entry ?? func.blocks[0].id;

  const reach = new Set();
  const work = [entry];
  while (work.length) {
    const id = work.pop();
    if (reach.has(id)) continue;
    reach.add(id);
    for (const s of blocks.get(id).succs || []) if (blocks.has(s)) work.push(s);
  }

  const types = new Map();
  for (const b of func.blocks)
    for (const i of b.insts) {
      if (i.op === 'def' || i.op === 'copy') types.set(i.dst, i.type);
      if (i.op === 'call' && i.dst) types.set(i.dst, i.dstType || 'anyref');
    }

  const preds = new Map();
  for (const id of reach) preds.set(id, []);
  for (const id of reach)
    for (const s of blocks.get(id).succs || [])
      if (reach.has(s)) preds.get(s).push(id);

  const liveIn = new Map();
  const liveOut = new Map();
  for (const id of reach) { liveIn.set(id, new Set()); liveOut.set(id, new Set()); }
  let changed = true;
  while (changed) {
    changed = false;
    for (const id of reach) {
      const b = blocks.get(id);
      const out = new Set();
      for (const s of b.succs || []) if (reach.has(s)) for (const v of liveIn.get(s)) out.add(v);
      liveOut.set(id, out);
      let live = new Set(out);
      for (let k = b.insts.length - 1; k >= 0; k--) {
        const ins = b.insts[k];
        for (const d of instDefs(ins)) live.delete(d);
        for (const u of instUses(ins)) live.add(u);
      }
      if (!setEq(live, liveIn.get(id))) { liveIn.set(id, live); changed = true; }
    }
  }

  const liveBefore = new Map();
  const liveAfter = new Map();
  for (const id of reach) {
    const b = blocks.get(id);
    let live = new Set(liveOut.get(id));
    for (let k = b.insts.length - 1; k >= 0; k--) {
      const ins = b.insts[k];
      liveAfter.set(ins, new Set(live));
      for (const d of instDefs(ins)) live.delete(d);
      for (const u of instUses(ins)) live.add(u);
      liveBefore.set(ins, new Set(live));
    }
  }

  const inState = new Map();
  const outState = new Map();
  inState.set(entry, emptyState());
  const queue = [entry];
  const inQueue = new Set([entry]);
  while (queue.length) {
    const id = queue.shift();
    inQueue.delete(id);
    const b = blocks.get(id);
    let st = inState.get(id);
    if (!st) continue;
    for (const ins of b.insts) st = transfer(st, ins);
    outState.set(id, st);
    for (const s of b.succs || []) {
      if (!reach.has(s)) continue;
      const merged = mergeStates(inState.get(s) || null, st);
      if (stateSig(inState.get(s)) !== stateSig(merged)) {
        inState.set(s, merged);
        if (!inQueue.has(s)) { queue.push(s); inQueue.add(s); }
      }
    }
  }
  const before = new Map();
  const after = new Map();
  for (const id of reach) {
    const b = blocks.get(id);
    let st = inState.get(id) || emptyState();
    for (const ins of b.insts) { before.set(ins, st); st = transfer(st, ins); after.set(ins, st); }
  }

  const dom = new Map();
  for (const id of reach) dom.set(id, id === entry ? new Set([id]) : new Set(reach));
  let dch = true;
  while (dch) {
    dch = false;
    for (const id of reach) {
      if (id === entry) continue;
      const ps = preds.get(id);
      if (!ps.length) continue;
      let inter = new Set(dom.get(ps[0]));
      for (let k = 1; k < ps.length; k++) {
        const d = dom.get(ps[k]);
        inter = new Set([...inter].filter((x) => d.has(x)));
      }
      inter.add(id);
      if (!setEq(inter, dom.get(id))) { dom.set(id, inter); dch = true; }
    }
  }

  const order = [];
  const seen = new Set();
  const dfs = (id) => {
    if (seen.has(id)) return;
    seen.add(id);
    const b = blocks.get(id);
    for (const s of b.succs || []) if (reach.has(s)) dfs(s);
    order.push(id);
  };
  dfs(entry);
  order.reverse();

  const instOrder = [];
  const instIndex = new Map();
  const pos = new Map();
  let g = 0;
  for (const id of order) {
    const b = blocks.get(id);
    for (let k = 0; k < b.insts.length; k++) {
      const ins = b.insts[k];
      instOrder.push(ins);
      instIndex.set(ins, g);
      pos.set(ins, { blockId: id, idx: k, g });
      g++;
    }
  }

  const safepoints = instOrder.filter((i) =>
    i.op === 'safepoint' || i.op === 'deopt' || i.op === 'call');

  return {
    func, blocks, entry, reach, types, preds,
    liveIn, liveOut, liveBefore, liveAfter,
    inState, outState, before, after,
    dom, order, instOrder, instIndex, pos, safepoints,
    blockDominates: (a, b) => a === b || (dom.get(b)?.has(a) ?? false),
  };
}

/* Validation */
function locHolds(st, v, loc) {
  if (!st) return false;
  if (loc.k === 'const') return st.constOf.has(v) && st.constOf.get(v) === loc.value;
  return !!st.locOf.get(v)?.has(locKey(loc));
}
function isSafeRoot(st, loc, types) {
  if (loc.k === 'const') return true;                 // constants cannot corrupt GC
  const holders = st?.mayHold.get(locKey(loc));
  if (!holders || holders.size === 0) return false;
  for (const h of holders) {
    if (h === GARBAGE) return false;
    if (!isMovable(types.get(h))) return false;
  }
  return true;
}
function safepointState(A, inst) {
  const before = A.before.get(inst) || emptyState();
  if (inst.op !== 'call') return before;
  // A call destroys caller-saved locations at the safepoint itself.
  const st = cloneState(before);
  for (const c of inst.clobbers || []) {
    const key = locKey(c);
    removeLoc(st, key);
    st.mayHold.set(key, new Set([GARBAGE]));
  }
  return st;
}
function requiredValues(A, inst) {
  const before = A.liveBefore.get(inst) || new Set();
  const req = new Map();
  for (const v of before) if (isMovable(A.types.get(v))) req.set(v, { v, deopt: false });
  for (const f of inst.frames || [])
    if (f.deopt) for (const v of Object.values(f.values)) req.set(v, { v, deopt: true });
  return [...req.values()];
}
function validate(func, preAnalysis) {
  const A = preAnalysis || analyze(func);
  const problems = [];
  for (const inst of A.safepoints) {
    const st = safepointState(A, inst);
    const reqs = requiredValues(A, inst);
    const requiredSet = new Set(reqs.map((r) => r.v));
    const map = inst.map || {};
    for (const r of reqs) {
      const loc = map[r.v];
      if (!loc) problems.push({ safepoint: inst.id, kind: r.deopt ? 'missing-deopt-value' : 'missing-root', v: r.v });
      else if (!locHolds(st, r.v, loc)) problems.push({ safepoint: inst.id, kind: 'stale-root', v: r.v, loc });
    }
    for (const [v, loc] of Object.entries(map)) {
      if (requiredSet.has(v)) continue;
      if (!isSafeRoot(st, loc, A.types))
        problems.push({ safepoint: inst.id, kind: 'unsafe-root', v, loc });
    }
  }
  return { ok: problems.length === 0, problems, analysis: A };
}

/* Repair: minimum number of inserted spills + map entries */
function firstExistingLoc(A, inst, v) {
  const st = safepointState(A, inst);
  const set = st?.locOf.get(v);
  if (!set || !set.size) return null;
  const key = [...set].sort()[0];
  if (key.startsWith('reg:')) return { k: 'reg', name: key.slice(4) };
  if (key.startsWith('slot:')) return { k: 'slot', index: Number(key.slice(5)) };
  return null;
}
function spillCoverage(A, v, anchor, needIndex) {
  const ap = A.pos.get(anchor);
  const covered = new Set();
  for (const [key, item] of needIndex) {
    if (item.v !== v) continue;
    const sp = A.pos.get(item.inst);
    const dominates = ap.blockId === sp.blockId ? ap.idx < sp.idx
      : A.blockDominates(ap.blockId, sp.blockId);
    if (!dominates) continue;
    let redefined = false;
    for (let q = ap.g + 1; q < sp.g; q++)
      if (instDefs(A.instOrder[q]).includes(v)) { redefined = true; break; }
    if (!redefined) covered.add(key);
  }
  return covered;
}
function minSetCover(universeSize, candidates) {
  const all = new Set();
  for (const c of candidates) for (const k of c.covers) all.add(k);
  if (all.size < universeSize) return null;
  let best = null;
  const target = universeSize;
  const chosen = [];
  const solve = (covered) => {
    if (chosen.length >= (best ? best.length : Infinity)) return;
    if (covered.size === target) {
      if (!best || chosen.length < best.length) best = [...chosen];
      return;
    }
    let pick = null;
    for (const k of all) if (!covered.has(k)) { pick = k; break; }
    const usable = candidates.filter((c) => c.covers.has(pick));
    usable.sort((a, b) => b.covers.size - a.covers.size);
    for (const c of usable) {
      chosen.push(c);
      solve(new Set([...covered, ...c.covers]));
      chosen.pop();
    }
  };
  solve(new Set());
  return best;
}
function planRepairs(func, preAnalysis) {
  const A = preAnalysis || analyze(func);
  const edits = [];
  const needIndex = new Map();
  let needSeq = 0;
  for (const inst of A.safepoints) {
    const st = safepointState(A, inst);
    const reqs = requiredValues(A, inst);
    const requiredSet = new Set(reqs.map((r) => r.v));
    const map = inst.map || (inst.map = {});
    for (const [v, loc] of Object.entries(map)) {
      if (requiredSet.has(v)) continue;
      if (!isSafeRoot(st, loc, A.types))
        edits.push({ action: 'remove', safepoint: inst.id, v, from: loc });
    }
    for (const r of reqs) {
      const loc = map[r.v];
      if (loc && locHolds(st, r.v, loc)) continue;
      const existing = firstExistingLoc(A, inst, r.v);
      if (existing) { edits.push({ action: 'set', safepoint: inst.id, v: r.v, to: existing }); continue; }
      if (st.constOf.has(r.v)) {
        edits.push({ action: 'set', safepoint: inst.id, v: r.v, to: { k: 'const', value: st.constOf.get(r.v) } });
        continue;
      }
      needIndex.set(needSeq++, { inst, v: r.v, deopt: r.deopt });
    }
  }
  const spillPlan = [];
  const slotAlloc = { next: nextSlot(A.func) };
  if (needIndex.size) {
    const candidates = [];
    const byV = new Map();
    for (const [key, item] of needIndex) {
      if (!byV.has(item.v)) byV.set(item.v, []);
      byV.get(item.v).push(key);
    }
    for (const [v] of byV) {
      for (const anchor of A.instOrder) {
        const st = A.after.get(anchor);
        if (!st || !st.locOf.get(v)?.size) continue;
        const covers = spillCoverage(A, v, anchor, needIndex);
        if (covers.size) candidates.push({ v, anchor, covers });
      }
    }
    const chosen = minSetCover(needIndex.size, candidates);
    if (!chosen) {
      for (const [, item] of needIndex) chosenPushFallback(A, item, spillPlan, slotAlloc);
    } else {
      const coveredKeys = new Set();
      for (const c of chosen) {
        const slot = { k: 'slot', index: slotAlloc.next++ };
        spillPlan.push({ v: c.v, anchor: c.anchor, slot });
        for (const k of c.covers) {
          coveredKeys.add(k);
          const item = needIndex.get(k);
          edits.push({ action: 'set', safepoint: item.inst.id, v: item.v, to: slot });
        }
      }
      for (const [k, item] of needIndex)
        if (!coveredKeys.has(k)) chosenPushFallback(A, item, spillPlan, slotAlloc);
    }
  }
  return { edits, spillPlan, analysis: A };
}
function chosenPushFallback(A, item, spillPlan, slotAlloc) {
  const sp = A.pos.get(item.inst);
  let anchor = null;
  for (let q = sp.g - 1; q >= 0; q--) {
    const ins = A.instOrder[q];
    const st = A.after.get(ins);
    if (st && st.locOf.get(item.v)?.size) { anchor = ins; break; }
  }
  if (!anchor) throw new Error(`cannot repair ${item.v} at ${item.inst.id}: no live location`);
  spillPlan.push({ v: item.v, anchor, slot: { k: 'slot', index: slotAlloc.next++ } });
}
function nextSlot(func) {
  let max = -1;
  for (const b of func.blocks)
    for (const i of b.insts) {
      const locs = [];
      if (i.loc) locs.push(i.loc);
      if (i.clobbers) locs.push(...i.clobbers);
      for (const l of locs) if (l && l.k === 'slot') max = Math.max(max, l.index);
    }
  return max + 1;
}
function applyRepairs(func, plan) {
  const out = structuredClone(func);
  const byBlock = new Map(out.blocks.map((b) => [b.id, b]));
  const spById = new Map();
  for (const b of out.blocks)
    for (const i of b.insts)
      if (i.op === 'safepoint' || i.op === 'deopt' || i.op === 'call') spById.set(i.id, i);

  for (const e of plan.edits) {
    const inst = spById.get(e.safepoint);
    if (!inst) continue;
    if (!inst.map) inst.map = {};
    if (e.action === 'remove') {
      if (inst.map[e.v] && locKey(inst.map[e.v]) === locKey(e.from)) delete inst.map[e.v];
    } else if (e.action === 'set') inst.map[e.v] = e.to;
  }
  const insertions = new Map();
  for (const s of plan.spillPlan) {
    const origPos = plan.analysis.pos.get(s.anchor);
    const ins = { op: 'moveto', v: s.v, loc: s.slot, __repair: true };
    if (!insertions.has(origPos.blockId)) insertions.set(origPos.blockId, []);
    insertions.get(origPos.blockId).push({ idx: origPos.idx, ins });
  }
  for (const [blockId, list] of insertions) {
    const b = byBlock.get(blockId);
    list.sort((a, c) => c.idx - a.idx);
    for (const { idx, ins } of list) b.insts.splice(idx + 1, 0, ins);
  }
  return out;
}

/* Moving-GC relocation + resume simulation */
function simulatePath(func, A) {
  const path = [];
  let id = A.entry;
  const guard = new Set();
  while (id && !guard.has(id)) {
    guard.add(id);
    const b = A.blocks.get(id);
    for (const ins of b.insts) path.push(ins);
    if (!b.succs || !b.succs.length) break;
    id = b.succs[0];
  }
  return path;
}
function simulateRelocation(func, assign, preAnalysis) {
  const A = preAnalysis || analyze(func);
  const path = simulatePath(func, A);
  const phys = new Map();
  const val = new Map();
  const failures = [];
  const frameSnapshots = [];
  let round = 0;

  const setPhys = (loc, v) => phys.set(locKey(loc), v);
  const clearVal = (v) => {
    val.delete(v);
    for (const [k, h] of [...phys]) if (h === v) phys.delete(k);
  };

  for (const ins of path) {
    switch (ins.op) {
      case 'def':
        clearVal(ins.dst);
        if (ins.loc.k === 'const') val.set(ins.dst, ins.loc.value);
        else { val.set(ins.dst, assign[ins.dst] !== undefined ? assign[ins.dst] : null); setPhys(ins.loc, ins.dst); }
        break;
      case 'copy': {
        clearVal(ins.dst);
        val.set(ins.dst, val.get(ins.src));
        const srcKey = [...phys.entries()].find(([, h]) => h === ins.src)?.[0];
        if (srcKey) phys.set(srcKey, ins.dst);
        break;
      }
      case 'moveto':
        for (const [k, h] of [...phys]) if (h === ins.v) phys.delete(k);
        setPhys(ins.loc, ins.v);
        break;
      case 'clobber':
        phys.delete(locKey(ins.loc));
        break;
      case 'call':
        for (const c of ins.clobbers || []) phys.delete(locKey(c));
        if (ins.dst && ins.loc) {
          clearVal(ins.dst);
          val.set(ins.dst, assign[ins.dst] !== undefined ? assign[ins.dst] : null);
          setPhys(ins.loc, ins.dst);
        }
        gcRound(ins);
        break;
      case 'safepoint':
      case 'deopt':
        gcRound(ins);
        break;
      default:
        break;
    }
  }

  function gcRound(inst) {
    round++;
    const reqs = requiredValues(A, inst);
    const map = inst.map || {};
    const moved = new Map();
    for (const [v, loc] of Object.entries(map)) {
      if (loc.k === 'const') continue;
      const holder = phys.get(locKey(loc));
      const obj = holder != null ? val.get(holder) : undefined;
      if (isMovable(A.types.get(holder)) && typeof obj === 'string' && !moved.has(obj))
        moved.set(obj, `${obj}@g${round}`);
    }
    for (const [v, x] of val) if (typeof x === 'string' && moved.has(x)) val.set(v, moved.get(x));

    for (const r of reqs) {
      const loc = map[r.v];
      if (!loc) { failures.push({ safepoint: inst.id, v: r.v, kind: 'missing', round }); continue; }
      let got;
      if (loc.k === 'const') got = loc.value;
      else { const holder = phys.get(locKey(loc)); got = holder != null ? val.get(holder) : undefined; }
      if (got !== val.get(r.v))
        failures.push({ safepoint: inst.id, v: r.v, kind: 'mismatch', got, exp: val.get(r.v), round });
    }
    const frameState = [];
    for (const f of inst.frames || []) {
      if (!f.deopt) continue;
      const vals = {};
      for (const [label, v] of Object.entries(f.values)) {
        const loc = map[v];
        let got;
        if (!loc) got = undefined;
        else if (loc.k === 'const') got = loc.value;
        else { const holder = phys.get(locKey(loc)); got = holder != null ? val.get(holder) : undefined; }
        vals[label] = got;
      }
      frameState.push({ id: f.id, pc: f.pc, values: vals });
    }
    if (frameState.length) frameSnapshots.push({ safepoint: inst.id, frames: frameState });
  }
  return { failures, frameSnapshots };
}

function checkAndRepair(func) {
  const before = validate(func);
  let repaired = func;
  let plan = null;
  if (!before.ok) {
    plan = planRepairs(func, before.analysis);
    repaired = applyRepairs(func, plan);
  }
  const after = validate(repaired);
  return { before, plan, repaired, after };
}

module.exports = {
  MOVABLE, GARBAGE, isMovable, locKey,
  analyze, validate, planRepairs, applyRepairs,
  requiredValues, locHolds, isSafeRoot,
  simulateRelocation, checkAndRepair,
  _internal: { mergeStates, transfer, emptyState, stateSig, minSetCover, nextSlot },
};

The complete stackmap.test.js (16 tests) and demo.js are on disk at ~/wasm-stackmap/; SOLUTION.md contains the full listings.

4. Verification

cd ~/wasm-stackmap
node --test        # 16 tests
node demo.js       # end-to-end diagnosis + repair + relocation/resume

# tests 16
# pass 16
# fail 0

Test	Property proved
sound map accepted	no false positives
safe over-approximation	dead-but-valid ref entry not rejected
missing live root	detected, repaired, object relocated correctly
`i31ref` not a root	no entry required
`i31ref` as root	rejected unsafe
garbage over-approximation	unsafe entry removed
clobbered register	exactly one spill; resume correct
two safepoints / one spill	minimum repair (set cover merges)
two independent clobbers	exactly two spills
shared vs singleton candidates	`minSetCover` picks the covering set
inline frames	outer-frame root preserved
deopt metadata	non-ref local reconstructed bit-identically
diamond CFG	must-analysis keeps common location
call clobber	caller-saved root stale; callee-saved accepted

node demo.js on a function wrong in all three ways at once:

=== validate(before) ===
ok: false
 - {"safepoint":"<email>","kind":"stale-root","v":"v0","loc":{"k":"reg","name":"rax"}}
 - {"safepoint":"<email>","kind":"missing-deopt-value","v":"v1"}

=== repair plan ===
 edit: {"action":"set","safepoint":"<email>","v":"v0","to":{"k":"slot","index":0}}
 edit: {"action":"set","safepoint":"<email>","v":"v1","to":{"k":"slot","index":1}}
inserted moveto count: 2

=== validate(after) ===
ok: true []

=== relocate + resume ===
failures: 0
resumed frames: {
  "safepoint": "<email>",
  "frames": [
    { "id": "inner", "pc": 12, "values": { "a": "<email>" } },
    { "id": "outer", "pc":  4, "values": { "b": "<email>" } }
  ]
}
DEMO PASSED

The dead v2 in rcx (a valid reference) is silently accepted as a safe conservative root, while the clobber-stale v0 and unmapped outer-frame v1 are repaired with the minimum two spills and then survive a real relocation round with deopt frames reconstructed identically.

5. Limits (explicit)

Spill placement uses dominators and assumes an acyclic region around the safepoint; loops are handled by the analyses (they are proper fixpoints), but a spill needed across a back-edge needs the standard preheader insertion.
This encodes the precise-moving semantics of over-approximation: an extra physical entry is accepted only if its location definitely holds a movable value or null. For framed/conservative scanning of a whole slot range, widen isSafeRoot for those slots only — never for values.
Non-null reference constants are accepted for resume metadata only, not as physical GC roots.

Evidence & signatures

# Evidence
- Problem class: js-20261008-wasm-gc-moving-heap-stackmap-deopt
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-10-08T23:15:43.858Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Build a validator and repair pass for WebAssembly stack maps emitted across moving-GC safepoints, including inlined frames, register spills, and deoptimization metadata. Given control-flow graphs and imperfect maps, identify unsound roots without rejecting safe conservative maps, then minimize repairs while preserving observable behavior across relocation and resume.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-20261008-wasm-gc-moving-heap-stackmap-deopt", "provider": "openrouter", "solved_at": "2026-10-08T23:15:43.858Z", "version": "20"}

Generated from the verified corpus · MIT licensedBack to the catalog