Skip to content

perf(optimize): fold constant control flow, simplify the CFG, and optimize module code - #341

Merged
siyul-park merged 2 commits into
mainfrom
perf/optimize-passes
Nov 15, 2026
Merged

siyul-park merged 2 commits into
mainfrom
perf/optimize-passes

Conversation

@siyul-park

Copy link
Copy Markdown
Owner

Summary

The bytecode optimizer left most of its opportunities unused: top-level code with a loop was never rewritten, constant branches and constant block params were never folded, and the benchmark harness never ran the optimizer at all.

SSA passes (shared by optimize and the JIT tiers)

  • Fold: a branch/table on a constant, or a branch with identical edges, becomes a jump (interpreter i32-lane rule); integer identities, absorbing constants (x*0, x&0, x|-1) and same-operand forms (x-x, x==x) fold on either side; a block param every surviving edge feeds the same constant is that constant. Bitwise results keep their operands' kind tag. Irreducible graphs retry without collapsing terminators.
  • SimplifyPass (new): removes trivial block params (fixed point) and merges a block into its only predecessor's jump.
  • CSE: commutative integer ops keyed on sorted operands.
  • Forward: a stored non-ref, non-i64 value becomes the held value of its slot.
  • LICM: shape guards and unstored local loads hoist out of loops that allocate/release but contain no call.
  • Pipelines: O1 Fold, Simplify, DCE; O2 adds CSE, Guard; O3 runs Simplify and Fold again after Promote.

Bytecode emitter

  • Module code may home values in locals, so top-level loops are now rewritten.
  • Leading operands load ahead of an expression tree that produces a later operand instead of homing its result.
  • Exit blocks go last; a loop header's invertible branch falls through into the body.

Contracts (documented + enforced)

  • Module locals are not program semantics (docs/pass-system.md).
  • Object representation is immutable: Interpreter.Store rejects a representation change with ErrTypeMismatch (scalar cells excepted) (docs/memory-model.md).
  • Host code, including finalizers, must not write caller locals or globals: SetLocal/SetGlobal return ErrHostCall; a caught host panic resets the count (docs/host-integration.md).

Benchmarks

  • New optimized mode (O3 bytecode, threaded) and an Optimized column in the report.
  • New naive-checksum fixture modelling unoptimized frontend output (existing fixtures are already hand-optimized, so they hid optimizer gains).

Measurements (local interleaved A/B vs main, Apple M-series, n=6–8)

Kernel Δ
branch-tree/optimized −64.8% … −99%
naive-checksum/optimized −45.4%
branch-tree/jit −22% … −26%
iterative-fib/optimized −6.6%
string-compare/jit −4.3% … −5.4%
map-ops/jit −3.6%
naive-checksum/jit −3.4%
sort-stress/optimized +1.9% … +4.0%
n-queens/jit ~0 … +2.7% (noisy)
geomean −6.1% … −6.4%

CI regenerates docs/benchmarks.md; no locally measured table is committed.

Known follow-ups

  • sort-stress/optimized: LICM copies an array into a new local at top level.
  • A finalizer that calls a guest function can still write globals (pre-existing).
  • REF_SET scalar() check cost unmeasured in isolation.
  • Fact propagation across calls (ProvePass) was designed and reviewed; measurement showed no worthwhile target, so it is not in this PR.

Test plan

  • make check (lint, generate check, all package tests incl. JIT)
  • git diff --check
  • No JIT golden changes
  • New subtests: Fold (collapse, absorb, reflexive, agreed params, tags), Simplify, CSE commutative, Forward store, LICM conditions, pipelines, emitter, interp contracts (Store, SetLocal/SetGlobal ErrHostCall, finalizer, panic restore)
  • CI green

🤖 Generated with Claude Code

…imize module code

The bytecode optimizer left most of its opportunities on the table: top-level
code with a loop was never rewritten, constant branches and constant block
params were never folded, and the benchmark harness never ran the optimizer.

SSA passes (shared by `optimize` and the JIT tiers):
- Fold turns a branch or table on a constant, or a branch with identical
  edges, into a jump; reduces integer identities, absorbing constants and
  same-operand forms; and treats a block param every surviving edge feeds the
  same constant as that constant. Bitwise results keep their operands' kind.
- SimplifyPass replaces trivial block params and merges a block into its only
  predecessor's jump.
- CSE keys commutative integer ops on sorted operands.
- Forward makes a stored non-ref, non-i64 value the held value of its slot.
- LICM hoists shape guards and unstored local loads out of loops that release
  or allocate but contain no call.
- O1/O2/O3 run Simplify; O3 folds again after promotion.

Bytecode emitter:
- Module code may home values in locals, so top-level loops are rewritten.
- Leading operands are loaded ahead of the expression tree that produces a
  later operand, instead of homing its result.
- Exit blocks go last; a loop header's invertible branch falls through into
  the body.

Contracts:
- Module locals are not program semantics.
- Object representation is immutable: Interpreter.Store rejects a
  representation change with ErrTypeMismatch (scalar cells excepted).
- Host code, including finalizers, must not write caller locals or globals:
  SetLocal/SetGlobal return ErrHostCall; a caught host panic resets the count.

Benchmarks: a new `optimized` mode (O3 bytecode, threaded) and the
`naive-checksum` fixture modelling unoptimized frontend output.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
@coderabbitai

coderabbitai Bot commented Nov 15, 2026 •

Copy link
Copy Markdown

Explain Change →

Important

  • Trigger review

This repository does not receive automatic reviews because it has fewer than 10 stars.

Run configuration

  • Source mode: Auto
  • Repository: Unavailable
  • Branch: Unavailable
  • File: No configuration file from this repository applied
  • Commit: Unavailable
  • Layers: defaults
  • Review profile: CHILL
  • Plan: Advanced
  • Run ID: 58d36b28-15f7-445e-8587-5e408d583cd3
Finishing Touches

Generate unit tests (beta)

  • Commit to this branch
  • Create a new PR
  • Autofix · Keep fixing CodeRabbit findings and required CI, and resolving merge conflicts

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

Share

@siyul-park
siyul-park merged commit 01a719c into main Nov 15, 2026
2 checks passed
@siyul-park
siyul-park deleted the perf/optimize-passes branch November 15, 2026 02:34
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant