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

Changeset 243642 in webkit


Ignore:
Timestamp:
Mar 28, 2019, 11:05:55 PM (7 years ago)
Author:
msaboff@apple.com
Message:

[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:
Location:
trunk/Source/JavaScriptCore
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r243639 r243642  
     12019-03-28  Michael Saboff  <msaboff@apple.com>
     2
     3        [YARR] Precompute BMP / non-BMP status when constructing character classes
     4        https://bugs.webkit.org/show_bug.cgi?id=196296
     5
     6        Reviewed by Keith Miller.
     7
     8        Changed CharacterClass::m_hasNonBMPCharacters into a character width bit field which
     9        indicateis if the class includes characters from either BMP, non-BMP or both ranges.
     10        This allows the recognizing code to eliminate checks for the width of a matched
     11        characters when the class has only one width.  The character width is needed to
     12        determine if we advance 1 or 2 character.  Also, the pre-computed width of character
     13        classes that contains either all BMP or all non-BMP characters allows the parser to
     14        use fixed widths for terms using those character classes.  Changed both the code gen
     15        scripts and Yarr compiler to compute this bit field during the construction of
     16        character classes.
     17
     18        For JIT'ed code of character classes that contain either all BMP or all non-BMP
     19        characters, we can eliminate the generic check we were doing do compute how much
     20        to advance after sucessfully matching a character in the class.
     21
     22                Generic isBMP check      BMP only            non-BMP only
     23                --------------           --------------      --------------
     24                inc %r9d                 inc %r9d            add $0x2, %r9d
     25                cmp $0x10000, %eax
     26                jl isBMP
     27                cmp %edx, %esi
     28                jz atEndOfString
     29                inc %r9d
     30                inc %esi
     31         isBMP:
     32
     33        For character classes that contained non-BMP characters, we were always generating
     34        the code in the left column.  The middle column is the code we generate for character
     35        classes that contain only BMP characters.  The right column is the code we now
     36        generate if the character class has only non-BMP characters.  In the fix width cases,
     37        we can eliminate both the isBMP check as well as the atEndOfString check.  The
     38        atEndOfstring check is eliminated since we know how many characters this character
     39        class requires and that check can be factored out to the beginning of the current
     40        alternative.  For character classes that contain both BMP and non-BMP characters,
     41        we still generate the generic left column.
     42
     43        This change is a ~8% perf progression on UniPoker and a ~2% improvement on RexBench
     44        as a whole.
     45
     46        * runtime/RegExp.cpp:
     47        (JSC::RegExp::matchCompareWithInterpreter):
     48        * runtime/RegExpInlines.h:
     49        (JSC::RegExp::matchInline):
     50        * yarr/YarrInterpreter.cpp:
     51        (JSC::Yarr::Interpreter::checkCharacterClassDontAdvanceInputForNonBMP):
     52        (JSC::Yarr::Interpreter::matchCharacterClass):
     53        * yarr/YarrJIT.cpp:
     54        (JSC::Yarr::YarrGenerator::optimizeAlternative):
     55        (JSC::Yarr::YarrGenerator::matchCharacterClass):
     56        (JSC::Yarr::YarrGenerator::advanceIndexAfterCharacterClassTermMatch):
     57        (JSC::Yarr::YarrGenerator::tryReadUnicodeCharImpl):
     58        (JSC::Yarr::YarrGenerator::generateCharacterClassOnce):
     59        (JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
     60        (JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
     61        (JSC::Yarr::YarrGenerator::backtrackCharacterClassGreedy):
     62        (JSC::Yarr::YarrGenerator::generateCharacterClassNonGreedy):
     63        (JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):
     64        (JSC::Yarr::YarrGenerator::generateEnter):
     65        (JSC::Yarr::YarrGenerator::YarrGenerator):
     66        (JSC::Yarr::YarrGenerator::compile):
     67        * yarr/YarrPattern.cpp:
     68        (JSC::Yarr::CharacterClassConstructor::CharacterClassConstructor):
     69        (JSC::Yarr::CharacterClassConstructor::reset):
     70        (JSC::Yarr::CharacterClassConstructor::charClass):
     71        (JSC::Yarr::CharacterClassConstructor::addSorted):
     72        (JSC::Yarr::CharacterClassConstructor::addSortedRange):
     73        (JSC::Yarr::CharacterClassConstructor::hasNonBMPCharacters):
     74        (JSC::Yarr::CharacterClassConstructor::characterWidths):
     75        (JSC::Yarr::PatternTerm::dump):
     76        (JSC::Yarr::anycharCreate):
     77        * yarr/YarrPattern.h:
     78        (JSC::Yarr::operator|):
     79        (JSC::Yarr::operator&):
     80        (JSC::Yarr::operator|=):
     81        (JSC::Yarr::CharacterClass::CharacterClass):
     82        (JSC::Yarr::CharacterClass::hasNonBMPCharacters):
     83        (JSC::Yarr::CharacterClass::hasOneCharacterSize):
     84        (JSC::Yarr::CharacterClass::hasOnlyNonBMPCharacters):
     85        (JSC::Yarr::PatternTerm::invert const):
     86        (JSC::Yarr::PatternTerm::invert): Deleted.
     87        * yarr/create_regex_tables:
     88        * yarr/generateYarrUnicodePropertyTables.py:
     89
    1902019-03-28  Saam Barati  <sbarati@apple.com>
    291

  • trunk/Source/JavaScriptCore/runtime/RegExp.cpp

    r243408 r243642  
    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 {

  • trunk/Source/JavaScriptCore/runtime/RegExpInlines.h

    r243408 r243642  
    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

  • trunk/Source/JavaScriptCore/yarr/YarrInterpreter.cpp

    r243237 r243642  
    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                }

  • trunk/Source/JavaScriptCore/yarr/YarrJIT.cpp

    r243237 r243642  
    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)

  • trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

    r242699 r243642  
    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;

  • trunk/Source/JavaScriptCore/yarr/YarrPattern.h

    r242699 r243642  
    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;

  • trunk/Source/JavaScriptCore/yarr/create_regex_tables

    r238004 r243642  
    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")

  • trunk/Source/JavaScriptCore/yarr/generateYarrUnicodePropertyTables.py

    r236870 r243642  
    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.