ReviewOS

zig-utils/zig-js

Optimizer: verify SSA effects and recovery maps after graph passes

#1088
Closed chris opened this 9 days ago ·
9 days ago

Parent: #469; related: #491, #466.

Implement the optimizer roadmap's explicit IR-verification requirement. Current Plan/ValueGraph already carries block arguments, edges, frame and edge recovery maps, active handler stacks, and exceptional targets. The existing graph compaction and selected-loop compaction phases need a common verifier before additional global optimization passes can rely on those contracts.

Scope:

  • Verify block/instruction/value identity and bounded slices before dereferencing malformed metadata.
  • Verify SSA definition order and CFG dominance, including exception edges, block arguments, entry seeds, and selected-loop entry/exit boundaries.
  • Verify effect flags/order and pre-operation recovery states; unknown values are not pure, and a future effect result cannot appear in its own pre-effect map.
  • Verify recovery value availability, edge arity, handler and exceptional-target shape, and preserve roots needed by maps.
  • Run the verifier after existing graph phases in test builds; retain a callable verifier for deterministic mutation tests. Keep production validation/compilation costs unchanged until separately measured and accepted.
  • Use iterative traversal and linear scratch storage; preserve allocation-failure cleanup and deterministic output.

Definition of done:

  • Valid loops, diamonds, calls/coercions, catch/finally, and selected-loop plans pass verification.
  • Corrupt ids/slices, non-dominating/forward values, missing effects/maps, inconsistent edge/handler state, and unsafe recovery values fail with stable verifier errors.
  • Existing planning and loop-compaction test paths invoke verification; OOM sweeps leak nothing.
  • Focused Debug, ReleaseSafe, unsuppressed TSan, broader native semantic/GC tests, and scoped before/after corpus comparisons pass.

This is a verifier prerequisite, not a claim that #469's optimization passes or performance acceptance are complete.

9 days ago

Implemented in bbeab18f, rebased onto exact parent e9400ed6.

Plan.verify checks CFG/value identities and ranges, SSA definition order and immediate-dominator availability, effect flags/order, block arguments and edges, recovery value availability, fixed local layout, handler stacks, and exceptional boundaries. It preserves the representation's intentional distinctions: pooled primitive seeds are globally available; tail-call results are post-operation while their maps remain pre-operation; exceptions and zero-output exits can resume interpreter-owned bytecode outside represented SSA blocks.

Test builds invoke verification after value-graph compaction and selected-loop compaction. Invalid generated IR panics rather than silently selecting a lower tier; allocator failures propagate through existing cleanup. Production call sites are compile-time excluded. This is the SSA recovery verifier; emitted native stack maps retain their separate backend construction/execution coverage.

Qualification:

  • Eight verifier cases reject corrupt ids/operands/slices, forward/non-dominating uses, absent effects/maps/exception targets, inconsistent edges/branches/handlers, impossible exceptional edges, and future values in pre-effect maps. Positive cross-block/eval cases and an allocation-failure sweep pass.
  • The complete focused optimizer suite passes 181/181 in Debug, ReleaseSafe, and unsuppressed TSan, refreshed after rebasing. Existing loops, diamonds, catch/finally, moving-GC, native effects/recovery, and selected-loop cases exercise the new phase hooks.
  • Iterative CFG chains at 1,024 / 2,048 / 4,096 blocks request 105,554 / 211,026 / 421,970 scratch bytes. Buffers derive from graph bounds; tests pin allocation growth and cleanup. These are structural diagnostics, not a throughput publication.
  • Combined-revision broader JIT gate: 139 passed / one platform skip / zero failures or leaks. VM/concurrency smokes: four each. Seeded default/verify threadfuzz: 400/300 programs, zero failures.
  • Exact e9400ed6 parent/current diagnostics and tree/VM reports match across five measured subtrees, 980 cases: zero default-tier failures, the same 11 existing tree/VM differences. Flips 0 test262 cases.
  • GC relocation and 378-file link audits pass; regenerated and checked 51-page docs manifest passes. The July 22 retired-array-kernel paragraph is now explicitly historical; its evidence is unchanged.

#933's existing memory cap still blocks the full local combined-unit link. Hosted integration is queued. #469's optimization passes and performance acceptance remain open.

Sign in to comment on this issue.