mirror of
https://github.com/hanzoai/wasm2go.git
synced 2026-10-30 15:06:48 +00:00
6e9edc766f
Arity-0 br_table — the shape a bytecode interpreter's computed goto
compiles to — used to lower to a chain of equality-If blocks, on the
assumption (recorded in the old handleBrTable comment) that the Go
compiler would fold the cascade back into a jump table. It does not:
gc lowers dense integer switch STATEMENTS to jump tables but never
reconstructs a switch from an if-else chain. The cost was measured
on go-python: CPython's eval loop (p0.Fn3247) dispatches every
bytecode through a 255-deep chain (~127 sequential compare+branch
per bytecode executed), and the pure-mode CPU profile puts 79% (fib)
/ 50% (loop-sum) of TOTAL flat time inside that one function.
This commit makes br_table a first-class SSA terminator instead:
- ssa: new BlockBrTable kind — one successor per UNIQUE target
(cases routing to one label dedupe into a single edge, keeping
phi bookkeeping one-arg-per-pred), selector as Control,
Block.TableCases/TableDefault mapping selector values to
successors. Verify checks case-value uniqueness, succ dedup,
i32 selector; print support. Existing passes needed no changes:
DCE already marks Control generically, BranchFold guards on
BlockIf, domtree/compact are kind-agnostic.
- lower: handleBrTable emits BlockBrTable when the branch arity is
0; payload-carrying tables (arity > 0, rare and never the hot
dispatch shape) keep the If-chain lowering.
- codegen (pure): the goto emitter renders BlockBrTable as ONE Go
switch statement — case clauses carry the per-edge phi assigns
and a goto, mirroring If arms; the default clause absorbs case
values that share the default's target. gc turns the dense
switch into a jump table: O(1) dispatch. The structured emitter
bails to the goto emitter on BlockBrTable (its default arm).
- asmgen (amd64 + arm64): a binary-search compare tree over the
sorted case values — O(log n) ≈ 8 compares for a 256-way table
instead of ~127. Selector staged once (AX / R0); signed compares
are correct because case values are non-negative table indices,
so a "negative" selector (u32 ≥ 2^31) walks off the tree into
the default, exactly wasm's out-of-range rule. Successors with
phis route through PHI_<blk>_<si> intermediates like If arms.
New tests:
- lower: TestLowerBrTableBlockKind — dedup (2 succs for a 3-case
table sharing targets), TableCases values, default index, verify.
- codegen: TestBrTableEmitsSwitch (switch/case/default pin);
TestBrTable64RuntimePure — NEW 64-way fixture
(testdata/cg_brtable64.wat) diffed against wazero for every
selector 0..70 plus the payload `pick` fallback.
- asmgen: TestBrTableBinarySearchTreeAMD64 / ...ARM64Shape (log-
shaped tree pins: JE/BEQ per case, ~n/4 splits, BT_ labels);
TestBrTable64Runtime — executes the emitted amd64 tree across
split paths, both extremes, out-of-range, and the payload
fallback.
Existing runtime coverage that now exercises the new path: the
control fixture's switch3 driver cases (asm, executed) and
cg_dispatchif (pure, wazero-diffed) — both green.
Verification so far (all exit 0, judged by exit code): go test ./...
on host amd64 AND GOARCH=arm64; make lint. Consumer bundles,
correctness matrix, and benchmarks follow in the PR description.
Co-authored-by: Claude Fable 5 <[email protected]>
284 lines
21 KiB
WebAssembly Text Format
284 lines
21 KiB
WebAssembly Text Format
(module
|
|
;; 64-way arity-0 br_table dispatcher — the computed-goto shape a
|
|
;; bytecode interpreter compiles to. Case k returns k*10+7 (odd
|
|
;; constants so a mis-routed binary-search tree path is caught by
|
|
;; value, not just by reachability); out-of-range returns -1.
|
|
(func (export "switch64") (param i32) (result i32)
|
|
(block $d
|
|
(block $b63
|
|
(block $b62
|
|
(block $b61
|
|
(block $b60
|
|
(block $b59
|
|
(block $b58
|
|
(block $b57
|
|
(block $b56
|
|
(block $b55
|
|
(block $b54
|
|
(block $b53
|
|
(block $b52
|
|
(block $b51
|
|
(block $b50
|
|
(block $b49
|
|
(block $b48
|
|
(block $b47
|
|
(block $b46
|
|
(block $b45
|
|
(block $b44
|
|
(block $b43
|
|
(block $b42
|
|
(block $b41
|
|
(block $b40
|
|
(block $b39
|
|
(block $b38
|
|
(block $b37
|
|
(block $b36
|
|
(block $b35
|
|
(block $b34
|
|
(block $b33
|
|
(block $b32
|
|
(block $b31
|
|
(block $b30
|
|
(block $b29
|
|
(block $b28
|
|
(block $b27
|
|
(block $b26
|
|
(block $b25
|
|
(block $b24
|
|
(block $b23
|
|
(block $b22
|
|
(block $b21
|
|
(block $b20
|
|
(block $b19
|
|
(block $b18
|
|
(block $b17
|
|
(block $b16
|
|
(block $b15
|
|
(block $b14
|
|
(block $b13
|
|
(block $b12
|
|
(block $b11
|
|
(block $b10
|
|
(block $b9
|
|
(block $b8
|
|
(block $b7
|
|
(block $b6
|
|
(block $b5
|
|
(block $b4
|
|
(block $b3
|
|
(block $b2
|
|
(block $b1
|
|
(block $b0
|
|
local.get 0
|
|
br_table 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
|
)
|
|
i32.const 7
|
|
return
|
|
)
|
|
i32.const 17
|
|
return
|
|
)
|
|
i32.const 27
|
|
return
|
|
)
|
|
i32.const 37
|
|
return
|
|
)
|
|
i32.const 47
|
|
return
|
|
)
|
|
i32.const 57
|
|
return
|
|
)
|
|
i32.const 67
|
|
return
|
|
)
|
|
i32.const 77
|
|
return
|
|
)
|
|
i32.const 87
|
|
return
|
|
)
|
|
i32.const 97
|
|
return
|
|
)
|
|
i32.const 107
|
|
return
|
|
)
|
|
i32.const 117
|
|
return
|
|
)
|
|
i32.const 127
|
|
return
|
|
)
|
|
i32.const 137
|
|
return
|
|
)
|
|
i32.const 147
|
|
return
|
|
)
|
|
i32.const 157
|
|
return
|
|
)
|
|
i32.const 167
|
|
return
|
|
)
|
|
i32.const 177
|
|
return
|
|
)
|
|
i32.const 187
|
|
return
|
|
)
|
|
i32.const 197
|
|
return
|
|
)
|
|
i32.const 207
|
|
return
|
|
)
|
|
i32.const 217
|
|
return
|
|
)
|
|
i32.const 227
|
|
return
|
|
)
|
|
i32.const 237
|
|
return
|
|
)
|
|
i32.const 247
|
|
return
|
|
)
|
|
i32.const 257
|
|
return
|
|
)
|
|
i32.const 267
|
|
return
|
|
)
|
|
i32.const 277
|
|
return
|
|
)
|
|
i32.const 287
|
|
return
|
|
)
|
|
i32.const 297
|
|
return
|
|
)
|
|
i32.const 307
|
|
return
|
|
)
|
|
i32.const 317
|
|
return
|
|
)
|
|
i32.const 327
|
|
return
|
|
)
|
|
i32.const 337
|
|
return
|
|
)
|
|
i32.const 347
|
|
return
|
|
)
|
|
i32.const 357
|
|
return
|
|
)
|
|
i32.const 367
|
|
return
|
|
)
|
|
i32.const 377
|
|
return
|
|
)
|
|
i32.const 387
|
|
return
|
|
)
|
|
i32.const 397
|
|
return
|
|
)
|
|
i32.const 407
|
|
return
|
|
)
|
|
i32.const 417
|
|
return
|
|
)
|
|
i32.const 427
|
|
return
|
|
)
|
|
i32.const 437
|
|
return
|
|
)
|
|
i32.const 447
|
|
return
|
|
)
|
|
i32.const 457
|
|
return
|
|
)
|
|
i32.const 467
|
|
return
|
|
)
|
|
i32.const 477
|
|
return
|
|
)
|
|
i32.const 487
|
|
return
|
|
)
|
|
i32.const 497
|
|
return
|
|
)
|
|
i32.const 507
|
|
return
|
|
)
|
|
i32.const 517
|
|
return
|
|
)
|
|
i32.const 527
|
|
return
|
|
)
|
|
i32.const 537
|
|
return
|
|
)
|
|
i32.const 547
|
|
return
|
|
)
|
|
i32.const 557
|
|
return
|
|
)
|
|
i32.const 567
|
|
return
|
|
)
|
|
i32.const 577
|
|
return
|
|
)
|
|
i32.const 587
|
|
return
|
|
)
|
|
i32.const 597
|
|
return
|
|
)
|
|
i32.const 607
|
|
return
|
|
)
|
|
i32.const 617
|
|
return
|
|
)
|
|
i32.const 627
|
|
return
|
|
)
|
|
i32.const 637
|
|
return
|
|
)
|
|
i32.const -1
|
|
)
|
|
|
|
;; Payload-carrying br_table (branch arity 1) — pins the If-chain
|
|
;; fallback lowering that arity>0 tables keep using.
|
|
(func (export "pick") (param i32) (result i32)
|
|
(block $b (result i32)
|
|
(block $a (result i32)
|
|
i32.const 111
|
|
local.get 0
|
|
br_table 0 1 0
|
|
)
|
|
i32.const 1000
|
|
i32.add
|
|
)
|
|
)
|
|
)
|