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