⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 244022 in webkit


Ignore:
Timestamp:
Apr 8, 2019, 10:09:18 AM (7 years ago)
Author:
bshafiei@apple.com
Message:

Cherry-pick r243642. rdar://problem/49589308

[YARR] Precompute BMP / non-BMP status when constructing character classes
​https://bugs.webkit.org/show_bug.cgi?id=196296

Reviewed by Keith Miller.

Changed CharacterClass::m_hasNonBMPCharacters into a character width bit field which
indicateis if the class includes characters from either BMP, non-BMP or both ranges.
This allows the recognizing code to eliminate checks for the width of a matched
characters when the class has only one width. The character width is needed to
determine if we advance 1 or 2 character. Also, the pre-computed width of character
classes that contains either all BMP or all non-BMP characters allows the parser to
use fixed widths for terms using those character classes. Changed both the code gen
scripts and Yarr compiler to compute this bit field during the construction of
character classes.

For JIT'ed code of character classes that contain either all BMP or all non-BMP
characters, we can eliminate the generic check we were doing do compute how much
to advance after sucessfully matching a character in the class.

Generic isBMP check BMP only non-BMP only
-------------- -------------- --------------
inc %r9d inc %r9d add $0x2, %r9d
cmp $0x10000, %eax
jl isBMP
cmp %edx, %esi
jz atEndOfString
inc %r9d
inc %esi

isBMP:

For character classes that contained non-BMP characters, we were always generating
the code in the left column. The middle column is the code we generate for character
classes that contain only BMP characters. The right column is the code we now
generate if the character class has only non-BMP characters. In the fix width cases,
we can eliminate both the isBMP check as well as the atEndOfString check. The
atEndOfstring check is eliminated since we know how many characters this character
class requires and that check can be factored out to the beginning of the current
alternative. For character classes that contain both BMP and non-BMP characters,
we still generate the generic left column.

This change is a ~8% perf progression on UniPoker and a ~2% improvement on RexBench
as a whole.

  • runtime/RegExp.cpp: (JSC::RegExp::matchCompareWithInterpreter):
  • runtime/RegExpInlines.h: (JSC::RegExp::matchInline):
  • yarr/YarrInterpreter.cpp: (JSC::Yarr::Interpreter::checkCharacterClassDontAdvanceInputForNonBMP): (JSC::Yarr::Interpreter::matchCharacterClass):
  • yarr/YarrJIT.cpp: (JSC::Yarr::YarrGenerator::optimizeAlternative): (JSC::Yarr::YarrGenerator::matchCharacterClass): (JSC::Yarr::YarrGenerator::advanceIndexAfterCharacterClassTermMatch): (JSC::Yarr::YarrGenerator::tryReadUnicodeCharImpl): (JSC::Yarr::YarrGenerator::generateCharacterClassOnce): (JSC::Yarr::YarrGenerator::generateCharacterClassFixed): (JSC::Yarr::YarrGenerator::generateCharacterClassGreedy): (JSC::Yarr::YarrGenerator::backtrackCharacterClassGreedy): (JSC::Yarr::YarrGenerator::generateCharacterClassNonGreedy): (JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy): (JSC::Yarr::YarrGenerator::generateEnter): (JSC::Yarr::YarrGenerator::YarrGenerator): (JSC::Yarr::YarrGenerator::compile):
  • yarr/YarrPattern.cpp: (JSC::Yarr::CharacterClassConstructor::CharacterClassConstructor): (JSC::Yarr::CharacterClassConstructor::reset): (JSC::Yarr::CharacterClassConstructor::charClass): (JSC::Yarr::CharacterClassConstructor::addSorted): (JSC::Yarr::CharacterClassConstructor::addSortedRange): (JSC::Yarr::CharacterClassConstructor::hasNonBMPCharacters): (JSC::Yarr::CharacterClassConstructor::characterWidths): (JSC::Yarr::PatternTerm::dump): (JSC::Yarr::anycharCreate):
  • yarr/YarrPattern.h: (JSC::Yarr::operator|): (JSC::Yarr::operator&): (JSC::Yarr::operator|=): (JSC::Yarr::CharacterClass::CharacterClass): (JSC::Yarr::CharacterClass::hasNonBMPCharacters): (JSC::Yarr::CharacterClass::hasOneCharacterSize): (JSC::Yarr::CharacterClass::hasOnlyNonBMPCharacters): (JSC::Yarr::PatternTerm::invert const): (JSC::Yarr::PatternTerm::invert): Deleted.
  • yarr/create_regex_tables:
  • yarr/generateYarrUnicodePropertyTables.py:

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

Location:
tags/Safari-608.1.15/Source/JavaScriptCore
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • tags/Safari-608.1.15/Source/JavaScriptCore/ChangeLog

    r243950 r244022  
     12019-04-08  Babak Shafiei  <bshafiei@apple.com>
     2
     3        Cherry-pick r243642. rdar://problem/49589308
     4
     5    [YARR] Precompute BMP / non-BMP status when constructing character classes
     6    https://bugs.webkit.org/show_bug.cgi?id=196296
     7   
     8    Reviewed by Keith Miller.
     9   
     10    Changed CharacterClass::m_hasNonBMPCharacters into a character width bit field which
     11    indicateis if the class includes characters from either BMP, non-BMP or both ranges.
     12    This allows the recognizing code to eliminate checks for the width of a matched
     13    characters when the class has only one width.  The character width is needed to
     14    determine if we advance 1 or 2 character.  Also, the pre-computed width of character
     15    classes that contains either all BMP or all non-BMP characters allows the parser to
     16    use fixed widths for terms using those character classes.  Changed both the code gen
     17    scripts and Yarr compiler to compute this bit field during the construction of
     18    character classes.
     19   
     20    For JIT'ed code of character classes that contain either all BMP or all non-BMP
     21    characters, we can eliminate the generic check we were doing do compute how much
     22    to advance after sucessfully matching a character in the class.
     23   
     24            Generic isBMP check      BMP only            non-BMP only
     25            --------------           --------------      --------------
     26            inc %r9d                 inc %r9d            add $0x2, %r9d
     27            cmp $0x10000, %eax
     28            jl isBMP
     29            cmp %edx, %esi
     30            jz atEndOfString
     31            inc %r9d
     32            inc %esi
     33     isBMP:
     34   
     35    For character classes that contained non-BMP characters, we were always generating
     36    the code in the left column.  The middle column is the code we generate for character
     37    classes that contain only BMP characters.  The right column is the code we now
     38    generate if the character class has only non-BMP characters.  In the fix width cases,
     39    we can eliminate both the isBMP check as well as the atEndOfString check.  The
     40    atEndOfstring check is eliminated since we know how many characters this character
     41    class requires and that check can be factored out to the beginning of the current
     42    alternative.  For character classes that contain both BMP and non-BMP characters,
     43    we still generate the generic left column.
     44   
     45    This change is a ~8% perf progression on UniPoker and a ~2% improvement on RexBench
     46    as a whole.
     47   
     48    * runtime/RegExp.cpp:
     49    (JSC::RegExp::matchCompareWithInterpreter):
     50    * runtime/RegExpInlines.h:
     51    (JSC::RegExp::matchInline):
     52    * yarr/YarrInterpreter.cpp:
     53    (JSC::Yarr::Interpreter::checkCharacterClassDontAdvanceInputForNonBMP):
     54    (JSC::Yarr::Interpreter::matchCharacterClass):
     55    * yarr/YarrJIT.cpp:
     56    (JSC::Yarr::YarrGenerator::optimizeAlternative):
     57    (JSC::Yarr::YarrGenerator::matchCharacterClass):
     58    (JSC::Yarr::YarrGenerator::advanceIndexAfterCharacterClassTermMatch):
     59    (JSC::Yarr::YarrGenerator::tryReadUnicodeCharImpl):
     60    (JSC::Yarr::YarrGenerator::generateCharacterClassOnce):
     61    (JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
     62    (JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
     63    (JSC::Yarr::YarrGenerator::backtrackCharacterClassGreedy):
     64    (JSC::Yarr::YarrGenerator::generateCharacterClassNonGreedy):
     65    (JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):
     66    (JSC::Yarr::YarrGenerator::generateEnter):
     67    (JSC::Yarr::YarrGenerator::YarrGenerator):
     68    (JSC::Yarr::YarrGenerator::compile):
     69    * yarr/YarrPattern.cpp:
     70    (JSC::Yarr::CharacterClassConstructor::CharacterClassConstructor):
     71    (JSC::Yarr::CharacterClassConstructor::reset):
     72    (JSC::Yarr::CharacterClassConstructor::charClass):
     73    (JSC::Yarr::CharacterClassConstructor::addSorted):
     74    (JSC::Yarr::CharacterClassConstructor::addSortedRange):
     75    (JSC::Yarr::CharacterClassConstructor::hasNonBMPCharacters):
     76    (JSC::Yarr::CharacterClassConstructor::characterWidths):
     77    (JSC::Yarr::PatternTerm::dump):
     78    (JSC::Yarr::anycharCreate):
     79    * yarr/YarrPattern.h:
     80    (JSC::Yarr::operator|):
     81    (JSC::Yarr::operator&):
     82    (JSC::Yarr::operator|=):
     83    (JSC::Yarr::CharacterClass::CharacterClass):
     84    (JSC::Yarr::CharacterClass::hasNonBMPCharacters):
     85    (JSC::Yarr::CharacterClass::hasOneCharacterSize):
     86    (JSC::Yarr::CharacterClass::hasOnlyNonBMPCharacters):
     87    (JSC::Yarr::PatternTerm::invert const):
     88    (JSC::Yarr::PatternTerm::invert): Deleted.
     89    * yarr/create_regex_tables:
     90    * yarr/generateYarrUnicodePropertyTables.py:
     91   
     92   
     93    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243642 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     94
     95    2019-03-28  Michael Saboff  <msaboff@apple.com>
     96
     97            [YARR] Precompute BMP / non-BMP status when constructing character classes
     98            https://bugs.webkit.org/show_bug.cgi?id=196296
     99
     100            Reviewed by Keith Miller.
     101
     102            Changed CharacterClass::m_hasNonBMPCharacters into a character width bit field which
     103            indicateis if the class includes characters from either BMP, non-BMP or both ranges.
     104            This allows the recognizing code to eliminate checks for the width of a matched
     105            characters when the class has only one width.  The character width is needed to
     106            determine if we advance 1 or 2 character.  Also, the pre-computed width of character
     107            classes that contains either all BMP or all non-BMP characters allows the parser to
     108            use fixed widths for terms using those character classes.  Changed both the code gen
     109            scripts and Yarr compiler to compute this bit field during the construction of
     110            character classes.
     111
     112            For JIT'ed code of character classes that contain either all BMP or all non-BMP
     113            characters, we can eliminate the generic check we were doing do compute how much
     114            to advance after sucessfully matching a character in the class.
     115
     116                    Generic isBMP check      BMP only            non-BMP only
     117                    --------------           --------------      --------------
     118                    inc %r9d                 inc %r9d            add $0x2, %r9d
     119                    cmp $0x10000, %eax
     120                    jl isBMP
     121                    cmp %edx, %esi
     122                    jz atEndOfString
     123                    inc %r9d
     124                    inc %esi
     125             isBMP:
     126
     127            For character classes that contained non-BMP characters, we were always generating
     128            the code in the left column.  The middle column is the code we generate for character
     129            classes that contain only BMP characters.  The right column is the code we now
     130            generate if the character class has only non-BMP characters.  In the fix width cases,
     131            we can eliminate both the isBMP check as well as the atEndOfString check.  The
     132            atEndOfstring check is eliminated since we know how many characters this character
     133            class requires and that check can be factored out to the beginning of the current
     134            alternative.  For character classes that contain both BMP and non-BMP characters,
     135            we still generate the generic left column.
     136
     137            This change is a ~8% perf progression on UniPoker and a ~2% improvement on RexBench
     138            as a whole.
     139
     140            * runtime/RegExp.cpp:
     141            (JSC::RegExp::matchCompareWithInterpreter):
     142            * runtime/RegExpInlines.h:
     143            (JSC::RegExp::matchInline):
     144            * yarr/YarrInterpreter.cpp:
     145            (JSC::Yarr::Interpreter::checkCharacterClassDontAdvanceInputForNonBMP):
     146            (JSC::Yarr::Interpreter::matchCharacterClass):
     147            * yarr/YarrJIT.cpp:
     148            (JSC::Yarr::YarrGenerator::optimizeAlternative):
     149            (JSC::Yarr::YarrGenerator::matchCharacterClass):
     150            (JSC::Yarr::YarrGenerator::advanceIndexAfterCharacterClassTermMatch):
     151            (JSC::Yarr::YarrGenerator::tryReadUnicodeCharImpl):
     152            (JSC::Yarr::YarrGenerator::generateCharacterClassOnce):
     153            (JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
     154            (JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
     155            (JSC::Yarr::YarrGenerator::backtrackCharacterClassGreedy):
     156            (JSC::Yarr::YarrGenerator::generateCharacterClassNonGreedy):
     157            (JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):
     158            (JSC::Yarr::YarrGenerator::generateEnter):
     159            (JSC::Yarr::YarrGenerator::YarrGenerator):
     160            (JSC::Yarr::YarrGenerator::compile):
     161            * yarr/YarrPattern.cpp:
     162            (JSC::Yarr::CharacterClassConstructor::CharacterClassConstructor):
     163            (JSC::Yarr::CharacterClassConstructor::reset):
     164            (JSC::Yarr::CharacterClassConstructor::charClass):
     165            (JSC::Yarr::CharacterClassConstructor::addSorted):
     166            (JSC::Yarr::CharacterClassConstructor::addSortedRange):
     167            (JSC::Yarr::CharacterClassConstructor::hasNonBMPCharacters):
     168            (JSC::Yarr::CharacterClassConstructor::characterWidths):
     169            (JSC::Yarr::PatternTerm::dump):
     170            (JSC::Yarr::anycharCreate):
     171            * yarr/YarrPattern.h:
     172            (JSC::Yarr::operator|):
     173            (JSC::Yarr::operator&):
     174            (JSC::Yarr::operator|=):
     175            (JSC::Yarr::CharacterClass::CharacterClass):
     176            (JSC::Yarr::CharacterClass::hasNonBMPCharacters):
     177            (JSC::Yarr::CharacterClass::hasOneCharacterSize):
     178            (JSC::Yarr::CharacterClass::hasOnlyNonBMPCharacters):
     179            (JSC::Yarr::PatternTerm::invert const):
     180            (JSC::Yarr::PatternTerm::invert): Deleted.
     181            * yarr/create_regex_tables:
     182            * yarr/generateYarrUnicodePropertyTables.py:
     183
    11842019-04-05  Kocsen Chung  <kocsen_chung@apple.com>
    2185

  • tags/Safari-608.1.15/Source/JavaScriptCore/runtime/RegExp.cpp

    r243950 r244022  
    386386        interpreterOffsetVector[j] = -1;
    387387
    388     interpreterResult = Yarr::interpret(m_regExpBytecode.get(), s, startOffset, interpreterOffsetVector);
     388    interpreterResult = Yarr::interpret(m_regExpBytecode.get(), s, startOffset, reinterpret_cast<unsigned*>(interpreterOffsetVector));
    389389
    390390    if (jitResult != interpreterResult)
    … …  
    403403
    404404        if (jitResult != interpreterResult) {
    405             dataLogF("    JIT result = %d, blah interpreted result = %d\n", jitResult, interpreterResult);
     405            dataLogF("    JIT result = %d, interpreted result = %d\n", jitResult, interpreterResult);
    406406            differences--;
    407407        } else {

  • tags/Safari-608.1.15/Source/JavaScriptCore/runtime/RegExpInlines.h

    r243950 r244022  
    182182
    183183#if ENABLE(YARR_JIT_DEBUG)
    184         matchCompareWithInterpreter(s, startOffset, offsetVector, result);
     184        if (m_state == JITCode) {
     185            byteCodeCompileIfNecessary(&vm);
     186            matchCompareWithInterpreter(s, startOffset, offsetVector, result);
     187        }
    185188#endif
    186189    } else

  • tags/Safari-608.1.15/Source/JavaScriptCore/yarr/YarrInterpreter.cpp

    r243950 r244022  
    429429        return invert ? !match : match;
    430430    }
     431   
     432    bool checkCharacterClassDontAdvanceInputForNonBMP(CharacterClass* characterClass, unsigned negativeInputOffset)
     433    {
     434        int readCharacter = characterClass->hasOnlyNonBMPCharacters() ? input.readSurrogatePairChecked(negativeInputOffset) :  input.readChecked(negativeInputOffset);
     435        return testCharacterClass(characterClass, readCharacter);
     436    }
    431437
    432438    bool tryConsumeBackReference(int matchBegin, int matchEnd, unsigned negativeInputOffset)
    … …  
    559565        case QuantifierFixedCount: {
    560566            if (unicode) {
     567                CharacterClass* charClass = term.atom.characterClass;
    561568                backTrack->begin = input.getPos();
    562569                unsigned matchAmount = 0;
    563570                for (matchAmount = 0; matchAmount < term.atom.quantityMaxCount; ++matchAmount) {
    564                     if (!checkCharacterClass(term.atom.characterClass, term.invert(), term.inputPosition - matchAmount)) {
    565                         input.setPos(backTrack->begin);
    566                         return false;
     571                    if (term.invert()) {
     572                        if (!checkCharacterClass(charClass, term.invert(), term.inputPosition - matchAmount)) {
     573                            input.setPos(backTrack->begin);
     574                            return false;
     575                        }
     576                    } else {
     577                        unsigned matchOffset = matchAmount * (charClass->hasOnlyNonBMPCharacters() ? 2 : 1);
     578                        if (!checkCharacterClassDontAdvanceInputForNonBMP(charClass, term.inputPosition - matchOffset)) {
     579                            input.setPos(backTrack->begin);
     580                            return false;
     581                        }
    567582                    }
    568583                }

  • tags/Safari-608.1.15/Source/JavaScriptCore/yarr/YarrJIT.cpp

    r243950 r244022  
    7373    static const RegisterID initialStart = ARM64Registers::x11;
    7474    static const RegisterID supplementaryPlanesBase = ARM64Registers::x12;
    75     static const RegisterID surrogateTagMask = ARM64Registers::x13;
    76     static const RegisterID leadingSurrogateTag = ARM64Registers::x14;
    77     static const RegisterID trailingSurrogateTag = ARM64Registers::x15;
     75    static const RegisterID leadingSurrogateTag = ARM64Registers::x13;
     76    static const RegisterID trailingSurrogateTag = ARM64Registers::x14;
     77    static const RegisterID endOfStringAddress = ARM64Registers::x15;
    7878
    7979    static const RegisterID returnRegister = ARM64Registers::x0;
    8080    static const RegisterID returnRegister2 = ARM64Registers::x1;
    8181
     82    const TrustedImm32 surrogateTagMask = TrustedImm32(0xfffffc00);
    8283#define HAVE_INITIAL_START_REG
    8384#define JIT_UNICODE_EXPRESSIONS
    … …  
    144145    static const RegisterID regUnicodeInputAndTrail = X86Registers::r13;
    145146    static const RegisterID leadingSurrogateTag = X86Registers::r14;
    146     static const RegisterID trailingSurrogateTag = X86Registers::r15;
     147    static const RegisterID endOfStringAddress = X86Registers::r15;
    147148
    148149    static const RegisterID returnRegister = X86Registers::eax;
    … …  
    150151
    151152    const TrustedImm32 supplementaryPlanesBase = TrustedImm32(0x10000);
     153    const TrustedImm32 trailingSurrogateTag = TrustedImm32(0xdc00);
    152154    const TrustedImm32 surrogateTagMask = TrustedImm32(0xfffffc00);
    153155#define HAVE_INITIAL_START_REG
    … …  
    320322            if ((term.type == PatternTerm::TypeCharacterClass)
    321323                && (term.quantityType == QuantifierFixedCount)
    322                 && (!m_decodeSurrogatePairs || (!term.characterClass->m_hasNonBMPCharacters && !term.m_invert))
     324                && (!m_decodeSurrogatePairs || (term.characterClass->hasOneCharacterSize() && !term.m_invert))
    323325                && (nextTerm.type == PatternTerm::TypePatternCharacter)
    324326                && (nextTerm.quantityType == QuantifierFixedCount)) {
    … …  
    384386            return;
    385387        }
     388
    386389        JumpList unicodeFail;
    387390        if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
    … …  
    448451            unicodeFail.link(this);
    449452    }
     453
     454#ifdef JIT_UNICODE_EXPRESSIONS
     455    void advanceIndexAfterCharacterClassTermMatch(const PatternTerm* term, JumpList& failures, const RegisterID character)
     456    {
     457        ASSERT(term->type == PatternTerm::TypeCharacterClass);
     458
     459        if (term->characterClass->hasOneCharacterSize() && !term->invert())
     460            add32(TrustedImm32(term->characterClass->hasNonBMPCharacters() ? 2 : 1), index);
     461        else {
     462            add32(TrustedImm32(1), index);
     463            failures.append(atEndOfInput());
     464            Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
     465            add32(TrustedImm32(1), index);
     466            isBMPChar.link(this);
     467        }
     468    }
     469#endif
    450470
    451471    // Jumps if input not available; will have (incorrectly) incremented already!
    … …  
    521541
    522542        JumpList notUnicode;
     543
    523544        load16Unaligned(regUnicodeInputAndTrail, resultReg);
    524545        and32(surrogateTagMask, resultReg, regT2);
    525546        notUnicode.append(branch32(NotEqual, regT2, leadingSurrogateTag));
    526547        addPtr(TrustedImm32(2), regUnicodeInputAndTrail);
    527         getEffectiveAddress(BaseIndex(input, length, TimesTwo), regT2);
    528         notUnicode.append(branch32(AboveOrEqual, regUnicodeInputAndTrail, regT2));
     548        notUnicode.append(branchPtr(AboveOrEqual, regUnicodeInputAndTrail, endOfStringAddress));
    529549        load16Unaligned(Address(regUnicodeInputAndTrail), regUnicodeInputAndTrail);
    530550        and32(surrogateTagMask, regUnicodeInputAndTrail, regT2);
    … …  
    17351755        }
    17361756#ifdef JIT_UNICODE_EXPRESSIONS
    1737         if (m_decodeSurrogatePairs) {
     1757        if (m_decodeSurrogatePairs && (!term->characterClass->hasOneCharacterSize() || term->invert())) {
    17381758            Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
    17391759            add32(TrustedImm32(1), index);
    … …  
    17691789
    17701790        move(index, countRegister);
    1771         sub32(Imm32(term->quantityMaxCount.unsafeGet()), countRegister);
     1791
     1792        Checked<unsigned> scaledMaxCount = term->quantityMaxCount;
     1793
     1794#ifdef JIT_UNICODE_EXPRESSIONS
     1795        if (m_decodeSurrogatePairs && term->characterClass->hasOnlyNonBMPCharacters() && !term->invert())
     1796            scaledMaxCount *= 2;
     1797#endif
     1798        sub32(Imm32(scaledMaxCount.unsafeGet()), countRegister);
    17721799
    17731800        Label loop(this);
    17741801        JumpList matchDest;
    1775         readCharacter(m_checkedOffset - term->inputPosition - term->quantityMaxCount, character, countRegister);
     1802        readCharacter(m_checkedOffset - term->inputPosition - scaledMaxCount, character, countRegister);
    17761803        // If we are matching the "any character" builtin class we only need to read the
    17771804        // character and don't need to match as it will always succeed.
    … …  
    17871814        }
    17881815
    1789         add32(TrustedImm32(1), countRegister);
    17901816#ifdef JIT_UNICODE_EXPRESSIONS
    17911817        if (m_decodeSurrogatePairs) {
    1792             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
    1793             op.m_jumps.append(atEndOfInput());
     1818            if (term->characterClass->hasOneCharacterSize() && !term->invert())
     1819                add32(TrustedImm32(term->characterClass->hasNonBMPCharacters() ? 2 : 1), countRegister);
     1820            else {
     1821                add32(TrustedImm32(1), countRegister);
     1822                Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
     1823                op.m_jumps.append(atEndOfInput());
     1824                add32(TrustedImm32(1), countRegister);
     1825                add32(TrustedImm32(1), index);
     1826                isBMPChar.link(this);
     1827            }
     1828        } else
     1829#endif
    17941830            add32(TrustedImm32(1), countRegister);
    1795             add32(TrustedImm32(1), index);
    1796             isBMPChar.link(this);
    1797         }
    1798 #endif
    17991831        branch32(NotEqual, countRegister, index).linkTo(loop, this);
    18001832    }
    … …  
    18121844        const RegisterID countRegister = regT1;
    18131845
    1814         if (m_decodeSurrogatePairs)
     1846        if (m_decodeSurrogatePairs && (!term->characterClass->hasOneCharacterSize() || term->invert()))
    18151847            storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex());
    18161848        move(TrustedImm32(0), countRegister);
    … …  
    18261858            JumpList matchDest;
    18271859            readCharacter(m_checkedOffset - term->inputPosition, character);
    1828             // If we are matching the "any character" builtin class we only need to read the
    1829             // character and don't need to match as it will always succeed.
     1860            // If we are matching the "any character" builtin class for non-unicode patterns,
     1861            // we only need to read the character and don't need to match as it will always succeed.
    18301862            if (!term->characterClass->m_anyCharacter) {
    18311863                matchCharacterClass(character, matchDest, term->characterClass);
    … …  
    18351867        }
    18361868
    1837         add32(TrustedImm32(1), index);
    18381869#ifdef JIT_UNICODE_EXPRESSIONS
    1839         if (m_decodeSurrogatePairs) {
    1840             failures.append(atEndOfInput());
    1841             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
     1870        if (m_decodeSurrogatePairs)
     1871            advanceIndexAfterCharacterClassTermMatch(term, failures, character);
     1872        else
     1873#endif
    18421874            add32(TrustedImm32(1), index);
    1843             isBMPChar.link(this);
    1844         }
    1845 #endif
    18461875        add32(TrustedImm32(1), countRegister);
    18471876
    … …  
    18691898        m_backtrackingState.append(branchTest32(Zero, countRegister));
    18701899        sub32(TrustedImm32(1), countRegister);
     1900        storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex());
     1901
    18711902        if (!m_decodeSurrogatePairs)
    18721903            sub32(TrustedImm32(1), index);
     1904        else if (term->characterClass->hasOneCharacterSize() && !term->invert())
     1905            sub32(TrustedImm32(term->characterClass->hasNonBMPCharacters() ? 2 : 1), index);
    18731906        else {
     1907            // Rematch one less
    18741908            const RegisterID character = regT0;
    18751909
    18761910            loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), index);
    1877             // Rematch one less
    1878             storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex());
    18791911
    18801912            Label rematchLoop(this);
    … …  
    19061938        move(TrustedImm32(0), countRegister);
    19071939        op.m_reentry = label();
    1908         if (m_decodeSurrogatePairs)
    1909             storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex());
    1910         storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex());
     1940        if (m_decodeSurrogatePairs) {
     1941            if (!term->characterClass->hasOneCharacterSize() || term->invert())
     1942                storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex());
     1943            storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex());
     1944        }
    19111945    }
    19121946
    … …  
    19231957        m_backtrackingState.link(this);
    19241958
    1925         if (m_decodeSurrogatePairs)
    1926             loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), index);
    1927         loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), countRegister);
     1959        if (m_decodeSurrogatePairs) {
     1960            if (!term->characterClass->hasOneCharacterSize() || term->invert())
     1961                loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), index);
     1962            loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), countRegister);
     1963        }
    19281964
    19291965        nonGreedyFailures.append(atEndOfInput());
    … …  
    19321968        JumpList matchDest;
    19331969        readCharacter(m_checkedOffset - term->inputPosition, character);
    1934         // If we are matching the "any character" builtin class we only need to read the
    1935         // character and don't need to match as it will always succeed.
     1970        // If we are matching the "any character" builtin class for non-unicode patterns,
     1971        // we only need to read the character and don't need to match as it will always succeed.
    19361972        if (term->invert() || !term->characterClass->m_anyCharacter) {
    19371973            matchCharacterClass(character, matchDest, term->characterClass);
    … …  
    19451981        }
    19461982
    1947         add32(TrustedImm32(1), index);
    19481983#ifdef JIT_UNICODE_EXPRESSIONS
    1949         if (m_decodeSurrogatePairs) {
    1950             nonGreedyFailures.append(atEndOfInput());
    1951             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
     1984        if (m_decodeSurrogatePairs)
     1985            advanceIndexAfterCharacterClassTermMatch(term, nonGreedyFailures, character);
     1986        else
     1987#endif
    19521988            add32(TrustedImm32(1), index);
    1953             isBMPChar.link(this);
    1954         }
    1955 #endif
    19561989        add32(TrustedImm32(1), countRegister);
    19571990
    … …  
    37013734
    37023735            move(TrustedImm32(0xd800), leadingSurrogateTag);
    3703             move(TrustedImm32(0xdc00), trailingSurrogateTag);
    37043736        }
    37053737        // The ABI doesn't guarantee the upper bits are zero on unsigned arguments, so clear them ourselves.
    … …  
    37353767            pushPair(framePointerRegister, linkRegister);
    37363768            move(TrustedImm32(0x10000), supplementaryPlanesBase);
    3737             move(TrustedImm32(0xfffffc00), surrogateTagMask);
    37383769            move(TrustedImm32(0xd800), leadingSurrogateTag);
    37393770            move(TrustedImm32(0xdc00), trailingSurrogateTag);
    … …  
    38163847        , m_decodeSurrogatePairs(m_charSize == Char16 && m_pattern.unicode())
    38173848        , m_unicodeIgnoreCase(m_pattern.unicode() && m_pattern.ignoreCase())
     3849        , m_fixedSizedAlternative(false)
    38183850        , m_canonicalMode(m_pattern.unicode() ? CanonicalMode::Unicode : CanonicalMode::UCS2)
    38193851#if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)
    … …  
    38693901        generateFailReturn();
    38703902        hasInput.link(this);
     3903
     3904#ifdef JIT_UNICODE_EXPRESSIONS
     3905        if (m_decodeSurrogatePairs)
     3906            getEffectiveAddress(BaseIndex(input, length, TimesTwo), endOfStringAddress);
     3907#endif
    38713908
    38723909#if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)
    … …  
    41644201    bool m_decodeSurrogatePairs;
    41654202    bool m_unicodeIgnoreCase;
     4203    bool m_fixedSizedAlternative;
    41664204    CanonicalMode m_canonicalMode;
    41674205#if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)

  • tags/Safari-608.1.15/Source/JavaScriptCore/yarr/YarrPattern.cpp

    r243950 r244022  
    4646    CharacterClassConstructor(bool isCaseInsensitive, CanonicalMode canonicalMode)
    4747        : m_isCaseInsensitive(isCaseInsensitive)
    48         , m_hasNonBMPCharacters(false)
    4948        , m_anyCharacter(false)
     49        , m_characterWidths(CharacterClassWidths::Unknown)
    5050        , m_canonicalMode(canonicalMode)
    5151    {
    … …  
    5858        m_matchesUnicode.clear();
    5959        m_rangesUnicode.clear();
    60         m_hasNonBMPCharacters = false;
    6160        m_anyCharacter = false;
     61        m_characterWidths = CharacterClassWidths::Unknown;
    6262    }
    6363
    … …  
    247247        characterClass->m_matchesUnicode.swap(m_matchesUnicode);
    248248        characterClass->m_rangesUnicode.swap(m_rangesUnicode);
    249         characterClass->m_hasNonBMPCharacters = hasNonBMPCharacters();
    250249        characterClass->m_anyCharacter = anyCharacter();
    251 
    252         m_hasNonBMPCharacters = false;
     250        characterClass->m_characterWidths = characterWidths();
     251
    253252        m_anyCharacter = false;
     253        m_characterWidths = CharacterClassWidths::Unknown;
    254254
    255255        return characterClass;
    … …  
    267267        unsigned range = matches.size();
    268268
    269         if (!U_IS_BMP(ch))
    270             m_hasNonBMPCharacters = true;
     269        m_characterWidths |= (U_IS_BMP(ch) ? CharacterClassWidths::HasBMPChars : CharacterClassWidths::HasNonBMPChars);
    271270
    272271        // binary chop, find position to insert char.
    … …  
    317316        size_t end = ranges.size();
    318317
     318        if (U_IS_BMP(lo))
     319            m_characterWidths |= CharacterClassWidths::HasBMPChars;
    319320        if (!U_IS_BMP(hi))
    320             m_hasNonBMPCharacters = true;
     321            m_characterWidths |= CharacterClassWidths::HasNonBMPChars;
    321322
    322323        // Simple linear scan - I doubt there are that many ranges anyway...
    … …  
    409410    bool hasNonBMPCharacters()
    410411    {
    411         return m_hasNonBMPCharacters;
     412        return m_characterWidths & CharacterClassWidths::HasNonBMPChars;
     413    }
     414
     415    CharacterClassWidths characterWidths()
     416    {
     417        return m_characterWidths;
    412418    }
    413419
    … …  
    418424
    419425    bool m_isCaseInsensitive : 1;
    420     bool m_hasNonBMPCharacters : 1;
    421426    bool m_anyCharacter : 1;
     427    CharacterClassWidths m_characterWidths;
     428   
    422429    CanonicalMode m_canonicalMode;
    423430
    … …  
    837844                    term.frameLocation = currentCallFrameSize;
    838845                    currentCallFrameSize += YarrStackSpaceForBackTrackInfoCharacterClass;
    839                     currentInputPosition += term.quantityMaxCount;
    840                     alternative->m_hasFixedSize = false;
     846                    if (term.characterClass->hasOneCharacterSize() && !term.invert()) {
     847                        Checked<unsigned, RecordOverflow> tempCount = term.quantityMaxCount;
     848                        tempCount *= term.characterClass->hasNonBMPCharacters() ? 2 : 1;
     849                        if (tempCount.hasOverflowed())
     850                            return ErrorCode::OffsetTooLarge;
     851                        currentInputPosition += tempCount;
     852                    } else {
     853                        currentInputPosition += term.quantityMaxCount;
     854                        alternative->m_hasFixedSize = false;
     855                    }
    841856                } else
    842857                    currentInputPosition += term.quantityMaxCount;
    … …  
    13191334    case TypeCharacterClass:
    13201335        out.print("character class ");
     1336        out.printf("inputPosition %u ", inputPosition);
    13211337        dumpCharacterClass(out, thisPattern, characterClass);
    13221338        dumpQuantifier(out);
    … …  
    14621478    characterClass->m_ranges.append(CharacterRange(0x00, 0x7f));
    14631479    characterClass->m_rangesUnicode.append(CharacterRange(0x0080, 0x10ffff));
    1464     characterClass->m_hasNonBMPCharacters = true;
     1480    characterClass->m_characterWidths = CharacterClassWidths::HasBothBMPAndNonBMP;
    14651481    characterClass->m_anyCharacter = true;
    14661482    return characterClass;

  • tags/Safari-608.1.15/Source/JavaScriptCore/yarr/YarrPattern.h

    r243950 r244022  
    5353};
    5454
     55enum struct CharacterClassWidths : unsigned char {
     56    Unknown = 0x0,
     57    HasBMPChars = 0x1,
     58    HasNonBMPChars = 0x2,
     59    HasBothBMPAndNonBMP = HasBMPChars | HasNonBMPChars
     60};
     61
     62inline CharacterClassWidths operator|(CharacterClassWidths lhs, CharacterClassWidths rhs)
     63{
     64    return static_cast<CharacterClassWidths>(static_cast<unsigned>(lhs) | static_cast<unsigned>(rhs));
     65}
     66
     67inline bool operator&(CharacterClassWidths lhs, CharacterClassWidths rhs)
     68{
     69    return static_cast<unsigned>(lhs) & static_cast<unsigned>(rhs);
     70}
     71
     72inline CharacterClassWidths& operator|=(CharacterClassWidths& lhs, CharacterClassWidths rhs)
     73{
     74    lhs = lhs | rhs;
     75    return lhs;
     76}
     77
    5578struct CharacterClass {
    5679    WTF_MAKE_FAST_ALLOCATED;
    … …  
    6184    CharacterClass()
    6285        : m_table(0)
    63         , m_hasNonBMPCharacters(false)
     86        , m_characterWidths(CharacterClassWidths::Unknown)
    6487        , m_anyCharacter(false)
    6588    {
    … …  
    6790    CharacterClass(const char* table, bool inverted)
    6891        : m_table(table)
     92        , m_characterWidths(CharacterClassWidths::Unknown)
    6993        , m_tableInverted(inverted)
    70         , m_hasNonBMPCharacters(false)
    7194        , m_anyCharacter(false)
    7295    {
    7396    }
    74     CharacterClass(std::initializer_list<UChar32> matches, std::initializer_list<CharacterRange> ranges, std::initializer_list<UChar32> matchesUnicode, std::initializer_list<CharacterRange> rangesUnicode)
     97    CharacterClass(std::initializer_list<UChar32> matches, std::initializer_list<CharacterRange> ranges, std::initializer_list<UChar32> matchesUnicode, std::initializer_list<CharacterRange> rangesUnicode, CharacterClassWidths widths)
    7598        : m_matches(matches)
    7699        , m_ranges(ranges)
    … …  
    78101        , m_rangesUnicode(rangesUnicode)
    79102        , m_table(0)
     103        , m_characterWidths(widths)
    80104        , m_tableInverted(false)
    81         , m_hasNonBMPCharacters(false)
    82105        , m_anyCharacter(false)
    83106    {
    84107    }
    85108
     109    bool hasNonBMPCharacters() { return m_characterWidths & CharacterClassWidths::HasNonBMPChars; }
     110
     111    bool hasOneCharacterSize() { return m_characterWidths == CharacterClassWidths::HasBMPChars || m_characterWidths == CharacterClassWidths::HasNonBMPChars; }
     112    bool hasOnlyNonBMPCharacters() { return m_characterWidths == CharacterClassWidths::HasNonBMPChars; }
     113   
    86114    Vector<UChar32> m_matches;
    87115    Vector<CharacterRange> m_ranges;
    … …  
    90118
    91119    const char* m_table;
     120    CharacterClassWidths m_characterWidths;
    92121    bool m_tableInverted : 1;
    93     bool m_hasNonBMPCharacters : 1;
    94122    bool m_anyCharacter : 1;
    95123};
    … …  
    221249    }
    222250   
    223     bool invert()
     251    bool invert() const
    224252    {
    225253        return m_invert;

  • tags/Safari-608.1.15/Source/JavaScriptCore/yarr/create_regex_tables

    r243950 r244022  
    101101    else:
    102102        function += ("    auto characterClass = std::make_unique<CharacterClass>();\n")
     103    hasBMPCharacters = False
    103104    hasNonBMPCharacters = False
    104105    for (min, max) in ranges:
     106        if min < 0x10000:
     107            hasBMPCharacters = True
     108        if max >= 0x10000:
     109            hasNonBMPCharacters = True
    105110        if (min == max):
    106111            if (min > 127):
    … …  
    113118        else:
    114119            function += ("    characterClass->m_ranges.append(CharacterRange(0x%02x, 0x%02x));\n" % (min, max))
    115         if max >= 0x10000:
    116             hasNonBMPCharacters = True
    117     function += ("    characterClass->m_hasNonBMPCharacters = %s;\n" % ("true" if hasNonBMPCharacters else "false"))
     120    function += ("    characterClass->m_characterWidths = CharacterClassWidths::%s;\n" % (("Unknown", "HasBMPChars", "HasNonBMPChars", "HasBothBMPAndNonBMP")[int(hasNonBMPCharacters) * 2 + int(hasBMPCharacters)]))
    118121    function += ("    return characterClass;\n")
    119122    function += ("}\n\n")

  • tags/Safari-608.1.15/Source/JavaScriptCore/yarr/generateYarrUnicodePropertyTables.py

    r243950 r244022  
    3636
    3737header = """/*
    38 * Copyright (C) 2017-2018 Apple Inc. All rights reserved.
     38* Copyright (C) 2017-2019 Apple Inc. All rights reserved.
    3939*
    4040* Redistribution and use in source and binary forms, with or without
    … …  
    226226        self.aliases = []
    227227        self.index = len(PropertyData.allPropertyData)
     228        self.hasBMPCharacters = False
    228229        self.hasNonBMPCharacters = False
    229230        self.matches = []
    … …  
    250251
    251252    def addMatch(self, codePoint):
    252         if codePoint > MaxBMP:
     253        if codePoint <= MaxBMP:
     254            self.hasBMPCharacters = True
     255        else:
    253256            self.hasNonBMPCharacters = True
    254257        if codePoint <= lastASCIICodePoint:
    … …  
    282285
    283286    def addRange(self, lowCodePoint, highCodePoint):
     287        if lowCodePoint <= MaxBMP:
     288            self.hasBMPCharacters = True
    284289        if highCodePoint > MaxBMP:
    285290            self.hasNonBMPCharacters = True
    … …  
    537542        file.write("        std::initializer_list<CharacterRange>(")
    538543        self.dumpMatchData(file, 4, self.unicodeRanges, lambda file, range: (file.write("{{{0:0=#6x}, {1:0=#6x}}}".format(range[0], range[1]))))
    539         file.write("));\n")
    540 
    541         file.write("    characterClass->m_hasNonBMPCharacters = {};\n".format(("false", "true")[self.hasNonBMPCharacters]))
     544        file.write("),\n")
     545
     546        file.write("        CharacterClassWidths::{});\n".format(("Unknown", "HasBMPChars", "HasNonBMPChars", "HasBothBMPAndNonBMP")[int(self.hasNonBMPCharacters) * 2 + int(self.hasBMPCharacters)]))
    542547        file.write("    return characterClass;\n}\n\n")
    543548
Note: See TracChangeset for help on using the changeset viewer.