Reduce dynamic memory allocation in css jit.
[WebKit-https.git] / Source / WebCore / cssjit / SelectorCompiler.cpp
1 /*
2  * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
3  * Copyright (C) 2014 Yusuke Suzuki <utatane.tea@gmail.com>
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24  * THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "SelectorCompiler.h"
29
30 #if ENABLE(CSS_SELECTOR_JIT)
31
32 #include "CSSSelector.h"
33 #include "CSSSelectorList.h"
34 #include "Element.h"
35 #include "ElementData.h"
36 #include "ElementRareData.h"
37 #include "FunctionCall.h"
38 #include "HTMLDocument.h"
39 #include "HTMLNames.h"
40 #include "InspectorInstrumentation.h"
41 #include "NodeRenderStyle.h"
42 #include "QualifiedName.h"
43 #include "RegisterAllocator.h"
44 #include "RenderElement.h"
45 #include "RenderStyle.h"
46 #include "SVGElement.h"
47 #include "SelectorCheckerTestFunctions.h"
48 #include "StackAllocator.h"
49 #include "StyledElement.h"
50 #include <JavaScriptCore/GPRInfo.h>
51 #include <JavaScriptCore/LinkBuffer.h>
52 #include <JavaScriptCore/MacroAssembler.h>
53 #include <JavaScriptCore/VM.h>
54 #include <limits>
55 #include <wtf/HashMap.h>
56 #include <wtf/HashSet.h>
57 #include <wtf/Vector.h>
58 #include <wtf/text/CString.h>
59
60 namespace WebCore {
61 namespace SelectorCompiler {
62
63 #define CSS_SELECTOR_JIT_DEBUGGING 0
64
65 enum class BacktrackingAction {
66     NoBacktracking,
67     JumpToDescendantEntryPoint,
68     JumpToIndirectAdjacentEntryPoint,
69     JumpToDescendantTreeWalkerEntryPoint,
70     JumpToIndirectAdjacentTreeWalkerEntryPoint,
71     JumpToDescendantTail,
72     JumpToDirectAdjacentTail
73 };
74
75 struct BacktrackingFlag {
76     enum {
77         DescendantEntryPoint = 1,
78         IndirectAdjacentEntryPoint = 1 << 1,
79         SaveDescendantBacktrackingStart = 1 << 2,
80         SaveAdjacentBacktrackingStart = 1 << 3,
81         DirectAdjacentTail = 1 << 4,
82         DescendantTail = 1 << 5,
83         InChainWithDescendantTail = 1 << 6
84     };
85 };
86
87 enum class FragmentRelation {
88     Rightmost,
89     Descendant,
90     Child,
91     DirectAdjacent,
92     IndirectAdjacent
93 };
94
95 enum class FunctionType {
96     SimpleSelectorChecker,
97     SelectorCheckerWithCheckingContext,
98     CannotMatchAnything,
99     CannotCompile
100 };
101
102 enum class FragmentPositionInRootFragments {
103     Rightmost,
104     NotRightmost
105 };
106
107 class AttributeMatchingInfo {
108 public:
109     AttributeMatchingInfo(const CSSSelector* selector, bool canDefaultToCaseSensitiveValueMatch)
110         : m_selector(selector)
111         , m_canDefaultToCaseSensitiveValueMatch(canDefaultToCaseSensitiveValueMatch)
112     {
113     }
114
115     bool canDefaultToCaseSensitiveValueMatch() const { return m_canDefaultToCaseSensitiveValueMatch; }
116     const CSSSelector& selector() const { return *m_selector; }
117
118 private:
119     const CSSSelector* m_selector;
120     bool m_canDefaultToCaseSensitiveValueMatch;
121 };
122
123 static const unsigned invalidHeight = std::numeric_limits<unsigned>::max();
124 static const unsigned invalidWidth = std::numeric_limits<unsigned>::max();
125
126 struct SelectorFragment {
127     SelectorFragment()
128         : traversalBacktrackingAction(BacktrackingAction::NoBacktracking)
129         , matchingTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
130         , matchingPostTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
131         , backtrackingFlags(0)
132         , tagNameMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
133         , tagNameNotMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
134         , heightFromDescendant(0)
135         , tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent(invalidWidth)
136         , tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent(invalidWidth)
137         , widthFromIndirectAdjacent(0)
138         , tagName(nullptr)
139         , id(nullptr)
140         , langFilter(nullptr)
141         , onlyMatchesLinksInQuirksMode(true)
142     {
143     }
144     FragmentRelation relationToLeftFragment;
145     FragmentRelation relationToRightFragment;
146     FragmentPositionInRootFragments positionInRootFragments;
147
148     BacktrackingAction traversalBacktrackingAction;
149     BacktrackingAction matchingTagNameBacktrackingAction;
150     BacktrackingAction matchingPostTagNameBacktrackingAction;
151     unsigned char backtrackingFlags;
152     unsigned tagNameMatchedBacktrackingStartHeightFromDescendant;
153     unsigned tagNameNotMatchedBacktrackingStartHeightFromDescendant;
154     unsigned heightFromDescendant;
155     unsigned tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
156     unsigned tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent;
157     unsigned widthFromIndirectAdjacent;
158
159     const QualifiedName* tagName;
160     const AtomicString* id;
161     const AtomicString* langFilter;
162     Vector<const AtomicStringImpl*, 2> classNames;
163     HashSet<unsigned> pseudoClasses;
164     Vector<JSC::FunctionPtr, 2> unoptimizedPseudoClasses;
165     Vector<AttributeMatchingInfo, 32> attributes;
166     Vector<std::pair<int, int>, 2> nthChildFilters;
167     Vector<SelectorFragment> notFilters;
168     Vector<Vector<SelectorFragment>> anyFilters;
169
170     // For quirks mode, follow this: http://quirks.spec.whatwg.org/#the-:active-and-:hover-quirk
171     // In quirks mode, a compound selector 'selector' that matches the following conditions must not match elements that would not also match the ':any-link' selector.
172     //
173     //    selector uses the ':active' or ':hover' pseudo-classes.
174     //    selector does not use a type selector.
175     //    selector does not use an attribute selector.
176     //    selector does not use an ID selector.
177     //    selector does not use a class selector.
178     //    selector does not use a pseudo-class selector other than ':active' and ':hover'.
179     //    selector does not use a pseudo-element selector.
180     //    selector is not part of an argument to a functional pseudo-class or pseudo-element.
181     bool onlyMatchesLinksInQuirksMode;
182 };
183
184 struct TagNamePattern {
185     TagNamePattern()
186         : tagName(nullptr)
187         , inverted(false)
188     {
189     }
190     const QualifiedName* tagName;
191     bool inverted;
192 };
193
194 typedef JSC::MacroAssembler Assembler;
195 typedef Vector<SelectorFragment, 16> SelectorFragmentList;
196 typedef Vector<TagNamePattern, 16> TagNameList;
197
198 class SelectorCodeGenerator {
199 public:
200     SelectorCodeGenerator(const CSSSelector*, SelectorContext);
201     SelectorCompilationStatus compile(JSC::VM*, JSC::MacroAssemblerCodeRef&);
202
203 private:
204     static const Assembler::RegisterID returnRegister;
205     static const Assembler::RegisterID elementAddressRegister;
206     static const Assembler::RegisterID checkingContextRegister;
207     static const Assembler::RegisterID callFrameRegister;
208
209     void generateSelectorChecker();
210
211     // Element relations tree walker.
212     void generateWalkToParentNode(Assembler::RegisterID targetRegister);
213     void generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister);
214     void generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
215     void generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
216
217     void generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
218     void generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID);
219     void generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment&);
220     void generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
221     void generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
222     void markParentElementIfResolvingStyle(int32_t);
223     void markParentElementIfResolvingStyle(JSC::FunctionPtr);
224
225     void linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction, Assembler::JumpList& localFailureCases);
226     void generateAdjacentBacktrackingTail();
227     void generateDescendantBacktrackingTail();
228     void generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
229
230     // Element properties matchers.
231     void generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment&);
232     void generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
233     void generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
234     void generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment&);
235     void generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment&);
236     void generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment&);
237     void generateElementIsInLanguage(Assembler::JumpList& failureCases, const AtomicString&);
238     void generateElementIsLastChild(Assembler::JumpList& failureCases, const SelectorFragment&);
239     void generateElementIsOnlyChild(Assembler::JumpList& failureCases, const SelectorFragment&);
240     void generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
241     void generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags);
242     void generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment&);
243     void generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo);
244     void generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo);
245     void generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool caseSensitive);
246     void generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool caseSensitive, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest);
247     void generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch);
248     void generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch);
249     void generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames);
250     void generateElementIsLink(Assembler::JumpList& failureCases);
251     void generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment&);
252     void generateElementMatchesNotPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment&);
253     void generateElementMatchesAnyPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment&);
254     void generateElementIsRoot(Assembler::JumpList& failureCases);
255     void generateElementIsTarget(Assembler::JumpList& failureCases);
256
257     // Helpers.
258     void addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t);
259     Assembler::JumpList jumpIfNoPreviousAdjacentElement();
260     Assembler::JumpList jumpIfNoNextAdjacentElement();
261     Assembler::Jump jumpIfNotResolvingStyle(Assembler::RegisterID checkingContextRegister);
262     void generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment&);
263     Assembler::Jump modulo(JSC::MacroAssembler::ResultCondition, Assembler::RegisterID inputDividend, int divisor);
264     void moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor);
265
266     bool generatePrologue();
267     void generateEpilogue();
268     Vector<StackAllocator::StackReference, registerCount> m_prologueStackReferences;
269
270     Assembler m_assembler;
271     RegisterAllocator m_registerAllocator;
272     StackAllocator m_stackAllocator;
273     Vector<std::pair<Assembler::Call, JSC::FunctionPtr>, 32> m_functionCalls;
274
275     SelectorContext m_selectorContext;
276     FunctionType m_functionType;
277     SelectorFragmentList m_selectorFragments;
278     bool m_needsAdjacentBacktrackingStart;
279
280     StackAllocator::StackReference m_checkingContextStackReference;
281
282     Assembler::Label m_descendantEntryPoint;
283     Assembler::Label m_indirectAdjacentEntryPoint;
284     Assembler::Label m_descendantTreeWalkerBacktrackingPoint;
285     Assembler::Label m_indirectAdjacentTreeWalkerBacktrackingPoint;
286     Assembler::RegisterID m_descendantBacktrackingStart;
287     Assembler::JumpList m_descendantBacktrackingFailureCases;
288     StackAllocator::StackReference m_adjacentBacktrackingStart;
289     Assembler::JumpList m_adjacentBacktrackingFailureCases;
290
291 #if CSS_SELECTOR_JIT_DEBUGGING
292     const CSSSelector* m_originalSelector;
293 #endif
294 };
295
296 const Assembler::RegisterID SelectorCodeGenerator::returnRegister = JSC::GPRInfo::returnValueGPR;
297 const Assembler::RegisterID SelectorCodeGenerator::elementAddressRegister = JSC::GPRInfo::argumentGPR0;
298 const Assembler::RegisterID SelectorCodeGenerator::checkingContextRegister = JSC::GPRInfo::argumentGPR1;
299 const Assembler::RegisterID SelectorCodeGenerator::callFrameRegister = JSC::GPRInfo::callFrameRegister;
300
301 enum class FragmentsLevel {
302     Root = 0,
303     InFunctionalPseudoType = 1
304 };
305
306 static FunctionType constructFragments(const CSSSelector* rootSelector, SelectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel, FragmentPositionInRootFragments);
307
308 static void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, bool& needsAdjacentBacktrackingStart);
309
310 SelectorCompilationStatus compileSelector(const CSSSelector* lastSelector, JSC::VM* vm, SelectorContext selectorContext, JSC::MacroAssemblerCodeRef& codeRef)
311 {
312     if (!vm->canUseJIT())
313         return SelectorCompilationStatus::CannotCompile;
314     SelectorCodeGenerator codeGenerator(lastSelector, selectorContext);
315     return codeGenerator.compile(vm, codeRef);
316 }
317
318 static inline FragmentRelation fragmentRelationForSelectorRelation(CSSSelector::Relation relation)
319 {
320     switch (relation) {
321     case CSSSelector::Descendant:
322         return FragmentRelation::Descendant;
323     case CSSSelector::Child:
324         return FragmentRelation::Child;
325     case CSSSelector::DirectAdjacent:
326         return FragmentRelation::DirectAdjacent;
327     case CSSSelector::IndirectAdjacent:
328         return FragmentRelation::IndirectAdjacent;
329     case CSSSelector::SubSelector:
330     case CSSSelector::ShadowDescendant:
331         ASSERT_NOT_REACHED();
332     }
333     ASSERT_NOT_REACHED();
334     return FragmentRelation::Descendant;
335 }
336
337 static inline FunctionType mostRestrictiveFunctionType(FunctionType a, FunctionType b)
338 {
339     return std::max(a, b);
340 }
341
342 static inline bool shouldUseRenderStyleFromCheckingContext(const SelectorFragment& fragment)
343 {
344     // Return true if the position of this fragment is Rightmost in the root fragments.
345     // In this case, we should use the RenderStyle stored in the CheckingContext.
346     return fragment.relationToRightFragment == FragmentRelation::Rightmost && fragment.positionInRootFragments == FragmentPositionInRootFragments::Rightmost;
347 }
348
349 static inline FunctionType addPseudoClassType(const CSSSelector& selector, SelectorFragment& fragment, SelectorContext selectorContext, FragmentPositionInRootFragments positionInRootFragments)
350 {
351     CSSSelector::PseudoClassType type = selector.pseudoClassType();
352     switch (type) {
353     // Unoptimized pseudo selector. They are just function call to a simple testing function.
354     case CSSSelector::PseudoClassAutofill:
355         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isAutofilled));
356         return FunctionType::SimpleSelectorChecker;
357     case CSSSelector::PseudoClassChecked:
358         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isChecked));
359         return FunctionType::SimpleSelectorChecker;
360     case CSSSelector::PseudoClassDefault:
361         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDefaultButtonForForm));
362         return FunctionType::SimpleSelectorChecker;
363     case CSSSelector::PseudoClassDisabled:
364         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isDisabled));
365         return FunctionType::SimpleSelectorChecker;
366     case CSSSelector::PseudoClassEnabled:
367         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isEnabled));
368         return FunctionType::SimpleSelectorChecker;
369     case CSSSelector::PseudoClassFocus:
370         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(SelectorChecker::matchesFocusPseudoClass));
371         return FunctionType::SimpleSelectorChecker;
372     case CSSSelector::PseudoClassIndeterminate:
373         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(shouldAppearIndeterminate));
374         return FunctionType::SimpleSelectorChecker;
375     case CSSSelector::PseudoClassInvalid:
376         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isInvalid));
377         return FunctionType::SimpleSelectorChecker;
378     case CSSSelector::PseudoClassOptional:
379         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isOptionalFormControl));
380         return FunctionType::SimpleSelectorChecker;
381     case CSSSelector::PseudoClassReadOnly:
382         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadOnlyPseudoClass));
383         return FunctionType::SimpleSelectorChecker;
384     case CSSSelector::PseudoClassReadWrite:
385         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesReadWritePseudoClass));
386         return FunctionType::SimpleSelectorChecker;
387     case CSSSelector::PseudoClassRequired:
388         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isRequiredFormControl));
389         return FunctionType::SimpleSelectorChecker;
390     case CSSSelector::PseudoClassValid:
391         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(isValid));
392         return FunctionType::SimpleSelectorChecker;
393 #if ENABLE(FULLSCREEN_API)
394     case CSSSelector::PseudoClassFullScreen:
395         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFullScreenPseudoClass));
396         return FunctionType::SimpleSelectorChecker;
397 #endif
398 #if ENABLE(VIDEO_TRACK)
399     case CSSSelector::PseudoClassFuture:
400         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesFutureCuePseudoClass));
401         return FunctionType::SimpleSelectorChecker;
402     case CSSSelector::PseudoClassPast:
403         fragment.unoptimizedPseudoClasses.append(JSC::FunctionPtr(matchesPastCuePseudoClass));
404         return FunctionType::SimpleSelectorChecker;
405 #endif
406
407     // Optimized pseudo selectors.
408     case CSSSelector::PseudoClassAnyLink:
409         fragment.pseudoClasses.add(CSSSelector::PseudoClassLink);
410         return FunctionType::SimpleSelectorChecker;
411
412     case CSSSelector::PseudoClassLink:
413     case CSSSelector::PseudoClassRoot:
414     case CSSSelector::PseudoClassTarget:
415         fragment.pseudoClasses.add(type);
416         return FunctionType::SimpleSelectorChecker;
417
418     case CSSSelector::PseudoClassActive:
419     case CSSSelector::PseudoClassFirstChild:
420     case CSSSelector::PseudoClassHover:
421     case CSSSelector::PseudoClassLastChild:
422     case CSSSelector::PseudoClassOnlyChild:
423         fragment.pseudoClasses.add(type);
424         if (selectorContext == SelectorContext::QuerySelector)
425             return FunctionType::SimpleSelectorChecker;
426         return FunctionType::SelectorCheckerWithCheckingContext;
427
428     case CSSSelector::PseudoClassNthChild:
429         {
430             if (!selector.parseNth())
431                 return FunctionType::CannotMatchAnything;
432
433             int a = selector.nthA();
434             int b = selector.nthB();
435
436             // The element count is always positive.
437             if (a <= 0 && b < 1)
438                 return FunctionType::CannotMatchAnything;
439
440             fragment.nthChildFilters.append(std::pair<int, int>(a, b));
441             if (selectorContext == SelectorContext::QuerySelector)
442                 return FunctionType::SimpleSelectorChecker;
443             return FunctionType::SelectorCheckerWithCheckingContext;
444         }
445
446     case CSSSelector::PseudoClassNot:
447         {
448             const CSSSelectorList* selectorList = selector.selectorList();
449
450             if (!selectorList)
451                 return FunctionType::CannotMatchAnything;
452
453             SelectorFragmentList notFragments;
454             FunctionType functionType = constructFragments(selectorList->first(), selectorContext, notFragments, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments);
455
456             // Since this is not pseudo class filter, CannotMatchAnything implies this filter always passes.
457             if (functionType == FunctionType::CannotMatchAnything)
458                 return FunctionType::SimpleSelectorChecker;
459
460             if (functionType == FunctionType::CannotCompile)
461                 return functionType;
462
463             ASSERT(notFragments.size() == 1);
464             if (notFragments.size() != 1)
465                 return FunctionType::CannotCompile;
466
467             const SelectorFragment& subFragment = notFragments.first();
468
469             // FIXME: Currently we don't support visitedMatchType.
470             if (subFragment.pseudoClasses.contains(CSSSelector::PseudoClassLink))
471                 return FunctionType::CannotCompile;
472
473             fragment.notFilters.append(subFragment);
474             return functionType;
475         }
476
477     case CSSSelector::PseudoClassAny:
478         {
479             Vector<SelectorFragment, 32> anyFragments;
480             FunctionType functionType = FunctionType::SimpleSelectorChecker;
481             for (const CSSSelector* rootSelector = selector.selectorList()->first(); rootSelector; rootSelector = CSSSelectorList::next(rootSelector)) {
482                 SelectorFragmentList fragmentList;
483                 FunctionType subFunctionType = constructFragments(rootSelector, selectorContext, fragmentList, FragmentsLevel::InFunctionalPseudoType, positionInRootFragments);
484
485                 // Since this fragment always unmatch against the element, don't insert it to anyFragments.
486                 if (subFunctionType == FunctionType::CannotMatchAnything)
487                     continue;
488
489                 if (subFunctionType == FunctionType::CannotCompile)
490                     return FunctionType::CannotCompile;
491
492                 // :any() may not contain complex selectors which have combinators.
493                 ASSERT(fragmentList.size() == 1);
494                 if (fragmentList.size() != 1)
495                     return FunctionType::CannotCompile;
496
497                 const SelectorFragment& subFragment = fragmentList.first();
498                 anyFragments.append(subFragment);
499                 functionType = mostRestrictiveFunctionType(functionType, subFunctionType);
500             }
501
502             // Since all fragments in :any() cannot match anything, this :any() filter cannot match anything.
503             if (anyFragments.isEmpty())
504                 return FunctionType::CannotMatchAnything;
505
506             ASSERT(!anyFragments.isEmpty());
507             fragment.anyFilters.append(anyFragments);
508
509             return functionType;
510         }
511     case CSSSelector::PseudoClassLang:
512         {
513             const AtomicString& argument = selector.argument();
514             if (argument.isEmpty())
515                 return FunctionType::CannotMatchAnything;
516
517             if (!fragment.langFilter)
518                 fragment.langFilter = &argument;
519             else if (*fragment.langFilter != argument) {
520                 // If there are multiple definition, we only care about the most restrictive one.
521                 if (argument.startsWith(*fragment.langFilter, false))
522                     fragment.langFilter = &argument;
523                 else if (fragment.langFilter->startsWith(argument, false))
524                     { } // The existing filter is more restrictive.
525                 else
526                     return FunctionType::CannotMatchAnything;
527             }
528             return FunctionType::SimpleSelectorChecker;
529         }
530
531     default:
532         break;
533     }
534     return FunctionType::CannotCompile;
535 }
536
537 inline SelectorCodeGenerator::SelectorCodeGenerator(const CSSSelector* rootSelector, SelectorContext selectorContext)
538     : m_stackAllocator(m_assembler)
539     , m_selectorContext(selectorContext)
540     , m_functionType(FunctionType::SimpleSelectorChecker)
541     , m_needsAdjacentBacktrackingStart(false)
542 #if CSS_SELECTOR_JIT_DEBUGGING
543     , m_originalSelector(rootSelector)
544 #endif
545 {
546 #if CSS_SELECTOR_JIT_DEBUGGING
547     dataLogF("Compiling \"%s\"\n", m_originalSelector->selectorText().utf8().data());
548 #endif
549
550     m_functionType = constructFragments(rootSelector, m_selectorContext, m_selectorFragments, FragmentsLevel::Root, FragmentPositionInRootFragments::Rightmost);
551     if (m_functionType != FunctionType::CannotCompile && m_functionType != FunctionType::CannotMatchAnything)
552         computeBacktrackingInformation(m_selectorFragments, m_needsAdjacentBacktrackingStart);
553 }
554
555 static bool pseudoClassOnlyMatchesLinksInQuirksMode(const CSSSelector& selector)
556 {
557     CSSSelector::PseudoClassType pseudoClassType = selector.pseudoClassType();
558     return pseudoClassType == CSSSelector::PseudoClassHover || pseudoClassType == CSSSelector::PseudoClassActive;
559 }
560
561 static FunctionType constructFragments(const CSSSelector* rootSelector, SelectorContext selectorContext, SelectorFragmentList& selectorFragments, FragmentsLevel fragmentLevel, FragmentPositionInRootFragments positionInRootFragments)
562 {
563     SelectorFragment fragment;
564     FragmentRelation relationToPreviousFragment = FragmentRelation::Rightmost;
565     FunctionType functionType = FunctionType::SimpleSelectorChecker;
566     for (const CSSSelector* selector = rootSelector; selector; selector = selector->tagHistory()) {
567         switch (selector->m_match) {
568         case CSSSelector::Tag:
569             ASSERT(!fragment.tagName);
570             fragment.tagName = &(selector->tagQName());
571             if (*fragment.tagName != anyQName())
572                 fragment.onlyMatchesLinksInQuirksMode = false;
573             break;
574         case CSSSelector::Id: {
575             const AtomicString& id = selector->value();
576             if (fragment.id) {
577                 if (id != *fragment.id)
578                     return FunctionType::CannotMatchAnything;
579             } else
580                 fragment.id = &(selector->value());
581             fragment.onlyMatchesLinksInQuirksMode = false;
582             break;
583         }
584         case CSSSelector::Class:
585             fragment.classNames.append(selector->value().impl());
586             fragment.onlyMatchesLinksInQuirksMode = false;
587             break;
588         case CSSSelector::PseudoClass: {
589             FragmentPositionInRootFragments subPosition = positionInRootFragments;
590             if (relationToPreviousFragment != FragmentRelation::Rightmost)
591                 subPosition = FragmentPositionInRootFragments::NotRightmost;
592
593             functionType = mostRestrictiveFunctionType(functionType, addPseudoClassType(*selector, fragment, selectorContext, subPosition));
594             if (!pseudoClassOnlyMatchesLinksInQuirksMode(*selector))
595                 fragment.onlyMatchesLinksInQuirksMode = false;
596             if (functionType == FunctionType::CannotCompile || functionType == FunctionType::CannotMatchAnything)
597                 return functionType;
598             break;
599         }
600
601         case CSSSelector::List:
602             if (selector->value().contains(' '))
603                 return FunctionType::CannotMatchAnything;
604             FALLTHROUGH;
605         case CSSSelector::Begin:
606         case CSSSelector::End:
607         case CSSSelector::Contain:
608             if (selector->value().isEmpty())
609                 return FunctionType::CannotMatchAnything;
610             FALLTHROUGH;
611         case CSSSelector::Exact:
612         case CSSSelector::Hyphen:
613             fragment.onlyMatchesLinksInQuirksMode = false;
614             fragment.attributes.append(AttributeMatchingInfo(selector, HTMLDocument::isCaseSensitiveAttribute(selector->attribute())));
615             break;
616
617         case CSSSelector::Set:
618             fragment.onlyMatchesLinksInQuirksMode = false;
619             fragment.attributes.append(AttributeMatchingInfo(selector, true));
620             break;
621         case CSSSelector::PagePseudoClass:
622             fragment.onlyMatchesLinksInQuirksMode = false;
623             // Pseudo page class are only relevant for style resolution, they are ignored for matching.
624             break;
625         case CSSSelector::Unknown:
626             ASSERT_NOT_REACHED();
627             return FunctionType::CannotMatchAnything;
628         case CSSSelector::PseudoElement:
629             fragment.onlyMatchesLinksInQuirksMode = false;
630             return FunctionType::CannotCompile;
631         }
632
633         CSSSelector::Relation relation = selector->relation();
634         if (relation == CSSSelector::SubSelector)
635             continue;
636
637         if (relation == CSSSelector::ShadowDescendant && !selector->isLastInTagHistory())
638             return FunctionType::CannotCompile;
639
640         if (relation == CSSSelector::DirectAdjacent || relation == CSSSelector::IndirectAdjacent) {
641             FunctionType relationFunctionType = FunctionType::SelectorCheckerWithCheckingContext;
642             if (selectorContext == SelectorContext::QuerySelector)
643                 relationFunctionType = FunctionType::SimpleSelectorChecker;
644             functionType = mostRestrictiveFunctionType(functionType, relationFunctionType);
645         }
646
647         fragment.relationToLeftFragment = fragmentRelationForSelectorRelation(relation);
648         fragment.relationToRightFragment = relationToPreviousFragment;
649         fragment.positionInRootFragments = positionInRootFragments;
650         relationToPreviousFragment = fragment.relationToLeftFragment;
651
652         if (fragmentLevel == FragmentsLevel::InFunctionalPseudoType)
653             fragment.onlyMatchesLinksInQuirksMode = false;
654         selectorFragments.append(fragment);
655         fragment = SelectorFragment();
656     }
657     return functionType;
658 }
659
660 static inline bool attributeNameTestingRequiresNamespaceRegister(const CSSSelector& attributeSelector)
661 {
662     return attributeSelector.attribute().prefix() != starAtom && !attributeSelector.attribute().namespaceURI().isNull();
663 }
664
665 static inline bool attributeValueTestingRequiresCaseFoldingRegister(const AttributeMatchingInfo& attributeInfo)
666 {
667     return !attributeInfo.canDefaultToCaseSensitiveValueMatch();
668 }
669
670 // Strict minimum to match anything interesting:
671 // Element + BacktrackingRegister + ElementData + a pointer to values + an index on that pointer + the value we expect;
672 static const unsigned minimumRequiredRegisterCount = 6;
673 // Element + ElementData + scratchRegister + attributeArrayPointer + expectedLocalName + (qualifiedNameImpl && expectedValue).
674 static const unsigned minimumRequiredRegisterCountForAttributeFilter = 6;
675
676 static inline unsigned minimumRegisterRequirements(const SelectorFragment& selectorFragment)
677 {
678     unsigned minimum = minimumRequiredRegisterCount;
679     const Vector<AttributeMatchingInfo>& attributes = selectorFragment.attributes;
680
681     unsigned backtrackingRegisterRequirements = 0;
682     if (selectorFragment.backtrackingFlags & BacktrackingFlag::InChainWithDescendantTail)
683         backtrackingRegisterRequirements = 1; // If there is a DescendantTail, there is a backtracking register.
684
685     // Attributes cause some register pressure.
686     unsigned attributeCount = attributes.size();
687     for (unsigned attributeIndex = 0; attributeIndex < attributeCount; ++attributeIndex) {
688         unsigned attributeMinimum = minimumRequiredRegisterCountForAttributeFilter + backtrackingRegisterRequirements;
689
690         if (attributeIndex + 1 < attributeCount)
691             attributeMinimum += 2; // For the local copy of the counter and attributeArrayPointer.
692
693         const AttributeMatchingInfo& attributeInfo = attributes[attributeIndex];
694         const CSSSelector& attributeSelector = attributeInfo.selector();
695         if (attributeNameTestingRequiresNamespaceRegister(attributeSelector)
696             || attributeValueTestingRequiresCaseFoldingRegister(attributeInfo))
697             attributeMinimum += 1;
698
699         minimum = std::max(minimum, attributeMinimum);
700     }
701
702     // :not pseudo class filters cause some register pressure.
703     for (const SelectorFragment& subFragment : selectorFragment.notFilters) {
704         unsigned notFilterMinimum = minimumRegisterRequirements(subFragment) + backtrackingRegisterRequirements;
705         minimum = std::max(minimum, notFilterMinimum);
706     }
707
708     // :any pseudo class filters cause some register pressure.
709     for (const auto& subFragments : selectorFragment.anyFilters) {
710         for (const SelectorFragment& subFragment : subFragments) {
711             unsigned anyFilterMinimum = minimumRegisterRequirements(subFragment) + backtrackingRegisterRequirements;
712             minimum = std::max(minimum, anyFilterMinimum);
713         }
714     }
715
716     return minimum;
717 }
718
719 static inline unsigned minimumRegisterRequirements(const SelectorFragmentList& selectorFragments)
720 {
721     unsigned minimum = minimumRequiredRegisterCount;
722
723     for (unsigned selectorFragmentIndex = 0; selectorFragmentIndex < selectorFragments.size(); ++selectorFragmentIndex) {
724         const SelectorFragment& selectorFragment = selectorFragments[selectorFragmentIndex];
725         minimum = std::max(minimum, minimumRegisterRequirements(selectorFragment));
726     }
727
728     return minimum;
729 }
730
731 inline SelectorCompilationStatus SelectorCodeGenerator::compile(JSC::VM* vm, JSC::MacroAssemblerCodeRef& codeRef)
732 {
733     switch (m_functionType) {
734     case FunctionType::SimpleSelectorChecker:
735     case FunctionType::SelectorCheckerWithCheckingContext:
736         generateSelectorChecker();
737         break;
738     case FunctionType::CannotMatchAnything:
739         m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
740         m_assembler.ret();
741         break;
742     case FunctionType::CannotCompile:
743         return SelectorCompilationStatus::CannotCompile;
744     }
745
746     JSC::LinkBuffer linkBuffer(*vm, &m_assembler, CSS_CODE_ID);
747     for (unsigned i = 0; i < m_functionCalls.size(); i++)
748         linkBuffer.link(m_functionCalls[i].first, m_functionCalls[i].second);
749
750 #if CSS_SELECTOR_JIT_DEBUGGING
751     codeRef = linkBuffer.finalizeCodeWithDisassembly("CSS Selector JIT for \"%s\"", m_originalSelector->selectorText().utf8().data());
752 #else
753     codeRef = FINALIZE_CODE(linkBuffer, ("CSS Selector JIT"));
754 #endif
755
756     if (m_functionType == FunctionType::SimpleSelectorChecker || m_functionType == FunctionType::CannotMatchAnything)
757         return SelectorCompilationStatus::SimpleSelectorChecker;
758     return SelectorCompilationStatus::SelectorCheckerWithCheckingContext;
759 }
760
761
762 static inline void updateChainStates(const SelectorFragment& fragment, bool& hasDescendantRelationOnTheRight, unsigned& ancestorPositionSinceDescendantRelation, bool& hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned& adjacentPositionSinceIndirectAdjacentTreeWalk)
763 {
764     switch (fragment.relationToRightFragment) {
765     case FragmentRelation::Rightmost:
766         break;
767     case FragmentRelation::Descendant:
768         hasDescendantRelationOnTheRight = true;
769         ancestorPositionSinceDescendantRelation = 0;
770         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
771         break;
772     case FragmentRelation::Child:
773         if (hasDescendantRelationOnTheRight)
774             ++ancestorPositionSinceDescendantRelation;
775         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
776         break;
777     case FragmentRelation::DirectAdjacent:
778         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
779             ++adjacentPositionSinceIndirectAdjacentTreeWalk;
780         break;
781     case FragmentRelation::IndirectAdjacent:
782         hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = true;
783         adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
784         break;
785     }
786 }
787
788 static inline bool isFirstAncestor(unsigned ancestorPositionSinceDescendantRelation)
789 {
790     return ancestorPositionSinceDescendantRelation == 1;
791 }
792
793 static inline bool isFirstAdjacent(unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
794 {
795     return adjacentPositionSinceIndirectAdjacentTreeWalk == 1;
796 }
797
798 static inline BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
799 {
800     // If height is invalid (e.g. There's no tag name).
801     if (backtrackingStartHeightFromDescendant == invalidHeight)
802         return BacktrackingAction::NoBacktracking;
803
804     // Start backtracking from the current element.
805     if (backtrackingStartHeightFromDescendant == fragment.heightFromDescendant)
806         return BacktrackingAction::JumpToDescendantEntryPoint;
807
808     // Start backtracking from the parent of current element.
809     if (backtrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
810         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
811
812     return BacktrackingAction::JumpToDescendantTail;
813 }
814
815 static inline BacktrackingAction solveAdjacentBacktrackingActionForDirectAdjacent(const SelectorFragment& fragment, unsigned backtrackingStartWidthFromIndirectAdjacent)
816 {
817     // If width is invalid (e.g. There's no tag name).
818     if (backtrackingStartWidthFromIndirectAdjacent == invalidWidth)
819         return BacktrackingAction::NoBacktracking;
820
821     // Start backtracking from the current element.
822     if (backtrackingStartWidthFromIndirectAdjacent == fragment.widthFromIndirectAdjacent)
823         return BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
824
825     // Start backtracking from the previous adjacent of current element.
826     if (backtrackingStartWidthFromIndirectAdjacent == (fragment.widthFromIndirectAdjacent + 1))
827         return BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint;
828
829     return BacktrackingAction::JumpToDirectAdjacentTail;
830 }
831
832 static inline BacktrackingAction solveAdjacentTraversalBacktrackingAction(const SelectorFragment& fragment, bool hasDescendantRelationOnTheRight)
833 {
834     if (!hasDescendantRelationOnTheRight)
835         return BacktrackingAction::NoBacktracking;
836
837     if (fragment.tagNameMatchedBacktrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
838         return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
839
840     return BacktrackingAction::JumpToDescendantTail;
841 }
842
843 static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
844 {
845     switch (fragment.relationToRightFragment) {
846     case FragmentRelation::Rightmost:
847     case FragmentRelation::Descendant:
848         break;
849     case FragmentRelation::Child:
850         // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
851         if (hasDescendantRelationOnTheRight) {
852             fragment.matchingTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant);
853             fragment.matchingPostTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
854         }
855         break;
856     case FragmentRelation::DirectAdjacent:
857         // Failure on traversal implies no other sibling traversal can match. Matching should resume at the
858         // nearest ancestor/descendant traversal.
859         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
860
861         // If the rightmost relation is a indirect adjacent, matching sould resume from there.
862         // Otherwise, we resume from the latest ancestor/descendant if any.
863         if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
864             fragment.matchingTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent);
865             fragment.matchingPostTagNameBacktrackingAction = solveAdjacentBacktrackingActionForDirectAdjacent(fragment, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
866         } else if (hasDescendantRelationOnTheRight) {
867             // Since we resume from the latest ancestor/descendant, the action is the same as the traversal action.
868             fragment.matchingTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
869             fragment.matchingPostTagNameBacktrackingAction = fragment.traversalBacktrackingAction;
870         }
871         break;
872     case FragmentRelation::IndirectAdjacent:
873         // Failure on traversal implies no other sibling matching will succeed. Matching can resume
874         // from the latest ancestor/descendant.
875         fragment.traversalBacktrackingAction = solveAdjacentTraversalBacktrackingAction(fragment, hasDescendantRelationOnTheRight);
876         break;
877     }
878 }
879
880 enum class TagNameEquality {
881     StrictlyNotEqual,
882     MaybeEqual,
883     StrictlyEqual
884 };
885
886 static inline TagNameEquality equalTagNames(const QualifiedName* lhs, const QualifiedName* rhs)
887 {
888     if (!lhs || *lhs == anyQName())
889         return TagNameEquality::MaybeEqual;
890
891     if (!rhs || *rhs == anyQName())
892         return TagNameEquality::MaybeEqual;
893
894     ASSERT(lhs && rhs);
895
896     const AtomicString& lhsLocalName = lhs->localName();
897     const AtomicString& rhsLocalName = rhs->localName();
898     if (lhsLocalName != starAtom && rhsLocalName != starAtom) {
899         if (lhsLocalName != rhsLocalName)
900             return TagNameEquality::StrictlyNotEqual;
901         return TagNameEquality::StrictlyEqual;
902     }
903
904     const AtomicString& lhsNamespaceURI = lhs->namespaceURI();
905     const AtomicString& rhsNamespaceURI = rhs->namespaceURI();
906     if (lhsNamespaceURI != starAtom && rhsNamespaceURI != starAtom) {
907         if (lhsNamespaceURI != rhsNamespaceURI)
908             return TagNameEquality::StrictlyNotEqual;
909         return TagNameEquality::StrictlyEqual;
910     }
911
912     return TagNameEquality::MaybeEqual;
913 }
914
915 static inline bool equalTagNamePatterns(const TagNamePattern& lhs, const QualifiedName* rhs)
916 {
917     TagNameEquality result = equalTagNames(lhs.tagName, rhs);
918     if (result == TagNameEquality::MaybeEqual)
919         return true;
920
921     // If both rhs & lhs have actual localName (or NamespaceURI),
922     // TagNameEquality result becomes StrictlyEqual or StrictlyNotEqual Since inverted lhs never matches on rhs.
923     bool equal = result == TagNameEquality::StrictlyEqual;
924     if (lhs.inverted)
925         return !equal;
926     return equal;
927 }
928
929 // Find the largest matching prefix from already known tagNames.
930 // And by using this, compute an appropriate height of backtracking start element from the closest base element in the chain.
931 static inline unsigned computeBacktrackingStartOffsetInChain(const TagNameList& tagNames, unsigned maxPrefixSize)
932 {
933     RELEASE_ASSERT(!tagNames.isEmpty());
934     RELEASE_ASSERT(maxPrefixSize < tagNames.size());
935
936     for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; --largestPrefixSize) {
937         unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
938         bool matched = true;
939         // Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
940         for (unsigned i = 0; i < largestPrefixSize; ++i) {
941             unsigned lastIndex = tagNames.size() - 1;
942             unsigned currentIndex = lastIndex - i;
943             if (!equalTagNamePatterns(tagNames[currentIndex], tagNames[currentIndex - offsetToLargestPrefix].tagName)) {
944                 matched = false;
945                 break;
946             }
947         }
948         if (matched)
949             return offsetToLargestPrefix;
950     }
951     return tagNames.size();
952 }
953
954 static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNamesForChildChain, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragmentInChildChain)
955 {
956     if (!hasDescendantRelationOnTheRight)
957         return;
958
959     if (fragment.relationToRightFragment == FragmentRelation::Descendant) {
960         tagNamesForChildChain.clear();
961
962         TagNamePattern pattern;
963         pattern.tagName = fragment.tagName;
964         tagNamesForChildChain.append(pattern);
965         fragment.heightFromDescendant = 0;
966         previousChildFragmentInChildChain = nullptr;
967     } else if (fragment.relationToRightFragment == FragmentRelation::Child) {
968         TagNamePattern pattern;
969         pattern.tagName = fragment.tagName;
970         tagNamesForChildChain.append(pattern);
971
972         unsigned maxPrefixSize = tagNamesForChildChain.size() - 1;
973         if (previousChildFragmentInChildChain) {
974             RELEASE_ASSERT(tagNamesForChildChain.size() >= previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant);
975             maxPrefixSize = tagNamesForChildChain.size() - previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
976         }
977
978         if (pattern.tagName) {
979             // Compute height from descendant in the case that tagName is not matched.
980             tagNamesForChildChain.last().inverted = true;
981             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
982         }
983
984         // Compute height from descendant in the case that tagName is matched.
985         tagNamesForChildChain.last().inverted = false;
986         fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartOffsetInChain(tagNamesForChildChain, maxPrefixSize);
987         fragment.heightFromDescendant = tagNamesForChildChain.size() - 1;
988         previousChildFragmentInChildChain = &fragment;
989     } else {
990         if (previousChildFragmentInChildChain) {
991             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameNotMatchedBacktrackingStartHeightFromDescendant;
992             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInChildChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
993             fragment.heightFromDescendant = previousChildFragmentInChildChain->heightFromDescendant;
994         } else {
995             fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
996             fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = tagNamesForChildChain.size();
997             fragment.heightFromDescendant = 0;
998         }
999     }
1000 }
1001
1002 static inline void computeBacktrackingWidthFromIndirectAdjacent(SelectorFragment& fragment, TagNameList& tagNamesForDirectAdjacentChain, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, const SelectorFragment*& previousDirectAdjacentFragmentInDirectAdjacentChain)
1003 {
1004     if (!hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain)
1005         return;
1006
1007     if (fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent) {
1008         tagNamesForDirectAdjacentChain.clear();
1009
1010         TagNamePattern pattern;
1011         pattern.tagName = fragment.tagName;
1012         tagNamesForDirectAdjacentChain.append(pattern);
1013         fragment.widthFromIndirectAdjacent = 0;
1014         previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1015     } else if (fragment.relationToRightFragment == FragmentRelation::DirectAdjacent) {
1016         TagNamePattern pattern;
1017         pattern.tagName = fragment.tagName;
1018         tagNamesForDirectAdjacentChain.append(pattern);
1019
1020         unsigned maxPrefixSize = tagNamesForDirectAdjacentChain.size() - 1;
1021         if (previousDirectAdjacentFragmentInDirectAdjacentChain) {
1022             RELEASE_ASSERT(tagNamesForDirectAdjacentChain.size() >= previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1023             maxPrefixSize = tagNamesForDirectAdjacentChain.size() - previousDirectAdjacentFragmentInDirectAdjacentChain->tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent;
1024         }
1025
1026         if (pattern.tagName) {
1027             // Compute height from descendant in the case that tagName is not matched.
1028             tagNamesForDirectAdjacentChain.last().inverted = true;
1029             fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1030         }
1031
1032         // Compute height from descendant in the case that tagName is matched.
1033         tagNamesForDirectAdjacentChain.last().inverted = false;
1034         fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent = computeBacktrackingStartOffsetInChain(tagNamesForDirectAdjacentChain, maxPrefixSize);
1035         fragment.widthFromIndirectAdjacent = tagNamesForDirectAdjacentChain.size() - 1;
1036         previousDirectAdjacentFragmentInDirectAdjacentChain = &fragment;
1037     }
1038 }
1039
1040 static bool requiresAdjacentTail(const SelectorFragment& fragment)
1041 {
1042     ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
1043     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
1044 }
1045
1046 static bool requiresDescendantTail(const SelectorFragment& fragment)
1047 {
1048     return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
1049 }
1050
1051 void computeBacktrackingInformation(SelectorFragmentList& selectorFragments, bool& needsAdjacentBacktrackingStart)
1052 {
1053     bool hasDescendantRelationOnTheRight = false;
1054     unsigned ancestorPositionSinceDescendantRelation = 0;
1055     bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain = false;
1056     unsigned adjacentPositionSinceIndirectAdjacentTreeWalk = 0;
1057
1058     bool needsAdjacentTail = false;
1059     bool needsDescendantTail = false;
1060     unsigned saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1061     unsigned saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1062
1063     TagNameList tagNamesForChildChain;
1064     TagNameList tagNamesForDirectAdjacentChain;
1065     const SelectorFragment* previousChildFragmentInChildChain = nullptr;
1066     const SelectorFragment* previousDirectAdjacentFragmentInDirectAdjacentChain = nullptr;
1067
1068     for (unsigned i = 0; i < selectorFragments.size(); ++i) {
1069         SelectorFragment& fragment = selectorFragments[i];
1070
1071         updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
1072
1073         computeBacktrackingHeightFromDescendant(fragment, tagNamesForChildChain, hasDescendantRelationOnTheRight, previousChildFragmentInChildChain);
1074
1075         computeBacktrackingWidthFromIndirectAdjacent(fragment, tagNamesForDirectAdjacentChain, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, previousDirectAdjacentFragmentInDirectAdjacentChain);
1076
1077 #if CSS_SELECTOR_JIT_DEBUGGING
1078         dataLogF("Computing fragment[%d] backtracking height %u. NotMatched %u / Matched %u | width %u. NotMatched %u / Matched %u\n", i, fragment.heightFromDescendant, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant, fragment.widthFromIndirectAdjacent, fragment.tagNameNotMatchedBacktrackingStartWidthFromIndirectAdjacent, fragment.tagNameMatchedBacktrackingStartWidthFromIndirectAdjacent);
1079 #endif
1080
1081         solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain);
1082
1083         needsAdjacentTail |= requiresAdjacentTail(fragment);
1084         needsDescendantTail |= requiresDescendantTail(fragment);
1085
1086         // Add code generation flags.
1087         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Descendant)
1088             fragment.backtrackingFlags |= BacktrackingFlag::DescendantEntryPoint;
1089         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
1090             fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
1091         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation)) {
1092             ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1093             saveDescendantBacktrackingStartFragmentIndex = i;
1094         }
1095         if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
1096             ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
1097             saveIndirectAdjacentBacktrackingStartFragmentIndex = i;
1098         }
1099         if (fragment.relationToLeftFragment != FragmentRelation::DirectAdjacent) {
1100             if (needsAdjacentTail) {
1101                 ASSERT(fragment.relationToRightFragment == FragmentRelation::DirectAdjacent);
1102                 ASSERT(saveIndirectAdjacentBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1103                 fragment.backtrackingFlags |= BacktrackingFlag::DirectAdjacentTail;
1104                 selectorFragments[saveIndirectAdjacentBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
1105                 needsAdjacentBacktrackingStart = true;
1106                 needsAdjacentTail = false;
1107             }
1108             saveIndirectAdjacentBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1109         }
1110         if (fragment.relationToLeftFragment == FragmentRelation::Descendant) {
1111             if (needsDescendantTail) {
1112                 ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
1113                 fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
1114                 selectorFragments[saveDescendantBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
1115                 needsDescendantTail = false;
1116                 for (unsigned j = saveDescendantBacktrackingStartFragmentIndex; j <= i; ++j)
1117                     selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;
1118             }
1119             saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
1120         }
1121     }
1122 }
1123
1124 inline bool SelectorCodeGenerator::generatePrologue()
1125 {
1126 #if CPU(ARM64)
1127     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1128     prologueRegisters.append(JSC::ARM64Registers::lr);
1129     prologueRegisters.append(JSC::ARM64Registers::fp);
1130     m_stackAllocator.push(m_prologueStackReferences, prologueRegisters);
1131     return true;
1132 #elif CPU(ARM_THUMB2)
1133     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1134     prologueRegisters.append(JSC::ARMRegisters::lr);
1135     // r6 is tempRegister in RegisterAllocator.h and addressTempRegister in MacroAssemblerARMv7.h and must be preserved by the callee.
1136     prologueRegisters.append(JSC::ARMRegisters::r6);
1137     m_stackAllocator.push(m_prologueStackReferences, prologueRegisters);
1138     return true;
1139 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1140     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
1141     prologueRegister.append(callFrameRegister);
1142     m_stackAllocator.push(m_prologueStackReferences, prologueRegister);
1143     return true;
1144 #endif
1145     return false;
1146 }
1147
1148 inline void SelectorCodeGenerator::generateEpilogue()
1149 {
1150 #if CPU(ARM64)
1151     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1152     prologueRegisters.append(JSC::ARM64Registers::lr);
1153     prologueRegisters.append(JSC::ARM64Registers::fp);
1154     m_stackAllocator.pop(m_prologueStackReferences, prologueRegisters);
1155 #elif CPU(ARM_THUMB2)
1156     Vector<JSC::MacroAssembler::RegisterID, 2> prologueRegisters;
1157     prologueRegisters.append(JSC::ARMRegisters::lr);
1158     prologueRegisters.append(JSC::ARMRegisters::r6);
1159     m_stackAllocator.pop(m_prologueStackReferences, prologueRegisters);
1160 #elif CPU(X86_64) && CSS_SELECTOR_JIT_DEBUGGING
1161     Vector<JSC::MacroAssembler::RegisterID, 1> prologueRegister;
1162     prologueRegister.append(callFrameRegister);
1163     m_stackAllocator.pop(m_prologueStackReferences, prologueRegister);
1164 #endif
1165 }
1166
1167 void SelectorCodeGenerator::generateSelectorChecker()
1168 {
1169     Vector<StackAllocator::StackReference, registerCount> calleeSavedRegisterStackReferences;
1170     bool reservedCalleeSavedRegisters = false;
1171     unsigned availableRegisterCount = m_registerAllocator.availableRegisterCount();
1172     unsigned minimumRegisterCountForAttributes = minimumRegisterRequirements(m_selectorFragments);
1173 #if CSS_SELECTOR_JIT_DEBUGGING
1174     dataLogF("Compiling with minimum required register count %u\n", minimumRegisterCountForAttributes);
1175 #endif
1176     
1177     bool needsEpilogue = generatePrologue();
1178     
1179     ASSERT(minimumRegisterCountForAttributes <= registerCount);
1180     if (availableRegisterCount < minimumRegisterCountForAttributes) {
1181         reservedCalleeSavedRegisters = true;
1182         m_stackAllocator.push(calleeSavedRegisterStackReferences, m_registerAllocator.reserveCalleeSavedRegisters(minimumRegisterCountForAttributes - availableRegisterCount));
1183     }
1184
1185     m_registerAllocator.allocateRegister(elementAddressRegister);
1186
1187     if (m_functionType == FunctionType::SelectorCheckerWithCheckingContext)
1188         m_checkingContextStackReference = m_stackAllocator.push(checkingContextRegister);
1189
1190     if (m_needsAdjacentBacktrackingStart)
1191         m_adjacentBacktrackingStart = m_stackAllocator.allocateUninitialized();
1192
1193     Assembler::JumpList failureCases;
1194
1195     for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
1196         const SelectorFragment& fragment = m_selectorFragments[i];
1197         switch (fragment.relationToRightFragment) {
1198         case FragmentRelation::Rightmost:
1199             generateElementMatching(failureCases, failureCases, fragment);
1200             break;
1201         case FragmentRelation::Descendant:
1202             generateAncestorTreeWalker(failureCases, fragment);
1203             break;
1204         case FragmentRelation::Child:
1205             generateParentElementTreeWalker(failureCases, fragment);
1206             break;
1207         case FragmentRelation::DirectAdjacent:
1208             generateDirectAdjacentTreeWalker(failureCases, fragment);
1209             break;
1210         case FragmentRelation::IndirectAdjacent:
1211             generateIndirectAdjacentTreeWalker(failureCases, fragment);
1212             break;
1213         }
1214         generateBacktrackingTailsIfNeeded(failureCases, fragment);
1215     }
1216
1217     m_registerAllocator.deallocateRegister(elementAddressRegister);
1218
1219     if (m_functionType == FunctionType::SimpleSelectorChecker) {
1220         if (!m_needsAdjacentBacktrackingStart && !reservedCalleeSavedRegisters && !needsEpilogue) {
1221             // Success.
1222             m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1223             m_assembler.ret();
1224
1225             // Failure.
1226             if (!failureCases.empty()) {
1227                 failureCases.link(&m_assembler);
1228                 m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1229                 m_assembler.ret();
1230             }
1231         } else {
1232             // Success.
1233             m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1234
1235             // Failure.
1236             if (!failureCases.empty()) {
1237                 Assembler::Jump skipFailureCase = m_assembler.jump();
1238                 failureCases.link(&m_assembler);
1239                 m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1240                 skipFailureCase.link(&m_assembler);
1241             }
1242
1243             if (m_needsAdjacentBacktrackingStart)
1244                 m_stackAllocator.popAndDiscardUpTo(m_adjacentBacktrackingStart);
1245             if (reservedCalleeSavedRegisters)
1246                 m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1247             if (needsEpilogue)
1248                 generateEpilogue();
1249             m_assembler.ret();
1250         }
1251     } else {
1252         ASSERT(m_functionType == FunctionType::SelectorCheckerWithCheckingContext);
1253
1254         // Success.
1255         m_assembler.move(Assembler::TrustedImm32(1), returnRegister);
1256
1257         // Failure.
1258         if (!failureCases.empty()) {
1259             Assembler::Jump skipFailureCase = m_assembler.jump();
1260             failureCases.link(&m_assembler);
1261             m_assembler.move(Assembler::TrustedImm32(0), returnRegister);
1262             skipFailureCase.link(&m_assembler);
1263         }
1264
1265         m_stackAllocator.popAndDiscardUpTo(m_checkingContextStackReference);
1266         if (reservedCalleeSavedRegisters)
1267             m_stackAllocator.pop(calleeSavedRegisterStackReferences, m_registerAllocator.restoreCalleeSavedRegisters());
1268         if (needsEpilogue)
1269             generateEpilogue();
1270         m_assembler.ret();
1271     }
1272 }
1273
1274 static inline Assembler::Jump testIsElementFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
1275 {
1276     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsElement()));
1277 }
1278
1279 void SelectorCodeGenerator::generateWalkToParentNode(Assembler::RegisterID targetRegister)
1280 {
1281     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
1282 }
1283
1284 void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
1285 {
1286     //    ContainerNode* parent = parentNode()
1287     //    if (!parent || !parent->isElementNode())
1288     //         failure
1289     generateWalkToParentNode(targetRegister);
1290     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
1291     failureCases.append(testIsElementFlagOnNode(Assembler::Zero, m_assembler, targetRegister));
1292 }
1293
1294 void SelectorCodeGenerator::generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1295 {
1296     Assembler::JumpList traversalFailureCases;
1297     generateWalkToParentElement(traversalFailureCases, elementAddressRegister);
1298     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
1299
1300     Assembler::JumpList matchingTagNameFailureCases;
1301     Assembler::JumpList matchingPostTagNameFailureCases;
1302     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
1303     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
1304     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
1305
1306     if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
1307         m_descendantBacktrackingStart = m_registerAllocator.allocateRegister();
1308         m_assembler.move(elementAddressRegister, m_descendantBacktrackingStart);
1309     }
1310 }
1311
1312 void SelectorCodeGenerator::generateAncestorTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1313 {
1314     // Loop over the ancestors until one of them matches the fragment.
1315     Assembler::Label loopStart(m_assembler.label());
1316
1317     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
1318         m_descendantTreeWalkerBacktrackingPoint = m_assembler.label();
1319
1320     generateWalkToParentElement(failureCases, elementAddressRegister);
1321
1322     if (fragment.backtrackingFlags & BacktrackingFlag::DescendantEntryPoint)
1323         m_descendantEntryPoint = m_assembler.label();
1324
1325     Assembler::JumpList matchingFailureCases;
1326     generateElementMatching(matchingFailureCases, matchingFailureCases, fragment);
1327     matchingFailureCases.linkTo(loopStart, &m_assembler);
1328 }
1329
1330 inline void SelectorCodeGenerator::generateWalkToNextAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
1331 {
1332     Assembler::Label loopStart = m_assembler.label();
1333     m_assembler.loadPtr(Assembler::Address(workRegister, Node::nextSiblingMemoryOffset()), workRegister);
1334     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
1335     testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
1336 }
1337
1338 inline void SelectorCodeGenerator::generateWalkToPreviousAdjacentElement(Assembler::JumpList& failureCases, Assembler::RegisterID workRegister)
1339 {
1340     Assembler::Label loopStart = m_assembler.label();
1341     m_assembler.loadPtr(Assembler::Address(workRegister, Node::previousSiblingMemoryOffset()), workRegister);
1342     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, workRegister));
1343     testIsElementFlagOnNode(Assembler::Zero, m_assembler, workRegister).linkTo(loopStart, &m_assembler);
1344 }
1345
1346 void SelectorCodeGenerator::generateWalkToPreviousAdjacent(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1347 {
1348     //    do {
1349     //        previousSibling = previousSibling->previousSibling();
1350     //        if (!previousSibling)
1351     //            failure!
1352     //    while (!previousSibling->isElement());
1353     Assembler::RegisterID previousSibling;
1354     bool useTailOnTraversalFailure = fragment.traversalBacktrackingAction >= BacktrackingAction::JumpToDescendantTail;
1355     if (!useTailOnTraversalFailure) {
1356         // If the current fragment is not dependant on a previously saved elementAddressRegister, a fast recover
1357         // from a failure would resume with elementAddressRegister.
1358         // When walking to the previous sibling, the failure can be that previousSibling is null. We cannot backtrack
1359         // with a null elementAddressRegister so we do the traversal on a copy.
1360         previousSibling = m_registerAllocator.allocateRegister();
1361         m_assembler.move(elementAddressRegister, previousSibling);
1362     } else
1363         previousSibling = elementAddressRegister;
1364
1365     Assembler::JumpList traversalFailureCases;
1366     generateWalkToPreviousAdjacentElement(traversalFailureCases, previousSibling);
1367     linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
1368
1369     // On success, move previousSibling over to elementAddressRegister if we could not work on elementAddressRegister directly.
1370     if (!useTailOnTraversalFailure) {
1371         m_assembler.move(previousSibling, elementAddressRegister);
1372         m_registerAllocator.deallocateRegister(previousSibling);
1373     }
1374 }
1375
1376 void SelectorCodeGenerator::generateDirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1377 {
1378     markParentElementIfResolvingStyle(Node::flagChildrenAffectedByDirectAdjacentRulesFlag());
1379
1380     generateWalkToPreviousAdjacent(failureCases, fragment);
1381
1382     Assembler::JumpList matchingTagNameFailureCases;
1383     Assembler::JumpList matchingPostTagNameFailureCases;
1384     generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
1385     linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
1386     linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
1387
1388     if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart) {
1389         unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
1390         m_assembler.storePtr(elementAddressRegister, Assembler::Address(Assembler::stackPointerRegister, offsetToAdjacentBacktrackingStart));
1391     }
1392 }
1393
1394 void SelectorCodeGenerator::generateIndirectAdjacentTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1395 {
1396     markParentElementIfResolvingStyle(Element::setChildrenAffectedByForwardPositionalRules);
1397
1398     Assembler::Label loopStart(m_assembler.label());
1399
1400     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
1401         m_indirectAdjacentTreeWalkerBacktrackingPoint = m_assembler.label();
1402
1403     generateWalkToPreviousAdjacent(failureCases, fragment);
1404
1405     if (fragment.backtrackingFlags & BacktrackingFlag::IndirectAdjacentEntryPoint)
1406         m_indirectAdjacentEntryPoint = m_assembler.label();
1407
1408     Assembler::JumpList localFailureCases;
1409     generateElementMatching(localFailureCases, localFailureCases, fragment);
1410     localFailureCases.linkTo(loopStart, &m_assembler);
1411 }
1412
1413
1414 void SelectorCodeGenerator::addFlagsToElementStyleFromContext(Assembler::RegisterID checkingContext, int64_t newFlag)
1415 {
1416     LocalRegister childStyle(m_registerAllocator);
1417     m_assembler.loadPtr(Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, elementStyle)), childStyle);
1418
1419     // FIXME: We should look into doing something smart in MacroAssembler instead.
1420     Assembler::Address flagAddress(childStyle, RenderStyle::noninheritedFlagsMemoryOffset() + RenderStyle::NonInheritedFlags::flagsMemoryOffset());
1421 #if CPU(ARM_THUMB2)
1422     int32_t flagLowBits = newFlag & 0xffffffff;
1423     int32_t flagHighBits = newFlag >> 32;
1424     if (flagLowBits)
1425         m_assembler.or32(Assembler::TrustedImm32(flagLowBits), flagAddress);
1426     if (flagHighBits) {
1427         Assembler::Address flagHighAddress = flagAddress.withOffset(4);
1428         m_assembler.or32(Assembler::TrustedImm32(flagHighBits), flagHighAddress);
1429     }
1430 #elif CPU(X86_64) || CPU(ARM64)
1431     LocalRegister flags(m_registerAllocator);
1432     m_assembler.load64(flagAddress, flags);
1433     LocalRegister isFirstChildStateFlagImmediate(m_registerAllocator);
1434     m_assembler.move(Assembler::TrustedImm64(newFlag), isFirstChildStateFlagImmediate);
1435     m_assembler.or64(isFirstChildStateFlagImmediate, flags);
1436     m_assembler.store64(flags, flagAddress);
1437 #else
1438 #error SelectorCodeGenerator::addFlagsToElementStyleFromContext not implemented for this architecture.
1439 #endif
1440 }
1441
1442 Assembler::JumpList SelectorCodeGenerator::jumpIfNoPreviousAdjacentElement()
1443 {
1444     Assembler::JumpList successCase;
1445     LocalRegister previousSibling(m_registerAllocator);
1446     m_assembler.move(elementAddressRegister, previousSibling);
1447     generateWalkToPreviousAdjacentElement(successCase, previousSibling);
1448     return successCase;
1449 }
1450
1451 Assembler::JumpList SelectorCodeGenerator::jumpIfNoNextAdjacentElement()
1452 {
1453     Assembler::JumpList successCase;
1454     LocalRegister nextSibling(m_registerAllocator);
1455     m_assembler.move(elementAddressRegister, nextSibling);
1456     generateWalkToNextAdjacentElement(successCase, nextSibling);
1457     return successCase;
1458 }
1459
1460 Assembler::Jump SelectorCodeGenerator::jumpIfNotResolvingStyle(Assembler::RegisterID checkingContext)
1461 {
1462     RELEASE_ASSERT(m_selectorContext == SelectorContext::RuleCollector);
1463
1464     // Get the checking context.
1465     unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
1466     m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
1467
1468     // If we not resolving style, skip the whole marking.
1469     return m_assembler.branch8(Assembler::NotEqual, Assembler::Address(checkingContext, OBJECT_OFFSETOF(CheckingContext, resolvingMode)), Assembler::TrustedImm32(SelectorChecker::ResolvingStyle));
1470 }
1471
1472 static void getDocument(Assembler& assembler, Assembler::RegisterID element, Assembler::RegisterID output)
1473 {
1474     assembler.loadPtr(Assembler::Address(element, Node::treeScopeMemoryOffset()), output);
1475     assembler.loadPtr(Assembler::Address(output, TreeScope::documentScopeMemoryOffset()), output);
1476 }
1477
1478 void SelectorCodeGenerator::generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1479 {
1480     if (fragment.onlyMatchesLinksInQuirksMode) {
1481         // If the element is a link, it can always match :hover or :active.
1482         Assembler::Jump isLink = m_assembler.branchTest32(Assembler::NonZero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink()));
1483
1484         // Only quirks mode restrict :hover and :active.
1485         static_assert(sizeof(DocumentCompatibilityMode) == 1, "We generate a byte load/test for the compatibility mode.");
1486         LocalRegister documentAddress(m_registerAllocator);
1487         getDocument(m_assembler, elementAddressRegister, documentAddress);
1488         failureCases.append(m_assembler.branchTest8(Assembler::NonZero, Assembler::Address(documentAddress, Document::compatibilityModeMemoryOffset()), Assembler::TrustedImm32(static_cast<std::underlying_type<DocumentCompatibilityMode>::type>(DocumentCompatibilityMode::QuirksMode))));
1489
1490         isLink.link(&m_assembler);
1491     }
1492 }
1493
1494 #if CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
1495 // FIXME: This could be implemented in assembly to avoid a function call, and we know the divisor at jit-compile time.
1496 static int moduloHelper(int dividend, int divisor)
1497 {
1498     return dividend % divisor;
1499 }
1500 #endif
1501
1502 // The value in inputDividend is destroyed by the modulo operation.
1503 Assembler::Jump SelectorCodeGenerator::modulo(Assembler::ResultCondition condition, Assembler::RegisterID inputDividend, int divisor)
1504 {
1505     RELEASE_ASSERT(divisor);
1506 #if CPU(ARM64) || CPU(APPLE_ARMV7S)
1507     LocalRegister divisorRegister(m_registerAllocator);
1508     m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
1509
1510     LocalRegister resultRegister(m_registerAllocator);
1511     m_assembler.m_assembler.sdiv<32>(resultRegister, inputDividend, divisorRegister);
1512     m_assembler.mul32(divisorRegister, resultRegister);
1513     return m_assembler.branchSub32(condition, inputDividend, resultRegister, resultRegister);
1514 #elif CPU(ARM_THUMB2) && !CPU(APPLE_ARMV7S)
1515     LocalRegisterWithPreference divisorRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
1516     m_assembler.move(Assembler::TrustedImm32(divisor), divisorRegister);
1517     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1518     functionCall.setFunctionAddress(moduloHelper);
1519     functionCall.setTwoArguments(inputDividend, divisorRegister);
1520     return functionCall.callAndBranchOnBooleanReturnValue(condition);
1521 #elif CPU(X86_64)
1522     // idiv takes RAX + an arbitrary register, and return RAX + RDX. Most of this code is about doing
1523     // an efficient allocation of those registers. If a register is already in use and is not the inputDividend,
1524     // we first try to copy it to a temporary register, it that is not possible we fall back to the stack.
1525     enum class RegisterAllocationType {
1526         External,
1527         AllocatedLocally,
1528         CopiedToTemporary,
1529         PushedToStack
1530     };
1531
1532     // 1) Get RAX and RDX.
1533     // If they are already used, push them to the stack.
1534     Assembler::RegisterID dividend = JSC::X86Registers::eax;
1535     RegisterAllocationType dividendAllocation = RegisterAllocationType::External;
1536     StackAllocator::StackReference temporaryDividendStackReference;
1537     Assembler::RegisterID temporaryDividendCopy = InvalidGPRReg;
1538     if (inputDividend != dividend) {
1539         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(dividend);
1540         if (registerIsInUse) {
1541             if (m_registerAllocator.availableRegisterCount()) {
1542                 temporaryDividendCopy = m_registerAllocator.allocateRegister();
1543                 m_assembler.move(dividend, temporaryDividendCopy);
1544                 dividendAllocation = RegisterAllocationType::CopiedToTemporary;
1545             } else {
1546                 temporaryDividendStackReference = m_stackAllocator.push(dividend);
1547                 dividendAllocation = RegisterAllocationType::PushedToStack;
1548             }
1549         } else {
1550             m_registerAllocator.allocateRegister(dividend);
1551             dividendAllocation = RegisterAllocationType::AllocatedLocally;
1552         }
1553         m_assembler.move(inputDividend, dividend);
1554     }
1555
1556     Assembler::RegisterID remainder = JSC::X86Registers::edx;
1557     RegisterAllocationType remainderAllocation = RegisterAllocationType::External;
1558     StackAllocator::StackReference temporaryRemainderStackReference;
1559     Assembler::RegisterID temporaryRemainderCopy = InvalidGPRReg;
1560     if (inputDividend != remainder) {
1561         bool registerIsInUse = m_registerAllocator.allocatedRegisters().contains(remainder);
1562         if (registerIsInUse) {
1563             if (m_registerAllocator.availableRegisterCount()) {
1564                 temporaryRemainderCopy = m_registerAllocator.allocateRegister();
1565                 m_assembler.move(remainder, temporaryRemainderCopy);
1566                 remainderAllocation = RegisterAllocationType::CopiedToTemporary;
1567             } else {
1568                 temporaryRemainderStackReference = m_stackAllocator.push(remainder);
1569                 remainderAllocation = RegisterAllocationType::PushedToStack;
1570             }
1571         } else {
1572             m_registerAllocator.allocateRegister(remainder);
1573             remainderAllocation = RegisterAllocationType::AllocatedLocally;
1574         }
1575     }
1576     m_assembler.m_assembler.cdq();
1577
1578     // 2) Perform the division with idiv.
1579     {
1580         LocalRegister divisorRegister(m_registerAllocator);
1581         m_assembler.move(Assembler::TrustedImm64(divisor), divisorRegister);
1582         m_assembler.m_assembler.idivl_r(divisorRegister);
1583         m_assembler.test32(condition, remainder);
1584     }
1585
1586     // 3) Return RAX and RDX.
1587     if (remainderAllocation == RegisterAllocationType::AllocatedLocally)
1588         m_registerAllocator.deallocateRegister(remainder);
1589     else if (remainderAllocation == RegisterAllocationType::CopiedToTemporary) {
1590         m_assembler.move(temporaryRemainderCopy, remainder);
1591         m_registerAllocator.deallocateRegister(temporaryRemainderCopy);
1592     } else if (remainderAllocation == RegisterAllocationType::PushedToStack)
1593         m_stackAllocator.pop(temporaryRemainderStackReference, remainder);
1594
1595     if (dividendAllocation == RegisterAllocationType::AllocatedLocally)
1596         m_registerAllocator.deallocateRegister(dividend);
1597     else if (dividendAllocation == RegisterAllocationType::CopiedToTemporary) {
1598         m_assembler.move(temporaryDividendCopy, dividend);
1599         m_registerAllocator.deallocateRegister(temporaryDividendCopy);
1600     } else if (dividendAllocation == RegisterAllocationType::PushedToStack)
1601         m_stackAllocator.pop(temporaryDividendStackReference, dividend);
1602
1603     // 4) Branch on the test.
1604     return m_assembler.branch(condition);
1605 #else
1606 #error Modulo is not implemented for this architecture.
1607 #endif
1608 }
1609
1610 void SelectorCodeGenerator::moduloIsZero(Assembler::JumpList& failureCases, Assembler::RegisterID inputDividend, int divisor)
1611 {
1612     if (divisor == 1 || divisor == -1)
1613         return;
1614     if (divisor == 2 || divisor == -2) {
1615         failureCases.append(m_assembler.branchTest32(Assembler::NonZero, inputDividend, Assembler::TrustedImm32(1)));
1616         return;
1617     }
1618
1619     failureCases.append(modulo(Assembler::NonZero, inputDividend, divisor));
1620 }
1621
1622 static void setNodeFlag(Assembler& assembler, Assembler::RegisterID elementAddress, int32_t flag)
1623 {
1624     assembler.or32(Assembler::TrustedImm32(flag), Assembler::Address(elementAddress, Node::nodeFlagsMemoryOffset()));
1625 }
1626
1627 void SelectorCodeGenerator::markParentElementIfResolvingStyle(int32_t nodeFlag)
1628 {
1629     if (m_selectorContext == SelectorContext::QuerySelector)
1630         return;
1631
1632     Assembler::JumpList skipMarking;
1633     {
1634         LocalRegister checkingContext(m_registerAllocator);
1635         skipMarking.append(jumpIfNotResolvingStyle(checkingContext));
1636     }
1637
1638     LocalRegister parentElement(m_registerAllocator);
1639     generateWalkToParentElement(skipMarking, parentElement);
1640
1641     setNodeFlag(m_assembler, parentElement, nodeFlag);
1642
1643     skipMarking.link(&m_assembler);
1644 }
1645
1646 void SelectorCodeGenerator::markParentElementIfResolvingStyle(JSC::FunctionPtr markingFunction)
1647 {
1648     if (m_selectorContext == SelectorContext::QuerySelector)
1649         return;
1650
1651     //     if (checkingContext.resolvingMode == ResolvingStyle) {
1652     //         Element* parent = element->parentNode();
1653     //         markingFunction(parent);
1654     //     }
1655
1656     Assembler::JumpList skipMarking;
1657     {
1658         LocalRegister checkingContext(m_registerAllocator);
1659         skipMarking.append(jumpIfNotResolvingStyle(checkingContext));
1660     }
1661
1662     // Get the parent element in a temporary register.
1663     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
1664     generateWalkToParentElement(skipMarking, parentElement);
1665
1666     // Return the register parentElement just before the function call since we don't need it to be preserved
1667     // on the stack.
1668     m_registerAllocator.deallocateRegister(parentElement);
1669
1670     // Invoke the marking function on the parent element.
1671     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1672     functionCall.setFunctionAddress(markingFunction);
1673     functionCall.setOneArgument(parentElement);
1674     functionCall.call();
1675
1676     skipMarking.link(&m_assembler);
1677 }
1678
1679
1680 void SelectorCodeGenerator::linkFailures(Assembler::JumpList& globalFailureCases, BacktrackingAction backtrackingAction, Assembler::JumpList& localFailureCases)
1681 {
1682     switch (backtrackingAction) {
1683     case BacktrackingAction::NoBacktracking:
1684         globalFailureCases.append(localFailureCases);
1685         break;
1686     case BacktrackingAction::JumpToDescendantEntryPoint:
1687         localFailureCases.linkTo(m_descendantEntryPoint, &m_assembler);
1688         break;
1689     case BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint:
1690         localFailureCases.linkTo(m_descendantTreeWalkerBacktrackingPoint, &m_assembler);
1691         break;
1692     case BacktrackingAction::JumpToDescendantTail:
1693         m_descendantBacktrackingFailureCases.append(localFailureCases);
1694         break;
1695     case BacktrackingAction::JumpToIndirectAdjacentEntryPoint:
1696         localFailureCases.linkTo(m_indirectAdjacentEntryPoint, &m_assembler);
1697         break;
1698     case BacktrackingAction::JumpToIndirectAdjacentTreeWalkerEntryPoint:
1699         localFailureCases.linkTo(m_indirectAdjacentTreeWalkerBacktrackingPoint, &m_assembler);
1700         break;
1701     case BacktrackingAction::JumpToDirectAdjacentTail:
1702         m_adjacentBacktrackingFailureCases.append(localFailureCases);
1703         break;
1704     }
1705 }
1706
1707 void SelectorCodeGenerator::generateAdjacentBacktrackingTail()
1708 {
1709     // Recovering tail.
1710     m_adjacentBacktrackingFailureCases.link(&m_assembler);
1711     m_adjacentBacktrackingFailureCases.clear();
1712     unsigned offsetToAdjacentBacktrackingStart = m_stackAllocator.offsetToStackReference(m_adjacentBacktrackingStart);
1713     m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToAdjacentBacktrackingStart), elementAddressRegister);
1714     m_assembler.jump(m_indirectAdjacentEntryPoint);
1715 }
1716
1717 void SelectorCodeGenerator::generateDescendantBacktrackingTail()
1718 {
1719     m_descendantBacktrackingFailureCases.link(&m_assembler);
1720     m_descendantBacktrackingFailureCases.clear();
1721     m_assembler.move(m_descendantBacktrackingStart, elementAddressRegister);
1722     m_registerAllocator.deallocateRegister(m_descendantBacktrackingStart);
1723     m_assembler.jump(m_descendantEntryPoint);
1724 }
1725
1726 void SelectorCodeGenerator::generateBacktrackingTailsIfNeeded(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1727 {
1728     if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail && fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
1729         Assembler::Jump normalCase = m_assembler.jump();
1730         generateAdjacentBacktrackingTail();
1731         generateDescendantBacktrackingTail();
1732         normalCase.link(&m_assembler);
1733     } else if (fragment.backtrackingFlags & BacktrackingFlag::DirectAdjacentTail) {
1734         Assembler::Jump normalCase = m_assembler.jump();
1735         generateAdjacentBacktrackingTail();
1736         failureCases.append(m_assembler.jump());
1737         normalCase.link(&m_assembler);
1738     } else if (fragment.backtrackingFlags & BacktrackingFlag::DescendantTail) {
1739         Assembler::Jump normalCase = m_assembler.jump();
1740         generateDescendantBacktrackingTail();
1741         normalCase.link(&m_assembler);
1742     }
1743 }
1744
1745 void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment& fragment)
1746 {
1747     if (fragment.tagName)
1748         generateElementHasTagName(matchingTagNameFailureCases, *(fragment.tagName));
1749
1750     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLink))
1751         generateElementIsLink(matchingPostTagNameFailureCases);
1752
1753     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassRoot))
1754         generateElementIsRoot(matchingPostTagNameFailureCases);
1755
1756     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassTarget))
1757         generateElementIsTarget(matchingPostTagNameFailureCases);
1758
1759     for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
1760         generateElementFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClasses[i]);
1761
1762     generateElementDataMatching(matchingPostTagNameFailureCases, fragment);
1763
1764     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassActive))
1765         generateElementIsActive(matchingPostTagNameFailureCases, fragment);
1766     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassHover))
1767         generateElementIsHovered(matchingPostTagNameFailureCases, fragment);
1768     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassOnlyChild))
1769         generateElementIsOnlyChild(matchingPostTagNameFailureCases, fragment);
1770     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFirstChild))
1771         generateElementIsFirstChild(matchingPostTagNameFailureCases, fragment);
1772     if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLastChild))
1773         generateElementIsLastChild(matchingPostTagNameFailureCases, fragment);
1774     if (!fragment.nthChildFilters.isEmpty())
1775         generateElementIsNthChild(matchingPostTagNameFailureCases, fragment);
1776     if (!fragment.notFilters.isEmpty())
1777         generateElementMatchesNotPseudoClass(matchingPostTagNameFailureCases, fragment);
1778     if (!fragment.anyFilters.isEmpty())
1779         generateElementMatchesAnyPseudoClass(matchingPostTagNameFailureCases, fragment);
1780     if (fragment.langFilter)
1781         generateElementIsInLanguage(matchingPostTagNameFailureCases, *fragment.langFilter);
1782 }
1783
1784 void SelectorCodeGenerator::generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
1785 {
1786     if (!fragment.id && fragment.classNames.isEmpty() && fragment.attributes.isEmpty())
1787         return;
1788
1789     //  Generate:
1790     //     elementDataAddress = element->elementData();
1791     //     if (!elementDataAddress)
1792     //         failure!
1793     LocalRegister elementDataAddress(m_registerAllocator);
1794     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::elementDataMemoryOffset()), elementDataAddress);
1795     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, elementDataAddress));
1796
1797     if (fragment.id)
1798         generateElementHasId(failureCases, elementDataAddress, *fragment.id);
1799     if (!fragment.classNames.isEmpty())
1800         generateElementHasClasses(failureCases, elementDataAddress, fragment.classNames);
1801     if (!fragment.attributes.isEmpty())
1802         generateElementAttributesMatching(failureCases, elementDataAddress, fragment);
1803 }
1804
1805 static inline Assembler::Jump testIsHTMLFlagOnNode(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID nodeAddress)
1806 {
1807     return assembler.branchTest32(condition, Assembler::Address(nodeAddress, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsHTML()));
1808 }
1809
1810 static inline bool canMatchStyleAttribute(const SelectorFragment& fragment)
1811 {
1812     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
1813         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
1814         const QualifiedName& attributeName = attributeSelector.attribute();
1815         if (Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeName.localName(), attributeName.namespaceURI()))
1816             return true;
1817
1818         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
1819         if (attributeName.localName() != canonicalLocalName
1820             && Attribute::nameMatchesFilter(HTMLNames::styleAttr, attributeName.prefix(), attributeSelector.attributeCanonicalLocalName(), attributeName.namespaceURI())) {
1821             return true;
1822         }
1823     }
1824     return false;
1825 }
1826
1827 void SelectorCodeGenerator::generateSynchronizeStyleAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
1828 {
1829     // The style attribute is updated lazily based on the flag styleAttributeIsDirty.
1830     Assembler::Jump styleAttributeNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::styleAttributeIsDirtyFlag()));
1831
1832     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1833     functionCall.setFunctionAddress(StyledElement::synchronizeStyleAttributeInternal);
1834     Assembler::RegisterID elementAddress = elementAddressRegister;
1835     functionCall.setOneArgument(elementAddress);
1836     functionCall.call();
1837
1838     styleAttributeNotDirty.link(&m_assembler);
1839 }
1840
1841 static inline bool canMatchAnimatableSVGAttribute(const SelectorFragment& fragment)
1842 {
1843     for (unsigned i = 0; i < fragment.attributes.size(); ++i) {
1844         const CSSSelector& attributeSelector = fragment.attributes[i].selector();
1845         const QualifiedName& selectorAttributeName = attributeSelector.attribute();
1846
1847         const QualifiedName& candidateForLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
1848         if (Attribute::nameMatchesFilter(candidateForLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
1849             return true;
1850
1851         const AtomicString& canonicalLocalName = attributeSelector.attributeCanonicalLocalName();
1852         if (selectorAttributeName.localName() != canonicalLocalName) {
1853             const QualifiedName& candidateForCanonicalLocalName = SVGElement::animatableAttributeForName(selectorAttributeName.localName());
1854             if (Attribute::nameMatchesFilter(candidateForCanonicalLocalName, selectorAttributeName.prefix(), selectorAttributeName.localName(), selectorAttributeName.namespaceURI()))
1855                 return true;
1856         }
1857     }
1858     return false;
1859 }
1860
1861 void SelectorCodeGenerator::generateSynchronizeAllAnimatedSVGAttribute(Assembler::RegisterID elementDataArraySizeAndFlags)
1862 {
1863     // SVG attributes can be updated lazily depending on the flag AnimatedSVGAttributesAreDirty. We need to check
1864     // that first.
1865     Assembler::Jump animatedSVGAttributesNotDirty = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::animatedSVGAttributesAreDirtyFlag()));
1866
1867     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
1868     functionCall.setFunctionAddress(SVGElement::synchronizeAllAnimatedSVGAttribute);
1869     Assembler::RegisterID elementAddress = elementAddressRegister;
1870     functionCall.setOneArgument(elementAddress);
1871     functionCall.call();
1872
1873     animatedSVGAttributesNotDirty.link(&m_assembler);
1874 }
1875
1876 void SelectorCodeGenerator::generateElementAttributesMatching(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const SelectorFragment& fragment)
1877 {
1878     LocalRegister scratchRegister(m_registerAllocator);
1879     Assembler::RegisterID elementDataArraySizeAndFlags = scratchRegister;
1880     Assembler::RegisterID attributeArrayLength = scratchRegister;
1881
1882     m_assembler.load32(Assembler::Address(elementDataAddress, ElementData::arraySizeAndFlagsMemoryOffset()), elementDataArraySizeAndFlags);
1883
1884     if (canMatchStyleAttribute(fragment))
1885         generateSynchronizeStyleAttribute(elementDataArraySizeAndFlags);
1886
1887     if (canMatchAnimatableSVGAttribute(fragment))
1888         generateSynchronizeAllAnimatedSVGAttribute(elementDataArraySizeAndFlags);
1889
1890     // Attributes can be stored either in a separate vector for UniqueElementData, or after the elementData itself
1891     // for ShareableElementData.
1892     LocalRegister attributeArrayPointer(m_registerAllocator);
1893     Assembler::Jump isShareableElementData  = m_assembler.branchTest32(Assembler::Zero, elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::isUniqueFlag()));
1894     {
1895         ptrdiff_t attributeVectorOffset = UniqueElementData::attributeVectorMemoryOffset();
1896         m_assembler.loadPtr(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::dataMemoryOffset()), attributeArrayPointer);
1897         m_assembler.load32(Assembler::Address(elementDataAddress, attributeVectorOffset + UniqueElementData::AttributeVector::sizeMemoryOffset()), attributeArrayLength);
1898     }
1899     Assembler::Jump skipShareable = m_assembler.jump();
1900
1901     {
1902         isShareableElementData.link(&m_assembler);
1903         m_assembler.urshift32(elementDataArraySizeAndFlags, Assembler::TrustedImm32(ElementData::arraySizeOffset()), attributeArrayLength);
1904         m_assembler.addPtr(Assembler::TrustedImm32(ShareableElementData::attributeArrayMemoryOffset()), elementDataAddress, attributeArrayPointer);
1905     }
1906
1907     skipShareable.link(&m_assembler);
1908
1909     // If there are no attributes, fail immediately.
1910     failureCases.append(m_assembler.branchTest32(Assembler::Zero, attributeArrayLength));
1911
1912     unsigned attributeCount = fragment.attributes.size();
1913     for (unsigned i = 0; i < attributeCount; ++i) {
1914         Assembler::RegisterID decIndexRegister;
1915         Assembler::RegisterID currentAttributeAddress;
1916
1917         bool isLastAttribute = i == (attributeCount - 1);
1918         if (!isLastAttribute) {
1919             // We need to make a copy to let the next iterations use the values.
1920             currentAttributeAddress = m_registerAllocator.allocateRegister();
1921             decIndexRegister = m_registerAllocator.allocateRegister();
1922             m_assembler.move(attributeArrayPointer, currentAttributeAddress);
1923             m_assembler.move(attributeArrayLength, decIndexRegister);
1924         } else {
1925             currentAttributeAddress = attributeArrayPointer;
1926             decIndexRegister = attributeArrayLength;
1927         }
1928
1929         generateElementAttributeMatching(failureCases, currentAttributeAddress, decIndexRegister, fragment.attributes[i]);
1930
1931         if (!isLastAttribute) {
1932             m_registerAllocator.deallocateRegister(decIndexRegister);
1933             m_registerAllocator.deallocateRegister(currentAttributeAddress);
1934         }
1935     }
1936 }
1937
1938 void SelectorCodeGenerator::generateElementAttributeMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, Assembler::RegisterID decIndexRegister, const AttributeMatchingInfo& attributeInfo)
1939 {
1940     // Get the localName used for comparison. HTML elements use a lowercase local name known in selectors as canonicalLocalName.
1941     LocalRegister localNameToMatch(m_registerAllocator);
1942
1943     // In general, canonicalLocalName and localName are the same. When they differ, we have to check if the node is HTML to know
1944     // which one to use.
1945     const CSSSelector& attributeSelector = attributeInfo.selector();
1946     const AtomicStringImpl* canonicalLocalName = attributeSelector.attributeCanonicalLocalName().impl();
1947     const AtomicStringImpl* localName = attributeSelector.attribute().localName().impl();
1948     if (canonicalLocalName == localName)
1949         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1950     else {
1951         m_assembler.move(Assembler::TrustedImmPtr(canonicalLocalName), localNameToMatch);
1952         Assembler::Jump elementIsHTML = testIsHTMLFlagOnNode(Assembler::NonZero, m_assembler, elementAddressRegister);
1953         m_assembler.move(Assembler::TrustedImmPtr(localName), localNameToMatch);
1954         elementIsHTML.link(&m_assembler);
1955     }
1956
1957     Assembler::JumpList successCases;
1958     Assembler::Label loopStart(m_assembler.label());
1959
1960     {
1961         LocalRegister qualifiedNameImpl(m_registerAllocator);
1962         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::nameMemoryOffset()), qualifiedNameImpl);
1963
1964         bool shouldCheckNamespace = attributeSelector.attribute().prefix() != starAtom;
1965         if (shouldCheckNamespace) {
1966             Assembler::Jump nameDoesNotMatch = m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch);
1967
1968             const AtomicStringImpl* namespaceURI = attributeSelector.attribute().namespaceURI().impl();
1969             if (namespaceURI) {
1970                 LocalRegister namespaceToMatch(m_registerAllocator);
1971                 m_assembler.move(Assembler::TrustedImmPtr(namespaceURI), namespaceToMatch);
1972                 successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), namespaceToMatch));
1973             } else
1974                 successCases.append(m_assembler.branchTestPtr(Assembler::Zero, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset())));
1975             nameDoesNotMatch.link(&m_assembler);
1976         } else
1977             successCases.append(m_assembler.branchPtr(Assembler::Equal, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), localNameToMatch));
1978     }
1979
1980     Assembler::Label loopReEntry(m_assembler.label());
1981
1982     // If we reached the last element -> failure.
1983     failureCases.append(m_assembler.branchSub32(Assembler::Zero, Assembler::TrustedImm32(1), decIndexRegister));
1984
1985     // Otherwise just loop over.
1986     m_assembler.addPtr(Assembler::TrustedImm32(sizeof(Attribute)), currentAttributeAddress);
1987     m_assembler.jump().linkTo(loopStart, &m_assembler);
1988
1989     successCases.link(&m_assembler);
1990
1991     if (attributeSelector.m_match != CSSSelector::Set) {
1992         // We make the assumption that name matching fails in most cases and we keep value matching outside
1993         // of the loop. We re-enter the loop if needed.
1994         // FIXME: exact case sensitive value matching is so simple that it should be done in the loop.
1995         Assembler::JumpList localFailureCases;
1996         generateElementAttributeValueMatching(localFailureCases, currentAttributeAddress, attributeInfo);
1997         localFailureCases.linkTo(loopReEntry, &m_assembler);
1998     }
1999 }
2000
2001 enum CaseSensitivity {
2002     CaseSensitive,
2003     CaseInsensitive
2004 };
2005
2006 template<CaseSensitivity caseSensitivity>
2007 static bool attributeValueBeginsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2008 {
2009     AtomicStringImpl& valueImpl = *attribute->value().impl();
2010     if (caseSensitivity == CaseSensitive)
2011         return valueImpl.startsWith(expectedString);
2012     return valueImpl.startsWith(expectedString, false);
2013 }
2014
2015 template<CaseSensitivity caseSensitivity>
2016 static bool attributeValueContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2017 {
2018     AtomicStringImpl& valueImpl = *attribute->value().impl();
2019     if (caseSensitivity == CaseSensitive)
2020         return valueImpl.find(expectedString) != notFound;
2021     return valueImpl.findIgnoringCase(expectedString) != notFound;
2022 }
2023
2024 template<CaseSensitivity caseSensitivity>
2025 static bool attributeValueEndsWith(const Attribute* attribute, AtomicStringImpl* expectedString)
2026 {
2027     AtomicStringImpl& valueImpl = *attribute->value().impl();
2028     if (caseSensitivity == CaseSensitive)
2029         return valueImpl.endsWith(expectedString);
2030     return valueImpl.endsWith(expectedString, false);
2031 }
2032
2033 template<CaseSensitivity caseSensitivity>
2034 static bool attributeValueMatchHyphenRule(const Attribute* attribute, AtomicStringImpl* expectedString)
2035 {
2036     AtomicStringImpl& valueImpl = *attribute->value().impl();
2037     if (valueImpl.length() < expectedString->length())
2038         return false;
2039
2040     bool valueStartsWithExpectedString;
2041     if (caseSensitivity == CaseSensitive)
2042         valueStartsWithExpectedString = valueImpl.startsWith(expectedString);
2043     else
2044         valueStartsWithExpectedString = valueImpl.startsWith(expectedString, false);
2045
2046     if (!valueStartsWithExpectedString)
2047         return false;
2048
2049     return valueImpl.length() == expectedString->length() || valueImpl[expectedString->length()] == '-';
2050 }
2051
2052 template<CaseSensitivity caseSensitivity>
2053 static bool attributeValueSpaceSeparetedListContains(const Attribute* attribute, AtomicStringImpl* expectedString)
2054 {
2055     AtomicStringImpl& value = *attribute->value().impl();
2056
2057     unsigned startSearchAt = 0;
2058     while (true) {
2059         size_t foundPos;
2060         if (caseSensitivity == CaseSensitive)
2061             foundPos = value.find(expectedString, startSearchAt);
2062         else
2063             foundPos = value.findIgnoringCase(expectedString, startSearchAt);
2064         if (foundPos == notFound)
2065             return false;
2066         if (!foundPos || value[foundPos - 1] == ' ') {
2067             unsigned endStr = foundPos + expectedString->length();
2068             if (endStr == value.length() || value[endStr] == ' ')
2069                 return true;
2070         }
2071         startSearchAt = foundPos + 1;
2072     }
2073     return false;
2074 }
2075
2076 void SelectorCodeGenerator::generateElementAttributeValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AttributeMatchingInfo& attributeInfo)
2077 {
2078     const CSSSelector& attributeSelector = attributeInfo.selector();
2079     const AtomicString& expectedValue = attributeSelector.value();
2080     ASSERT(!expectedValue.isNull());
2081     bool defaultToCaseSensitiveValueMatch = attributeInfo.canDefaultToCaseSensitiveValueMatch();
2082
2083     switch (attributeSelector.m_match) {
2084     case CSSSelector::Begin:
2085         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueBeginsWith<CaseSensitive>, attributeValueBeginsWith<CaseInsensitive>);
2086         break;
2087     case CSSSelector::Contain:
2088         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueContains<CaseSensitive>, attributeValueContains<CaseInsensitive>);
2089         break;
2090     case CSSSelector::End:
2091         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueEndsWith<CaseSensitive>, attributeValueEndsWith<CaseInsensitive>);
2092         break;
2093     case CSSSelector::Exact:
2094         generateElementAttributeValueExactMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch);
2095         break;
2096     case CSSSelector::Hyphen:
2097         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueMatchHyphenRule<CaseSensitive>, attributeValueMatchHyphenRule<CaseInsensitive>);
2098         break;
2099     case CSSSelector::List:
2100         generateElementAttributeFunctionCallValueMatching(failureCases, currentAttributeAddress, expectedValue, defaultToCaseSensitiveValueMatch, attributeValueSpaceSeparetedListContains<CaseSensitive>, attributeValueSpaceSeparetedListContains<CaseInsensitive>);
2101         break;
2102     default:
2103         ASSERT_NOT_REACHED();
2104     }
2105 }
2106
2107 static inline Assembler::Jump testIsHTMLClassOnDocument(Assembler::ResultCondition condition, Assembler& assembler, Assembler::RegisterID documentAddress)
2108 {
2109     return assembler.branchTest32(condition, Assembler::Address(documentAddress, Document::documentClassesMemoryOffset()), Assembler::TrustedImm32(Document::isHTMLDocumentClassFlag()));
2110 }
2111
2112 void SelectorCodeGenerator::generateElementAttributeValueExactMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool canDefaultToCaseSensitiveValueMatch)
2113 {
2114     LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2115     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
2116
2117     if (canDefaultToCaseSensitiveValueMatch)
2118         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister));
2119     else {
2120         Assembler::Jump skipCaseInsensitiveComparison = m_assembler.branchPtr(Assembler::Equal, Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), expectedValueRegister);
2121
2122         // If the element is an HTML element, in a HTML dcoument (not including XHTML), value matching is case insensitive.
2123         // Taking the contrapositive, if we find the element is not HTML or is not in a HTML document, the condition above
2124         // sould be sufficient and we can fail early.
2125         failureCases.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
2126
2127         {
2128             LocalRegister document(m_registerAllocator);
2129             getDocument(m_assembler, elementAddressRegister, document);
2130             failureCases.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, document));
2131         }
2132
2133         LocalRegister valueStringImpl(m_registerAllocator);
2134         m_assembler.loadPtr(Assembler::Address(currentAttributeAddress, Attribute::valueMemoryOffset()), valueStringImpl);
2135
2136         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2137         functionCall.setFunctionAddress(WTF::equalIgnoringCaseNonNull);
2138         functionCall.setTwoArguments(valueStringImpl, expectedValueRegister);
2139         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2140
2141         skipCaseInsensitiveComparison.link(&m_assembler);
2142     }
2143 }
2144
2145 void SelectorCodeGenerator::generateElementAttributeFunctionCallValueMatching(Assembler::JumpList& failureCases, Assembler::RegisterID currentAttributeAddress, const AtomicString& expectedValue, bool canDefaultToCaseSensitiveValueMatch, JSC::FunctionPtr caseSensitiveTest, JSC::FunctionPtr caseInsensitiveTest)
2146 {
2147     LocalRegisterWithPreference expectedValueRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2148     m_assembler.move(Assembler::TrustedImmPtr(expectedValue.impl()), expectedValueRegister);
2149
2150     if (canDefaultToCaseSensitiveValueMatch) {
2151         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2152         functionCall.setFunctionAddress(caseSensitiveTest);
2153         functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
2154         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2155     } else {
2156         Assembler::JumpList shouldUseCaseSensitiveComparison;
2157         shouldUseCaseSensitiveComparison.append(testIsHTMLFlagOnNode(Assembler::Zero, m_assembler, elementAddressRegister));
2158         {
2159             LocalRegister scratchRegister(m_registerAllocator);
2160             // scratchRegister = pointer to treeScope.
2161             m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::treeScopeMemoryOffset()), scratchRegister);
2162             // scratchRegister = pointer to document.
2163             m_assembler.loadPtr(Assembler::Address(scratchRegister, TreeScope::documentScopeMemoryOffset()), scratchRegister);
2164             shouldUseCaseSensitiveComparison.append(testIsHTMLClassOnDocument(Assembler::Zero, m_assembler, scratchRegister));
2165         }
2166
2167         {
2168             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2169             functionCall.setFunctionAddress(caseInsensitiveTest);
2170             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
2171             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2172         }
2173
2174         Assembler::Jump skipCaseSensitiveCase = m_assembler.jump();
2175
2176         {
2177             shouldUseCaseSensitiveComparison.link(&m_assembler);
2178             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2179             functionCall.setFunctionAddress(caseSensitiveTest);
2180             functionCall.setTwoArguments(currentAttributeAddress, expectedValueRegister);
2181             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2182         }
2183
2184         skipCaseSensitiveCase.link(&m_assembler);
2185     }
2186 }
2187
2188 void SelectorCodeGenerator::generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr testFunction)
2189 {
2190     Assembler::RegisterID elementAddress = elementAddressRegister;
2191     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2192     functionCall.setFunctionAddress(testFunction);
2193     functionCall.setOneArgument(elementAddress);
2194     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2195 }
2196
2197 static void setFirstChildState(Element* element)
2198 {
2199     if (RenderStyle* style = element->renderStyle())
2200         style->setFirstChildState();
2201 }
2202
2203 static bool elementIsActive(Element* element)
2204 {
2205     return element->active() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassActive);
2206 }
2207
2208 static bool elementIsActiveForStyleResolution(Element* element, const CheckingContext* checkingContext)
2209 {
2210     if (checkingContext->resolvingMode == SelectorChecker::ResolvingStyle)
2211         element->setChildrenAffectedByActive();
2212     return element->active() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassActive);
2213 }
2214
2215 void SelectorCodeGenerator::generateElementIsActive(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2216 {
2217     generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
2218     if (m_selectorContext == SelectorContext::QuerySelector) {
2219         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2220         functionCall.setFunctionAddress(elementIsActive);
2221         functionCall.setOneArgument(elementAddressRegister);
2222         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2223     } else {
2224         if (shouldUseRenderStyleFromCheckingContext(fragment)) {
2225             LocalRegister checkingContext(m_registerAllocator);
2226             Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2227             addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsaffectedByActive());
2228             notResolvingStyle.link(&m_assembler);
2229
2230             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2231             functionCall.setFunctionAddress(elementIsActive);
2232             functionCall.setOneArgument(elementAddressRegister);
2233             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2234         } else {
2235             unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
2236             Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegisterWithPreference(JSC::GPRInfo::argumentGPR1);
2237             m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
2238             m_registerAllocator.deallocateRegister(checkingContext);
2239
2240             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2241             functionCall.setFunctionAddress(elementIsActiveForStyleResolution);
2242             functionCall.setTwoArguments(elementAddressRegister, checkingContext);
2243             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2244         }
2245     }
2246 }
2247
2248 void SelectorCodeGenerator::generateElementIsFirstChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2249 {
2250     if (m_selectorContext == SelectorContext::QuerySelector) {
2251         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2252         failureCases.append(m_assembler.jump());
2253         successCase.link(&m_assembler);
2254         LocalRegister parent(m_registerAllocator);
2255         generateWalkToParentElement(failureCases, parent);
2256         return;
2257     }
2258
2259     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2260     generateWalkToParentElement(failureCases, parentElement);
2261
2262     // Zero in isFirstChildRegister is the success case. The register is set to non-zero if a sibling if found.
2263     LocalRegister isFirstChildRegister(m_registerAllocator);
2264     m_assembler.move(Assembler::TrustedImm32(0), isFirstChildRegister);
2265
2266     {
2267         Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2268
2269         // If there was a sibling element, the element was not the first child -> failure case.
2270         m_assembler.move(Assembler::TrustedImm32(1), isFirstChildRegister);
2271
2272         successCase.link(&m_assembler);
2273     }
2274
2275     LocalRegister checkingContext(m_registerAllocator);
2276     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2277
2278     setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByFirstChildRulesFlag());
2279     m_registerAllocator.deallocateRegister(parentElement);
2280
2281     // The parent marking is unconditional. If the matching is not a success, we can now fail.
2282     // Otherwise we need to apply setFirstChildState() on the RenderStyle.
2283     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
2284
2285     if (shouldUseRenderStyleFromCheckingContext(fragment))
2286         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setFirstChildStateFlags());
2287     else {
2288         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2289         functionCall.setFunctionAddress(setFirstChildState);
2290         Assembler::RegisterID elementAddress = elementAddressRegister;
2291         functionCall.setOneArgument(elementAddress);
2292         functionCall.call();
2293     }
2294
2295     notResolvingStyle.link(&m_assembler);
2296     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isFirstChildRegister));
2297 }
2298
2299 static bool elementIsHovered(Element* element)
2300 {
2301     return element->hovered() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassHover);
2302 }
2303
2304 static bool elementIsHoveredForStyleResolution(Element* element, const CheckingContext* checkingContext)
2305 {
2306     if (checkingContext->resolvingMode == SelectorChecker::ResolvingStyle)
2307         element->setChildrenAffectedByHover();
2308     return element->hovered() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoClassHover);
2309 }
2310
2311 void SelectorCodeGenerator::generateElementIsHovered(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2312 {
2313     generateSpecialFailureInQuirksModeForActiveAndHoverIfNeeded(failureCases, fragment);
2314     if (m_selectorContext == SelectorContext::QuerySelector) {
2315         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2316         functionCall.setFunctionAddress(elementIsHovered);
2317         functionCall.setOneArgument(elementAddressRegister);
2318         failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2319     } else {
2320         if (shouldUseRenderStyleFromCheckingContext(fragment)) {
2321             LocalRegisterWithPreference checkingContext(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2322             Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2323             addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsaffectedByHover());
2324             notResolvingStyle.link(&m_assembler);
2325
2326             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2327             functionCall.setFunctionAddress(elementIsHovered);
2328             functionCall.setOneArgument(elementAddressRegister);
2329             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2330         } else {
2331             unsigned offsetToCheckingContext = m_stackAllocator.offsetToStackReference(m_checkingContextStackReference);
2332             Assembler::RegisterID checkingContext = m_registerAllocator.allocateRegisterWithPreference(JSC::GPRInfo::argumentGPR1);
2333             m_assembler.loadPtr(Assembler::Address(Assembler::stackPointerRegister, offsetToCheckingContext), checkingContext);
2334             m_registerAllocator.deallocateRegister(checkingContext);
2335
2336             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2337             functionCall.setFunctionAddress(elementIsHoveredForStyleResolution);
2338             functionCall.setTwoArguments(elementAddressRegister, checkingContext);
2339             failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2340         }
2341     }
2342 }
2343
2344 void SelectorCodeGenerator::generateElementIsInLanguage(Assembler::JumpList& failureCases, const AtomicString& langFilter)
2345 {
2346     LocalRegisterWithPreference langFilterRegister(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2347     m_assembler.move(Assembler::TrustedImmPtr(langFilter.impl()), langFilterRegister);
2348
2349     Assembler::RegisterID elementAddress = elementAddressRegister;
2350     FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2351     functionCall.setFunctionAddress(matchesLangPseudoClass);
2352     functionCall.setTwoArguments(elementAddress, langFilterRegister);
2353     failureCases.append(functionCall.callAndBranchOnBooleanReturnValue(Assembler::Zero));
2354 }
2355
2356 static void setLastChildState(Element* element)
2357 {
2358     if (RenderStyle* style = element->renderStyle())
2359         style->setLastChildState();
2360 }
2361
2362 void SelectorCodeGenerator::generateElementIsLastChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2363 {
2364     if (m_selectorContext == SelectorContext::QuerySelector) {
2365         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2366         failureCases.append(m_assembler.jump());
2367
2368         successCase.link(&m_assembler);
2369         LocalRegister parent(m_registerAllocator);
2370         generateWalkToParentElement(failureCases, parent);
2371
2372         failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2373
2374         return;
2375     }
2376
2377     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2378     generateWalkToParentElement(failureCases, parentElement);
2379
2380     // Zero in isLastChildRegister is the success case. The register is set to non-zero if a sibling if found.
2381     LocalRegister isLastChildRegister(m_registerAllocator);
2382     m_assembler.move(Assembler::TrustedImm32(0), isLastChildRegister);
2383
2384     {
2385         Assembler::Jump notFinishedParsingChildren = m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentElement, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished()));
2386
2387         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2388
2389         notFinishedParsingChildren.link(&m_assembler);
2390         m_assembler.move(Assembler::TrustedImm32(1), isLastChildRegister);
2391
2392         successCase.link(&m_assembler);
2393     }
2394
2395     LocalRegister checkingContext(m_registerAllocator);
2396     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2397
2398     setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByLastChildRulesFlag());
2399     m_registerAllocator.deallocateRegister(parentElement);
2400
2401     // The parent marking is unconditional. If the matching is not a success, we can now fail.
2402     // Otherwise we need to apply setLastChildState() on the RenderStyle.
2403     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
2404
2405     if (shouldUseRenderStyleFromCheckingContext(fragment))
2406         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setLastChildStateFlags());
2407     else {
2408         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2409         functionCall.setFunctionAddress(setLastChildState);
2410         Assembler::RegisterID elementAddress = elementAddressRegister;
2411         functionCall.setOneArgument(elementAddress);
2412         functionCall.call();
2413     }
2414
2415     notResolvingStyle.link(&m_assembler);
2416     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isLastChildRegister));
2417 }
2418
2419 static void setOnlyChildState(Element* element)
2420 {
2421     if (RenderStyle* style = element->renderStyle()) {
2422         style->setFirstChildState();
2423         style->setLastChildState();
2424     }
2425 }
2426
2427 void SelectorCodeGenerator::generateElementIsOnlyChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2428 {
2429     // Is Only child is pretty much a combination of isFirstChild + isLastChild. The main difference is that tree marking is combined.
2430     if (m_selectorContext == SelectorContext::QuerySelector) {
2431         Assembler::JumpList previousSuccessCase = jumpIfNoPreviousAdjacentElement();
2432         failureCases.append(m_assembler.jump());
2433         previousSuccessCase.link(&m_assembler);
2434
2435         Assembler::JumpList nextSuccessCase = jumpIfNoNextAdjacentElement();
2436         failureCases.append(m_assembler.jump());
2437         nextSuccessCase.link(&m_assembler);
2438
2439         LocalRegister parent(m_registerAllocator);
2440         generateWalkToParentElement(failureCases, parent);
2441
2442         failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parent, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2443
2444         return;
2445     }
2446
2447     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2448     generateWalkToParentElement(failureCases, parentElement);
2449
2450     // Zero in isOnlyChildRegister is the success case. The register is set to non-zero if a sibling if found.
2451     LocalRegister isOnlyChildRegister(m_registerAllocator);
2452     m_assembler.move(Assembler::TrustedImm32(0), isOnlyChildRegister);
2453
2454     {
2455         Assembler::JumpList localFailureCases;
2456         {
2457             Assembler::JumpList successCase = jumpIfNoPreviousAdjacentElement();
2458             localFailureCases.append(m_assembler.jump());
2459             successCase.link(&m_assembler);
2460         }
2461         localFailureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(parentElement, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsParsingChildrenFinished())));
2462         Assembler::JumpList successCase = jumpIfNoNextAdjacentElement();
2463
2464         localFailureCases.link(&m_assembler);
2465         m_assembler.move(Assembler::TrustedImm32(1), isOnlyChildRegister);
2466
2467         successCase.link(&m_assembler);
2468     }
2469
2470     LocalRegister checkingContext(m_registerAllocator);
2471     Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2472
2473     setNodeFlag(m_assembler, parentElement, Node::flagChildrenAffectedByFirstChildRulesFlag() | Node::flagChildrenAffectedByLastChildRulesFlag());
2474     m_registerAllocator.deallocateRegister(parentElement);
2475
2476     // The parent marking is unconditional. If the matching is not a success, we can now fail.
2477     // Otherwise we need to apply setLastChildState() on the RenderStyle.
2478     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
2479
2480     if (shouldUseRenderStyleFromCheckingContext(fragment))
2481         addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::setFirstChildStateFlags() | RenderStyle::NonInheritedFlags::setLastChildStateFlags());
2482     else {
2483         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2484         functionCall.setFunctionAddress(setOnlyChildState);
2485         Assembler::RegisterID elementAddress = elementAddressRegister;
2486         functionCall.setOneArgument(elementAddress);
2487         functionCall.call();
2488     }
2489
2490     notResolvingStyle.link(&m_assembler);
2491     failureCases.append(m_assembler.branchTest32(Assembler::NonZero, isOnlyChildRegister));
2492 }
2493
2494 inline void SelectorCodeGenerator::generateElementHasTagName(Assembler::JumpList& failureCases, const QualifiedName& nameToMatch)
2495 {
2496     if (nameToMatch == anyQName())
2497         return;
2498
2499     // Load the QualifiedNameImpl from the input.
2500     LocalRegister qualifiedNameImpl(m_registerAllocator);
2501     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Element::tagQNameMemoryOffset() + QualifiedName::implMemoryOffset()), qualifiedNameImpl);
2502
2503     const AtomicString& selectorLocalName = nameToMatch.localName();
2504     if (selectorLocalName != starAtom) {
2505         // Generate localName == element->localName().
2506         LocalRegister constantRegister(m_registerAllocator);
2507         m_assembler.move(Assembler::TrustedImmPtr(selectorLocalName.impl()), constantRegister);
2508         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::localNameMemoryOffset()), constantRegister));
2509     }
2510
2511     const AtomicString& selectorNamespaceURI = nameToMatch.namespaceURI();
2512     if (selectorNamespaceURI != starAtom) {
2513         // Generate namespaceURI == element->namespaceURI().
2514         LocalRegister constantRegister(m_registerAllocator);
2515         m_assembler.move(Assembler::TrustedImmPtr(selectorNamespaceURI.impl()), constantRegister);
2516         failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(qualifiedNameImpl, QualifiedName::QualifiedNameImpl::namespaceMemoryOffset()), constantRegister));
2517     }
2518 }
2519
2520 void SelectorCodeGenerator::generateElementHasId(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const AtomicString& idToMatch)
2521 {
2522     // Compare the pointers of the AtomicStringImpl from idForStyleResolution with the reference idToMatch.
2523     LocalRegister idToMatchRegister(m_registerAllocator);
2524     m_assembler.move(Assembler::TrustedImmPtr(idToMatch.impl()), idToMatchRegister);
2525     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(elementDataAddress, ElementData::idForStyleResolutionMemoryOffset()), idToMatchRegister));
2526 }
2527
2528 void SelectorCodeGenerator::generateElementHasClasses(Assembler::JumpList& failureCases, const LocalRegister& elementDataAddress, const Vector<const AtomicStringImpl*>& classNames)
2529 {
2530     // Load m_classNames.
2531     LocalRegister spaceSplitStringData(m_registerAllocator);
2532     m_assembler.loadPtr(Assembler::Address(elementDataAddress, ElementData::classNamesMemoryOffset()), spaceSplitStringData);
2533
2534     // If SpaceSplitString does not have a SpaceSplitStringData pointer, it is empty -> failure case.
2535     failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, spaceSplitStringData));
2536
2537     // We loop over the classes of SpaceSplitStringData for each class name we need to match.
2538     LocalRegister indexRegister(m_registerAllocator);
2539     for (unsigned i = 0; i < classNames.size(); ++i) {
2540         LocalRegister classNameToMatch(m_registerAllocator);
2541         m_assembler.move(Assembler::TrustedImmPtr(classNames[i]), classNameToMatch);
2542         m_assembler.move(Assembler::TrustedImm32(0), indexRegister);
2543
2544         // Beginning of a loop over all the class name of element to find the one we are looking for.
2545         Assembler::Label loopStart(m_assembler.label());
2546
2547         // If the pointers match, proceed to the next matcher.
2548         Assembler::Jump classFound = m_assembler.branchPtr(Assembler::Equal, Assembler::BaseIndex(spaceSplitStringData, indexRegister, Assembler::timesPtr(), SpaceSplitStringData::tokensMemoryOffset()), classNameToMatch);
2549
2550         // Increment the index.
2551         m_assembler.add32(Assembler::TrustedImm32(1), indexRegister);
2552
2553         // If we reached the last element -> failure.
2554         failureCases.append(m_assembler.branch32(Assembler::Equal, Assembler::Address(spaceSplitStringData, SpaceSplitStringData::sizeMemoryOffset()), indexRegister));
2555         // Otherwise just loop over.
2556         m_assembler.jump().linkTo(loopStart, &m_assembler);
2557
2558         // Success case.
2559         classFound.link(&m_assembler);
2560     }
2561 }
2562
2563 void SelectorCodeGenerator::generateElementIsLink(Assembler::JumpList& failureCases)
2564 {
2565     failureCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(elementAddressRegister, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagIsLink())));
2566 }
2567
2568 static void setElementChildIndex(Element* element, int index)
2569 {
2570     element->setChildIndex(index);
2571 }
2572
2573 static void setElementChildIndexAndUpdateStyle(Element* element, int index)
2574 {
2575     element->setChildIndex(index);
2576     if (RenderStyle* childStyle = element->renderStyle())
2577         childStyle->setUnique();
2578 }
2579
2580 void SelectorCodeGenerator::generateElementIsNthChild(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2581 {
2582     Assembler::RegisterID parentElement = m_registerAllocator.allocateRegister();
2583     generateWalkToParentElement(failureCases, parentElement);
2584
2585     Vector<std::pair<int, int>, 32> validSubsetFilters;
2586     validSubsetFilters.reserveInitialCapacity(fragment.nthChildFilters.size());
2587     for (const auto& slot : fragment.nthChildFilters) {
2588         int a = slot.first;
2589         int b = slot.second;
2590
2591         // Anything modulo 1 is zero. Unless b restricts the range, this does not filter anything out.
2592         if (a == 1 && (!b || (b == 1)))
2593             continue;
2594         validSubsetFilters.uncheckedAppend(slot);
2595     }
2596     if (validSubsetFilters.isEmpty()) {
2597         m_registerAllocator.deallocateRegister(parentElement);
2598         return;
2599     }
2600     if (m_selectorContext == SelectorContext::QuerySelector)
2601         m_registerAllocator.deallocateRegister(parentElement);
2602
2603     // Setup the counter at 1.
2604     LocalRegisterWithPreference elementCounter(m_registerAllocator, JSC::GPRInfo::argumentGPR1);
2605     m_assembler.move(Assembler::TrustedImm32(1), elementCounter);
2606
2607     // Loop over the previous adjacent elements and increment the counter.
2608     {
2609         LocalRegister previousSibling(m_registerAllocator);
2610         m_assembler.move(elementAddressRegister, previousSibling);
2611
2612         // Getting the child index is very efficient when it works. When there is no child index,
2613         // querying at every iteration is very inefficient. We solve this by only testing the child
2614         // index on the first direct adjacent.
2615         Assembler::JumpList noMoreSiblingsCases;
2616
2617         Assembler::JumpList noCachedChildIndexCases;
2618         generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
2619         noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, Assembler::Address(previousSibling, Node::nodeFlagsMemoryOffset()), Assembler::TrustedImm32(Node::flagHasRareData())));
2620         {
2621             LocalRegister elementRareData(m_registerAllocator);
2622             m_assembler.loadPtr(Assembler::Address(previousSibling, Node::rareDataMemoryOffset()), elementRareData);
2623             LocalRegister cachedChildIndex(m_registerAllocator);
2624             m_assembler.load16(Assembler::Address(elementRareData, ElementRareData::childIndexMemoryOffset()), cachedChildIndex);
2625             noCachedChildIndexCases.append(m_assembler.branchTest32(Assembler::Zero, cachedChildIndex));
2626             m_assembler.add32(cachedChildIndex, elementCounter);
2627             noMoreSiblingsCases.append(m_assembler.jump());
2628         }
2629         noCachedChildIndexCases.link(&m_assembler);
2630         m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
2631
2632         Assembler::Label loopStart = m_assembler.label();
2633         generateWalkToPreviousAdjacentElement(noMoreSiblingsCases, previousSibling);
2634         m_assembler.add32(Assembler::TrustedImm32(1), elementCounter);
2635         m_assembler.jump().linkTo(loopStart, &m_assembler);
2636         noMoreSiblingsCases.link(&m_assembler);
2637     }
2638
2639     // Tree marking when doing style resolution.
2640     if (m_selectorContext != SelectorContext::QuerySelector) {
2641         LocalRegister checkingContext(m_registerAllocator);
2642         Assembler::Jump notResolvingStyle = jumpIfNotResolvingStyle(checkingContext);
2643
2644         m_registerAllocator.deallocateRegister(parentElement);
2645         FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2646         functionCall.setFunctionAddress(Element::setChildrenAffectedByForwardPositionalRules);
2647         functionCall.setOneArgument(parentElement);
2648         functionCall.call();
2649
2650         if (shouldUseRenderStyleFromCheckingContext(fragment)) {
2651             addFlagsToElementStyleFromContext(checkingContext, RenderStyle::NonInheritedFlags::flagIsUnique());
2652
2653             Assembler::RegisterID elementAddress = elementAddressRegister;
2654             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2655             functionCall.setFunctionAddress(setElementChildIndex);
2656             functionCall.setTwoArguments(elementAddress, elementCounter);
2657             functionCall.call();
2658         } else {
2659             Assembler::RegisterID elementAddress = elementAddressRegister;
2660             FunctionCall functionCall(m_assembler, m_registerAllocator, m_stackAllocator, m_functionCalls);
2661             functionCall.setFunctionAddress(setElementChildIndexAndUpdateStyle);
2662             functionCall.setTwoArguments(elementAddress, elementCounter);
2663             functionCall.call();
2664         }
2665
2666         notResolvingStyle.link(&m_assembler);
2667     }
2668
2669     // Test every the nth-child filter.
2670     for (const auto& slot : validSubsetFilters) {
2671         int a = slot.first;
2672         int b = slot.second;
2673
2674         if (!a)
2675             failureCases.append(m_assembler.branch32(Assembler::NotEqual, Assembler::TrustedImm32(b), elementCounter));
2676         else if (a > 0) {
2677             if (a == 2 && b == 1) {
2678                 // This is the common case 2n+1 (or "odd"), we can test for odd values without doing the arithmetic.
2679                 failureCases.append(m_assembler.branchTest32(Assembler::Zero, elementCounter, Assembler::TrustedImm32(1)));
2680             } else {
2681                 if (b)
2682                     failureCases.append(m_assembler.branchSub32(Assembler::Signed, Assembler::TrustedImm32(b), elementCounter));
2683                 moduloIsZero(failureCases, elementCounter, a);
2684             }
2685         } else {
2686             LocalRegister bRegister(m_registerAllocator);
2687             m_assembler.move(Assembler::TrustedImm32(b), bRegister);
2688
2689             failureCases.append(m_assembler.branchSub32(Assembler::Signed, elementCounter, bRegister));
2690             moduloIsZero(failureCases, bRegister, a);
2691         }
2692     }
2693 }
2694
2695 void SelectorCodeGenerator::generateElementMatchesNotPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2696 {
2697     for (const auto& subFragment : fragment.notFilters) {
2698         Assembler::JumpList localFailureCases;
2699         generateElementMatching(localFailureCases, localFailureCases, subFragment);
2700         // Since this is a not pseudo class filter, reaching here is a failure.
2701         failureCases.append(m_assembler.jump());
2702         localFailureCases.link(&m_assembler);
2703     }
2704 }
2705
2706 void SelectorCodeGenerator::generateElementMatchesAnyPseudoClass(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
2707 {
2708     for (const auto& subFragments : fragment.anyFilters) {
2709         RELEASE_ASSERT(!subFragments.isEmpty());
2710
2711         // Don't handle the last fragment in this loop.
2712         Assembler::JumpList successCases;
2713         for (unsigned i = 0; i < subFragments.size() - 1; ++i) {
2714             Assembler::JumpList localFailureCases;
2715             generateElementMatching(localFailureCases, localFailureCases, subFragments[i]);
2716             successCases.append(m_assembler.jump());
2717             localFailureCases.link(&m_assembler);
2718         }
2719
2720         // At the last fragment, optimize the failure jump to jump to the non-local failure directly.
2721         generateElementMatching(failureCases, failureCases, subFragments.last());
2722         successCases.link(&m_assembler);
2723     }
2724 }
2725
2726 void SelectorCodeGenerator::generateElementIsRoot(Assembler::JumpList& failureCases)
2727 {
2728     LocalRegister document(m_registerAllocator);
2729     getDocument(m_assembler, elementAddressRegister, document);
2730     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(document, Document::documentElementMemoryOffset()), elementAddressRegister));
2731 }
2732
2733 void SelectorCodeGenerator::generateElementIsTarget(Assembler::JumpList& failureCases)
2734 {
2735     LocalRegister document(m_registerAllocator);
2736     getDocument(m_assembler, elementAddressRegister, document);
2737     failureCases.append(m_assembler.branchPtr(Assembler::NotEqual, Assembler::Address(document, Document::cssTargetMemoryOffset()), elementAddressRegister));
2738 }
2739
2740 }; // namespace SelectorCompiler.
2741 }; // namespace WebCore.
2742
2743 #endif // ENABLE(CSS_SELECTOR_JIT)