[YARR] Extend size of fixed characters bulk matching in 64bit platform
authoryusukesuzuki@slowstart.org <yusukesuzuki@slowstart.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 21 Aug 2018 03:29:32 +0000 (03:29 +0000)
committeryusukesuzuki@slowstart.org <yusukesuzuki@slowstart.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 21 Aug 2018 03:29:32 +0000 (03:29 +0000)
https://bugs.webkit.org/show_bug.cgi?id=181989

Patch by Yusuke Suzuki <utatane.tea@gmail.com> on 2018-08-20
Reviewed by Michael Saboff.

JSTests:

* stress/characters-regexp-ignore-case.js: Added.
(shouldBe):
(testH):
(testHe):
(testHel):
(testHell):
(testHello):
(testHelloW):
(testHelloWo):
(testHelloWor):
(testHelloWorl):
(testHelloWorld):
* stress/characters-regexp.js: Added.
(shouldBe):
(testH):
(testHe):
(testHel):
(testHell):
(testHello):
(testHelloW):
(testHelloWo):
(testHelloWor):
(testHelloWorl):
(testHelloWorld):

Source/JavaScriptCore:

This patch extends bulk matching style for fixed-sized characters.
In 64bit environment, the GPR can hold up to 8 characters. This change
reduces the code size since we can fuse multiple `mov` operations into one.

* assembler/LinkBuffer.h:
* runtime/Options.h:
* yarr/YarrJIT.cpp:
(JSC::Yarr::YarrGenerator::generatePatternCharacterOnce):
(JSC::Yarr::YarrGenerator::compile):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@235104 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JSTests/ChangeLog
JSTests/stress/characters-regexp-ignore-case.js [new file with mode: 0644]
JSTests/stress/characters-regexp.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/assembler/LinkBuffer.h
Source/JavaScriptCore/runtime/Options.h
Source/JavaScriptCore/yarr/YarrJIT.cpp

index 49011a0..7104839 100644 (file)
@@ -1,3 +1,35 @@
+2018-08-20  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [YARR] Extend size of fixed characters bulk matching in 64bit platform
+        https://bugs.webkit.org/show_bug.cgi?id=181989
+
+        Reviewed by Michael Saboff.
+
+        * stress/characters-regexp-ignore-case.js: Added.
+        (shouldBe):
+        (testH):
+        (testHe):
+        (testHel):
+        (testHell):
+        (testHello):
+        (testHelloW):
+        (testHelloWo):
+        (testHelloWor):
+        (testHelloWorl):
+        (testHelloWorld):
+        * stress/characters-regexp.js: Added.
+        (shouldBe):
+        (testH):
+        (testHe):
+        (testHel):
+        (testHell):
+        (testHello):
+        (testHelloW):
+        (testHelloWo):
+        (testHelloWor):
+        (testHelloWorl):
+        (testHelloWorld):
+
 2018-08-17  Saam barati  <sbarati@apple.com>
 
         intersectionOfPastValuesAtHead must filter values after they've observed an invalidation point
diff --git a/JSTests/stress/characters-regexp-ignore-case.js b/JSTests/stress/characters-regexp-ignore-case.js
new file mode 100644 (file)
index 0000000..a587f95
--- /dev/null
@@ -0,0 +1,77 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function testH(string) {
+    return string.match(/h/i);
+}
+noInline(testH);
+
+function testHe(string) {
+    return string.match(/he/i);
+}
+noInline(testHe);
+
+function testHel(string) {
+    return string.match(/hel/i);
+}
+noInline(testHel);
+
+function testHell(string) {
+    return string.match(/hell/i);
+}
+noInline(testHell);
+
+function testHello(string) {
+    return string.match(/hello/i);
+}
+noInline(testHello);
+
+function testHelloW(string) {
+    return string.match(/hellow/i);
+}
+noInline(testHelloW);
+
+function testHelloWo(string) {
+    return string.match(/hellowo/i);
+}
+noInline(testHelloWo);
+
+function testHelloWor(string) {
+    return string.match(/hellowor/i);
+}
+noInline(testHelloWor);
+
+function testHelloWorl(string) {
+    return string.match(/helloworl/i);
+}
+noInline(testHelloWorl);
+
+function testHelloWorld(string) {
+    return string.match(/helloworld/i);
+}
+noInline(testHelloWorld);
+
+for (var i = 0; i < 1e4; ++i) {
+    shouldBe(testH("HelloWorld")[0], `H`);
+    shouldBe(testHe("HelloWorld")[0], `He`);
+    shouldBe(testHel("HelloWorld")[0], `Hel`);
+    shouldBe(testHell("HelloWorld")[0], `Hell`);
+    shouldBe(testHello("HelloWorld")[0], `Hello`);
+    shouldBe(testHelloW("HelloWorld")[0], `HelloW`);
+    shouldBe(testHelloWo("HelloWorld")[0], `HelloWo`);
+    shouldBe(testHelloWor("HelloWorld")[0], `HelloWor`);
+    shouldBe(testHelloWorl("HelloWorld")[0], `HelloWorl`);
+    shouldBe(testHelloWorld("HelloWorld")[0], `HelloWorld`);
+    shouldBe(testH("HelloWorldこんにちは")[0], `H`);
+    shouldBe(testHe("HelloWorldこんにちは")[0], `He`);
+    shouldBe(testHel("HelloWorldこんにちは")[0], `Hel`);
+    shouldBe(testHell("HelloWorldこんにちは")[0], `Hell`);
+    shouldBe(testHello("HelloWorldこんにちは")[0], `Hello`);
+    shouldBe(testHelloW("HelloWorldこんにちは")[0], `HelloW`);
+    shouldBe(testHelloWo("HelloWorldこんにちは")[0], `HelloWo`);
+    shouldBe(testHelloWor("HelloWorldこんにちは")[0], `HelloWor`);
+    shouldBe(testHelloWorl("HelloWorldこんにちは")[0], `HelloWorl`);
+    shouldBe(testHelloWorld("HelloWorldこんにちは")[0], `HelloWorld`);
+}
diff --git a/JSTests/stress/characters-regexp.js b/JSTests/stress/characters-regexp.js
new file mode 100644 (file)
index 0000000..16b060e
--- /dev/null
@@ -0,0 +1,77 @@
+function shouldBe(actual, expected) {
+    if (actual !== expected)
+        throw new Error('bad value: ' + actual);
+}
+
+function testH(string) {
+    return string.match(/H/);
+}
+noInline(testH);
+
+function testHe(string) {
+    return string.match(/He/);
+}
+noInline(testHe);
+
+function testHel(string) {
+    return string.match(/Hel/);
+}
+noInline(testHel);
+
+function testHell(string) {
+    return string.match(/Hell/);
+}
+noInline(testHell);
+
+function testHello(string) {
+    return string.match(/Hello/);
+}
+noInline(testHello);
+
+function testHelloW(string) {
+    return string.match(/HelloW/);
+}
+noInline(testHelloW);
+
+function testHelloWo(string) {
+    return string.match(/HelloWo/);
+}
+noInline(testHelloWo);
+
+function testHelloWor(string) {
+    return string.match(/HelloWor/);
+}
+noInline(testHelloWor);
+
+function testHelloWorl(string) {
+    return string.match(/HelloWorl/);
+}
+noInline(testHelloWorl);
+
+function testHelloWorld(string) {
+    return string.match(/HelloWorld/);
+}
+noInline(testHelloWorld);
+
+for (var i = 0; i < 1e4; ++i) {
+    shouldBe(testH("HelloWorld")[0], `H`);
+    shouldBe(testHe("HelloWorld")[0], `He`);
+    shouldBe(testHel("HelloWorld")[0], `Hel`);
+    shouldBe(testHell("HelloWorld")[0], `Hell`);
+    shouldBe(testHello("HelloWorld")[0], `Hello`);
+    shouldBe(testHelloW("HelloWorld")[0], `HelloW`);
+    shouldBe(testHelloWo("HelloWorld")[0], `HelloWo`);
+    shouldBe(testHelloWor("HelloWorld")[0], `HelloWor`);
+    shouldBe(testHelloWorl("HelloWorld")[0], `HelloWorl`);
+    shouldBe(testHelloWorld("HelloWorld")[0], `HelloWorld`);
+    shouldBe(testH("HelloWorldこんにちは")[0], `H`);
+    shouldBe(testHe("HelloWorldこんにちは")[0], `He`);
+    shouldBe(testHel("HelloWorldこんにちは")[0], `Hel`);
+    shouldBe(testHell("HelloWorldこんにちは")[0], `Hell`);
+    shouldBe(testHello("HelloWorldこんにちは")[0], `Hello`);
+    shouldBe(testHelloW("HelloWorldこんにちは")[0], `HelloW`);
+    shouldBe(testHelloWo("HelloWorldこんにちは")[0], `HelloWo`);
+    shouldBe(testHelloWor("HelloWorldこんにちは")[0], `HelloWor`);
+    shouldBe(testHelloWorl("HelloWorldこんにちは")[0], `HelloWorl`);
+    shouldBe(testHelloWorld("HelloWorldこんにちは")[0], `HelloWorld`);
+}
index 6fb0e78..6ed2c6b 100644 (file)
@@ -1,3 +1,20 @@
+2018-08-20  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [YARR] Extend size of fixed characters bulk matching in 64bit platform
+        https://bugs.webkit.org/show_bug.cgi?id=181989
+
+        Reviewed by Michael Saboff.
+
+        This patch extends bulk matching style for fixed-sized characters.
+        In 64bit environment, the GPR can hold up to 8 characters. This change
+        reduces the code size since we can fuse multiple `mov` operations into one.
+
+        * assembler/LinkBuffer.h:
+        * runtime/Options.h:
+        * yarr/YarrJIT.cpp:
+        (JSC::Yarr::YarrGenerator::generatePatternCharacterOnce):
+        (JSC::Yarr::YarrGenerator::compile):
+
 2018-08-20  Devin Rousso  <drousso@apple.com>
 
         Web Inspector: allow breakpoints to be set for specific event listeners
index 06c2670..559908a 100644 (file)
@@ -386,6 +386,9 @@ bool shouldDumpDisassemblyFor(CodeBlock*);
 #define FINALIZE_DFG_CODE(linkBufferReference, resultPtrTag, ...)  \
     FINALIZE_CODE_IF((JSC::Options::asyncDisassembly() || JSC::Options::dumpDisassembly() || Options::dumpDFGDisassembly()), linkBufferReference, resultPtrTag, __VA_ARGS__)
 
+#define FINALIZE_REGEXP_CODE(linkBufferReference, resultPtrTag, dataLogFArgumentsForHeading)  \
+    FINALIZE_CODE_IF(JSC::Options::asyncDisassembly() || JSC::Options::dumpDisassembly() || Options::dumpRegExpDisassembly(), linkBufferReference, resultPtrTag, dataLogFArgumentsForHeading)
+
 } // namespace JSC
 
 #endif // ENABLE(ASSEMBLER)
index c1413d5..27396d2 100644 (file)
@@ -177,6 +177,7 @@ constexpr bool enableWebAssemblyStreamingApi = false;
     v(bool, asyncDisassembly, false, Normal, nullptr) \
     v(bool, dumpDFGDisassembly, false, Normal, "dumps disassembly of DFG function upon compilation") \
     v(bool, dumpFTLDisassembly, false, Normal, "dumps disassembly of FTL function upon compilation") \
+    v(bool, dumpRegExpDisassembly, false, Normal, "dumps disassembly of RegExp upon compilation") \
     v(bool, dumpAllDFGNodes, false, Normal, nullptr) \
     v(optionRange, bytecodeRangeToJITCompile, 0, Normal, "bytecode size range to allow compilation on, e.g. 1:100") \
     v(optionRange, bytecodeRangeToDFGCompile, 0, Normal, "bytecode size range to allow DFG compilation on, e.g. 1:100") \
index 8b2c412..a114ccf 100644 (file)
@@ -1128,12 +1128,16 @@ class YarrGenerator : public YarrJITInfo, private MacroAssembler {
         }
 
         const RegisterID character = regT0;
+#if CPU(X86_64) || CPU(ARM64)
+        unsigned maxCharactersAtOnce = m_charSize == Char8 ? 8 : 4;
+#else
         unsigned maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2;
-        unsigned ignoreCaseMask = 0;
+#endif
+        uint64_t ignoreCaseMask = 0;
 #if CPU(BIG_ENDIAN)
-        int allCharacters = ch << (m_charSize == Char8 ? 24 : 16);
+        uint64_t allCharacters = ch << (m_charSize == Char8 ? 24 : 16);
 #else
-        int allCharacters = ch;
+        uint64_t allCharacters = ch;
 #endif
         unsigned numberCharacters;
         unsigned startTermPosition = term->inputPosition;
@@ -1142,16 +1146,19 @@ class YarrGenerator : public YarrJITInfo, private MacroAssembler {
         // upper & lower case representations are converted to a character class.
         ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode));
 
-        if (m_pattern.ignoreCase() && isASCIIAlpha(ch))
+        if (m_pattern.ignoreCase() && isASCIIAlpha(ch)) {
 #if CPU(BIG_ENDIAN)
             ignoreCaseMask |= 32 << (m_charSize == Char8 ? 24 : 16);
 #else
             ignoreCaseMask |= 32;
 #endif
+        }
 
         for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) {
             PatternTerm* nextTerm = nextOp->m_term;
-            
+
+            // YarrJIT handles decoded surrogate pair as one character if unicode flag is enabled.
+            // Note that the numberCharacters become 1 while the width of the pattern character becomes 32bit in this case.
             if (nextTerm->type != PatternTerm::TypePatternCharacter
                 || nextTerm->quantityType != QuantifierFixedCount
                 || nextTerm->quantityMaxCount != 1
@@ -1179,49 +1186,129 @@ class YarrGenerator : public YarrJITInfo, private MacroAssembler {
             // upper & lower case representations are converted to a character class.
             ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(currentCharacter) || isCanonicallyUnique(currentCharacter, m_canonicalMode));
 
-            allCharacters |= (currentCharacter << shiftAmount);
+            allCharacters |= (static_cast<uint64_t>(currentCharacter) << shiftAmount);
 
             if ((m_pattern.ignoreCase()) && (isASCIIAlpha(currentCharacter)))
-                ignoreCaseMask |= 32 << shiftAmount;                    
+                ignoreCaseMask |= 32ULL << shiftAmount;
         }
 
         if (m_charSize == Char8) {
+            auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) {
+                op.m_jumps.append(jumpIfCharNotEquals(characters, offset, character));
+            };
+
+            auto check2 = [&] (Checked<unsigned> offset, uint16_t characters, uint16_t mask) {
+                load16Unaligned(negativeOffsetIndexedAddress(offset, character), character);
+                if (mask)
+                    or32(Imm32(mask), character);
+                op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask)));
+            };
+
+            auto check4 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) {
+                if (mask) {
+                    load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(offset, character), character);
+                    if (mask)
+                        or32(Imm32(mask), character);
+                    op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask)));
+                    return;
+                }
+                op.m_jumps.append(branch32WithUnalignedHalfWords(NotEqual, negativeOffsetIndexedAddress(offset, character), TrustedImm32(characters)));
+            };
+
+#if CPU(X86_64) || CPU(ARM64)
+            auto check8 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) {
+                load64(negativeOffsetIndexedAddress(offset, character), character);
+                if (mask)
+                    or64(TrustedImm64(mask), character);
+                op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask)));
+            };
+#endif
+
             switch (numberCharacters) {
             case 1:
-                op.m_jumps.append(jumpIfCharNotEquals(ch, m_checkedOffset - startTermPosition, character));
+                // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag.
+                check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff);
                 return;
             case 2: {
-                load16Unaligned(negativeOffsetIndexedAddress(m_checkedOffset - startTermPosition, character), character);
-                break;
+                check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff);
+                return;
             }
             case 3: {
-                load16Unaligned(negativeOffsetIndexedAddress(m_checkedOffset - startTermPosition, character), character);
-                if (ignoreCaseMask)
-                    or32(Imm32(ignoreCaseMask), character);
-                op.m_jumps.append(branch32(NotEqual, character, Imm32((allCharacters & 0xffff) | ignoreCaseMask)));
-                op.m_jumps.append(jumpIfCharNotEquals(allCharacters >> 16, m_checkedOffset - startTermPosition - 2, character));
+                check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff);
+                check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 16) & 0xff);
                 return;
             }
             case 4: {
-                load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(m_checkedOffset- startTermPosition, character), character);
-                break;
+                check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
+                return;
+            }
+#if CPU(X86_64) || CPU(ARM64)
+            case 5: {
+                check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
+                check1(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xff);
+                return;
             }
+            case 6: {
+                check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
+                check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff);
+                return;
+            }
+            case 7: {
+                check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
+                check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff);
+                check1(m_checkedOffset - startTermPosition - 6, (allCharacters >> 48) & 0xff);
+                return;
+            }
+            case 8: {
+                check8(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask);
+                return;
+            }
+#endif
             }
         } else {
+            auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) {
+                op.m_jumps.append(jumpIfCharNotEquals(characters, offset, character));
+            };
+
+            auto check2 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) {
+                if (mask) {
+                    load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(offset, character), character);
+                    if (mask)
+                        or32(Imm32(mask), character);
+                    op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask)));
+                    return;
+                }
+                op.m_jumps.append(branch32WithUnalignedHalfWords(NotEqual, negativeOffsetIndexedAddress(offset, character), TrustedImm32(characters)));
+            };
+
+#if CPU(X86_64) || CPU(ARM64)
+            auto check4 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) {
+                load64(negativeOffsetIndexedAddress(offset, character), character);
+                if (mask)
+                    or64(TrustedImm64(mask), character);
+                op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask)));
+            };
+#endif
+
             switch (numberCharacters) {
             case 1:
-                op.m_jumps.append(jumpIfCharNotEquals(ch, m_checkedOffset - term->inputPosition, character));
+                // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag.
+                check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff);
                 return;
             case 2:
-                load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(m_checkedOffset- term->inputPosition, character), character);
-                break;
+                check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
+                return;
+#if CPU(X86_64) || CPU(ARM64)
+            case 3:
+                check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
+                check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 32) & 0xffff);
+                return;
+            case 4:
+                check4(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask);
+                return;
+#endif
             }
         }
-
-        if (ignoreCaseMask)
-            or32(Imm32(ignoreCaseMask), character);
-        op.m_jumps.append(branch32(NotEqual, character, Imm32(allCharacters | ignoreCaseMask)));
-        return;
     }
     void backtrackPatternCharacterOnce(size_t opIndex)
     {
@@ -3472,7 +3559,7 @@ public:
             return;
         }
 
-        if (UNLIKELY(Options::dumpDisassembly()))
+        if (UNLIKELY(Options::dumpDisassembly() || Options::dumpRegExpDisassembly()))
             m_disassembler = std::make_unique<YarrDisassembler>(this);
 
         if (m_disassembler)
@@ -3546,14 +3633,14 @@ public:
 
         if (compileMode == MatchOnly) {
             if (m_charSize == Char8)
-                codeBlock.set8BitCodeMatchOnly(FINALIZE_CODE(linkBuffer, YarrMatchOnly8BitPtrTag, "Match-only 8-bit regular expression"));
+                codeBlock.set8BitCodeMatchOnly(FINALIZE_REGEXP_CODE(linkBuffer, YarrMatchOnly8BitPtrTag, "Match-only 8-bit regular expression"));
             else
-                codeBlock.set16BitCodeMatchOnly(FINALIZE_CODE(linkBuffer, YarrMatchOnly16BitPtrTag, "Match-only 16-bit regular expression"));
+                codeBlock.set16BitCodeMatchOnly(FINALIZE_REGEXP_CODE(linkBuffer, YarrMatchOnly16BitPtrTag, "Match-only 16-bit regular expression"));
         } else {
             if (m_charSize == Char8)
-                codeBlock.set8BitCode(FINALIZE_CODE(linkBuffer, Yarr8BitPtrTag, "8-bit regular expression"));
+                codeBlock.set8BitCode(FINALIZE_REGEXP_CODE(linkBuffer, Yarr8BitPtrTag, "8-bit regular expression"));
             else
-                codeBlock.set16BitCode(FINALIZE_CODE(linkBuffer, Yarr16BitPtrTag, "16-bit regular expression"));
+                codeBlock.set16BitCode(FINALIZE_REGEXP_CODE(linkBuffer, Yarr16BitPtrTag, "16-bit regular expression"));
         }
         if (m_failureReason)
             codeBlock.setFallBackWithFailureReason(*m_failureReason);