Changeset 167218 in webkit


Ignore:
Timestamp:
Apr 14, 2014 1:42:53 AM (10 years ago)
Author:
benjamin@webkit.org
Message:

CSS JIT: compile the :nth-child() pseudo class
https://bugs.webkit.org/show_bug.cgi?id=131602

Reviewed by Andreas Kling.

Source/WebCore:

Tests: fast/selectors/nth-child-bounds.html

fast/selectors/nth-child-with-backtracking.html

Compile the :nth-child() pseudo class function + some related clean up.

  • css/CSSSelector.cpp:

(WebCore::CSSSelector::nthA):
(WebCore::CSSSelector::nthB):
Expose the parsed value of an+b filters. Those values are used to compile
the selector.

(WebCore::CSSSelector::RareData::parseNth):
While working on the patch, I discovered some severe issues with the parsing of large
values of a and/or b. The problem comes from the way the CSS parser handle the values:
the values are parsed as a double then converted to an AtomicString for CSSSelector.

There are many problems related to large values but we never got bug reports because
they are very uncommon. Fixing those problem would require changing the parser.

Here, CSSSelector::RareData::parseNth() is hardened a little bit to avoid absurd values
of a and b.

  • css/CSSSelector.h:
  • cssjit/RegisterAllocator.h:

It looks like I forgot RDX in the list of register. Add it now since it is required
for SelectorCodeGenerator::modulo().

  • cssjit/SelectorCompiler.cpp:

(WebCore::SelectorCompiler::addPseudoType):
(WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
(WebCore::SelectorCompiler::SelectorCodeGenerator::modulo):
(WebCore::SelectorCompiler::SelectorCodeGenerator::moduloIsZero):
There is no modulo() operation exposed on the macro assemblers. This is a basic
implementation on top of idiv for x86_64.

Since idiv works exclusively with RAX and RDX, most of the code is about getting
those registers efficiently.

(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
(WebCore::SelectorCompiler::setElementChildIndex):
(WebCore::SelectorCompiler::setElementChildIndexAndUpdateStyle):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsNthChild):
This is pretty much a straightforward implementation of :nth-child().
The first part counts the number of previous elements.
The second part updates the tree if this is style resolution.
The last part compares the number of previous siblings to an+b to find if the filter matches.

The only part that diverges from SelectorChecker is how childIndex is used. Instead of testing it
at every iteration, only the first iteration handle the cache.

  • dom/ElementRareData.h:

(WebCore::ElementRareData::childIndexMemoryOffset):

  • dom/Node.h:

(WebCore::Node::rareDataMemoryOffset):
(WebCore::Node::flagHasRareData):

  • rendering/style/RenderStyle.h:

LayoutTests:

Add a couple of test for the new code:
-nth-child-with-backtracking tests the register pressure with backtracking.
-nth-child-bounds tests invalid selectors do not cause problems.

  • fast/selectors/nth-child-bounds-expected.txt: Added.
  • fast/selectors/nth-child-bounds.html: Added.
  • fast/selectors/nth-child-with-backtracking-expected.txt: Added.
  • fast/selectors/nth-child-with-backtracking.html: Added.
  • http/tests/security/video-poster-cross-origin-crash.html:

Now that CSSSelector filters out ridiculously bad values, the pseudo class in this test
was no longer executed.
The particular value of nth-child is irrelevant for this test, all it needs it the tree marking
while not matching.

Location:
trunk
Files:
4 added
10 edited

Legend:

Unmodified
Added
Removed
  • trunk/LayoutTests/ChangeLog

    r167215 r167218  
     12014-04-14  Benjamin Poulain  <benjamin@webkit.org>
     2
     3        CSS JIT: compile the :nth-child() pseudo class
     4        https://bugs.webkit.org/show_bug.cgi?id=131602
     5
     6        Reviewed by Andreas Kling.
     7
     8        Add a couple of test for the new code:
     9        -nth-child-with-backtracking tests the register pressure with backtracking.
     10        -nth-child-bounds tests invalid selectors do not cause problems.
     11
     12        * fast/selectors/nth-child-bounds-expected.txt: Added.
     13        * fast/selectors/nth-child-bounds.html: Added.
     14        * fast/selectors/nth-child-with-backtracking-expected.txt: Added.
     15        * fast/selectors/nth-child-with-backtracking.html: Added.
     16
     17        * http/tests/security/video-poster-cross-origin-crash.html:
     18        Now that CSSSelector filters out ridiculously bad values, the pseudo class in this test
     19        was no longer executed.
     20        The particular value of nth-child is irrelevant for this test, all it needs it the tree marking
     21        while not matching.
     22
    1232014-04-14  Mihnea Ovidenie  <mihnea@adobe.com>
    224
  • trunk/LayoutTests/http/tests/security/video-poster-cross-origin-crash.html

    r123121 r167218  
    11<sub id=tCF1></sub>>>><button hidden=false id=tCF7>><video crossorigin="" poster="http://localhost:8080/misc/resources/compass.jpg">><style>
    2 .c29:nth-child(1814762996n + 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999) { -webkit-locale: "zh_CN";</style><script>
     2.c29:nth-child(n + 2) { -webkit-locale: "zh_CN";</style><script>
    33if (window.testRunner) {
    44    testRunner.dumpAsText();
  • trunk/Source/WebCore/ChangeLog

    r167216 r167218  
     12014-04-14  Benjamin Poulain  <benjamin@webkit.org>
     2
     3        CSS JIT: compile the :nth-child() pseudo class
     4        https://bugs.webkit.org/show_bug.cgi?id=131602
     5
     6        Reviewed by Andreas Kling.
     7
     8        Tests: fast/selectors/nth-child-bounds.html
     9               fast/selectors/nth-child-with-backtracking.html
     10
     11        Compile the :nth-child() pseudo class function + some related clean up.
     12
     13        * css/CSSSelector.cpp:
     14        (WebCore::CSSSelector::nthA):
     15        (WebCore::CSSSelector::nthB):
     16        Expose the parsed value of an+b filters. Those values are used to compile
     17        the selector.
     18
     19        (WebCore::CSSSelector::RareData::parseNth):
     20        While working on the patch, I discovered some severe issues with the parsing of large
     21        values of a and/or b. The problem comes from the way the CSS parser handle the values:
     22        the values are parsed as a double then converted to an AtomicString for CSSSelector.
     23
     24        There are many problems related to large values but we never got bug reports because
     25        they are very uncommon. Fixing those problem would require changing the parser.
     26
     27        Here, CSSSelector::RareData::parseNth() is hardened a little bit to avoid absurd values
     28        of a and b.
     29
     30        * css/CSSSelector.h:
     31        * cssjit/RegisterAllocator.h:
     32        It looks like I forgot RDX in the list of register. Add it now since it is required
     33        for SelectorCodeGenerator::modulo().
     34
     35        * cssjit/SelectorCompiler.cpp:
     36        (WebCore::SelectorCompiler::addPseudoType):
     37        (WebCore::SelectorCompiler::SelectorCodeGenerator::SelectorCodeGenerator):
     38        (WebCore::SelectorCompiler::SelectorCodeGenerator::modulo):
     39        (WebCore::SelectorCompiler::SelectorCodeGenerator::moduloIsZero):
     40        There is no modulo() operation exposed on the macro assemblers. This is a basic
     41        implementation on top of idiv for x86_64.
     42
     43        Since idiv works exclusively with RAX and RDX, most of the code is about getting
     44        those registers efficiently.
     45
     46        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
     47        (WebCore::SelectorCompiler::setElementChildIndex):
     48        (WebCore::SelectorCompiler::setElementChildIndexAndUpdateStyle):
     49        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsNthChild):
     50        This is pretty much a straightforward implementation of :nth-child().
     51        The first part counts the number of previous elements.
     52        The second part updates the tree if this is style resolution.
     53        The last part compares the number of previous siblings to an+b to find if the filter matches.
     54
     55        The only part that diverges from SelectorChecker is how childIndex is used. Instead of testing it
     56        at every iteration, only the first iteration handle the cache.
     57
     58        * dom/ElementRareData.h:
     59        (WebCore::ElementRareData::childIndexMemoryOffset):
     60        * dom/Node.h:
     61        (WebCore::Node::rareDataMemoryOffset):
     62        (WebCore::Node::flagHasRareData):
     63        * rendering/style/RenderStyle.h:
     64
    1652014-04-14  Tim Horton  <timothy_horton@apple.com>
    266
  • trunk/Source/WebCore/css/CSSSelector.cpp

    r166883 r167218  
    582582}
    583583
     584int CSSSelector::nthA() const
     585{
     586    ASSERT(m_hasRareData);
     587    ASSERT(m_parsedNth);
     588    return m_data.m_rareData->m_a;
     589}
     590
     591int CSSSelector::nthB() const
     592{
     593    ASSERT(m_hasRareData);
     594    ASSERT(m_parsedNth);
     595    return m_data.m_rareData->m_b;
     596}
     597
    584598CSSSelector::RareData::RareData(PassRefPtr<AtomicStringImpl> value)
    585599    : m_value(value.leakRef())
     
    619633                if (n == 1)
    620634                    m_a = -1; // -n == -1n
    621                 else
    622                     m_a = argument.substring(0, n).toInt();
     635                else {
     636                    bool ok;
     637                    m_a = argument.substringSharingImpl(0, n).toIntStrict(&ok);
     638                    if (!ok)
     639                        return false;
     640                }
    623641            } else if (!n)
    624642                m_a = 1; // n == 1n
    625             else
    626                 m_a = argument.substring(0, n).toInt();
     643            else {
     644                bool ok;
     645                m_a = argument.substringSharingImpl(0, n).toIntStrict(&ok);
     646                if (!ok)
     647                    return false;
     648            }
    627649
    628650            size_t p = argument.find('+', n);
    629             if (p != notFound)
    630                 m_b = argument.substring(p + 1, argument.length() - p - 1).toInt();
    631             else {
     651            if (p != notFound) {
     652                bool ok;
     653                m_b = argument.substringSharingImpl(p + 1, argument.length() - p - 1).toIntStrict(&ok);
     654                if (!ok)
     655                    return false;
     656            } else {
    632657                p = argument.find('-', n);
    633                 if (p != notFound)
    634                     m_b = -argument.substring(p + 1, argument.length() - p - 1).toInt();
    635             }
    636         } else
    637             m_b = argument.toInt();
     658                if (p != notFound) {
     659                    bool ok;
     660                    m_b = -argument.substringSharingImpl(p + 1, argument.length() - p - 1).toIntStrict(&ok);
     661                    if (!ok)
     662                        return false;
     663                }
     664            }
     665        } else {
     666            bool ok;
     667            m_b = argument.toIntStrict(&ok);
     668            if (!ok)
     669                return false;
     670        }
    638671    }
    639672    return true;
  • trunk/Source/WebCore/css/CSSSelector.h

    r166883 r167218  
    218218        bool parseNth() const;
    219219        bool matchNth(int count) const;
     220        int nthA() const;
     221        int nthB() const;
    220222
    221223        PseudoElementType pseudoElementType() const { ASSERT(m_match == PseudoElement); return static_cast<PseudoElementType>(m_pseudoType); }
  • trunk/Source/WebCore/cssjit/RegisterAllocator.h

    r166666 r167218  
    4040    JSC::X86Registers::eax,
    4141    JSC::X86Registers::ecx,
     42    JSC::X86Registers::edx,
    4243    JSC::X86Registers::esi,
    4344    JSC::X86Registers::edi,
  • trunk/Source/WebCore/cssjit/SelectorCompiler.cpp

    r166870 r167218  
    3232#include "Element.h"
    3333#include "ElementData.h"
     34#include "ElementRareData.h"
    3435#include "FunctionCall.h"
    3536#include "HTMLDocument.h"
     
    132133    Vector<JSC::FunctionPtr> unoptimizedPseudoClasses;
    133134    Vector<AttributeMatchingInfo> attributes;
     135    Vector<std::pair<int, int>> nthChildfilters;
    134136};
    135137
     
    190192    void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames);
    191193    void generateElementIsLink(Assembler::JumpList& failureCases);
     194    void generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment&);
    192195
    193196    // Helpers.
    194197    Assembler::Jump jumpIfNotResolvingStyle(Assembler::RegisterID checkingContextRegister);
     198    Assembler::Jump modulo(JSC::MacroAssembler::ResultCondition, Assembler::RegisterID inputDividend, int divisor);
     199    void moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor);
    195200
    196201    Assembler m_assembler;
     
    252257}
    253258
    254 static inline FunctionType addPseudoType(CSSSelector::PseudoType type, SelectorFragment& pseudoClasses, SelectorContext selectorContext)
    255 {
     259static inline FunctionType addPseudoType(const CSSSelector& selector, SelectorFragment& fragment, SelectorContext selectorContext)
     260{
     261    CSSSelector::PseudoType type = selector.pseudoType();
    256262    switch (type) {
    257263    // Unoptimized pseudo selector. They are just function call to a simple testing function.
    258264    case CSSSelector::PseudoAutofill:
    259         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
     265        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
    260266        return FunctionType::SimpleSelectorChecker;
    261267    case CSSSelector::PseudoChecked:
    262         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
     268        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
    263269        return FunctionType::SimpleSelectorChecker;
    264270    case CSSSelector::PseudoDefault:
    265         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
     271        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
    266272        return FunctionType::SimpleSelectorChecker;
    267273    case CSSSelector::PseudoDisabled:
    268         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
     274        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
    269275        return FunctionType::SimpleSelectorChecker;
    270276    case CSSSelector::PseudoEnabled:
    271         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
     277        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
    272278        return FunctionType::SimpleSelectorChecker;
    273279    case CSSSelector::PseudoFocus:
    274         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
     280        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
    275281        return FunctionType::SimpleSelectorChecker;
    276282    case CSSSelector::PseudoIndeterminate:
    277         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
     283        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
    278284        return FunctionType::SimpleSelectorChecker;
    279285    case CSSSelector::PseudoInvalid:
    280         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
     286        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
    281287        return FunctionType::SimpleSelectorChecker;
    282288    case CSSSelector::PseudoOptional:
    283         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
     289        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
    284290        return FunctionType::SimpleSelectorChecker;
    285291    case CSSSelector::PseudoReadOnly:
    286         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
     292        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
    287293        return FunctionType::SimpleSelectorChecker;
    288294    case CSSSelector::PseudoReadWrite:
    289         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
     295        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
    290296        return FunctionType::SimpleSelectorChecker;
    291297    case CSSSelector::PseudoRequired:
    292         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
     298        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
    293299        return FunctionType::SimpleSelectorChecker;
    294300    case CSSSelector::PseudoValid:
    295         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
     301        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
    296302        return FunctionType::SimpleSelectorChecker;
    297303#if ENABLE(FULLSCREEN_API)
    298304    case CSSSelector::PseudoFullScreen:
    299         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
     305        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
    300306        return FunctionType::SimpleSelectorChecker;
    301307#endif
    302308#if ENABLE(VIDEO_TRACK)
    303309    case CSSSelector::PseudoFuture:
    304         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
     310        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
    305311        return FunctionType::SimpleSelectorChecker;
    306312    case CSSSelector::PseudoPast:
    307         pseudoClasses.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
     313        fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
    308314        return FunctionType::SimpleSelectorChecker;
    309315#endif
     
    311317    // Optimized pseudo selectors.
    312318    case CSSSelector::PseudoAnyLink:
    313         pseudoClasses.pseudoClasses.add(CSSSelector::PseudoLink);
     319        fragment.pseudoClasses.add(CSSSelector::PseudoLink);
    314320        return FunctionType::SimpleSelectorChecker;
    315321
    316322    case CSSSelector::PseudoLink:
    317         pseudoClasses.pseudoClasses.add(type);
     323        fragment.pseudoClasses.add(type);
    318324        return FunctionType::SimpleSelectorChecker;
    319325
     
    321327    case CSSSelector::PseudoLastChild:
    322328    case CSSSelector::PseudoOnlyChild:
    323         pseudoClasses.pseudoClasses.add(type);
     329        fragment.pseudoClasses.add(type);
    324330        if (selectorContext == SelectorContext::QuerySelector)
    325331            return FunctionType::SimpleSelectorChecker;
    326332        return FunctionType::SelectorCheckerWithCheckingContext;
    327333
     334    case CSSSelector::PseudoNthChild:
     335        {
     336            if (!selector.parseNth())
     337                return FunctionType::CannotMatchAnything;
     338
     339            int a = selector.nthA();
     340            int b = selector.nthB();
     341
     342            // The element count is always positive.
     343            if (a <= 0 && b < 1)
     344                return FunctionType::CannotMatchAnything;
     345
     346            // Anything modulo 1 is zero. Unless b restrict the range, this does not filter anything out.
     347            if (a == 1 && (!b || (b == 1)))
     348                return FunctionType::SimpleSelectorChecker;
     349
     350            fragment.nthChildfilters.append(std::pair<int, int>(a, b));
     351            if (selectorContext == SelectorContext::QuerySelector)
     352                return FunctionType::SimpleSelectorChecker;
     353            return FunctionType::SelectorCheckerWithCheckingContext;
     354        }
    328355    default:
    329356        break;
     
    368395            break;
    369396        case CSSSelector::PseudoClass:
    370             m_functionType = mostRestrictiveFunctionType(m_functionType, addPseudoType(selector->pseudoType(), fragment, m_selectorContext));
     397            m_functionType = mostRestrictiveFunctionType(m_functionType, addPseudoType(*selector, fragment, m_selectorContext));
    371398            if (m_functionType == FunctionType::CannotCompile || m_functionType == FunctionType::CannotMatchAnything)
    372399                return;
     
    898925}
    899926
     927// The value in inputDividend is destroyed by the modulo operation.
     928Assembler::Jump SelectorCodeGenerator::modulo(Assembler::ResultCondition condition, Assembler::RegisterID inputDividend, int divisor)
     929{
     930    RELEASE_ASSERT(divisor);
     931#if CPU(X86_64)
     932    // idiv takes RAX + an arbitrary register, and return RAX + RDX. Most of this code is about doing
     933    // an efficient allocation of those registers. If a register is already in use and is not the inputDividend,
     934    // we first try to copy it to a temporary register, it that is not possible we fall back to the stack.
     935    enum class RegisterAllocationType {
     936        External,
     937        AllocatedLocally,
     938        CopiedToTemporary,
     939        PushedToStack
     940    };
     941
     942    // 1) Get RAX and RDX.
     943    // If they are already used, push them to the stack.
     944    Assembler::RegisterID dividend = JSC::X86Registers::eax;
     945    RegisterAllocationType dividendAllocation = RegisterAllocationType::External;
     946    StackAllocator::StackReference temporaryDividendStackReference;
     947    Assembler::RegisterID temporaryDividendCopy = InvalidGPRReg;
     948    if (inputDividend != dividend) {
     949        bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
     950        if (registerIsInUse) {
     951            if (m_registerAllocator.availableRegisterCount()) {
     952                temporaryDividendCopy = m_registerAllocator.allocateRegister();
     953                m_assembler.move(dividend, temporaryDividendCopy);
     954                dividendAllocation = RegisterAllocationType::CopiedToTemporary;
     955            } else {
     956                temporaryDividendStackReference = m_stackAllocator.push(dividend);
     957                dividendAllocation = RegisterAllocationType::PushedToStack;
     958            }
     959        } else {
     960            m_registerAllocator.allocateRegister(dividend);
     961            dividendAllocation = RegisterAllocationType::AllocatedLocally;
     962        }
     963        m_assembler.move(inputDividend, dividend);
     964    }
     965
     966    Assembler::RegisterID remainder = JSC::X86Registers::edx;
     967    RegisterAllocationType remainderAllocation = RegisterAllocationType::External;
     968    StackAllocator::StackReference temporaryRemainderStackReference;
     969    Assembler::RegisterID temporaryRemainderCopy = InvalidGPRReg;
     970    if (inputDividend != remainder) {
     971        bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
     972        if (registerIsInUse) {
     973            if (m_registerAllocator.availableRegisterCount()) {
     974                temporaryRemainderCopy = m_registerAllocator.allocateRegister();
     975                m_assembler.move(remainder, temporaryRemainderCopy);
     976                remainderAllocation = RegisterAllocationType::CopiedToTemporary;
     977            } else {
     978                temporaryRemainderStackReference = m_stackAllocator.push(remainder);
     979                remainderAllocation = RegisterAllocationType::PushedToStack;
     980            }
     981        } else {
     982            m_registerAllocator.allocateRegister(remainder);
     983            remainderAllocation = RegisterAllocationType::AllocatedLocally;
     984        }
     985    }
     986    m_assembler.m_assembler.cdq();
     987
     988    // 2) Perform the division with idiv.
     989    {
     990        LocalRegister divisorRegister(m_registerAllocator);
     991        m_assembler.move(Assembler::TrustedImm64(divisor), divisorRegister);
     992        m_assembler.m_assembler.idivl_r(divisorRegister);
     993        m_assembler.test32(remainder);
     994    }
     995
     996    // 3) Return RAX and RDX.
     997    if (remainderAllocation == RegisterAllocationType::AllocatedLocally)
     998        m_registerAllocator.deallocateRegister(remainder);
     999    else if (remainderAllocation == RegisterAllocationType::CopiedToTemporary) {
     1000        m_assembler.move(temporaryRemainderCopy, remainder);
     1001        m_registerAllocator.deallocateRegister(temporaryRemainderCopy);
     1002    } else if (remainderAllocation == RegisterAllocationType::PushedToStack)
     1003        m_stackAllocator.pop(temporaryRemainderStackReference, remainder);
     1004
     1005    if (dividendAllocation == RegisterAllocationType::AllocatedLocally)
     1006        m_registerAllocator.deallocateRegister(dividend);
     1007    else if (dividendAllocation == RegisterAllocationType::CopiedToTemporary) {
     1008        m_assembler.move(temporaryDividendCopy, dividend);
     1009        m_registerAllocator.deallocateRegister(temporaryDividendCopy);
     1010    } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
     1011        m_stackAllocator.pop(temporaryDividendStackReference, dividend);
     1012
     1013    // 4) Branch on the test.
     1014    return m_assembler.branch(condition);
     1015#else
     1016#error Modulo is not implemented for this architecture.
     1017#endif
     1018}
     1019
     1020void SelectorCodeGenerator::moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor)
     1021{
     1022    if (divisor == 1 || divisor == -1)
     1023        return;
     1024    if (divisor == 2 || divisor == -2) {
     1025        failureCases.append(m_assembler.branchTest32(Assembler::NonZero, inputDividend, Assembler::TrustedImm32(1)));
     1026        return;
     1027    }
     1028
     1029    failureCases.append(modulo(Assembler::NonZero, inputDividend, divisor));
     1030}
     1031
    9001032static void setNodeFlag(Assembler& assembler, Assembler::RegisterID elementAddress, int32_t flag)
    9011033{
     
    10431175    if (fragment.pseudoClasses.contains(CSSSelector::PseudoLastChild))
    10441176        generateElementIsLastChild(failureCases, fragment);
     1177    if (!fragment.nthChildfilters.isEmpty())
     1178        generateElementIsNthChild(failureCases, fragment);
    10451179}
    10461180
     
    17781912}
    17791913
     1914static void setElementChildIndex(Element* element, int index)
     1915{
     1916    element->setChildIndex(index);
     1917}
     1918
     1919static void setElementChildIndexAndUpdateStyle(Element* element, int index)
     1920{
     1921    element->setChildIndex(index);
     1922    if (RenderStyle* childStyle = element->renderStyle())
     1923        childStyle->setUnique();
     1924}
     1925
     1926void SelectorCodeGenerator::generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
     1927{
     1928    Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
     1929    generateWalkToParentElement(failureCases, parentElement);
     1930
     1931    // Setup the counter at 1.
     1932    LocalRegister elementCounter(m_registerAllocator);
     1933    m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
     1934
     1935    // Loop over the previous adjacent elements and increment the counter.
     1936    {
     1937        LocalRegister previousSibling(m_registerAllocator);
     1938        m_assembler.move(elementAddressRegister, previousSibling);
     1939
     1940        // Getting the child index is very efficient when it works. When there is no child index,
     1941        // querying at every iteration is very inefficient. We solve this by only testing the child
     1942        // index on the first direct adjacent.
     1943        Assembler::JumpList noMoreSiblingsCases;
     1944
     1945        Assembler::JumpList noCachedChildIndexCases;
     1946        generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
     1947        noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(previousSibling, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagHasRareData())));
     1948        {
     1949            LocalRegister elementRareData(m_registerAllocator);
     1950            m_assembler.loadPtr(Assembler::Address(previousSibling, Node::rareDataMemoryOffset()), elementRareData);
     1951            LocalRegister cachedChildIndex(m_registerAllocator);
     1952            m_assembler.load16(Assembler::Address(elementRareData, ElementRareData::childIndexMemoryOffset()), cachedChildIndex);
     1953            noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, cachedChildIndex));
     1954            m_assembler.add32(cachedChildIndex, elementCounter);
     1955            noMoreSiblingsCases.append(m_assembler.jump());
     1956        }
     1957        noCachedChildIndexCases.link(&m_assembler);
     1958        m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
     1959
     1960        Assembler::Label loopStart = m_assembler.label();
     1961        generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
     1962        m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
     1963        m_assembler.jump().linkTo(loopStart, &m_assembler);
     1964        noMoreSiblingsCases.link(&m_assembler);
     1965    }
     1966
     1967    // Tree marking when doing style resolution.
     1968    if (m_selectorContext != SelectorContext::QuerySelector) {
     1969        LocalRegister checkingContext(m_registerAllocator);
     1970        Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
     1971
     1972        m_registerAllocator.deallocateRegister(parentElement);
     1973        FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
     1974        functionCall.setFunctionAddress(Element::setChildrenAffectedByForwardPositionalRules);
     1975        functionCall.setOneArgument(parentElement);
     1976        functionCall.call();
     1977
     1978        if (fragment.relationToRightFragment == FragmentRelation::Rightmost) {
     1979            LocalRegister childStyle(m_registerAllocator);
     1980            m_assembler.loadPtr(Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, elementStyle)), childStyle);
     1981
     1982            LocalRegister flags(m_registerAllocator);
     1983            Assembler::Address flagAddress(childStyle, RenderStyle::noninheritedFlagsMemoryOffset() + RenderStyle::NonInheritedFlags::flagsMemoryOffset());
     1984            m_assembler.load64(flagAddress, flags);
     1985            LocalRegister isUniqueFlagImmediate(m_registerAllocator);
     1986            m_assembler.move(Assembler::TrustedImm64(RenderStyle::NonInheritedFlags::flagIsUnique()), isUniqueFlagImmediate);
     1987            m_assembler.or64(isUniqueFlagImmediate, flags);
     1988            m_assembler.store64(flags, flagAddress);
     1989
     1990            Assembler::RegisterID elementAddress = elementAddressRegister;
     1991            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
     1992            functionCall.setFunctionAddress(setElementChildIndex);
     1993            functionCall.setTwoArguments(elementAddress, elementCounter);
     1994            functionCall.call();
     1995        } else {
     1996            Assembler::RegisterID elementAddress = elementAddressRegister;
     1997            FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
     1998            functionCall.setFunctionAddress(setElementChildIndexAndUpdateStyle);
     1999            functionCall.setTwoArguments(elementAddress, elementCounter);
     2000            functionCall.call();
     2001        }
     2002
     2003        notResolvingStyle.link(&m_assembler);
     2004    }
     2005
     2006    // Test every the nth-child filter.
     2007    for (const auto& slot : fragment.nthChildfilters) {
     2008        int a = slot.first;
     2009        int b = slot.second;
     2010
     2011        if (!a)
     2012            failureCases.append(m_assembler.branch32(Assembler::NotEqual, Assembler::TrustedImm32(b), elementCounter));
     2013        else if (a > 0) {
     2014            if (a == 2 && b == 1) {
     2015                // This is the common case 2n+1 (or "odd"), we can test for odd values without doing the arithmetic.
     2016                failureCases.append(m_assembler.branchTest32(Assembler::Zero, elementCounter, Assembler::TrustedImm32(1)));
     2017            } else {
     2018                if (b)
     2019                    failureCases.append(m_assembler.branchSub32(Assembler::Signed, Assembler::TrustedImm32(b), elementCounter));
     2020                moduloIsZero(failureCases, elementCounter, a);
     2021            }
     2022        } else {
     2023            LocalRegister bRegister(m_registerAllocator);
     2024            m_assembler.move(Assembler::TrustedImm32(b), bRegister);
     2025
     2026            failureCases.append(m_assembler.branchSub32(Assembler::Signed, elementCounter, bRegister));
     2027            moduloIsZero(failureCases, bRegister, a);
     2028        }
     2029    }
     2030}
     2031
    17802032}; // namespace SelectorCompiler.
    17812033}; // namespace WebCore.
  • trunk/Source/WebCore/dom/ElementRareData.h

    r166353 r167218  
    8383    bool childrenAffectedByBackwardPositionalRules() const { return m_childrenAffectedByBackwardPositionalRules; }
    8484    void setChildrenAffectedByBackwardPositionalRules(bool value) { m_childrenAffectedByBackwardPositionalRules = value; }
     85
    8586    unsigned childIndex() const { return m_childIndex; }
    8687    void setChildIndex(unsigned index) { m_childIndex = index; }
     88    static ptrdiff_t childIndexMemoryOffset() { return OBJECT_OFFSETOF(ElementRareData, m_childIndex); }
    8789
    8890    void clearShadowRoot() { m_shadowRoot = nullptr; }
  • trunk/Source/WebCore/dom/Node.h

    r166870 r167218  
    572572#if ENABLE(CSS_SELECTOR_JIT)
    573573    static ptrdiff_t nodeFlagsMemoryOffset() { return OBJECT_OFFSETOF(Node, m_nodeFlags); }
     574    static ptrdiff_t rareDataMemoryOffset() { return OBJECT_OFFSETOF(Node, m_data.m_rareData); }
    574575    static int32_t flagIsElement() { return IsElementFlag; }
    575576    static int32_t flagIsHTML() { return IsHTMLFlag; }
    576577    static int32_t flagIsLink() { return IsLinkFlag; }
     578    static int32_t flagHasRareData() { return HasRareDataFlag; }
    577579    static int32_t flagIsParsingChildrenFinished() { return IsParsingChildrenFinishedFlag; }
    578580    static int32_t flagChildrenAffectedByFirstChildRulesFlag() { return ChildrenAffectedByFirstChildRulesFlag; }
  • trunk/Source/WebCore/rendering/style/RenderStyle.h

    r166862 r167218  
    279279
    280280        static ptrdiff_t flagsMemoryOffset() { return OBJECT_OFFSETOF(NonInheritedFlags, m_flags); }
     281        static uint64_t flagIsUnique() { return oneBitMask << isUniqueOffset; }
    281282        static uint64_t setFirstChildStateFlags() { return flagFirstChildState() | flagIsUnique(); }
    282283        static uint64_t setLastChildStateFlags() { return flagLastChildState() | flagIsUnique(); }
     
    307308        }
    308309
    309         static uint64_t flagIsUnique() { return oneBitMask << isUniqueOffset; }
    310310        static uint64_t flagFirstChildState() { return oneBitMask << firstChildStateOffset; }
    311311        static uint64_t flagLastChildState() { return oneBitMask << lastChildStateOffset; }
Note: See TracChangeset for help on using the changeset viewer.