1920951 - Optimize loops in createMoveGroupsFromLiveRangeTransitions

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, task, P1)

Description

[Jan de Mooij [:jandem]]

Some of the loops in createMoveGroupsFromLiveRangeTransitions have quadratic behavior and this hurts us when compiling Wasm modules with very large functions.

Fixing this improves the ONNX module in bug 1916442 from ~5.4 seconds to ~3.9 seconds and a PhotoShop module from 25 seconds to 14.5 seconds.

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Bug 1920951 part 1 - Turn a quadratic loop into an assertion. r?jseward!

This looks like an optimization, but it never hits on any tests because two overlapping
ranges for a virtual register should have a different allocation. The loop is also
quadratic.

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Bug 1920951 part 2 - Mark some methods and fields as const. r?jseward!

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Bug 1920951 part 3 - Optimize adding move groups within blocks. r?jseward!

Use a vector to keep track of previous 'active' ranges that could be predecessor
ranges. This vector contains only a few ranges so this is much more efficient than
using rangeFor.

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Bug 1920951 part 4 - Optimize adding move groups for control flow edges. r?jseward!

First add all edges to a vector, including the range on the successor side.
Then sort this vector and iterate over the ranges and the edges simultaneously
to resolve all edges. This avoids quadratic behavior.

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Bug 1920951 part 5 - Avoid inserting some unnecessary moves in createMoveGroupsForControlFlowEdges. r?jseward!

In createMoveGroupsForControlFlowEdges, for at least 70% of all edges, the predecessor
and successor blocks have ranges with the same allocation. In this case moveAtEdge is a
no-op.

We can increase this number by a few percentage points if we stop searching for a range
when we find an exact match.

This also fixes the register allocation issue reported in bug 1912154.

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/49949b890d66
part 1 - Turn a quadratic loop into an assertion. r=jseward
https://hg.mozilla.org/integration/autoland/rev/3df242142132
part 2 - Mark some methods and fields as const. r=jseward
https://hg.mozilla.org/integration/autoland/rev/56f929b201ff
part 3 - Optimize adding move groups within blocks. r=jseward
https://hg.mozilla.org/integration/autoland/rev/b1faf0f24bd2
part 4 - Optimize adding move groups for control flow edges. r=jseward
https://hg.mozilla.org/integration/autoland/rev/db4000b52409
part 5 - Avoid inserting some unnecessary moves in createMoveGroupsForControlFlowEdges. r=jseward

Comment 7

[Mayank Bansal]

Improvements
27% improvement on Jetstream2-HashSet-wasm-Runtime
4.6% improvement on Jetstream2- stanford-crypto-aes-Average
3.4% improvement on Jetstream2-segmentation- suite

Regressions:
17% regression on Jetstream2-float-mm.c-Average (Effectively neutralizing the gains from bug 1918970)

Comment 8

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/49949b890d66
https://hg.mozilla.org/mozilla-central/rev/3df242142132
https://hg.mozilla.org/mozilla-central/rev/56f929b201ff
https://hg.mozilla.org/mozilla-central/rev/b1faf0f24bd2
https://hg.mozilla.org/mozilla-central/rev/db4000b52409