1919025 - Investigate using Semi-NCA in ComputeImmediateDominators

Status: RESOLVED FIXED

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

Description

[Jan de Mooij [:jandem]]

Spinning this off from bug 1916442.

The next issue is MIR dominator-tree building. The algorithm we have doesn't scale well with large MIR graphs and I want to see if we can change that to Semi-NCA which is a more recent algorithm that's also used by LLVM.

I've reimplemented ComputeImmediateDominators using Semi-NCA and it's a large improvement: 14 seconds to 7.9 seconds for ort-wasm-simd-threaded.jsep.wasm. I also verified it produces exactly the same immediate dominators for all jit-tests and this Wasm file.

My prototype patch for this is pretty straight-forward and I've added assertions to check it computes the same information as the current algorithm for all jit-tests.

The main thing left is to clean it up and make sure it doesn't regress JS/Wasm compile times for normal-size graphs.

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Bug 1919025 part 1 - Move dominator tree building code to a new jit/DominatorTree.cpp file. r?mgaudet!

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Bug 1919025 part 2 - Add Semi-NCA implementation. r?mgaudet!

With this patch we run both algorithms at the same time and the Semi-NCA code asserts
the immediate dominators match.

Semi-NCA is much faster for very large graphs. For the ort-wasm-simd-threaded.jsep.wasm
Wasm module in bug 1916442, it reduces the total time spent in ComputeImmediateDominators
with --no-threads from 7171 ms to 151 ms. The LLVM backend also uses Semi-NCA.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Bug 1919025 part 3 - Remove old implementation of ComputeImmediateDominators. r?mgaudet!

Comment 4

[Jan de Mooij [:jandem]]

I'm landing the "assert same results in DEBUG builds" patch first. It doesn't affect release builds yet.

If that's green I'll land part 3 a few days later.

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/2da59767e15f
part 1 - Move dominator tree building code to a new jit/DominatorTree.cpp file. r=mgaudet
https://hg.mozilla.org/integration/autoland/rev/17850ee711c4
part 2 - Add Semi-NCA implementation. r=mgaudet

Comment 6

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/2da59767e15f
https://hg.mozilla.org/mozilla-central/rev/17850ee711c4

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/55aff6551061
part 3 - Remove old implementation of ComputeImmediateDominators. r=mgaudet

Comment 8

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/55aff6551061