AffectsNextSibling style relation marking is inefficient
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 15 Apr 2016 07:54:20 +0000 (07:54 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 15 Apr 2016 07:54:20 +0000 (07:54 +0000)
https://bugs.webkit.org/show_bug.cgi?id=156593

Reviewed by Benjamin Poulain.

We currently add a Style::Relation entry for each sibling to mark. With long sibling lists this can be inefficient
in terms of both memory and speed. Instead make a single entry that includes the sibling count to mark.

* css/SelectorChecker.cpp:
(WebCore::addStyleRelation):

    When adding AffectsNextSibling entry check if the last entry in the style relation vector has the
    same type and is part of the same sibling chain. If so just update the existing entry.

* cssjit/SelectorCompiler.cpp:
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateAddStyleRelation):

    The same thing in hand-crafted macro assembler.

* cssjit/SelectorCompiler.h:

    Stop lying about the constness of the CheckingContext.

* style/StyleRelations.cpp:
(WebCore::Style::commitRelations):

    Mark as many sibling elements as the value indicates.

* style/StyleRelations.h:
(WebCore::Style::Relation::Relation):

    Make element a pointer so we can udpate it.

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

Source/WebCore/ChangeLog
Source/WebCore/css/SelectorChecker.cpp
Source/WebCore/cssjit/SelectorCompiler.cpp
Source/WebCore/cssjit/SelectorCompiler.h
Source/WebCore/style/StyleRelations.cpp
Source/WebCore/style/StyleRelations.h

index 4f96e7c..a93bcd9 100644 (file)
@@ -1,3 +1,38 @@
+2016-04-14  Antti Koivisto  <antti@apple.com>
+
+        AffectsNextSibling style relation marking is inefficient
+        https://bugs.webkit.org/show_bug.cgi?id=156593
+
+        Reviewed by Benjamin Poulain.
+
+        We currently add a Style::Relation entry for each sibling to mark. With long sibling lists this can be inefficient
+        in terms of both memory and speed. Instead make a single entry that includes the sibling count to mark.
+
+        * css/SelectorChecker.cpp:
+        (WebCore::addStyleRelation):
+
+            When adding AffectsNextSibling entry check if the last entry in the style relation vector has the
+            same type and is part of the same sibling chain. If so just update the existing entry.
+
+        * cssjit/SelectorCompiler.cpp:
+        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateAddStyleRelation):
+
+            The same thing in hand-crafted macro assembler.
+
+        * cssjit/SelectorCompiler.h:
+
+            Stop lying about the constness of the CheckingContext.
+
+        * style/StyleRelations.cpp:
+        (WebCore::Style::commitRelations):
+
+            Mark as many sibling elements as the value indicates.
+
+        * style/StyleRelations.h:
+        (WebCore::Style::Relation::Relation):
+
+            Make element a pointer so we can udpate it.
+
 2016-04-15  Brady Eidson  <beidson@apple.com>
 
         Add the message property to DOMError.
index 9ae2963..b691ce4 100644 (file)
@@ -89,6 +89,14 @@ static inline void addStyleRelation(SelectorChecker::CheckingContext& checkingCo
     ASSERT(value == 1 || type == Style::Relation::NthChildIndex || type == Style::Relation::AffectedByEmpty);
     if (checkingContext.resolvingMode != SelectorChecker::Mode::ResolvingStyle)
         return;
+    if (type == Style::Relation::AffectsNextSibling && !checkingContext.styleRelations.isEmpty()) {
+        auto& last = checkingContext.styleRelations.last();
+        if (last.type == Style::Relation::AffectsNextSibling && last.element == element.nextElementSibling()) {
+            ++last.value;
+            last.element = &element;
+            return;
+        }
+    }
     checkingContext.styleRelations.append({ element, type, value });
 }
 
index f670db6..ad9ab59 100644 (file)
@@ -2198,16 +2198,56 @@ void SelectorCodeGenerator::generateAddStyleRelation(Assembler::RegisterID check
 {
     ASSERT(m_selectorContext != SelectorContext::QuerySelector);
 
+    Assembler::Address vectorAddress(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, styleRelations));
+    auto dataAddress = vectorAddress.withOffset(Style::Relations::dataMemoryOffset());
+    auto sizeAddress = vectorAddress.withOffset(Style::Relations::sizeMemoryOffset());
+
+    // For AffectsNextSibling we just increment the count if the previous added relation was in the same sibling chain.
+    Assembler::JumpList mergeSuccess;
+    if (relationType == Style::Relation::AffectsNextSibling) {
+        Assembler::JumpList mergeFailure;
+
+        LocalRegister lastRelation(m_registerAllocator);
+        m_assembler.load32(sizeAddress, lastRelation);
+
+        // if (!checkingContext.styleRelations.isEmpty())
+        mergeFailure.append(m_assembler.branchTest32(Assembler::Zero, lastRelation));
+
+        // Style::Relation& lastRelation = checkingContext.styleRelations.last();
+        m_assembler.sub32(Assembler::TrustedImm32(1), lastRelation);
+        m_assembler.mul32(Assembler::TrustedImm32(sizeof(Style::Relation)), lastRelation, lastRelation);
+        m_assembler.addPtr(dataAddress, lastRelation);
+
+        // if (lastRelation.type == Style::Relation::AffectsNextSibling)
+        Assembler::Address typeAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, type));
+        mergeFailure.append(m_assembler.branch32(Assembler::NotEqual, typeAddress, Assembler::TrustedImm32(Style::Relation::AffectsNextSibling)));
+
+        Assembler::Address elementAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, element));
+        {
+            // if (element.nextSiblingElement() == lastRelation.element)
+            LocalRegister nextSiblingElement(m_registerAllocator);
+            m_assembler.move(element, nextSiblingElement);
+            generateWalkToNextAdjacentElement(mergeFailure, nextSiblingElement);
+            mergeFailure.append(m_assembler.branchPtr(Assembler::NotEqual, nextSiblingElement, elementAddress));
+        }
+
+        // ++lastRelation.value;
+        Assembler::Address valueAddress(lastRelation, OBJECT_OFFSETOF(Style::Relation, value));
+        m_assembler.add32(Assembler::TrustedImm32(1), valueAddress);
+
+        // lastRelation.element = &element;
+        m_assembler.storePtr(element, elementAddress);
+
+        mergeSuccess.append(m_assembler.jump());
+        mergeFailure.link(&m_assembler);
+    }
+
     // FIXME: Append to vector without a function call at least when there is sufficient capacity.
     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
     functionCall.setFunctionAddress(addStyleRelationFunction);
     functionCall.setTwoArguments(checkingContext, element);
     functionCall.call();
 
-    Assembler::Address vectorAddress(checkingContext, OBJECT_OFFSETOF(SelectorChecker::CheckingContext, styleRelations));
-    auto dataAddress = vectorAddress.withOffset(Style::Relations::dataMemoryOffset());
-    auto sizeAddress = vectorAddress.withOffset(Style::Relations::sizeMemoryOffset());
-
     LocalRegister relationPointer(m_registerAllocator);
     m_assembler.load32(sizeAddress, relationPointer);
     m_assembler.sub32(Assembler::TrustedImm32(1), relationPointer);
@@ -2221,6 +2261,8 @@ void SelectorCodeGenerator::generateAddStyleRelation(Assembler::RegisterID check
         Assembler::Address valueAddress(relationPointer, OBJECT_OFFSETOF(Style::Relation, value));
         m_assembler.store32(*value, valueAddress);
     }
+
+    mergeSuccess.link(&m_assembler);
 }
 
 Assembler::JumpList SelectorCodeGenerator::jumpIfNoPreviousAdjacentElement()
index a3167b5..3952530 100644 (file)
@@ -80,7 +80,7 @@ enum class SelectorContext {
 typedef unsigned (*RuleCollectorSimpleSelectorChecker)(const Element*, unsigned*);
 typedef unsigned (*QuerySelectorSimpleSelectorChecker)(const Element*);
 
-typedef unsigned (*RuleCollectorSelectorCheckerWithCheckingContext)(const Element*, const SelectorChecker::CheckingContext*, unsigned*);
+typedef unsigned (*RuleCollectorSelectorCheckerWithCheckingContext)(const Element*, SelectorChecker::CheckingContext*, unsigned*);
 typedef unsigned (*QuerySelectorSelectorCheckerWithCheckingContext)(const Element*, const SelectorChecker::CheckingContext*);
 
 SelectorCompilationStatus compileSelector(const CSSSelector*, JSC::VM*, SelectorContext, JSC::MacroAssemblerCodeRef& outputCodeRef);
index 993f8a4..58ea6a5 100644 (file)
@@ -45,7 +45,7 @@ std::unique_ptr<Relations> commitRelationsToRenderStyle(RenderStyle& style, cons
     };
 
     for (auto& relation : relations) {
-        if (&relation.element != &element) {
+        if (relation.element != &element) {
             appendStyleRelation(relation);
             continue;
         }
@@ -91,7 +91,7 @@ void commitRelations(std::unique_ptr<Relations> relations, Update& update)
     if (!relations)
         return;
     for (auto& relation : *relations) {
-        auto& element = const_cast<Element&>(relation.element);
+        auto& element = const_cast<Element&>(*relation.element);
         switch (relation.type) {
         case Relation::AffectedByActive:
             element.setChildrenAffectedByActive();
@@ -108,9 +108,12 @@ void commitRelations(std::unique_ptr<Relations> relations, Update& update)
         case Relation::AffectedByPreviousSibling:
             element.setStyleIsAffectedByPreviousSibling();
             break;
-        case Relation::AffectsNextSibling:
-            element.setAffectsNextSiblingElementStyle();
+        case Relation::AffectsNextSibling: {
+            auto* sibling = &element;
+            for (unsigned i = 0; i < relation.value && sibling; ++i, sibling = sibling->nextElementSibling())
+                sibling->setAffectsNextSiblingElementStyle();
             break;
+        }
         case Relation::ChildrenAffectedByBackwardPositionalRules:
             element.setChildrenAffectedByBackwardPositionalRules();
             break;
index 31aa5cc..b7b40a2 100644 (file)
@@ -44,6 +44,7 @@ struct Relation {
         AffectedByEmpty,
         AffectedByHover,
         AffectedByPreviousSibling,
+        // For AffectsNextSibling 'value' tells how many element siblings to mark starting with 'element'.
         AffectsNextSibling,
         ChildrenAffectedByBackwardPositionalRules,
         ChildrenAffectedByFirstChildRules,
@@ -54,12 +55,12 @@ struct Relation {
         NthChildIndex,
         Unique,
     };
-    const Element& element;
+    const Element* element;
     Type type;
     unsigned value;
 
     Relation(const Element& element, Type type, unsigned value = 1)
-        : element(element)
+        : element(&element)
         , type(type)
         , value(value)
     { }