883713 - Ion: Poor handling of sequence of ifs equivalent to a switch statement

Status: NEW

(Core :: JavaScript Engine: JIT, enhancement, P3)

Description

[Marc Feeley]

Attachment: Test program

A sequence of ifs testing a single variable for a set of values, semantically equivalent to a "switch", is not optimized.  For the test program the performance is 20x slower than v8 which seems to optimize this case:

% /usr/bin/time js switch-opt1.js
start = 0
end sum=200000000
       61.19 real        61.16 user         0.00 sys

% /usr/bin/time d8 switch-opt1.js
start = 0
end sum=200000000
        3.33 real         3.31 user         0.00 sys

This was discovered while experimenting with emscripten which (sometimes?) translates the C switch statement into a sequence of ifs.  While that issue may be resolved by improving emscripten, it is a style of code that might arise in some other settings (automatically generated code, naive programmers, macros?) so it is worthwhile detecting this pattern and handling it as efficiently as a switch statement.

Comment 1

[Till Schneidereit [:till]]

I guess we might want to optimize this in IM, too, but Odinmonky is probably more pressing.

Comment 2

[Nicolas B. Pierron [:nbp]]

I suggested a while back to add a way to balance comparisons in some-kind of decision diagram, such as when we have a switch made out of string-cases, we can reduce the number of comparison to a log of it.  The optimization I was thinking of would be independent of the bytecode representation, for all sequences of condition which are side-effect-free.

Comment 3

[BMO Automation]

Per policy at https://wiki.mozilla.org/Bug_Triage/Projects/Bug_Handling/Bug_Husbandry#Inactive_Bugs. If this bug is not an enhancement request or a bug not present in a supported release of Firefox, then it may be reopened.

Comment 4

[Lars T Hansen [:lth]]

Indeed, there's a sizable performance gap here. Chromium runs the JS test case in about 2.2s, while Firefox comes in around 4.8 (Fedora 33, x64, current Nightly vs latest Chromium for Fedora 33). For the equivalent wasm program, Chromium runs it in about 2.0s while Firefox still uses about 4.8.

(3x is better than the 20x of eight years ago, for one thing. For another thing, if the series of ifs were actually rewritten as a switch in v8 I would have expected a bigger performance difference than than, so maybe it's more of a binary search solution, as nbp writes above.)

If what Marc writes is still true, that Emscripten sometimes emits a series of ifs, then we should look into optimizing this too, at least for wasm. Should ping the emscripten folks first.

Comment 5

[Lars T Hansen [:lth]]

Attachment: branch-sequence-tests.tar

JS test case + wasm test case, packaged as JS for the shell and HTML for the browser.

Comment 6

[Yury Delendik (:yury)]

Attachment: WIP: Bug 883713 - Fold chain of if with int constants into MTableSwitch.

Comment 7

[Yury Delendik (:yury)]

Attachment: MIR for "Fold Tests", "Fold Table Switches", and "DCE" passes

Comment 8

[Yury Delendik (:yury)]

WIP. Here is times for running "dispatch.js": without pass "time=4.421" and with "time=0.484". I did not really do correctness check: just trusted MTableSwitch behavior.

The JS test (from comment 5) did not really work since the congruentTo fails when scope lookup involved, but if the test is modified to use local pc, it folds blocks as expected. Also, it is probably worth to white list only local vars in the compare node.

Comment 9

[Yury Delendik (:yury)]

Some digging into emscripten/llvm outputs:

• emscripten does not produce such output. assemblyscript might though, but there is a pass to convert them into br_table under certain conditions (e.g. https://github.com/WebAssembly/binaryen/pull/1502/files)
• llvm does not convert into br_table into br_if, so it is very unlikely llvm will have br_if equivalent instead of br_table

Comment 10

[Yury Delendik (:yury)]

Moving into JS bucket since (after talking to Lars) WebAssembly team has a little interest in this feature. We anticipate well optimized input from a LLVM/emscripten toolchain, and ifs equivalents to a switch statements is not the case there. It only makes sense if there is some popular framework that generates such JS scripts.