Closed Bug 1950284 Opened 1 year ago Closed 1 year ago

Build an experimental loop unroller for wasm

Categories

(Core :: JavaScript: WebAssembly, enhancement, P3)

enhancement

Tracking

()

RESOLVED FIXED
139 Branch
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.

See Also: → 1039458
Attached patch bug1950284-loop-unroller.diff-6 (obsolete) — — Splinter Review

WIP patch; incomplete; not remotely usable.

Attached patch bug1950284-loop-unroller.diff-9 (obsolete) — — Splinter Review

Control-flow fixups work now, but still lacks the ability to add phi nodes for
values defined inside the loop and used afterwards.

Attachment #9468386 - Attachment is obsolete: true
Attached patch bug1950284-loop-unroller.diff-12 (obsolete) — — Splinter Review

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.

Attachment #9468936 - Attachment is obsolete: true
Attached patch bug1950284-loop-unroller.diff-15 (obsolete) — — Splinter Review

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.

Attachment #9469384 - Attachment is obsolete: true
Attached patch bug1950284-loop-unroller.diff-17 (obsolete) — — Splinter Review

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; find const 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 %
Attachment #9469752 - Attachment is obsolete: true
Attached patch bug1950284-loop-unroller.diff-19 (obsolete) — — Splinter Review
  • another bug fix

  • enables cloning for the most common wasm-GC MIR node types

Attachment #9470221 - Attachment is obsolete: true
Attached patch bug1950284-loop-unroller.diff-20 (obsolete) — — Splinter Review
  • now with test cases (jit-test/tests/wasm/unroll*.js)
Attachment #9470484 - Attachment is obsolete: true
Attached patch bug1950284-loop-unroller.diff-21 (obsolete) — — Splinter Review
  • 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 %
Attachment #9470707 - Attachment is obsolete: true
Attached patch bug1950284-loop-unroller.diff-26 (obsolete) — — Splinter Review
  • now with reworked top level structure, and more comments
Attachment #9470993 - Attachment is obsolete: true
  • Cleaned up for review, although not split into pieces yet.

  • Rebased to m-c 778475:726d5bb29819 (Sun Mar 16 06:02:52 2025 +0200)

Attachment #9472017 - Attachment is obsolete: true

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

This patch adds clone methods for a bunch of wasm MIR node kinds. It is not
exhaustive. It also provides an MPhi::clone method.

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

This adds 5 new test cases for unrolling.

Blocks: 1959049
Blocks: 1959074
Blocks: 1959078
Blocks: 1959091
Pushed by jseward@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/fab49991ab1b part 1: improvments to MIR debug printing routines. r=rhunt. https://hg.mozilla.org/integration/autoland/rev/25e5719d414f part 2: add clone routines for wasm MIR node kinds. r=rhunt. https://hg.mozilla.org/integration/autoland/rev/0afe7ac4be10 part 3: add a loop unroller for MIR. r=iain. https://hg.mozilla.org/integration/autoland/rev/68b709e108bd part 4: test cases for loop unrolling. r=rhunt.

Backed out for causing build bustages.

Flags: needinfo?(jseward)
Pushed by jseward@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/125f73224424 part 1: improvments to MIR debug printing routines. r=rhunt. https://hg.mozilla.org/integration/autoland/rev/ed3d5e9ade33 part 2: add clone routines for wasm MIR node kinds. r=rhunt. https://hg.mozilla.org/integration/autoland/rev/7a4a9b370bb1 part 3: add a loop unroller for MIR. r=iain. https://hg.mozilla.org/integration/autoland/rev/8f097d9c2420 part 4: test cases for loop unrolling. r=rhunt.
QA Whiteboard: [qa-triage-done-c140/b139]
Flags: needinfo?(jseward)
Blocks: wasm-perf
No longer blocks: wasm-perf-gap
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: