Changeset 174035 in webkit


Ignore:
Timestamp:
Sep 27, 2014 11:49:12 AM (10 years ago)
Author:
benjamin@webkit.org
Message:

Chaining multiple :nth-child() does not work properly
​https://bugs.webkit.org/show_bug.cgi?id=137032

Patch by Benjamin Poulain <​bpoulain@apple.com> on 2014-09-27
Reviewed by Gavin Barraclough.

Source/WebCore:

When multiple :nth-child() are chained, the evaluation of each "An+B" could depend on
the execution of the previous "An+B". The reason is that the register holding the position
of the current element could be modified by the evaluation of "An+B".

There are two cases in which the register was used as the destination of an operation:
1) When A and B are positive, the counter would be the destination of "counter - B".
2) When A is not 1 or 2, the modulo operation was not preserving the input register.

For (1), we a copy of the counter in that case of generateElementIsNthChild().

For (2), we also preserve a copy of the input if it is used by the operation. In this case,
if the input register is one of the argument we need for idiv, we preserve it on the stack
or in a register depending on what is available.

This increases the register requirements by 2 in the worst case on x86. The extra registers
can push generateElementIsNthChild() above the 4 available registers. To accomodate for that,
minimumRegisterRequirements() reserve more registers on x86.

The extra register pressure has strictly no effect on performance, x86_64 has 9 registers
available without pushing anything. The extra allocation is only necessary for debugging.

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

fast/selectors/nth-child-chained.html
fast/selectors/nth-child-of-basics-2.html
fast/selectors/nth-child-of-chained.html

  • cssjit/SelectorCompiler.cpp:

(WebCore::SelectorCompiler::minimumRegisterRequirements):
(WebCore::SelectorCompiler::SelectorCodeGenerator::modulo):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsNthChild):

LayoutTests:

  • fast/selectors/nth-child-chained-expected.txt: Added.
  • fast/selectors/nth-child-chained.html: Added.
  • fast/selectors/nth-child-of-chained-expected.txt: Added.
  • fast/selectors/nth-child-of-chained.html: Added.

Those new tests target specifically the register reuse bug fixed by the patch.

  • fast/selectors/nth-child-basics-expected.txt: Added.
  • fast/selectors/nth-child-basics.html: Added.
  • fast/selectors/nth-child-of-basics-2-expected.txt: Added.
  • fast/selectors/nth-child-of-basics-2.html: Added.

Those tests add coverage for the examples used by ​http://nthmaster.com. This is to increase
the general test coverage.

I added nth-child-of-basics-2.html instead of extending nth-child-of-basics.html because
of the speed issue in debug without CSS JIT (otherwise the test can timeout).

Location:
trunk
Files:
8 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r174032 r174035  
     12014-09-27  Benjamin Poulain  <bpoulain@apple.com>
     2
     3        Chaining multiple :nth-child() does not work properly
     4        https://bugs.webkit.org/show_bug.cgi?id=137032
     5
     6        Reviewed by Gavin Barraclough.
     7
     8        * fast/selectors/nth-child-chained-expected.txt: Added.
     9        * fast/selectors/nth-child-chained.html: Added.
     10        * fast/selectors/nth-child-of-chained-expected.txt: Added.
     11        * fast/selectors/nth-child-of-chained.html: Added.
     12        Those new tests target specifically the register reuse bug fixed by the patch.
     13
     14        * fast/selectors/nth-child-basics-expected.txt: Added.
     15        * fast/selectors/nth-child-basics.html: Added.
     16        * fast/selectors/nth-child-of-basics-2-expected.txt: Added.
     17        * fast/selectors/nth-child-of-basics-2.html: Added.
     18        Those tests add coverage for the examples used by http://nthmaster.com. This is to increase
     19        the general test coverage.
     20
     21        I added nth-child-of-basics-2.html instead of extending nth-child-of-basics.html because
     22        of the speed issue in debug without CSS JIT (otherwise the test can timeout).
     23
    1242014-09-26  Yusuke Suzuki  <utatane.tea@gmail.com>
    225

  • trunk/Source/WebCore/ChangeLog

    r174031 r174035  
     12014-09-27  Benjamin Poulain  <bpoulain@apple.com>
     2
     3        Chaining multiple :nth-child() does not work properly
     4        https://bugs.webkit.org/show_bug.cgi?id=137032
     5
     6        Reviewed by Gavin Barraclough.
     7
     8        When multiple :nth-child() are chained, the evaluation of each "An+B" could depend on
     9        the execution of the previous "An+B". The reason is that the register holding the position
     10        of the current element could be modified by the evaluation of "An+B".
     11
     12        There are two cases in which the register was used as the destination of an operation:
     13        1) When A and B are positive, the counter would be the destination of "counter - B".
     14        2) When A is not 1 or 2, the modulo operation was not preserving the input register.
     15
     16        For (1), we a copy of the counter in that case of generateElementIsNthChild().
     17
     18        For (2), we also preserve a copy of the input if it is used by the operation. In this case,
     19        if the input register is one of the argument we need for idiv, we preserve it on the stack
     20        or in a register depending on what is available.
     21
     22        This increases the register requirements by 2 in the worst case on x86. The extra registers
     23        can push generateElementIsNthChild() above the 4 available registers. To accomodate for that,
     24        minimumRegisterRequirements() reserve more registers on x86.
     25
     26        The extra register pressure has strictly no effect on performance, x86_64 has 9 registers
     27        available without pushing anything. The extra allocation is only necessary for debugging.
     28
     29        Tests: fast/selectors/nth-child-basics.html
     30               fast/selectors/nth-child-chained.html
     31               fast/selectors/nth-child-of-basics-2.html
     32               fast/selectors/nth-child-of-chained.html
     33
     34        * cssjit/SelectorCompiler.cpp:
     35        (WebCore::SelectorCompiler::minimumRegisterRequirements):
     36        (WebCore::SelectorCompiler::SelectorCodeGenerator::modulo):
     37        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementIsNthChild):
     38
    1392014-09-26  Christophe Dumez  <cdumez@apple.com>
    240

  • trunk/Source/WebCore/cssjit/SelectorCompiler.cpp

    r174031 r174035  
    849849// Element + BacktrackingRegister + ElementData + a pointer to values + an index on that pointer + the value we expect;
    850850static const unsigned minimumRequiredRegisterCount = 6;
     851
    851852// Element + ElementData + scratchRegister + attributeArrayPointer + expectedLocalName + (qualifiedNameImpl && expectedValue).
    852853static const unsigned minimumRequiredRegisterCountForAttributeFilter = 6;
     854
     855#if CPU(X86_64)
     856// Element + SiblingCounter + SiblingCounterCopy + divisor + dividend + remainder.
     857static const unsigned minimumRequiredRegisterCountForNthChildFilter = 6;
     858#endif
    853859
    854860static inline unsigned minimumRegisterRequirements(const SelectorFragment& selectorFragment)
    … …  
    877883        minimum = std::max(minimum, attributeMinimum);
    878884    }
     885
     886#if CPU(X86_64)
     887    if (!selectorFragment.nthChildFilters.isEmpty())
     888        minimum = std::max(minimum, minimumRequiredRegisterCountForNthChildFilter + backtrackingRegisterRequirements);
     889#endif
    879890
    880891    // :not pseudo class filters cause some register pressure.
    … …  
    17551766        bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
    17561767        if (registerIsInUse) {
    1757             if (m_registerAllocator.availableRegisterCount()) {
     1768            if (m_registerAllocator.availableRegisterCount() > 1) {
    17581769                temporaryDividendCopy = m_registerAllocator.allocateRegister();
    17591770                m_assembler.move(dividend, temporaryDividendCopy);
    … …  
    17771788        bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
    17781789        if (registerIsInUse) {
    1779             if (m_registerAllocator.availableRegisterCount()) {
     1790            if (m_registerAllocator.availableRegisterCount() > 1) {
    17801791                temporaryRemainderCopy = m_registerAllocator.allocateRegister();
    17811792                m_assembler.move(remainder, temporaryRemainderCopy);
    … …  
    17901801        }
    17911802    }
     1803
     1804    // If the input register is used by idiv, save its value to restore it after the operation.
     1805    Assembler::RegisterID inputDividendCopy;
     1806    StackAllocator::StackReference pushedInputDividendStackReference;
     1807    RegisterAllocationType savedInputDividendAllocationType = RegisterAllocationType::External;
     1808    if (inputDividend == dividend || inputDividend == remainder) {
     1809        if (m_registerAllocator.availableRegisterCount() > 1) {
     1810            inputDividendCopy = m_registerAllocator.allocateRegister();
     1811            m_assembler.move(inputDividend, inputDividendCopy);
     1812            savedInputDividendAllocationType = RegisterAllocationType::CopiedToTemporary;
     1813        } else {
     1814            pushedInputDividendStackReference = m_stackAllocator.push(inputDividend);
     1815            savedInputDividendAllocationType = RegisterAllocationType::PushedToStack;
     1816        }
     1817    }
     1818
    17921819    m_assembler.m_assembler.cdq();
    17931820
    … …  
    18161843    } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
    18171844        m_stackAllocator.pop(temporaryDividendStackReference, dividend);
     1845
     1846    if (savedInputDividendAllocationType != RegisterAllocationType::External) {
     1847        if (savedInputDividendAllocationType == RegisterAllocationType::CopiedToTemporary) {
     1848            m_assembler.move(inputDividendCopy, inputDividend);
     1849            m_registerAllocator.deallocateRegister(inputDividendCopy);
     1850        } else if (savedInputDividendAllocationType == RegisterAllocationType::PushedToStack)
     1851            m_stackAllocator.pop(pushedInputDividendStackReference, inputDividend);
     1852    }
    18181853
    18191854    // 4) Branch on the test.
    … …  
    29993034                failureCases.append(m_assembler.branchTest32(Assembler::Zero, elementCounter, Assembler::TrustedImm32(1)));
    30003035            } else {
    3001                 if (b)
    3002                     failureCases.append(m_assembler.branchSub32(Assembler::Signed, Assembler::TrustedImm32(b), elementCounter));
    3003                 moduloIsZero(failureCases, elementCounter, a);
     3036                if (b) {
     3037                    LocalRegister elementCounterCopy(m_registerAllocator);
     3038                    m_assembler.move(elementCounter, elementCounterCopy);
     3039                    failureCases.append(m_assembler.branchSub32(Assembler::Signed, Assembler::TrustedImm32(b), elementCounterCopy));
     3040                    moduloIsZero(failureCases, elementCounterCopy, a);
     3041                } else
     3042                    moduloIsZero(failureCases, elementCounter, a);
    30043043            }
    30053044        } else {
Note: See TracChangeset for help on using the changeset viewer.