1735207 - Wasm bounds check elimination is ineffective

Status: RESOLVED FIXED

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

Description

[Lars T Hansen [:lth]]

Consider a simple program:

var mod = new WebAssembly.Module(wasmTextToBinary(
`(module
   (memory 1)
   (func (param i32) (result i32)
     (i32.load (local.get 0))
     drop
     (i32.load (local.get 0))))`));
wasmDis(mod)

Run with --wasm-compiler=optimizing --spectre-mitigations=off --disable-wasm-huge-memory after commenting out the body of MacroAssembler::assertCanonicalInt32 (in order to get legible code). Output:

00000000  55                        push %rbp
00000001  48 8b ec                  mov %rsp, %rbp
00000004  41 83 fa 23               cmp $0x23, %r10d
00000008  0f 84 06 00 00 00         jz 0x0000000000000014
0000000E  0f 0b                     ud2
00000010  55                        push %rbp
00000011  48 8b ec                  mov %rsp, %rbp
00000014  49 8b 46 08               movq 0x08(%r14), %rax
00000018  8b cf                     mov %edi, %ecx
0000001A  48 3b c8                  cmp %rax, %rcx
0000001D  0f 82 02 00 00 00         jb 0x0000000000000025
00000023  0f 0b                     ud2
00000025  41 8b 0c 3f               movl (%r15,%rdi,1), %ecx
00000029  8b cf                     mov %edi, %ecx
0000002B  48 3b c8                  cmp %rax, %rcx
0000002E  0f 82 02 00 00 00         jb 0x0000000000000036
00000034  0f 0b                     ud2
00000036  41 8b 04 3f               movl (%r15,%rdi,1), %eax
0000003A  5d                        pop %rbp
0000003B  c3                        ret

This has both bounds checks intact, even though the second one is clearly redundant. The reason seems to be that the two addressing nodes in the MIR graphs, both representing "local 0", have different IDs and thus are not considered the same by BCE (non-constant case).

Poor BCE will hurt us big-time on 32-bit systems but also on 64-bit systems with Memory64. We should get at least simple cases right, which means constant indices and checks that are dominated by identical checks, as is this one. And we need to have test cases to check that BCE works.

Comment 1

[Lars T Hansen [:lth]]

Looks like WasmExtendU32Index node is not GVN-friendly. Easy fix.

Comment 2

[Lars T Hansen [:lth]]

I think this only affects 64-bit systems at present (memory64 may change that); as we rarely use explicit bounds checking on 64-bit the regression is not a huge problem in practice.

Comment 3

[Lars T Hansen [:lth]]

Elimination of bounds checks on constant indices below the heap minimum is also broken because WasmExtendU32Index(constant) is not folded, and so the constant-index case does not trigger.

Comment 4

[Lars T Hansen [:lth]]

The introduction of support for 4GB heaps with 64-bit bounds created this problem:

changeset:   640948:293371b99fca
user:        Lars T Hansen <[e-mail]>
date:        Fri Mar 26 12:33:01 2021 +0000
summary:     Bug 1676441 - Bounds checking for 4GB heaps. r=rhunt

Comment 5

[Lars T Hansen [:lth]]

Attachment: Bug 1735207 - Improve WasmExtendU32Index and WasmWrapU32Index. r?nbp

WasmExtendU32Index and WasmWrapU32Index were not GVN-friendly and did
not perform constant folding. (The problem was introduced by the
support for 4GB heaps and 64-bit bounds, which created these nodes.)
As a consequence, these nodes impeded bounds check elimination, with
the effect that BCE on 64-bit systems did nothing. BCE on 32-bit
systems was likely unaffected by the bug, as the max heap size on
32-bit is 2GB.

Make these nodes GVN-friendly and add appropriate constant folding.

Add simple white-box test cases to test that the BCE works properly on
64-bit and 32-bit both.

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/399badd3e25b
Improve WasmExtendU32Index and WasmWrapU32Index. r=nbp

Comment 7

[Cristina Cozmuta (:CrissCozmuta)]

Backed out for causing failures on codegen-x64-test.js. CLOSED TREE
Backout link : https://hg.mozilla.org/integration/autoland/rev/f4fd920a7d8b37e0f8aa4454ce27fb801d4aa515
Push with failures : https://treeherder.mozilla.org/jobs?repo=autoland&resultStatus=testfailed%2Cbusted%2Cexception%2Crunnable&revision=399badd3e25b1557dda3606ae68b872b88c65cb5&selectedTaskRun=Tzjok2ZmT1WSvP_ylCtRUQ.0
Link to failure log :
https://treeherder.mozilla.org/logviewer?job_id=354482638&repo=autoland&lineNumber=46338
https://treeherder.mozilla.org/jobs?repo=autoland&resultStatus=testfailed%2Cbusted%2Cexception%2Crunnable&revision=399badd3e25b1557dda3606ae68b872b88c65cb5&selectedTaskRun=NLleLv8pTriWj0ExZaLiBw.0

Comment 8

[BugBot [:suhaib / :marco/ :calixte]]

Set release status flags based on info from the regressing bug 1676441

Comment 9

[Lars T Hansen [:lth]]

The failure to match the generated code is caused by extra code inserted by --ion-check-range-analysis. This code is inserted into the function:

00000014  33 c0                     xor %eax, %eax
00000016  85 c0                     test %eax, %eax
00000018  0f 8d 01 00 00 00         jnl 0x000000000000001F
0000001E  cc                        int3
0000001F  85 c0                     test %eax, %eax
00000021  0f 8e 01 00 00 00         jle 0x0000000000000028
00000027  cc                        int3

This is just the integer zero + an AssertRange node that checks that it is in the range [0,0], I think. Not very helpful. Constant folding AssertRange nodes would have maybe gotten rid of most of this but might still leave us with the dead integer zero.

Hard to say where the zero comes from, to be honest. The test case is

var mod = new WebAssembly.Module(wasmTextToBinary(
`(module
   (memory 1)
   (func (result i32)
     (i32.load (i32.const 16))))`));
wasmDis(mod)

Comment 10

[Lars T Hansen [:lth]]

I'm skipping the test if ion.check-range-analysis is true though I'm still baffled as to why this problem does not affect the codegen tests in the simd subdirectory.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/5051da6637dc
Improve WasmExtendU32Index and WasmWrapU32Index. r=nbp

Comment 12

[Noemi Erli[:noemi_erli]]

https://hg.mozilla.org/mozilla-central/rev/5051da6637dc

Comment 13

[Lars T Hansen [:lth]]

Comment on attachment 9245420 [details]
Bug 1735207 - Improve WasmExtendU32Index and WasmWrapU32Index. r?nbp

ESR Uplift Approval Request

• If this is not a sec:{high,crit} bug, please state case for ESR consideration: Wasm content on some 64-bit devices that are underprovisioned with virtual memory (mobile phones typically; virtualized environments sometimes) may execute more slowly because bounds check elimination was rendered inoperative by a previous patch. The present patch reenables the optimization.
• User impact if declined: Somewhat (but not hugely) slower wasm execution in contexts mentioned above.
• Fix Landed on Version: FF95
• Risk to taking this patch: Low
• Why is the change risky/not risky? (and alternatives if risky): This is pretty well-understood code, and the fix is the obvious one and not complicated. That said, any change to the optimizer is a little risky.
• String or UUID changes made by this patch:

Comment 14

[Ryan VanderMeulen [:RyanVM]]

Comment on attachment 9245420 [details]
Bug 1735207 - Improve WasmExtendU32Index and WasmWrapU32Index. r?nbp

Approved for 91.4esr.

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-esr91/rev/3edd7821b9f5