Skip to content

Commit 0c51f43

Browse files
ConstellationConstellation
committed
[JSC] Quick pattern matching for byte-copy loop in OMG
https://bugs.webkit.org/show_bug.cgi?id=321468 rdar://184557364 Reviewed by Keith Miller. Depending on toolchain, options etc., very naive byte-copy loop is generated instead of wasm bulk-memory operations like memory.copy / memory.fill. This patch does quick pattern matching, detecting it and spreading MemoryCopy / MemoryFill operation with guards before the actual naive loop. We just prepend the fast path with MemoryCopy and MemoryFill since we do not know whether src and destination are overlapping or not at runtime easily. So we need to check them, and we need to fall back to the normal loop when it is overlapping badly. The replacement can be turned off with the useWasmByteLoopReplacement option. Tests: JSTests/wasm/stress/byte-loop-idiom-recognition.js JSTests/wasm/stress/byte-loop-idiom-loop-osr.js * JSTests/wasm/stress/byte-loop-idiom-loop-osr.js: Added. (async test.seed): (async test.assertMemoryMatches): (async test.copyMemmoveLike): (async test.copyReplicating): (async test.copyDownwards): (async test.fillRegion): (async test): * JSTests/wasm/stress/byte-loop-idiom-recognition.js: Added. (access): (modelCopyForward): (modelCopyBackward): (modelFill): (async test.seedWindow): (async test.seedEverything): (async test.assertMemoryMatches): (async test.checkEveryCase): (async test.assertTraps): (async test): * Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj: * Source/JavaScriptCore/runtime/OptionsList.h: * Source/JavaScriptCore/wasm/WasmByteLoopIdiom.h: Added. (JSC::Wasm::ByteLoopIdiom::isFill const): (JSC::Wasm::ByteLoopIdiom::isBackward const): (JSC::Wasm::ByteLoopIdiom::match): (JSC::Wasm::ByteLoopIdiom::localsAreDistinct const): (JSC::Wasm::ByteLoopIdiom::matchCopyForward): (JSC::Wasm::ByteLoopIdiom::matchCopyBackward): (JSC::Wasm::ByteLoopIdiom::matchFill): * Source/JavaScriptCore/wasm/WasmOMGIRGenerator.cpp: (JSC::Wasm::OMGIRGenerator::addMemoryFill): (JSC::Wasm::OMGIRGenerator::emitMemoryFill): (JSC::Wasm::OMGIRGenerator::addMemoryCopy): (JSC::Wasm::OMGIRGenerator::emitMemoryCopy): (JSC::Wasm::OMGIRGenerator::matchByteLoopIdiom): (JSC::Wasm::OMGIRGenerator::emitByteLoopIdiom): (JSC::Wasm::OMGIRGenerator::addLoop): Canonical link: https://commits.webkit.org/319065@main
1 parent b7fac90 commit 0c51f43

6 files changed

Lines changed: 808 additions & 10 deletions

File tree

‎JSTests/wasm/stress/byte-loop-idiom-loop-osr.js‎

Lines changed: 195 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,195 @@
1+
//@ runDefaultWasm("-m", "--useConcurrentJIT=0")
2+
3+
// A byte-at-a-time copy or fill loop can be entered by OSR part way through its run, with the
4+
// pointers and the counter already advanced. What is left of the run then has to come out the same
5+
// whether it is finished by the loop or by the bulk memory operation that replaces it, so each
6+
// function here runs a count long enough to tier up in the middle of the loop.
7+
8+
import { instantiate } from "../wabt-wrapper.js";
9+
import * as assert from "../assert.js";
10+
11+
const PAGE = 65536;
12+
const COUNT = 30000;
13+
14+
const golden = new Uint8Array(PAGE);
15+
for (let i = 0; i < PAGE; ++i)
16+
golden[i] = (i * 31 + 7) & 0xff;
17+
18+
let wat = `
19+
(module
20+
(memory (export "mem") 1)
21+
(global $d (mut i32) (i32.const 0))
22+
(global $s (mut i32) (i32.const 0))
23+
(global $n (mut i32) (i32.const 0))
24+
25+
;; for (; n; --n) mem[d++] = mem[s++];
26+
(func (export "copyForward") (param i32 i32 i32)
27+
(local i32)
28+
local.get 2
29+
if
30+
local.get 0
31+
local.set 3
32+
loop
33+
local.get 3
34+
local.get 1
35+
i32.load8_u
36+
i32.store8
37+
local.get 3
38+
i32.const 1
39+
i32.add
40+
local.set 3
41+
local.get 1
42+
i32.const 1
43+
i32.add
44+
local.set 1
45+
local.get 2
46+
i32.const 1
47+
i32.sub
48+
local.tee 2
49+
br_if 0
50+
end
51+
end
52+
local.get 3
53+
global.set $d
54+
local.get 1
55+
global.set $s
56+
local.get 2
57+
global.set $n)
58+
59+
;; for (; n; --n) mem[--d] = mem[--s]; -- the caller passes the ends of the regions.
60+
(func (export "copyBackward") (param i32 i32 i32)
61+
(local i32)
62+
local.get 2
63+
if
64+
local.get 0
65+
local.set 3
66+
loop
67+
local.get 3
68+
i32.const 1
69+
i32.sub
70+
local.tee 3
71+
local.get 1
72+
i32.const 1
73+
i32.sub
74+
local.tee 1
75+
i32.load8_u
76+
i32.store8
77+
local.get 2
78+
i32.const 1
79+
i32.sub
80+
local.tee 2
81+
br_if 0
82+
end
83+
end
84+
local.get 3
85+
global.set $d
86+
local.get 1
87+
global.set $s
88+
local.get 2
89+
global.set $n)
90+
91+
;; for (; n; --n) mem[d++] = v;
92+
(func (export "fill") (param i32 i32 i32)
93+
(local i32)
94+
local.get 2
95+
if
96+
local.get 0
97+
local.set 3
98+
loop
99+
local.get 3
100+
local.get 1
101+
i32.store8
102+
local.get 3
103+
i32.const 1
104+
i32.add
105+
local.set 3
106+
local.get 2
107+
i32.const 1
108+
i32.sub
109+
local.tee 2
110+
br_if 0
111+
end
112+
end
113+
local.get 3
114+
global.set $d
115+
local.get 2
116+
global.set $n)
117+
118+
(func (export "readD") (result i32) global.get $d)
119+
(func (export "readS") (result i32) global.get $s)
120+
(func (export "readN") (result i32) global.get $n)
121+
)
122+
`;
123+
124+
async function test()
125+
{
126+
const instance = await instantiate(wat, {}, {});
127+
const { copyForward, copyBackward, fill, readD, readS, readN, mem } = instance.exports;
128+
const memory = new Uint8Array(mem.buffer);
129+
const expected = new Uint8Array(PAGE);
130+
131+
function seed()
132+
{
133+
memory.set(golden);
134+
expected.set(golden);
135+
}
136+
137+
function assertMemoryMatches()
138+
{
139+
let i = 0;
140+
while (i < PAGE && memory[i] === expected[i])
141+
++i;
142+
assert.eq(i, PAGE, "memory differs at index " + i);
143+
}
144+
145+
// Overlapping with the destination below the source, which a bulk copy performs faithfully.
146+
function copyMemmoveLike()
147+
{
148+
seed();
149+
copyForward(0, 20000, COUNT);
150+
expected.copyWithin(0, 20000, 20000 + COUNT);
151+
assert.eq([readD(), readS(), readN()], [COUNT, 20000 + COUNT, 0]);
152+
assertMemoryMatches();
153+
}
154+
155+
// Overlapping the other way, which replicates a byte across the destination rather than moving
156+
// the region, so the loop has to keep running after the OSR entry.
157+
function copyReplicating()
158+
{
159+
seed();
160+
copyForward(20000, 19999, COUNT);
161+
for (let i = 0; i < COUNT; ++i)
162+
expected[20000 + i] = expected[19999 + i];
163+
assert.eq([readD(), readS(), readN()], [20000 + COUNT, 19999 + COUNT, 0]);
164+
assertMemoryMatches();
165+
}
166+
167+
function copyDownwards()
168+
{
169+
seed();
170+
copyBackward(PAGE, PAGE - COUNT, COUNT);
171+
expected.copyWithin(PAGE - COUNT, PAGE - 2 * COUNT, PAGE - COUNT);
172+
assert.eq([readD(), readS(), readN()], [PAGE - COUNT, PAGE - 2 * COUNT, 0]);
173+
assertMemoryMatches();
174+
}
175+
176+
function fillRegion()
177+
{
178+
seed();
179+
fill(1000, 0x5a, COUNT);
180+
expected.fill(0x5a, 1000, 1000 + COUNT);
181+
assert.eq([readD(), readN()], [1000 + COUNT, 0]);
182+
assertMemoryMatches();
183+
}
184+
185+
// The OSR entry happens on the run where the loop's own back edges tier the function up, which
186+
// takes more than one run of a loop this long.
187+
for (let repeat = 0; repeat < 4; ++repeat) {
188+
copyMemmoveLike();
189+
copyReplicating();
190+
copyDownwards();
191+
fillRegion();
192+
}
193+
}
194+
195+
await assert.asyncTest(test());

0 commit comments

Comments
 (0)