Build an experimental loop unroller for wasm
Categories
(Core :: JavaScript: WebAssembly, enhancement, P3)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox139 | --- | fixed |
People
(Reporter: jseward, Assigned: jseward)
References
(Blocks 4 open bugs)
Details
Attachments
(1 file, 4 external files, 9 obsolete files)
|
130.23 KB,
patch
|
Details | Diff | Splinter Review |
Build an experimental loop unroller for wasm, primarily as a way to reduce the
per-iteration cost of interrupt checks in tight loops. Could also serve as a
basis for future experimentation with loop peeling.
| Assignee | ||
Comment 1•1 year ago
|
||
WIP patch; incomplete; not remotely usable.
| Assignee | ||
Comment 2•1 year ago
|
||
Control-flow fixups work now, but still lacks the ability to add phi nodes for
values defined inside the loop and used afterwards.
| Assignee | ||
Comment 3•1 year ago
|
||
Can unroll loops that have either: one exit, and arbitrarily many values
defined in the loop and used after it, OR multiple exits, but no values defined
in the loop used after it.
| Assignee | ||
Comment 4•1 year ago
|
||
First usable version:
-
limited to unrolling wasm only
-
cannot unroll loops with more than one exit AND that have values defined in
the loop, that are used afterwards (logged as "TooDifficult").
Either individually (multiple exits, or values used after the loop, is OK). -
unrolling factor hardwired to 3
-
disabled by default (
--setpref=wasm_loop_unrolling=0).
Setting this to =1 enables unrolling.
Setting this to =2 enables unrolling, plus 1-line per loop summary logging. -
most wasm-gc MIR nodes can't currently be cloned, so loops containing them
won't be unrolled.
| Assignee | ||
Comment 5•1 year ago
|
||
Second usable version. Applies to base rev 774493:508a834f0ff7.
-
limited to unrolling wasm only
-
cannot unroll loops with more than one exit AND that have values defined in
the loop, that are used afterwards (logged as "TooDifficult"). Either
individually (multiple exits, or values used after the loop), is OK. -
unrolling factor hardwired to 3, as that seems to give the best results.
Can be set to any value >= 2; findconst uint32_t unrollFactor = 3;. -
disabled by default (
--setpref=wasm_unroll_loops=0). Note: name changed
compared to comment 4.- setting this to =1 enables unrolling.
- setting this to =2 enables unrolling, plus 1-line per loop summary logging.
-
optionally, can rerun GVN and dead-block removal after unrolling:
--setpref=wasm_rerun_gvn_after_unroll=1
-
most wasm-gc MIR nodes can't currently be cloned, so loops containing them
won't be unrolled. This could easily be fixed.
For JetStream3 on Intel Tiger Lake fixed at 3.0 GHz:
Run time / Average numbers -- higher is better (verified)
Best of 10 runs
NO-UNROLL UNROLL-3 UNROLL-3+GVN rel-to-NO-UNROLL
tsf-wasm 39.580 39.946 40.048 + 1.2 %
tfjs-wasm-simd 1.699 1.727 1.728 + 1.7 %
tfjs-wasm 0.649 0.654 0.653 + 0.6 %
sqlite3-wasm 12.813 13.869 14.246 +11.2 %
richards-wasm 37.896 38.499 38.342 + 1.2 %
quicksort-wasm 131.508 137.173 136.792 + 4.0 % GVN worse
HashSet-wasm 135.173 135.173 135.653 + 0.4 %
gcc-loops-wasm 137.117 139.134 144.083 + 5.1 %
argon2-wasm-simd 7.962 8.014 8.019 + 0.7 %
argon2-wasm 0.275 0.273 0.272 - 1.1 %
8bitbench-wasm 0.941 0.967 0.970 + 3.1 %
| Assignee | ||
Comment 6•1 year ago
|
||
-
another bug fix
-
enables cloning for the most common wasm-GC MIR node types
| Assignee | ||
Comment 7•1 year ago
|
||
- now with test cases (
jit-test/tests/wasm/unroll*.js)
| Assignee | ||
Comment 8•1 year ago
•
|
||
- now with an experimental implementation of peeling. Peeling is enabled
whenever unrolling is (--setpref=wasm_unroll_loops=1
--setpref=wasm_rerun_gvn_after_unroll=1). It produces 1 peeled iteration
and 3 unrolled iterations:loop { B; } --> B; loop { B; B; B; }
UNROLL-3 UNROLL-3 %-rel-to
NO-UNROLL UNROLL-3 +GVN +PEEL+GVN -NO-UNROLL
---------------------------------------------------------------------------
tsf-wasm 39.580 39.946 40.048 39.965 + 0.9 %
tfjs-wasm-simd 1.699 1.727 1.728 1.732 + 1.9 %
tfjs-wasm 0.649 0.654 0.653 0.654 + 0.8 %
sqlite3-wasm 12.813 13.869 14.246 14.260 +11.3 %
richards-wasm 37.896 38.499 38.342 38.077 + 0.5 %
quicksort-wasm 131.508 137.173 136.792 138.289 + 5.2 %
HashSet-wasm 135.173 135.173 135.653 137.430 + 1.7 %
gcc-loops-wasm 137.117 139.134 144.083 144.125 + 5.1 %
argon2-wasm-simd 7.962 8.014 8.019 7.999 + 0.5 %
argon2-wasm 0.275 0.273 0.272 0.278 + 1.1 %
8bitbench-wasm 0.941 0.967 0.970 0.992 + 5.4 %
| Assignee | ||
Comment 9•1 year ago
|
||
- now with reworked top level structure, and more comments
| Assignee | ||
Comment 10•1 year ago
|
||
-
Cleaned up for review, although not split into pieces yet.
-
Rebased to m-c 778475:726d5bb29819 (Sun Mar 16 06:02:52 2025 +0200)
| Assignee | ||
Comment 11•1 year ago
|
||
This patch expands and regularises the DumpMIR* family of routines, so that:
-
There are now DumpMIRDefinition, DumpMIRBlock and DumpMIRGraph, with
compatible signatures, and helper routines DumpMIRDefinitionID and
DumpMIRBlockID. -
DumpMIRBlock is extended to print the loop depth, block kind, and
successor-with-phis fields. -
Optionally, the routines can print hashed versions of block and definition
pointers, in base 26. This is to avoid ambiguity in cases where ID values
are duplicate or not set. This is controlled by a defaulted-false boolean
argument to the functions.
A block that was previously printed as
Block3:
24 = Int32.Phi 58 46
25 = None.Goto Block4
will now be shown as
Block3 -- preds=[Block2, Block7] -- LD=1 -- K=LOOP_HEADER -- s-w-phis=(null)
24 = Int32.Phi 58 46
25 = None.Goto Block4
or, if hashed-pointer printing is enabled, as
Block.bvufv.3 -- preds=[Block.nbloq.2, Block.zrexd.7] -- LD=1 -- K=LOOP_HEADER -- s-w-phis=(null)
rdzcr.24 = Int32.Phi bfyya.58 bfqhy.46
tmiue.25 = None.Goto Block4
| Assignee | ||
Comment 12•1 year ago
|
||
This patch adds clone methods for a bunch of wasm MIR node kinds. It is not
exhaustive. It also provides an MPhi::clone method.
| Assignee | ||
Comment 13•1 year ago
|
||
This patch adds a simple loop unroller for MIR, currently restricted to wasm
functions. The unroller proper is in new file wUnrollLoops.cpp, which is
extensively commented. Top level changes beyond that are:
-
OptimizeMIR gets a new subsection, that calls into UnrollLoops.cpp to try
loop unrolling. If any was performed, GVN and empty-block-removal are rerun
and the dominator tree is rebuilt. -
new IONFLAGS=unroll JitSpew printing, so we can see what is going on
-
in MIR.h / MIRGraph.h, a few new accessor methods:
MGoto::setTarget
MTest::setIf{True,False}
MPhi::addInputFallible
MBasicBlock::{setLoopHeader,appendPredecessor,erasePredecessor} -
jit/UnrollLoops.cpp: the unroller. See comments there.
-
new pref javascript.options.wasm_unroll_loops, by default false
| Assignee | ||
Comment 14•1 year ago
|
||
This adds 5 new test cases for unrolling.
Comment 15•1 year ago
|
||
Comment 17•1 year ago
|
||
Comment 18•1 year ago
|
||
| bugherder | ||
https://hg.mozilla.org/mozilla-central/rev/125f73224424
https://hg.mozilla.org/mozilla-central/rev/ed3d5e9ade33
https://hg.mozilla.org/mozilla-central/rev/7a4a9b370bb1
https://hg.mozilla.org/mozilla-central/rev/8f097d9c2420
Updated•1 year ago
|
| Assignee | ||
Updated•1 year ago
|
Updated•9 days ago
|
Description
•