Add SIMD implementation of SMRegExpMacroAssembler::SkipUntilBitInTable
Categories
(Core :: JavaScript Engine, enhancement, P2)
Tracking
()
People
(Reporter: iain, Assigned: iain, NeedInfo)
References
(Blocks 1 open bug)
Details
(Whiteboard: [js-perf-next])
Attachments
(1 file)
In bug 1928862, we are updating our version of irregexp. One of the changes is a new regexp opcode, SkipUntilBitInTable. Upstream V8 generates SIMD instructions where possible, and uses a scalar version otherwise. Bug 1928862 only includes the scalar version. This bug is for implementing the SIMD version. V8 supports SIMD on x64 and arm64.
Without looking too closely at how this code works, it looks like V8's x64 version uses movdqu, movddup, andps, psrlw, pshufb, pcmbeqb, and pmovmskb, all of which we already use at least a little bit.
|
||
Comment 1•1 year ago
|
||
Hello iain!
This does seems like an interesting bug i would love to poke on! any pointers on which parts of code i can look at here to understand this (other than the v8 impl)?
Thank you!!
|
Assignee | |
Comment 2•1 year ago
|
||
I wrote this blog post a few years ago when we did the last big overhaul of irregexp. In particular, the Code Generation section is the short high-level summary of why this code exists. SkipUntilBitInTable is a new operation, and we want to generate efficient code for it.
The most important difference between the linked V8 code and the version that we want to write is that V8 has a version of this per-architecture, using instructions by name (eg pshufb), whereas our macroassembler is an architecture-independent abstraction layer with generic names. For example, in LoadCurrentCharacterUnchecked, we have calls like masm.load8ZeroExtend, and they have calls like movzxbl. The interface to the macroassembler is mostly in js/src/jit/MacroAssembler.h, and while I'd like to point you to a bunch of great documentation, it's mostly just a matter of looking for things in that file and poking around at other code. You can roughly think of this code as existing in a few layers: there is hardware-independent code in js/src/jit/MacroAssembler.cpp that generally provides higher-level APIs; each architecture has its own MacroAssembler-<arch>.cpp in s/src/jit/<arch>/, which implements the architecture-independent API using the lower layer; and Assembler-<arch>.cpp / BaseAssembler-<arch>.cpp is the lowest layer where all the gross details about eg instruction encodings are hidden.
Based on my quick initial survey, all the instructions that V8 is using (at least in the x64 implementation) are already implemented in our Assembler/BaseAssembler layer, but may not be exposed in an architecture independent way in the higher layers. Beyond reading the V8 implementations and figuring out what the algorithm is, I suspect that the other trickiest part of this bug will be designing a reasonable architecture-independent interface. Some masm calls correspond one-to-one with a single instruction, whereas others very much don't. In cases where there's a 1-1 mapping between the x64 and arm64 instructions, you might expose an API for generating that instruction; in cases where the two platforms do the same thing in two different ways, you might want to add MacroAssembler::doTheHighLevelAbstraction and let the two backends implement it in whichever way works best.
Hope this is a helpful starting point! Please feel free to ask questions, either here or in #spidermonkey.
|
|
||
Comment 3•1 year ago
|
||
Hello iain!
Hope you are doing well! sorry for the delay, i had some difficulty in understanding but heres a rough plan i have in mind reading from code and what high level functions we could break them into:
Along with this i think we have to make corresponding implementation of VRegister too? I couldnt find any example usage
I have tried my best to find existing uses if any to come up with these methods but I could be wrong too since dont have that much context of the codebase what do you think of the plan? does it seem to be in the right direction 😅
Thank you!
|
|
Assignee | |
Comment 4•1 year ago
|
||
Yeah, this seems like you're moving in the right direction!.
Instead of having a separate VRegister type, we just use FloatRegister. On most architectures*, the vector register file is overload on the floating point register file. In the same way that eg rax is a 64-bit register on x86, but there are some instructions that work on the low 32 bits (eax) or low 16 bits (ax), xmm0 is a 128-bit SIMD register that can also be used for 64-bit doubles or 32-bit floats. (Also, xmm0 is the low half of ymm0, which is the low half of zmm0, but I think we currently don't use anything past 128 bits.) You can see this in the huge list of existing SIMD instructions here in MacroAssembler.h, where are the arguments are float registers.
(* Everything we officially support, but apparently not RISC-V. But we don't have to worry about RISC-V here.)
Taking your list one at a time:
- InitializeVectorTable: In this case, we just need to load a value from an address in memory into a vector register. I think loadUnalignedSIMD128 is probably a good start here. Alternatively, since it looks like the nibble table is constant, maybe loadConstantSimd128.
- LoadVectorMaskConstant: This could be a loadConstantSimd128. Because it's a repeated pattern, there might also be a way to accomplish it more efficiently using splat.
- LoadToVectorTable: This looks like loadUnalignedSIMD128 (and in this case we can't use a constant because we're loading from the input string.)
- VectorAnd: this looks like bitwiseAndSIMD128.
- VectorRightShift: We define a lot of different shifts here, depending on whether you're shifting the whole register or individual lanes.
- VectorTableLookup: swizzleInt8x16 looks like it generates the right instructions?
And so on. What I'm mostly doing here (in cases where the answer requires more work than eg searching for the word "shift") is looking at the x86/arm64 instructions that V8 is generating by name, figuring out where we generate those instructions in our own code base, and then looking at the callers until I figure out whether the instruction already has a name.
In the above cases, it looks to me like we are directly exposing the instructions we need, so you shouldn't need to add many higher-level helpers (if any). The VectorCompareAndTest/"(not so sure...)" section is interesting, because the x86 and arm implementations don't seem to be precisely 1-1 in terms of instructions. I think your options here are to either figure out a way to write the logic in terms of shared instructions, or add some sort of higher-level operation. Here I would suggest digging in to understand how the algorithm works. It looks like the code up until this point has created two registers (bitmask and row), with 16 one-byte lanes, each representing a particular character from the input. I haven't looked closely enough at the code to be able to say exactly what the values are, but it looks like we want to find the first (if any) lane index where both registers are non-zero. (But double-check my work here.)
So one option would be something like masm.findFirstMatchingByteSimd128 that wraps all this into a single high-level operation with individual per-architecture implementations. There may also be ways to break it down into smaller ops, which might be more reusable. Play around a bit! Writing SIMD code is often as much an art as a science.
Hopefully this helps! Please feel free to ask follow-up questions.
|
|
Assignee | |
Comment 5•5 months ago
•
|
||
Use of SIMD code to speed up SkipUntilBitInTable appears to be the explanation for why V8 is roughly 20x faster on a regexp in TodoMVC-jquery. Matching V8's performance would be ~2% improvement on jquery.
js-perf-next: Implement this.
|
|
Assignee | |
Comment 6•2 months ago
|
||
Claude wrote a prototype of this patch, then I rewrote it by hand and polished up a bunch of stuff.
V8 has two other ops that it implements using SIMD (SkipUntilOneOfMasked and SkipUntilOneOfMasked3), but the latter was disabled because it regressed TodoMVC-jquery, and despite my best efforts, I can't write a single testcase that triggers the former in V8.
|
||
Updated•2 months ago
|
|
||
Comment 9•2 months ago
|
||
Backed out for causing spidermonkey failures
Backout Link
Push with failures
Failure Log
Failure line TEST-UNEXPECTED-FAIL | js\src\jit-test\tests\wasm\simd\baseline-bug1636235.js | [10428] Assertion failure: src0 == invalid_xmm || src0 == dst (Legacy SSE (pre-AVX) encoding requires the output register to be the same as the src0 input register), at D:\task_177974459518065\src\js\src\jit\x86-shared\BaseAssembler-x86-shared.h:4892 (code 2147483651, args "--wasm-compiler=optimizing --no-avx") [0.2 s]
Description
•