Skip to content

Commit c7bfc7c

Browse files
ConstellationConstellation
committed
[JSC] Add B3::eliminateWasmGCAllocations phase
https://bugs.webkit.org/show_bug.cgi?id=318768 Reviewed by Justin Michaud. This patch adds B3::eliminateWasmGCAllocations phase. This is super duper simple scalar replacement for WasmGC struct types. We record usesWasmGCStructAllocations and run this phase only when this is recorded as this phase is meaningless if we do not have WasmStructNew. The key insight here is we already run CSE with WasmGC structs, which can successfully remove load-elimination and store-elimination. Thus, at this point, most of related WasmGC struct loads are no longer associated with the WasmGC struct. Thus we only need to care about WasmStructSet here since WasmStructGet should be already converted to the pointed value if the struct is not escaped and CSE ran already. This assumption (of course, this is not covering all the cases, but most of beneficial cases should be in this class) makes this phase extremely simple. Basically just collecting WasmStructSet-use-only WasmStructNew since it is not escaped. And then we convert all of them into Nop. Tests: JSTests/wasm/stress/wasm-gc-eliminate-allocations-basic.js JSTests/wasm/stress/wasm-gc-eliminate-allocations-control-flow.js JSTests/wasm/stress/wasm-gc-eliminate-allocations-escape.js * JSTests/wasm/stress/wasm-gc-eliminate-allocations-basic.js: Added. (async test): * JSTests/wasm/stress/wasm-gc-eliminate-allocations-control-flow.js: Added. (loopLocalExpected): (async test): * JSTests/wasm/stress/wasm-gc-eliminate-allocations-escape.js: Added. (async test): * Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj: * Source/JavaScriptCore/Sources.txt: * Source/JavaScriptCore/b3/B3EliminateWasmGCAllocations.cpp: Added. (JSC::B3::eliminateWasmGCAllocations): * Source/JavaScriptCore/b3/B3EliminateWasmGCAllocations.h: Added. * Source/JavaScriptCore/b3/B3Generate.cpp: (JSC::B3::generateToAir): * Source/JavaScriptCore/b3/B3MemoryValue.h: * Source/JavaScriptCore/b3/B3Procedure.h: (JSC::B3::Procedure::setUsesWasmGCStructAllocations): (JSC::B3::Procedure::usesWasmGCStructAllocations const): (JSC::B3::Procedure::setUsesWasmGCArrayAllocations): (JSC::B3::Procedure::usesWasmGCArrayAllocations const): * Source/JavaScriptCore/runtime/OptionsList.h: * Source/JavaScriptCore/wasm/WasmOMGIRGenerator.cpp: (JSC::Wasm::OMGIRGenerator::addArrayNew): (JSC::Wasm::OMGIRGenerator::addArrayNewDefault): (JSC::Wasm::OMGIRGenerator::addArrayNewFixed): (JSC::Wasm::OMGIRGenerator::addStructNew): (JSC::Wasm::OMGIRGenerator::addStructNewDefault): Canonical link: https://commits.webkit.org/316659@main
1 parent 20f0fc4 commit c7bfc7c

12 files changed

Lines changed: 452 additions & 2 deletions

‎JSTests/wasm/stress/wasm-gc-eliminate-allocations-basic.js‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
//@ runDefaultWasm("-m", "--useConcurrentJIT=0", "--thresholdForOMGOptimizeAfterWarmUp=0", "--thresholdForBBQOptimizeAfterWarmUp=0")
2+
3+
// Exercises B3's eliminateWasmGCAllocations (dead non-escaping struct removal) plus the
4+
// reduceStrength ref.eq folding of fresh allocations. Everything runs in a hot loop so the
5+
// OMG tier (where the pass runs) compiles and executes.
6+
7+
import { instantiate } from "../gc/wast-wrapper.js"
8+
import * as assert from "../assert.js"
9+
10+
const wat = `
11+
(module
12+
(type $point (struct (field $x (mut i32)) (field $y (mut i32))))
13+
(type $box (struct (field $p (mut (ref null $point)))))
14+
(type $node (struct (field $v (mut i32)) (field $next (mut (ref null $node)))))
15+
16+
;; Allocate a struct, initialize it, never read it: pure dead allocation.
17+
(func (export "deadStruct") (param $a i32) (param $b i32) (result i32)
18+
(local $p (ref $point))
19+
(local.set $p (struct.new $point (local.get $a) (local.get $b)))
20+
(i32.add (local.get $a) (local.get $b)))
21+
22+
;; Allocate, set fields, read them back: CSE forwards the reads, the allocation is dead,
23+
;; and the returned value must still be correct.
24+
(func (export "readBack") (param $a i32) (param $b i32) (result i32)
25+
(local $p (ref $point))
26+
(local.set $p (struct.new $point (local.get $a) (local.get $b)))
27+
(i32.sub (struct.get $point $x (local.get $p))
28+
(struct.get $point $y (local.get $p))))
29+
30+
;; The struct escapes into a longer-lived struct that is returned, so it must NOT be
31+
;; removed and the field read through the escaped reference must be correct.
32+
(func (export "escapeIntoBox") (param $a i32) (result i32)
33+
(local $p (ref $point))
34+
(local $b (ref $box))
35+
(local.set $p (struct.new $point (local.get $a) (i32.const 7)))
36+
(local.set $b (struct.new $box (local.get $p)))
37+
(struct.get $point $x (struct.get $box $p (local.get $b))))
38+
39+
;; ref.eq of a fresh struct against itself is always true.
40+
(func (export "eqSelf") (param $a i32) (result i32)
41+
(local $p (ref $point))
42+
(local.set $p (struct.new $point (local.get $a) (local.get $a)))
43+
(ref.eq (local.get $p) (local.get $p)))
44+
45+
;; ref.eq of two distinct fresh structs is always false.
46+
(func (export "eqTwo") (param $a i32) (result i32)
47+
(ref.eq (struct.new $point (local.get $a) (local.get $a))
48+
(struct.new $point (local.get $a) (local.get $a))))
49+
50+
;; ref.eq of a fresh struct against null is always false (fresh is non-null).
51+
(func (export "eqNull") (param $a i32) (result i32)
52+
(ref.eq (struct.new $point (local.get $a) (local.get $a))
53+
(ref.null $point)))
54+
55+
;; Self-referential store: the allocation's own pointer is written into its own field
56+
;; (child(0) is the base, so it stays a removal candidate), and it is never read. This
57+
;; is the a.next = a shape; it must be removed without miscompiling.
58+
(func (export "selfRefDead") (param $a i32) (result i32)
59+
(local $n (ref $node))
60+
(local.set $n (struct.new $node (local.get $a) (ref.null $node)))
61+
(struct.set $node $next (local.get $n) (local.get $n))
62+
(local.get $a))
63+
64+
;; Same self-referential store, but a field is read back afterwards (CSE forwards the
65+
;; read of $v). Still dead; result must be correct.
66+
(func (export "selfRefRead") (param $a i32) (result i32)
67+
(local $n (ref $node))
68+
(local.set $n (struct.new $node (local.get $a) (ref.null $node)))
69+
(struct.set $node $next (local.get $n) (local.get $n))
70+
(struct.get $node $v (local.get $n)))
71+
72+
;; Self-referential store AND the node escapes (returned via $makeNode); it must be kept
73+
;; and the cycle followed one hop must read the right value.
74+
(func $makeNode (param $a i32) (result (ref $node))
75+
(local $n (ref $node))
76+
(local.set $n (struct.new $node (local.get $a) (ref.null $node)))
77+
(struct.set $node $next (local.get $n) (local.get $n))
78+
(local.get $n))
79+
(func (export "selfRefEscape") (param $a i32) (result i32)
80+
(local $n (ref $node))
81+
(local.set $n (call $makeNode (local.get $a)))
82+
;; n.next.next.v -- follows the self-cycle twice, must equal a.
83+
(struct.get $node $v
84+
(struct.get $node $next
85+
(struct.get $node $next (local.get $n)))))
86+
)
87+
`;
88+
89+
globalThis.testLoopCount ??= 10000;
90+
91+
async function test() {
92+
const instance = await instantiate(wat, {});
93+
const { deadStruct, readBack, escapeIntoBox, eqSelf, eqTwo, eqNull, selfRefDead, selfRefRead, selfRefEscape } = instance.exports;
94+
95+
for (let i = 0; i < testLoopCount; ++i) {
96+
assert.eq(deadStruct(i, 3), i + 3);
97+
assert.eq(readBack(i + 10, 4), i + 6);
98+
assert.eq(escapeIntoBox(i), i);
99+
assert.eq(eqSelf(i), 1);
100+
assert.eq(eqTwo(i), 0);
101+
assert.eq(eqNull(i), 0);
102+
assert.eq(selfRefDead(i), i);
103+
assert.eq(selfRefRead(i), i);
104+
assert.eq(selfRefEscape(i), i);
105+
}
106+
}
107+
108+
await assert.asyncTest(test());

‎JSTests/wasm/stress/wasm-gc-eliminate-allocations-control-flow.js‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
//@ runDefaultWasm("-m", "--useConcurrentJIT=0", "--thresholdForOMGOptimizeAfterWarmUp=0", "--thresholdForBBQOptimizeAfterWarmUp=0")
2+
3+
// Exercises eliminateWasmGCAllocations against control-flow graph shapes that produce
4+
// Identity wrappers and Phi nodes for struct pointers: block results, if/else, select,
5+
// and loops. The pass must look through Identity (foldIdentity) and must treat a pointer
6+
// that flows into a Phi/select or an escaping position as observable (kept), while still
7+
// removing the genuinely-dead ones. All results are numeric so a miscompile is caught.
8+
9+
import { instantiate } from "../gc/wast-wrapper.js"
10+
import * as assert from "../assert.js"
11+
12+
const wat = `
13+
(module
14+
(type $point (struct (field $x (mut i32)) (field $y (mut i32))))
15+
16+
;; The struct pointer flows out of a block as its result (an Identity wrapper), then is
17+
;; read. Dead after CSE forwarding; result must be correct.
18+
(func (export "blockResult") (param $a i32) (result i32)
19+
(local $p (ref $point))
20+
(local.set $p
21+
(block (result (ref $point))
22+
(struct.new $point (local.get $a) (i32.const 5))))
23+
(struct.get $point $x (local.get $p)))
24+
25+
;; Two fresh structs on the two arms of an if; the selected one is read. Both are
26+
;; non-escaping; the merge is a Phi of two allocations.
27+
(func (export "ifElse") (param $a i32) (param $c i32) (result i32)
28+
(local $p (ref $point))
29+
(local.set $p
30+
(if (result (ref $point)) (local.get $c)
31+
(then (struct.new $point (local.get $a) (i32.const 1)))
32+
(else (struct.new $point (i32.const 2) (local.get $a)))))
33+
(struct.get $point $x (local.get $p)))
34+
35+
;; select between two fresh structs, then read.
36+
(func (export "selectStruct") (param $a i32) (param $c i32) (result i32)
37+
(local $p (ref $point))
38+
(local.set $p
39+
(select (result (ref $point))
40+
(struct.new $point (local.get $a) (i32.const 0))
41+
(struct.new $point (i32.const 9) (i32.const 0))
42+
(local.get $c)))
43+
(struct.get $point $y (local.get $p)))
44+
45+
;; A struct freshly allocated and read inside each loop iteration (the common
46+
;; steady-state shape). The loop carries an accumulator, not the pointer.
47+
(func (export "loopLocal") (param $n i32) (result i32)
48+
(local $i i32)
49+
(local $sum i32)
50+
(local $p (ref $point))
51+
(block $done
52+
(loop $loop
53+
(br_if $done (i32.ge_s (local.get $i) (local.get $n)))
54+
(local.set $p (struct.new $point (local.get $i) (i32.const 3)))
55+
(local.set $sum
56+
(i32.add (local.get $sum)
57+
(i32.add (struct.get $point $x (local.get $p))
58+
(struct.get $point $y (local.get $p)))))
59+
(local.set $i (i32.add (local.get $i) (i32.const 1)))
60+
(br $loop)))
61+
(local.get $sum))
62+
63+
;; The pointer is loop-carried through a Phi (escapes the simple pattern): must not be
64+
;; miscompiled. Returns the last-written x.
65+
(func (export "loopCarried") (param $n i32) (result i32)
66+
(local $i i32)
67+
(local $p (ref $point))
68+
(local.set $p (struct.new $point (i32.const -1) (i32.const 0)))
69+
(block $done
70+
(loop $loop
71+
(br_if $done (i32.ge_s (local.get $i) (local.get $n)))
72+
(local.set $p (struct.new $point (local.get $i) (i32.const 0)))
73+
(local.set $i (i32.add (local.get $i) (i32.const 1)))
74+
(br $loop)))
75+
(struct.get $point $x (local.get $p)))
76+
)
77+
`;
78+
79+
function loopLocalExpected(n) {
80+
let sum = 0;
81+
for (let i = 0; i < n; ++i)
82+
sum += i + 3;
83+
return sum;
84+
}
85+
86+
globalThis.testLoopCount ??= 10000;
87+
88+
async function test() {
89+
const instance = await instantiate(wat, {});
90+
const { blockResult, ifElse, selectStruct, loopLocal, loopCarried } = instance.exports;
91+
92+
for (let i = 0; i < testLoopCount; ++i) {
93+
assert.eq(blockResult(i), i);
94+
assert.eq(ifElse(i, 1), i);
95+
assert.eq(ifElse(i, 0), 2);
96+
assert.eq(selectStruct(i, 1), 0);
97+
assert.eq(selectStruct(i, 0), 0);
98+
assert.eq(loopLocal(i % 20), loopLocalExpected(i % 20));
99+
assert.eq(loopCarried(i % 20 + 1), (i % 20 + 1) - 1);
100+
}
101+
}
102+
103+
await assert.asyncTest(test());

‎JSTests/wasm/stress/wasm-gc-eliminate-allocations-escape.js‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
//@ runDefaultWasm("-m", "--useConcurrentJIT=0", "--thresholdForOMGOptimizeAfterWarmUp=0", "--thresholdForBBQOptimizeAfterWarmUp=0")
2+
3+
// Exercises cases where a struct allocation must be KEPT (it escapes) and cases mixing
4+
// structs with arrays (which this pass does not touch). If the pass wrongly removed an
5+
// escaping allocation these results would be wrong or it would crash.
6+
7+
import { instantiate } from "../gc/wast-wrapper.js"
8+
import * as assert from "../assert.js"
9+
10+
const wat = `
11+
(module
12+
(type $point (struct (field $x (mut i32)) (field $y (mut i32))))
13+
(type $arr (array (mut (ref null $point))))
14+
15+
(global $g (mut (ref null $point)) (ref.null $point))
16+
17+
;; Escapes into a global, then read back out: must be kept.
18+
(func (export "escapeGlobal") (param $a i32) (result i32)
19+
(global.set $g (struct.new $point (local.get $a) (i32.const 0)))
20+
(struct.get $point $x (global.get $g)))
21+
22+
;; Escapes by being returned from $make; the caller (returnStruct) reads a field. The
23+
;; returned reference must stay valid, so $make's allocation must be kept.
24+
(func $make (param $a i32) (result (ref $point))
25+
(struct.new $point (local.get $a) (i32.mul (local.get $a) (i32.const 2))))
26+
(func (export "returnStruct") (param $a i32) (result i32)
27+
(local $p (ref $point))
28+
(local.set $p (call $make (local.get $a)))
29+
(i32.add (struct.get $point $x (local.get $p))
30+
(struct.get $point $y (local.get $p))))
31+
32+
;; Escapes into an array element, then read back: struct kept, array untouched by pass.
33+
(func (export "escapeArray") (param $a i32) (result i32)
34+
(local $arr (ref $arr))
35+
(local.set $arr (array.new $arr (ref.null $point) (i32.const 4)))
36+
(array.set $arr (local.get $arr) (i32.const 2)
37+
(struct.new $point (local.get $a) (i32.const 0)))
38+
(struct.get $point $x (array.get $arr (local.get $arr) (i32.const 2))))
39+
40+
;; Escapes by being passed to a call: must be kept.
41+
(func $readX (param $p (ref $point)) (result i32)
42+
(struct.get $point $x (local.get $p)))
43+
(func (export "escapeCall") (param $a i32) (result i32)
44+
(call $readX (struct.new $point (local.get $a) (i32.const 0))))
45+
46+
;; A dead struct alongside a live array in the same function: the struct is removed, the
47+
;; array is left alone and its element read is correct.
48+
(func (export "deadStructLiveArray") (param $a i32) (result i32)
49+
(local $dead (ref $point))
50+
(local $arr (ref $arr))
51+
(local.set $dead (struct.new $point (local.get $a) (local.get $a)))
52+
(local.set $arr (array.new $arr (ref.null $point) (i32.const 2)))
53+
(array.set $arr (local.get $arr) (i32.const 0)
54+
(struct.new $point (local.get $a) (i32.const 0)))
55+
(struct.get $point $x (array.get $arr (local.get $arr) (i32.const 0))))
56+
)
57+
`;
58+
59+
globalThis.testLoopCount ??= 10000;
60+
61+
async function test() {
62+
const instance = await instantiate(wat, {});
63+
const { escapeGlobal, returnStruct, escapeArray, escapeCall, deadStructLiveArray } = instance.exports;
64+
65+
for (let i = 0; i < testLoopCount; ++i) {
66+
assert.eq(escapeGlobal(i), i);
67+
assert.eq(returnStruct(i), i + i * 2);
68+
assert.eq(escapeArray(i), i);
69+
assert.eq(escapeCall(i), i);
70+
assert.eq(deadStructLiveArray(i), i);
71+
}
72+
}
73+
74+
await assert.asyncTest(test());

‎Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -968,6 +968,7 @@
968968
31770C5827B94CE600308091 /* TemporalPlainDate.h in Headers */ = {isa = PBXBuildFile; fileRef = 31770C5227B94CE500308091 /* TemporalPlainDate.h */; settings = {ATTRIBUTES = (Private, ); }; };
969969
33111B8B2397256500AA34CE /* Scribble.h in Headers */ = {isa = PBXBuildFile; fileRef = 33111B8A2397256500AA34CE /* Scribble.h */; settings = {ATTRIBUTES = (Private, ); }; };
970970
3395C70722555F6D00BDBFAD /* B3EliminateDeadCode.h in Headers */ = {isa = PBXBuildFile; fileRef = 3395C70522555F6D00BDBFAD /* B3EliminateDeadCode.h */; };
971+
0378445DC7A9472E81DD9A6A /* B3EliminateWasmGCAllocations.h in Headers */ = {isa = PBXBuildFile; fileRef = BE117353BAB446559D01F3D2 /* B3EliminateWasmGCAllocations.h */; };
971972
33A920BD23DA2C6D000EBAF0 /* CommonSlowPathsInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 33A920BC23DA2C6D000EBAF0 /* CommonSlowPathsInlines.h */; };
972973
33B2A54722653481005A0F79 /* B3ValueInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84FB1BDACDAC0080FF74 /* B3ValueInlines.h */; };
973974
33B2A548226543BF005A0F79 /* FTLLowerDFGToB3.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEA0A04170513DB00BB722C /* FTLLowerDFGToB3.cpp */; };
@@ -4305,6 +4306,8 @@
43054306
3374364A224D79EF00C8C227 /* B3OptimizeAssociativeExpressionTrees.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = B3OptimizeAssociativeExpressionTrees.h; path = b3/B3OptimizeAssociativeExpressionTrees.h; sourceTree = "<group>"; };
43064307
3395C70422555F6C00BDBFAD /* B3EliminateDeadCode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3EliminateDeadCode.cpp; path = b3/B3EliminateDeadCode.cpp; sourceTree = "<group>"; };
43074308
3395C70522555F6D00BDBFAD /* B3EliminateDeadCode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3EliminateDeadCode.h; path = b3/B3EliminateDeadCode.h; sourceTree = "<group>"; };
4309+
A064075875F64769B8C0A842 /* B3EliminateWasmGCAllocations.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3EliminateWasmGCAllocations.cpp; path = b3/B3EliminateWasmGCAllocations.cpp; sourceTree = "<group>"; };
4310+
BE117353BAB446559D01F3D2 /* B3EliminateWasmGCAllocations.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3EliminateWasmGCAllocations.h; path = b3/B3EliminateWasmGCAllocations.h; sourceTree = "<group>"; };
43084311
33A920BC23DA2C6D000EBAF0 /* CommonSlowPathsInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CommonSlowPathsInlines.h; sourceTree = "<group>"; };
43094312
33B2A54522651D53005A0F79 /* MarkedSpace.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = MarkedSpace.cpp; sourceTree = "<group>"; };
43104313
36A7683254F6484D925EA7FE /* B3WasmArrayLengthValue.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = B3WasmArrayLengthValue.h; path = b3/B3WasmArrayLengthValue.h; sourceTree = "<group>"; };
@@ -7059,6 +7062,8 @@
70597062
0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */,
70607063
3395C70422555F6C00BDBFAD /* B3EliminateDeadCode.cpp */,
70617064
3395C70522555F6D00BDBFAD /* B3EliminateDeadCode.h */,
7065+
A064075875F64769B8C0A842 /* B3EliminateWasmGCAllocations.cpp */,
7066+
BE117353BAB446559D01F3D2 /* B3EliminateWasmGCAllocations.h */,
70627067
0F5BF16E1F23A5A10029D91D /* B3EnsureLoopPreHeaders.cpp */,
70637068
0F5BF16F1F23A5A10029D91D /* B3EnsureLoopPreHeaders.h */,
70647069
52E65A1A27682760002B4C0A /* B3EstimateStaticExecutionCounts.cpp */,
@@ -11232,6 +11237,7 @@
1123211237
0FEC85C11BE167A00080FF74 /* B3Effects.h in Headers */,
1123311238
0F725CA81C503DED00AD943A /* B3EliminateCommonSubexpressions.h in Headers */,
1123411239
3395C70722555F6D00BDBFAD /* B3EliminateDeadCode.h in Headers */,
11240+
0378445DC7A9472E81DD9A6A /* B3EliminateWasmGCAllocations.h in Headers */,
1123511241
0F5BF1711F23A5A10029D91D /* B3EnsureLoopPreHeaders.h in Headers */,
1123611242
52E65A1E27682771002B4C0A /* B3EstimateStaticExecutionCounts.h in Headers */,
1123711243
5318045C22EAAC4B004A7342 /* B3ExtractValue.h in Headers */,

‎Source/JavaScriptCore/Sources.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -138,6 +138,7 @@ b3/B3DuplicateTails.cpp
138138
b3/B3Effects.cpp
139139
b3/B3EliminateCommonSubexpressions.cpp
140140
b3/B3EliminateDeadCode.cpp
141+
b3/B3EliminateWasmGCAllocations.cpp
141142
b3/B3EnsureLoopPreHeaders.cpp
142143
b3/B3EstimateStaticExecutionCounts.cpp
143144
b3/B3ExtractValue.cpp

0 commit comments

Comments
 (0)