brintos

brintos / hwjs-cc public Read only

0
0

coroutinize: e8-registry escape-walk blowup on clang (visitExpr) — the #16 memo is disabled during e8Building #1

Closed sasha opened this issue · 1 comment
S sasha commented

Component: hwjs-cc / HwjsCoroutinize pass — e8-registry phase (populateE8Registry in CoroutinizePass.cpp). Found: 2026-07-09, cross-building the clang-22 fork (7ca43933) as a WASM-HWJS target for the self-hosted build image (BRINTOS-22). Plugin pin 893bf82 (ds_region_abi=2).

Symptom

The final clang-22 LTO link merges clang/LLVM into one ~252 MB module and runs the coroutinize pass over it. The pass never completes — it pins one core at 100% with no output. Under a bounded budget it is a clean never-silent refuse, attributed to a single function:

# HWJS_CORO_BUDGET_SECONDS=300
BUDGET REFUSE phase=e8-registry fn=clang::interp::Compiler<ByteCodeEmitter>::visitExpr
  exceeded=wall-clock elapsed_ms=300004 work_units=153878528
# HWJS_CORO_BUDGET_SECONDS=3600
BUDGET REFUSE phase=e8-registry fn=clang::interp::Compiler<ByteCodeEmitter>::visitExpr
  exceeded=wall-clock work_units=2130362368

Work-units grow linearly with the budget (590 k/s) and do not converge (2.13 B at 1 h, still climbing). For scale, the most expensive function that does complete is clang::FieldDecl::printName at 6.79 M — visitExpr is >300× that and unbounded.

Root cause

populateE8Registry runs a ≤64-round fixpoint that, per round, calls e8PerTargetNocapture(F) for every address-taken target — an interprocedural escape walk (classifyEscape). Issue #16 fixed exactly this walk's exponential blowup by memoizing it (callee-fate memo, d51b4e6), which this plugin includes. But that memo is gated … && !e8Building(), and the whole e8 fixpoint runs with e8Building() == true — so inside this phase the walk runs unmemoized, and clang's deeply-recursive constexpr-bytecode-interpreter functions reproduce the #16 exponential path-enumeration the memo no longer guards here. The code documents the dependency itself (CoroutinizePass.cpp:581): depth-10 is "Affordable AFTER the #16 memo (depth is IN the calleeFateMemo key → DP, not path enumeration)." With the memo off, it is path enumeration again.

Not #16, not #25: this plugin post-dates #16's fix (d51b4e6 is an ancestor of 893bf82) and #25's escape-lifts (db11f81). Clang is simply the first module large/recursive enough to exercise the unmemoized e8 fixpoint. No ops knob works around it — the e8 walk uses the hardcoded kEscapeScanDepth=10 (comment :575 "E8-mask queries stay at kEscapeScanDepth"), so HWJS_CORO_NO_DEEPWEB_DEPTH / HWJS_DBG_DEPTH don't touch it (a full 1 h run under HWJS_CORO_NO_DEEPWEB_DEPTH=1 refused identically); and populateE8Registry is on the mandatory lowering path.

Proposed fix

Two independent, opt-in changes; both validated by a full clang link (see below). Off by default so stock behavior is unchanged.

  1. HWJS_E8_ROUND_MEMO — enable the callee-fate memo within an e8 fixpoint round, clearing it at each round boundary. The memo was excluded across the fixpoint because per-round estimates change (e8Mask() only descends, at the per-round MEET) — but within one round the estimates are constant, so a round-scoped memo is sound and restores the #16 DP. This is the real fix; you may prefer to make it unconditional rather than knob-gated.

  2. HWJS_E8_TARGET_WORK_CAP=<N> — a per-target ceiling on escape-walk steps; a target exceeding it bails to a conservative Opaque (over-approximates escape, never a miscompile). Empirically the memo alone gives a clean ~18× on every function it covers (getNameForDiagnostic 19.2 s→1.0 s, printName 22 s→1.2 s) but does not bound visitExpr — its blowup is in the use-graph worklist, not callee re-descent — so the cap is the backstop that bounds that one pathological target. The only cost of the conservative bail is efficiency, not correctness: the capped target's wasm-signature class gets pessimistic nocapture bits, so its pointer args at indirect-call sites are covered by the coroutine frame descriptor even when they need not be — slightly larger frames + marginally more save/restore/relocate at suspend points. Negligible here (visitExpr is compile-time code that rarely suspends), and the validity census below confirms no correctness impact.

Validation: with both enabled (HWJS_E8_ROUND_MEMO=1 HWJS_E8_TARGET_WORK_CAP=20000000) the pass runs the whole clang module to completion:

SUMMARY coroutinized=104299 refused=0 skipped=0 defined=142009 coroutinized_fraction=73.45%
OUTPUT-VALIDITY-CENSUS transformed=104299 invalid_functions=0 module_broken=0
BUDGET-OK (not REFUSE)

Fix branch (brintos/hwjs-cc, on top of current main)

Branch: fix/e8-round-memo Commit: d7ad555

29 insertions / 2 deletions in pass/coroutinize/CoroutinizePass.cpp: relax the two !e8Building() memo gates to (!e8Building() || e8RoundMemoEnabled()); clear calleeFateMemo()/recFateBank() at the top of each populateE8Registry fixpoint round; add the per-target-step cap in the classifyEscape worklist (conservative Opaque on exceed); reset the per-target counter in e8PerTargetNocapture; plus two small env-reading helpers. Both knobs default OFF, so stock behavior is unchanged.

Repro

Cross-build the clang-22 fork (7ca43933) for wasm32-hwjs against a ported libc++ and LTO-link bin/clang-22; set HWJS_CORO_BUDGET_SECONDS=300 for the fast attributed refuse. (Any module whose address-taken set includes a large, deeply-recursive C++ function should reproduce it; happy to reduce a standalone fixture if useful.)

Impact

Blocks the on-target clang toolchain (BRINTOS-22). Everything upstream (all 2245 TUs, libc++) is built and cached, so the fix unblocks an immediate relink.

Proposed fix

Proposed fix targets brintos/hwjs-cc only — no distro submodule pins moved. All distros share one lineage, so pin bumps are coordinated on merge, not per-engineer.

jdbrinton jdbrinton commented

Fixed at F1624278a49 on joel-dev (pass advanced from F161 06665f7; superproject gitlink 7090416). The e8-registry escape walk is now provably bounded (round-scoped #16 DP), all distros are rebuilt green on the new plugin and deployed, and the gate battery carries a genuinely flipping RED arm reproducing this ticket's exact signature.

Root cause — two coupled gates, not one

Your analysis found the first: both #16 memos (calleeFateMemo + recFateBank) are gated !e8Building(), and the whole ≤64-round fixpoint runs with e8Building()==true. The exclusion existed for a real reason: the per-sig estimates descend across rounds (the MEET only clears bits), so an entry carried across a round boundary can stay stale-optimistic — a blessing the shrunken mask no longer grants — silently over-blessing indirect-call args. I built a fixture proving exactly that corruption (a capturing target's sig-class stays blessed at meet=0x1 if the memo survives a round boundary).

But there is a second gate the proposed branch missed: e8PerTargetNocapture passes a dead &ou opaqueUse out-param (never read) into classifyEscape, and both memo gates also require opaqueUse == nullptr (the deep-leaf-attribution exclusion). opaqueUse is threaded down the entire walk, so the memo was disabled on the whole e8 path independently of e8Building().

Consequently the fix/e8-round-memo branch (d7ad555) is vacuous as a memo fix: HWJS_E8_ROUND_MEMO=1 never engages either memo (the opaqueUse == nullptr conjunct is false throughout). Reproduced empirically on a d7ad555-equivalent probe: with the knob on, the SCC-web fixture blows up identically (23.54M vs 23.48M work units at 60s, same fn= attribution). The clang-link completion you measured was therefore carried entirely by HWJS_E8_TARGET_WORK_CAP — the result-changing conservative bail. This also means "the memo alone does not bound visitExpr" was measured with the memo never actually on; the real memo (below) does bound it.

And a third contributor once the memo IS on: the blanket recFate == nullptr store-exclusion meant every iteration of a Q1 recursion solve re-walked every node's non-recursive helper sub-DAG from scratch — on the interp visit* SCC that is the per-solve blowup the round-scoped bank alone cannot bound.

The fix (F162, default ON — no knob needed)

  1. Round-scoped memo during e8Building — your insight, made real: both gates relax to (!e8Building() || e8RoundMemoOn()); populateE8Registry clears both memos at every round boundary (estimates are constant within a round — e8Mask() merges only after all targets), at the build→post-build transition (open-world consult semantics differ across it), and at exit (nothing survives into the morphs). The dead &ou is dropped (opaqueUse is a telemetry-only output channel — result-identical).
  2. Clean-descent participation inside a Q1 solve (recFateTouchEpoch): a completed descent whose sub-walk provably never read/seeded in-flight recursion state executed exactly as its plain twin and is banked/consumed like one. This is what bounds each solve iteration. Descents that touched the solve stay excluded — that exclusion is soundness-critical (an entry embedding a pre-convergence optimistic estimate would be genuinely unsound).
  3. Bail-free Opaque banking (depthBailEpoch): the depth==0/cycle fail-safes are context-DEPENDENT (the same query bails under a shallow stack, completes under a deep one). A bail aborts the whole walk as Opaque, so only Opaque results can carry bail taint — those are never banked. Every banked entry is therefore a context-free completed classification.

HWJS_E8_TARGET_WORK_CAP is rejected: it changes emitted results (pessimistic masks → different frames) and its necessity evidence was tainted by the vacuous memo. With the real DP the walk is bounded without it; if the clang relink still exceeds the budget, the never-silent BUDGET REFUSE names the target and we take real evidence (HWJS_CORO_BUDGET_SECONDS remains the ops knob).

Result-equivalence (the part that had to be adversarially exact)

Gate e8_round_memo.mjs (in run-coro.sh), every run:

  • EQUIV: on modules whose walk never trips the depth/cycle fail-safe, memo on/off emit byte-identical IR and identical [e8]/[e8field] registries (proved against both HWJS_E8_NO_ROUND_MEMO and HWJS_CORO_NO_CALLEE_FATE_MEMO).
  • DIVERGENCE (one-directional, pinned): on depth-pressure SCC shapes the legacy answer is a context-dependent budget artifact — the same target classifies differently by stack shape. The memoized walk replaces exactly those bail-artifact Opaques with completed, budget-honoring proofs: masks only gain bits (fixture: ground truth 0x3 recovered vs legacy artifact 0x0; superset asserted; IR still byte-identical there). Never more conservative, never a wrong binary.
  • STALENESS: the cross-round MEET is honored exactly (dep2 correctly descends to meet=0x0 in round 2). Scratch-verified the arm flips: removing the round clears converges to the corrupted 0x1.
  • Real-corpus check: on a real whole-program glibc link (the #2 gqsort fixture, full glibc pool) memo on/off produce identical decision sets (coroutinized=381 refused=0, same per-fn sets) and identical [e8]/[e8field] registries. (Artifact byte-diff is void on that path: two identical-env links already differ in ~142 data-address bytes — a pre-existing benign link nondeterminism, noted for a separate ticket.)

RED → GREEN complexity evidence

  • RED (committed, deterministic, flipping): HWJS_E8_NO_ROUND_MEMO=1 on the clang-shaped fixture (24-member address-taken SCC + helper DAG) → BUDGET REFUSE phase=e8-registry fn=v_0 exceeded=work-units at a 2M work budget. Pre-fix behavior measured: 23.5M units at 60s, still on target 5/24 of round 1, work-units unconverged — this ticket's exact signature.
  • GREEN: the same module completes in 0.24s / 0.11M units (>200× less work than the legacy walk had already spent while still climbing).
  • Scale headline: a 512-member single-SCC module (1152 functions, 3.7MB IR) completes the whole pass in 10.6s / 14.6M units / 65MB RSS; escape-walk units scale linearly in SCC size (16.9k/33.8k/67.6k/135k at K=64/128/256/512).
  • Honesty on clang scale: I did not run the full 252MB clang LTO link here (tens of hours of upstream build). The synthetic module exceeds clang's visit* web on the pathological dimension (SCC size and recursive density); the 142k-function total mostly adds linear classify-phase work. Your cached TUs + libc++ should relink directly on the F162 plugin — with no knobs at all. If it still budget-refuses, post the attributed line and I'll take it from there.

Lineage / verification

  • Pass battery: 179 pass / 7 skip (deps absent) / 0 fail (was 178; +1 = the new gate).
  • Plugin re-derived from the committed submodule: PLUGIN-PROVENANCE commit=4278a49 dirty=0, provenance gate 6/6.
  • Kernel force-recompiled (per #84): all 884 TUs attest the new plugin; green.
  • All distros rebuilt green, 0 new REFUSEs; substrate gates re-run green on the final artifacts: #73 malloc-fatal + F158 dtor leg, hwjscc2 gqsort (F159), hwjscc3 gstrerror (F160), hwjscc4 static-glibc (F161), hwjs2-r6, dlopen-70 launch churn.
  • Deployed live: linux-6.12-musl-busybox, linux-6.12-musl-bash-coreutils, linux-6.12-glibc-bash-coreutils (vmlinux byte-identical verified, journals drained). wabuntu-24.04 is W0 scaffolding — nothing deployable by design.
  • SHAs: hwjs-cc 4278a49 (F162), superproject 7090416 (both pushed on joel-dev).

Closing as completed: the escape walk is provably scalable-and-correct on the final artifact, with the equivalence contract pinned by committed, flipping gates.

jdbrinton closed this as completed