Make better use of the stack when compiling selectors
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 9 Jan 2015 01:50:41 +0000 (01:50 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 9 Jan 2015 01:50:41 +0000 (01:50 +0000)
commit3c1a492e6ea16571ce8c14cd5800a2fc1c5aef3a
tree37160673229048c53a930b4e8559893925c59b08
parent56b20743ac1009310aedfc43006e291108456595
Make better use of the stack when compiling selectors
https://bugs.webkit.org/show_bug.cgi?id=139615
rdar://problem/19226482

Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-01-08
Reviewed by Andreas Kling.

Source/WebCore:

Selectors used to be only on one level. To avoid memory allocations, we were allocating
a lot of stack upfront and we were using that to create all the intermediary objects
used by the code generator.

Then, selectors became multilevel. We now support arbitrary nesting of selector lists.

We did not adapt any of the structures and the creation of the intermediary object is recursive.
This resulted in over 1k of stack allocation at every level, quickly accumulating to unreasonable
numbers.

This patch fixes this problem by making each stack frame of the recursion much lighter.
We no longer allocate the big objects (SelectorFragment and SelectorFragmentList) on the stack.

In each case where we would have used a Stack allocated SelectorFragment or SelectorFragmentList,
we now allocate the memory directly into the target vector.

In the cases where the object should not be on the vector, we simply remove it. Those are uncommon
cases so that should not be too bad.

Tests: fast/selectors/matches-selector-list-ending-with-never-matching-selectors.html
       fast/selectors/not-selector-list-ending-with-never-matching-selectors.html
       fast/selectors/nth-child-of-selector-list-ending-with-never-matching-selectors.html
       fast/selectors/nth-last-child-of-selector-list-ending-with-never-matching-selectors.html

* cssjit/SelectorCompiler.cpp:
SelectorFragmentList is also used for nested lists. Keeping 32 SelectorFragment preallocated
for each nested list is way too big.

(WebCore::SelectorCompiler::addPseudoClassType):
There are three cases of nested selector lists supported by the compiler: :matches(), :not()
and :nth-child(). For those 3 cases, use the target vector memory instead of the stack.

(WebCore::SelectorCompiler::constructFragmentsInternal):
(WebCore::SelectorCompiler::constructFragments):
Make sure we do not modify the input list on failure since it may be reused.

(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatchesSelectorList):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatchesMatchesPseudoClass):
I changed the handling of :nth-child(An+B of selectorList) to not generate empty filters.
With that we can generalize the assertion to generateElementMatchesSelectorList() and simplify
the flow of selector lists a bit.

LayoutTests:

Those tests are checking the tail behavior of the various loop, just in case.

* fast/selectors/matches-selector-list-ending-with-never-matching-selectors-expected.txt: Added.
* fast/selectors/matches-selector-list-ending-with-never-matching-selectors.html: Added.
* fast/selectors/not-selector-list-ending-with-never-matching-selectors-expected.txt: Added.
* fast/selectors/not-selector-list-ending-with-never-matching-selectors.html: Added.
* fast/selectors/nth-child-of-selector-list-ending-with-never-matching-selectors-expected.txt: Added.
* fast/selectors/nth-child-of-selector-list-ending-with-never-matching-selectors.html: Added.
* fast/selectors/nth-last-child-of-selector-list-ending-with-never-matching-selectors-expected.txt: Added.
* fast/selectors/nth-last-child-of-selector-list-ending-with-never-matching-selectors.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@178150 268f45cc-cd09-0410-ab3c-d52691b4dbfc
LayoutTests/ChangeLog
LayoutTests/fast/selectors/matches-selector-list-ending-with-never-matching-selectors-expected.txt [new file with mode: 0644]
LayoutTests/fast/selectors/matches-selector-list-ending-with-never-matching-selectors.html [new file with mode: 0644]
LayoutTests/fast/selectors/not-selector-list-ending-with-never-matching-selectors-expected.txt [new file with mode: 0644]
LayoutTests/fast/selectors/not-selector-list-ending-with-never-matching-selectors.html [new file with mode: 0644]
LayoutTests/fast/selectors/nth-child-of-selector-list-ending-with-never-matching-selectors-expected.txt [new file with mode: 0644]
LayoutTests/fast/selectors/nth-child-of-selector-list-ending-with-never-matching-selectors.html [new file with mode: 0644]
LayoutTests/fast/selectors/nth-last-child-of-selector-list-ending-with-never-matching-selectors-expected.txt [new file with mode: 0644]
LayoutTests/fast/selectors/nth-last-child-of-selector-list-ending-with-never-matching-selectors.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/cssjit/SelectorCompiler.cpp