[YARR] Extend size of fixed characters bulk matching in 64bit platform
[WebKit-https.git] / Source / JavaScriptCore / yarr / YarrJIT.cpp
1 /*
2  * Copyright (C) 2009-2018 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "YarrJIT.h"
28
29 #include <wtf/ASCIICType.h>
30 #include "LinkBuffer.h"
31 #include "Options.h"
32 #include "VM.h"
33 #include "Yarr.h"
34 #include "YarrCanonicalize.h"
35 #include "YarrDisassembler.h"
36
37 #if ENABLE(YARR_JIT)
38
39 using namespace WTF;
40
41 namespace JSC { namespace Yarr {
42
43 template<YarrJITCompileMode compileMode>
44 class YarrGenerator : public YarrJITInfo, private MacroAssembler {
45
46 #if CPU(ARM)
47     static const RegisterID input = ARMRegisters::r0;
48     static const RegisterID index = ARMRegisters::r1;
49     static const RegisterID length = ARMRegisters::r2;
50     static const RegisterID output = ARMRegisters::r3;
51
52     static const RegisterID regT0 = ARMRegisters::r4;
53     static const RegisterID regT1 = ARMRegisters::r5;
54     static const RegisterID initialStart = ARMRegisters::r8;
55
56     static const RegisterID returnRegister = ARMRegisters::r0;
57     static const RegisterID returnRegister2 = ARMRegisters::r1;
58
59 #define HAVE_INITIAL_START_REG
60 #elif CPU(ARM64)
61     // Argument registers
62     static const RegisterID input = ARM64Registers::x0;
63     static const RegisterID index = ARM64Registers::x1;
64     static const RegisterID length = ARM64Registers::x2;
65     static const RegisterID output = ARM64Registers::x3;
66     static const RegisterID freelistRegister = ARM64Registers::x4;
67     static const RegisterID freelistSizeRegister = ARM64Registers::x5;
68
69     // Scratch registers
70     static const RegisterID regT0 = ARM64Registers::x6;
71     static const RegisterID regT1 = ARM64Registers::x7;
72     static const RegisterID regT2 = ARM64Registers::x8;
73     static const RegisterID remainingMatchCount = ARM64Registers::x9;
74     static const RegisterID regUnicodeInputAndTrail = ARM64Registers::x10;
75     static const RegisterID initialStart = ARM64Registers::x11;
76     static const RegisterID supplementaryPlanesBase = ARM64Registers::x12;
77     static const RegisterID surrogateTagMask = ARM64Registers::x13;
78     static const RegisterID leadingSurrogateTag = ARM64Registers::x14;
79     static const RegisterID trailingSurrogateTag = ARM64Registers::x15;
80
81     static const RegisterID returnRegister = ARM64Registers::x0;
82     static const RegisterID returnRegister2 = ARM64Registers::x1;
83
84 #define HAVE_INITIAL_START_REG
85 #define JIT_UNICODE_EXPRESSIONS
86 #elif CPU(MIPS)
87     static const RegisterID input = MIPSRegisters::a0;
88     static const RegisterID index = MIPSRegisters::a1;
89     static const RegisterID length = MIPSRegisters::a2;
90     static const RegisterID output = MIPSRegisters::a3;
91
92     static const RegisterID regT0 = MIPSRegisters::t4;
93     static const RegisterID regT1 = MIPSRegisters::t5;
94     static const RegisterID initialStart = MIPSRegisters::t6;
95
96     static const RegisterID returnRegister = MIPSRegisters::v0;
97     static const RegisterID returnRegister2 = MIPSRegisters::v1;
98
99 #define HAVE_INITIAL_START_REG
100 #elif CPU(X86)
101     static const RegisterID input = X86Registers::eax;
102     static const RegisterID index = X86Registers::edx;
103     static const RegisterID length = X86Registers::ecx;
104     static const RegisterID output = X86Registers::edi;
105
106     static const RegisterID regT0 = X86Registers::ebx;
107     static const RegisterID regT1 = X86Registers::esi;
108
109     static const RegisterID returnRegister = X86Registers::eax;
110     static const RegisterID returnRegister2 = X86Registers::edx;
111 #elif CPU(X86_64)
112 #if !OS(WINDOWS)
113     // Argument registers
114     static const RegisterID input = X86Registers::edi;
115     static const RegisterID index = X86Registers::esi;
116     static const RegisterID length = X86Registers::edx;
117     static const RegisterID output = X86Registers::ecx;
118     static const RegisterID freelistRegister = X86Registers::r8;
119     static const RegisterID freelistSizeRegister = X86Registers::r9; // Only used during initialization.
120 #else
121     // If the return value doesn't fit in 64bits, its destination is pointed by rcx and the parameters are shifted.
122     // http://msdn.microsoft.com/en-us/library/7572ztz4.aspx
123     COMPILE_ASSERT(sizeof(MatchResult) > sizeof(void*), MatchResult_does_not_fit_in_64bits);
124     static const RegisterID input = X86Registers::edx;
125     static const RegisterID index = X86Registers::r8;
126     static const RegisterID length = X86Registers::r9;
127     static const RegisterID output = X86Registers::r10;
128 #endif
129
130     // Scratch registers
131     static const RegisterID regT0 = X86Registers::eax;
132 #if !OS(WINDOWS)
133     static const RegisterID regT1 = X86Registers::r9;
134     static const RegisterID regT2 = X86Registers::r10;
135 #else
136     static const RegisterID regT1 = X86Registers::ecx;
137     static const RegisterID regT2 = X86Registers::edi;
138 #endif
139
140     static const RegisterID initialStart = X86Registers::ebx;
141 #if !OS(WINDOWS)
142     static const RegisterID remainingMatchCount = X86Registers::r12;
143 #else
144     static const RegisterID remainingMatchCount = X86Registers::esi;
145 #endif
146     static const RegisterID regUnicodeInputAndTrail = X86Registers::r13;
147     static const RegisterID leadingSurrogateTag = X86Registers::r14;
148     static const RegisterID trailingSurrogateTag = X86Registers::r15;
149
150     static const RegisterID returnRegister = X86Registers::eax;
151     static const RegisterID returnRegister2 = X86Registers::edx;
152
153     const TrustedImm32 supplementaryPlanesBase = TrustedImm32(0x10000);
154     const TrustedImm32 surrogateTagMask = TrustedImm32(0xfffffc00);
155 #define HAVE_INITIAL_START_REG
156 #define JIT_UNICODE_EXPRESSIONS
157 #endif
158
159 #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)
160     struct ParenContextSizes {
161         size_t m_numSubpatterns;
162         size_t m_frameSlots;
163
164         ParenContextSizes(size_t numSubpatterns, size_t frameSlots)
165             : m_numSubpatterns(numSubpatterns)
166             , m_frameSlots(frameSlots)
167         {
168         }
169
170         size_t numSubpatterns() { return m_numSubpatterns; }
171
172         size_t frameSlots() { return m_frameSlots; }
173     };
174
175     struct ParenContext {
176         struct ParenContext* next;
177         uint32_t begin;
178         uint32_t matchAmount;
179         uintptr_t returnAddress;
180         struct Subpatterns {
181             unsigned start;
182             unsigned end;
183         } subpatterns[0];
184         uintptr_t frameSlots[0];
185
186         static size_t sizeFor(ParenContextSizes& parenContextSizes)
187         {
188             return sizeof(ParenContext) + sizeof(Subpatterns) * parenContextSizes.numSubpatterns() + sizeof(uintptr_t) * parenContextSizes.frameSlots();
189         }
190
191         static ptrdiff_t nextOffset()
192         {
193             return offsetof(ParenContext, next);
194         }
195
196         static ptrdiff_t beginOffset()
197         {
198             return offsetof(ParenContext, begin);
199         }
200
201         static ptrdiff_t matchAmountOffset()
202         {
203             return offsetof(ParenContext, matchAmount);
204         }
205
206         static ptrdiff_t returnAddressOffset()
207         {
208             return offsetof(ParenContext, returnAddress);
209         }
210
211         static ptrdiff_t subpatternOffset(size_t subpattern)
212         {
213             return offsetof(ParenContext, subpatterns) + (subpattern - 1) * sizeof(Subpatterns);
214         }
215
216         static ptrdiff_t savedFrameOffset(ParenContextSizes& parenContextSizes)
217         {
218             return offsetof(ParenContext, subpatterns) + (parenContextSizes.numSubpatterns()) * sizeof(Subpatterns);
219         }
220     };
221
222     void initParenContextFreeList()
223     {
224         RegisterID parenContextPointer = regT0;
225         RegisterID nextParenContextPointer = regT2;
226
227         size_t parenContextSize = ParenContext::sizeFor(m_parenContextSizes);
228
229         parenContextSize = WTF::roundUpToMultipleOf<sizeof(uintptr_t)>(parenContextSize);
230
231         // Check that the paren context is a reasonable size.
232         if (parenContextSize > INT16_MAX)
233             m_abortExecution.append(jump());
234
235         Jump emptyFreeList = branchTestPtr(Zero, freelistRegister);
236         move(freelistRegister, parenContextPointer);
237         addPtr(TrustedImm32(parenContextSize), freelistRegister, nextParenContextPointer);
238         addPtr(freelistRegister, freelistSizeRegister);
239         subPtr(TrustedImm32(parenContextSize), freelistSizeRegister);
240
241         Label loopTop(this);
242         Jump initDone = branchPtr(Above, nextParenContextPointer, freelistSizeRegister);
243         storePtr(nextParenContextPointer, Address(parenContextPointer, ParenContext::nextOffset()));
244         move(nextParenContextPointer, parenContextPointer);
245         addPtr(TrustedImm32(parenContextSize), parenContextPointer, nextParenContextPointer);
246         jump(loopTop);
247
248         initDone.link(this);
249         storePtr(TrustedImmPtr(nullptr), Address(parenContextPointer, ParenContext::nextOffset()));
250         emptyFreeList.link(this);
251     }
252
253     void allocateParenContext(RegisterID result)
254     {
255         m_abortExecution.append(branchTestPtr(Zero, freelistRegister));
256         sub32(TrustedImm32(1), remainingMatchCount);
257         m_hitMatchLimit.append(branchTestPtr(Zero, remainingMatchCount));
258         move(freelistRegister, result);
259         loadPtr(Address(freelistRegister, ParenContext::nextOffset()), freelistRegister);
260     }
261
262     void freeParenContext(RegisterID headPtrRegister, RegisterID newHeadPtrRegister)
263     {
264         loadPtr(Address(headPtrRegister, ParenContext::nextOffset()), newHeadPtrRegister);
265         storePtr(freelistRegister, Address(headPtrRegister, ParenContext::nextOffset()));
266         move(headPtrRegister, freelistRegister);
267     }
268
269     void saveParenContext(RegisterID parenContextReg, RegisterID tempReg, unsigned firstSubpattern, unsigned lastSubpattern, unsigned subpatternBaseFrameLocation)
270     {
271         store32(index, Address(parenContextReg, ParenContext::beginOffset()));
272         loadFromFrame(subpatternBaseFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), tempReg);
273         store32(tempReg, Address(parenContextReg, ParenContext::matchAmountOffset()));
274         loadFromFrame(subpatternBaseFrameLocation + BackTrackInfoParentheses::returnAddressIndex(), tempReg);
275         storePtr(tempReg, Address(parenContextReg, ParenContext::returnAddressOffset()));
276         if (compileMode == IncludeSubpatterns) {
277             for (unsigned subpattern = firstSubpattern; subpattern <= lastSubpattern; subpattern++) {
278                 loadPtr(Address(output, (subpattern << 1) * sizeof(unsigned)), tempReg);
279                 storePtr(tempReg, Address(parenContextReg, ParenContext::subpatternOffset(subpattern)));
280                 clearSubpatternStart(subpattern);
281             }
282         }
283         subpatternBaseFrameLocation += YarrStackSpaceForBackTrackInfoParentheses;
284         for (unsigned frameLocation = subpatternBaseFrameLocation; frameLocation < m_parenContextSizes.frameSlots(); frameLocation++) {
285             loadFromFrame(frameLocation, tempReg);
286             storePtr(tempReg, Address(parenContextReg, ParenContext::savedFrameOffset(m_parenContextSizes) + frameLocation * sizeof(uintptr_t)));
287         }
288     }
289
290     void restoreParenContext(RegisterID parenContextReg, RegisterID tempReg, unsigned firstSubpattern, unsigned lastSubpattern, unsigned subpatternBaseFrameLocation)
291     {
292         load32(Address(parenContextReg, ParenContext::beginOffset()), index);
293         storeToFrame(index, subpatternBaseFrameLocation + BackTrackInfoParentheses::beginIndex());
294         load32(Address(parenContextReg, ParenContext::matchAmountOffset()), tempReg);
295         storeToFrame(tempReg, subpatternBaseFrameLocation + BackTrackInfoParentheses::matchAmountIndex());
296         loadPtr(Address(parenContextReg, ParenContext::returnAddressOffset()), tempReg);
297         storeToFrame(tempReg, subpatternBaseFrameLocation + BackTrackInfoParentheses::returnAddressIndex());
298         if (compileMode == IncludeSubpatterns) {
299             for (unsigned subpattern = firstSubpattern; subpattern <= lastSubpattern; subpattern++) {
300                 loadPtr(Address(parenContextReg, ParenContext::subpatternOffset(subpattern)), tempReg);
301                 storePtr(tempReg, Address(output, (subpattern << 1) * sizeof(unsigned)));
302             }
303         }
304         subpatternBaseFrameLocation += YarrStackSpaceForBackTrackInfoParentheses;
305         for (unsigned frameLocation = subpatternBaseFrameLocation; frameLocation < m_parenContextSizes.frameSlots(); frameLocation++) {
306             loadPtr(Address(parenContextReg, ParenContext::savedFrameOffset(m_parenContextSizes) + frameLocation * sizeof(uintptr_t)), tempReg);
307             storeToFrame(tempReg, frameLocation);
308         }
309     }
310 #endif
311
312     void optimizeAlternative(PatternAlternative* alternative)
313     {
314         if (!alternative->m_terms.size())
315             return;
316
317         for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
318             PatternTerm& term = alternative->m_terms[i];
319             PatternTerm& nextTerm = alternative->m_terms[i + 1];
320
321             // We can move BMP only character classes after fixed character terms.
322             if ((term.type == PatternTerm::TypeCharacterClass)
323                 && (term.quantityType == QuantifierFixedCount)
324                 && (!m_decodeSurrogatePairs || (!term.characterClass->m_hasNonBMPCharacters && !term.m_invert))
325                 && (nextTerm.type == PatternTerm::TypePatternCharacter)
326                 && (nextTerm.quantityType == QuantifierFixedCount)) {
327                 PatternTerm termCopy = term;
328                 alternative->m_terms[i] = nextTerm;
329                 alternative->m_terms[i + 1] = termCopy;
330             }
331         }
332     }
333
334     void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar32* matches, unsigned matchCount)
335     {
336         do {
337             // pick which range we're going to generate
338             int which = count >> 1;
339             char lo = ranges[which].begin;
340             char hi = ranges[which].end;
341
342             // check if there are any ranges or matches below lo.  If not, just jl to failure -
343             // if there is anything else to check, check that first, if it falls through jmp to failure.
344             if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
345                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
346
347                 // generate code for all ranges before this one
348                 if (which)
349                     matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
350
351                 while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
352                     matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
353                     ++*matchIndex;
354                 }
355                 failures.append(jump());
356
357                 loOrAbove.link(this);
358             } else if (which) {
359                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
360
361                 matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
362                 failures.append(jump());
363
364                 loOrAbove.link(this);
365             } else
366                 failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
367
368             while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
369                 ++*matchIndex;
370
371             matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
372             // fall through to here, the value is above hi.
373
374             // shuffle along & loop around if there are any more matches to handle.
375             unsigned next = which + 1;
376             ranges += next;
377             count -= next;
378         } while (count);
379     }
380
381     void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
382     {
383         if (charClass->m_table && !m_decodeSurrogatePairs) {
384             ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table));
385             matchDest.append(branchTest8(charClass->m_tableInverted ? Zero : NonZero, tableEntry));
386             return;
387         }
388         JumpList unicodeFail;
389         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
390             JumpList isAscii;
391             if (charClass->m_matches.size() || charClass->m_ranges.size())
392                 isAscii.append(branch32(LessThanOrEqual, character, TrustedImm32(0x7f)));
393
394             if (charClass->m_matchesUnicode.size()) {
395                 for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
396                     UChar32 ch = charClass->m_matchesUnicode[i];
397                     matchDest.append(branch32(Equal, character, Imm32(ch)));
398                 }
399             }
400
401             if (charClass->m_rangesUnicode.size()) {
402                 for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
403                     UChar32 lo = charClass->m_rangesUnicode[i].begin;
404                     UChar32 hi = charClass->m_rangesUnicode[i].end;
405
406                     Jump below = branch32(LessThan, character, Imm32(lo));
407                     matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
408                     below.link(this);
409                 }
410             }
411
412             if (charClass->m_matches.size() || charClass->m_ranges.size())
413                 unicodeFail = jump();
414             isAscii.link(this);
415         }
416
417         if (charClass->m_ranges.size()) {
418             unsigned matchIndex = 0;
419             JumpList failures;
420             matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
421             while (matchIndex < charClass->m_matches.size())
422                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
423
424             failures.link(this);
425         } else if (charClass->m_matches.size()) {
426             // optimization: gather 'a','A' etc back together, can mask & test once.
427             Vector<char> matchesAZaz;
428
429             for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
430                 char ch = charClass->m_matches[i];
431                 if (m_pattern.ignoreCase()) {
432                     if (isASCIILower(ch)) {
433                         matchesAZaz.append(ch);
434                         continue;
435                     }
436                     if (isASCIIUpper(ch))
437                         continue;
438                 }
439                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
440             }
441
442             if (unsigned countAZaz = matchesAZaz.size()) {
443                 or32(TrustedImm32(32), character);
444                 for (unsigned i = 0; i < countAZaz; ++i)
445                     matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
446             }
447         }
448
449         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
450             unicodeFail.link(this);
451     }
452
453     // Jumps if input not available; will have (incorrectly) incremented already!
454     Jump jumpIfNoAvailableInput(unsigned countToCheck = 0)
455     {
456         if (countToCheck)
457             add32(Imm32(countToCheck), index);
458         return branch32(Above, index, length);
459     }
460
461     Jump jumpIfAvailableInput(unsigned countToCheck)
462     {
463         add32(Imm32(countToCheck), index);
464         return branch32(BelowOrEqual, index, length);
465     }
466
467     Jump checkInput()
468     {
469         return branch32(BelowOrEqual, index, length);
470     }
471
472     Jump atEndOfInput()
473     {
474         return branch32(Equal, index, length);
475     }
476
477     Jump notAtEndOfInput()
478     {
479         return branch32(NotEqual, index, length);
480     }
481
482     BaseIndex negativeOffsetIndexedAddress(Checked<unsigned> negativeCharacterOffset, RegisterID tempReg, RegisterID indexReg = index)
483     {
484         RegisterID base = input;
485
486         // BaseIndex() addressing can take a int32_t offset. Given that we can have a regular
487         // expression that has unsigned character offsets, BaseIndex's signed offset is insufficient
488         // for addressing in extreme cases where we might underflow. Therefore we check to see if
489         // negativeCharacterOffset will underflow directly or after converting for 16 bit characters.
490         // If so, we do our own address calculating by adjusting the base, using the result register
491         // as a temp address register.
492         unsigned maximumNegativeOffsetForCharacterSize = m_charSize == Char8 ? 0x7fffffff : 0x3fffffff;
493         unsigned offsetAdjustAmount = 0x40000000;
494         if (negativeCharacterOffset.unsafeGet() > maximumNegativeOffsetForCharacterSize) {
495             base = tempReg;
496             move(input, base);
497             while (negativeCharacterOffset.unsafeGet() > maximumNegativeOffsetForCharacterSize) {
498                 subPtr(TrustedImm32(offsetAdjustAmount), base);
499                 if (m_charSize != Char8)
500                     subPtr(TrustedImm32(offsetAdjustAmount), base);
501                 negativeCharacterOffset -= offsetAdjustAmount;
502             }
503         }
504
505         Checked<int32_t> characterOffset(-static_cast<int32_t>(negativeCharacterOffset.unsafeGet()));
506
507         if (m_charSize == Char8)
508             return BaseIndex(input, indexReg, TimesOne, (characterOffset * static_cast<int32_t>(sizeof(char))).unsafeGet());
509
510         return BaseIndex(input, indexReg, TimesTwo, (characterOffset * static_cast<int32_t>(sizeof(UChar))).unsafeGet());
511     }
512
513 #ifdef JIT_UNICODE_EXPRESSIONS
514     void tryReadUnicodeCharImpl(RegisterID resultReg)
515     {
516         ASSERT(m_charSize == Char16);
517
518         JumpList notUnicode;
519         load16Unaligned(regUnicodeInputAndTrail, resultReg);
520         and32(surrogateTagMask, resultReg, regT2);
521         notUnicode.append(branch32(NotEqual, regT2, leadingSurrogateTag));
522         addPtr(TrustedImm32(2), regUnicodeInputAndTrail);
523         getEffectiveAddress(BaseIndex(input, length, TimesTwo), regT2);
524         notUnicode.append(branch32(AboveOrEqual, regUnicodeInputAndTrail, regT2));
525         load16Unaligned(Address(regUnicodeInputAndTrail), regUnicodeInputAndTrail);
526         and32(surrogateTagMask, regUnicodeInputAndTrail, regT2);
527         notUnicode.append(branch32(NotEqual, regT2, trailingSurrogateTag));
528         sub32(leadingSurrogateTag, resultReg);
529         sub32(trailingSurrogateTag, regUnicodeInputAndTrail);
530         lshift32(TrustedImm32(10), resultReg);
531         or32(regUnicodeInputAndTrail, resultReg);
532         add32(supplementaryPlanesBase, resultReg);
533         notUnicode.link(this);
534     }
535
536     void tryReadUnicodeChar(BaseIndex address, RegisterID resultReg)
537     {
538         ASSERT(m_charSize == Char16);
539
540         getEffectiveAddress(address, regUnicodeInputAndTrail);
541
542         if (resultReg == regT0)
543             m_tryReadUnicodeCharacterCalls.append(nearCall());
544         else
545             tryReadUnicodeCharImpl(resultReg);
546     }
547 #endif
548
549     void readCharacter(Checked<unsigned> negativeCharacterOffset, RegisterID resultReg, RegisterID indexReg = index)
550     {
551         BaseIndex address = negativeOffsetIndexedAddress(negativeCharacterOffset, resultReg, indexReg);
552
553         if (m_charSize == Char8)
554             load8(address, resultReg);
555 #ifdef JIT_UNICODE_EXPRESSIONS
556         else if (m_decodeSurrogatePairs)
557             tryReadUnicodeChar(address, resultReg);
558 #endif
559         else
560             load16Unaligned(address, resultReg);
561     }
562
563     Jump jumpIfCharNotEquals(UChar32 ch, Checked<unsigned> negativeCharacterOffset, RegisterID character)
564     {
565         readCharacter(negativeCharacterOffset, character);
566
567         // For case-insesitive compares, non-ascii characters that have different
568         // upper & lower case representations are converted to a character class.
569         ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode));
570         if (m_pattern.ignoreCase() && isASCIIAlpha(ch)) {
571             or32(TrustedImm32(0x20), character);
572             ch |= 0x20;
573         }
574
575         return branch32(NotEqual, character, Imm32(ch));
576     }
577     
578     void storeToFrame(RegisterID reg, unsigned frameLocation)
579     {
580         poke(reg, frameLocation);
581     }
582
583     void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
584     {
585         poke(imm, frameLocation);
586     }
587
588 #if CPU(ARM64) || CPU(X86_64)
589     void storeToFrame(TrustedImmPtr imm, unsigned frameLocation)
590     {
591         poke(imm, frameLocation);
592     }
593 #endif
594
595     DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
596     {
597         return storePtrWithPatch(TrustedImmPtr(nullptr), Address(stackPointerRegister, frameLocation * sizeof(void*)));
598     }
599
600     void loadFromFrame(unsigned frameLocation, RegisterID reg)
601     {
602         peek(reg, frameLocation);
603     }
604
605     void loadFromFrameAndJump(unsigned frameLocation)
606     {
607         jump(Address(stackPointerRegister, frameLocation * sizeof(void*)), YarrBacktrackPtrTag);
608     }
609
610     unsigned alignCallFrameSizeInBytes(unsigned callFrameSize)
611     {
612         if (!callFrameSize)
613             return 0;
614
615         callFrameSize *= sizeof(void*);
616         if (callFrameSize / sizeof(void*) != m_pattern.m_body->m_callFrameSize)
617             CRASH();
618         callFrameSize = (callFrameSize + 0x3f) & ~0x3f;
619         return callFrameSize;
620     }
621     void initCallFrame()
622     {
623         unsigned callFrameSizeInBytes = alignCallFrameSizeInBytes(m_pattern.m_body->m_callFrameSize);
624         if (callFrameSizeInBytes) {
625 #if CPU(X86_64) || CPU(ARM64)
626             if (Options::zeroStackFrame()) {
627                 // We need to start from the stack pointer, because we could have spilled callee saves
628                 move(stackPointerRegister, regT0);
629                 subPtr(Imm32(callFrameSizeInBytes), stackPointerRegister);
630                 if (callFrameSizeInBytes <= 128) {
631                     for (unsigned offset = 0; offset < callFrameSizeInBytes; offset += sizeof(intptr_t))
632                         storePtr(TrustedImm32(0), Address(regT0, -8 - offset));
633                 } else {
634                     Label zeroLoop = label();
635                     subPtr(TrustedImm32(sizeof(intptr_t) * 2), regT0);
636 #if CPU(ARM64)
637                     storePair64(ARM64Registers::zr, ARM64Registers::zr, regT0);
638 #else
639                     storePtr(TrustedImm32(0), Address(regT0));
640                     storePtr(TrustedImm32(0), Address(regT0, sizeof(intptr_t)));
641 #endif
642                     branchPtr(NotEqual, regT0, stackPointerRegister).linkTo(zeroLoop, this);
643                 }
644             } else
645 #endif
646                 subPtr(Imm32(callFrameSizeInBytes), stackPointerRegister);
647
648         }
649     }
650     void removeCallFrame()
651     {
652         unsigned callFrameSizeInBytes = alignCallFrameSizeInBytes(m_pattern.m_body->m_callFrameSize);
653         if (callFrameSizeInBytes)
654             addPtr(Imm32(callFrameSizeInBytes), stackPointerRegister);
655     }
656
657     void generateFailReturn()
658     {
659         move(TrustedImmPtr((void*)WTF::notFound), returnRegister);
660         move(TrustedImm32(0), returnRegister2);
661         generateReturn();
662     }
663
664     void generateJITFailReturn()
665     {
666         if (m_abortExecution.empty() && m_hitMatchLimit.empty())
667             return;
668
669         JumpList finishExiting;
670         if (!m_abortExecution.empty()) {
671             m_abortExecution.link(this);
672             move(TrustedImmPtr((void*)static_cast<size_t>(-2)), returnRegister);
673             finishExiting.append(jump());
674         }
675
676         if (!m_hitMatchLimit.empty()) {
677             m_hitMatchLimit.link(this);
678             move(TrustedImmPtr((void*)static_cast<size_t>(-1)), returnRegister);
679         }
680
681         finishExiting.link(this);
682         removeCallFrame();
683         move(TrustedImm32(0), returnRegister2);
684         generateReturn();
685     }
686
687     // Used to record subpatterns, should only be called if compileMode is IncludeSubpatterns.
688     void setSubpatternStart(RegisterID reg, unsigned subpattern)
689     {
690         ASSERT(subpattern);
691         // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
692         store32(reg, Address(output, (subpattern << 1) * sizeof(int)));
693     }
694     void setSubpatternEnd(RegisterID reg, unsigned subpattern)
695     {
696         ASSERT(subpattern);
697         // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
698         store32(reg, Address(output, ((subpattern << 1) + 1) * sizeof(int)));
699     }
700     void clearSubpatternStart(unsigned subpattern)
701     {
702         ASSERT(subpattern);
703         // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
704         store32(TrustedImm32(-1), Address(output, (subpattern << 1) * sizeof(int)));
705     }
706
707     void clearMatches(unsigned subpattern, unsigned lastSubpattern)
708     {
709         for (; subpattern <= lastSubpattern; subpattern++)
710             clearSubpatternStart(subpattern);
711     }
712
713     // We use one of three different strategies to track the start of the current match,
714     // while matching.
715     // 1) If the pattern has a fixed size, do nothing! - we calculate the value lazily
716     //    at the end of matching. This is irrespective of compileMode, and in this case
717     //    these methods should never be called.
718     // 2) If we're compiling IncludeSubpatterns, 'output' contains a pointer to an output
719     //    vector, store the match start in the output vector.
720     // 3) If we're compiling MatchOnly, 'output' is unused, store the match start directly
721     //    in this register.
722     void setMatchStart(RegisterID reg)
723     {
724         ASSERT(!m_pattern.m_body->m_hasFixedSize);
725         if (compileMode == IncludeSubpatterns)
726             store32(reg, output);
727         else
728             move(reg, output);
729     }
730     void getMatchStart(RegisterID reg)
731     {
732         ASSERT(!m_pattern.m_body->m_hasFixedSize);
733         if (compileMode == IncludeSubpatterns)
734             load32(output, reg);
735         else
736             move(output, reg);
737     }
738
739     enum YarrOpCode {
740         // These nodes wrap body alternatives - those in the main disjunction,
741         // rather than subpatterns or assertions. These are chained together in
742         // a doubly linked list, with a 'begin' node for the first alternative,
743         // a 'next' node for each subsequent alternative, and an 'end' node at
744         // the end. In the case of repeating alternatives, the 'end' node also
745         // has a reference back to 'begin'.
746         OpBodyAlternativeBegin,
747         OpBodyAlternativeNext,
748         OpBodyAlternativeEnd,
749         // Similar to the body alternatives, but used for subpatterns with two
750         // or more alternatives.
751         OpNestedAlternativeBegin,
752         OpNestedAlternativeNext,
753         OpNestedAlternativeEnd,
754         // Used for alternatives in subpatterns where there is only a single
755         // alternative (backtracking is easier in these cases), or for alternatives
756         // which never need to be backtracked (those in parenthetical assertions,
757         // terminal subpatterns).
758         OpSimpleNestedAlternativeBegin,
759         OpSimpleNestedAlternativeNext,
760         OpSimpleNestedAlternativeEnd,
761         // Used to wrap 'Once' subpattern matches (quantityMaxCount == 1).
762         OpParenthesesSubpatternOnceBegin,
763         OpParenthesesSubpatternOnceEnd,
764         // Used to wrap 'Terminal' subpattern matches (at the end of the regexp).
765         OpParenthesesSubpatternTerminalBegin,
766         OpParenthesesSubpatternTerminalEnd,
767         // Used to wrap generic captured matches
768         OpParenthesesSubpatternBegin,
769         OpParenthesesSubpatternEnd,
770         // Used to wrap parenthetical assertions.
771         OpParentheticalAssertionBegin,
772         OpParentheticalAssertionEnd,
773         // Wraps all simple terms (pattern characters, character classes).
774         OpTerm,
775         // Where an expression contains only 'once through' body alternatives
776         // and no repeating ones, this op is used to return match failure.
777         OpMatchFailed
778     };
779
780     // This structure is used to hold the compiled opcode information,
781     // including reference back to the original PatternTerm/PatternAlternatives,
782     // and JIT compilation data structures.
783     struct YarrOp {
784         explicit YarrOp(PatternTerm* term)
785             : m_op(OpTerm)
786             , m_term(term)
787             , m_isDeadCode(false)
788         {
789         }
790
791         explicit YarrOp(YarrOpCode op)
792             : m_op(op)
793             , m_isDeadCode(false)
794         {
795         }
796
797         // The operation, as a YarrOpCode, and also a reference to the PatternTerm.
798         YarrOpCode m_op;
799         PatternTerm* m_term;
800
801         // For alternatives, this holds the PatternAlternative and doubly linked
802         // references to this alternative's siblings. In the case of the
803         // OpBodyAlternativeEnd node at the end of a section of repeating nodes,
804         // m_nextOp will reference the OpBodyAlternativeBegin node of the first
805         // repeating alternative.
806         PatternAlternative* m_alternative;
807         size_t m_previousOp;
808         size_t m_nextOp;
809
810         // Used to record a set of Jumps out of the generated code, typically
811         // used for jumps out to backtracking code, and a single reentry back
812         // into the code for a node (likely where a backtrack will trigger
813         // rematching).
814         Label m_reentry;
815         JumpList m_jumps;
816
817         // Used for backtracking when the prior alternative did not consume any
818         // characters but matched.
819         Jump m_zeroLengthMatch;
820
821         // This flag is used to null out the second pattern character, when
822         // two are fused to match a pair together.
823         bool m_isDeadCode;
824
825         // Currently used in the case of some of the more complex management of
826         // 'm_checkedOffset', to cache the offset used in this alternative, to avoid
827         // recalculating it.
828         Checked<unsigned> m_checkAdjust;
829
830         // Used by OpNestedAlternativeNext/End to hold the pointer to the
831         // value that will be pushed into the pattern's frame to return to,
832         // upon backtracking back into the disjunction.
833         DataLabelPtr m_returnAddress;
834     };
835
836     // BacktrackingState
837     // This class encapsulates information about the state of code generation
838     // whilst generating the code for backtracking, when a term fails to match.
839     // Upon entry to code generation of the backtracking code for a given node,
840     // the Backtracking state will hold references to all control flow sources
841     // that are outputs in need of further backtracking from the prior node
842     // generated (which is the subsequent operation in the regular expression,
843     // and in the m_ops Vector, since we generated backtracking backwards).
844     // These references to control flow take the form of:
845     //  - A jump list of jumps, to be linked to code that will backtrack them
846     //    further.
847     //  - A set of DataLabelPtr values, to be populated with values to be
848     //    treated effectively as return addresses backtracking into complex
849     //    subpatterns.
850     //  - A flag indicating that the current sequence of generated code up to
851     //    this point requires backtracking.
852     class BacktrackingState {
853     public:
854         BacktrackingState()
855             : m_pendingFallthrough(false)
856         {
857         }
858
859         // Add a jump or jumps, a return address, or set the flag indicating
860         // that the current 'fallthrough' control flow requires backtracking.
861         void append(const Jump& jump)
862         {
863             m_laterFailures.append(jump);
864         }
865         void append(JumpList& jumpList)
866         {
867             m_laterFailures.append(jumpList);
868         }
869         void append(const DataLabelPtr& returnAddress)
870         {
871             m_pendingReturns.append(returnAddress);
872         }
873         void fallthrough()
874         {
875             ASSERT(!m_pendingFallthrough);
876             m_pendingFallthrough = true;
877         }
878
879         // These methods clear the backtracking state, either linking to the
880         // current location, a provided label, or copying the backtracking out
881         // to a JumpList. All actions may require code generation to take place,
882         // and as such are passed a pointer to the assembler.
883         void link(MacroAssembler* assembler)
884         {
885             if (m_pendingReturns.size()) {
886                 Label here(assembler);
887                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
888                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
889                 m_pendingReturns.clear();
890             }
891             m_laterFailures.link(assembler);
892             m_laterFailures.clear();
893             m_pendingFallthrough = false;
894         }
895         void linkTo(Label label, MacroAssembler* assembler)
896         {
897             if (m_pendingReturns.size()) {
898                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
899                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], label));
900                 m_pendingReturns.clear();
901             }
902             if (m_pendingFallthrough)
903                 assembler->jump(label);
904             m_laterFailures.linkTo(label, assembler);
905             m_laterFailures.clear();
906             m_pendingFallthrough = false;
907         }
908         void takeBacktracksToJumpList(JumpList& jumpList, MacroAssembler* assembler)
909         {
910             if (m_pendingReturns.size()) {
911                 Label here(assembler);
912                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
913                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
914                 m_pendingReturns.clear();
915                 m_pendingFallthrough = true;
916             }
917             if (m_pendingFallthrough)
918                 jumpList.append(assembler->jump());
919             jumpList.append(m_laterFailures);
920             m_laterFailures.clear();
921             m_pendingFallthrough = false;
922         }
923
924         bool isEmpty()
925         {
926             return m_laterFailures.empty() && m_pendingReturns.isEmpty() && !m_pendingFallthrough;
927         }
928
929         // Called at the end of code generation to link all return addresses.
930         void linkDataLabels(LinkBuffer& linkBuffer)
931         {
932             ASSERT(isEmpty());
933             for (unsigned i = 0; i < m_backtrackRecords.size(); ++i)
934                 linkBuffer.patch(m_backtrackRecords[i].m_dataLabel, linkBuffer.locationOf<YarrBacktrackPtrTag>(m_backtrackRecords[i].m_backtrackLocation));
935         }
936
937     private:
938         struct ReturnAddressRecord {
939             ReturnAddressRecord(DataLabelPtr dataLabel, Label backtrackLocation)
940                 : m_dataLabel(dataLabel)
941                 , m_backtrackLocation(backtrackLocation)
942             {
943             }
944
945             DataLabelPtr m_dataLabel;
946             Label m_backtrackLocation;
947         };
948
949         JumpList m_laterFailures;
950         bool m_pendingFallthrough;
951         Vector<DataLabelPtr, 4> m_pendingReturns;
952         Vector<ReturnAddressRecord, 4> m_backtrackRecords;
953     };
954
955     // Generation methods:
956     // ===================
957
958     // This method provides a default implementation of backtracking common
959     // to many terms; terms commonly jump out of the forwards  matching path
960     // on any failed conditions, and add these jumps to the m_jumps list. If
961     // no special handling is required we can often just backtrack to m_jumps.
962     void backtrackTermDefault(size_t opIndex)
963     {
964         YarrOp& op = m_ops[opIndex];
965         m_backtrackingState.append(op.m_jumps);
966     }
967
968     void generateAssertionBOL(size_t opIndex)
969     {
970         YarrOp& op = m_ops[opIndex];
971         PatternTerm* term = op.m_term;
972
973         if (m_pattern.multiline()) {
974             const RegisterID character = regT0;
975
976             JumpList matchDest;
977             if (!term->inputPosition)
978                 matchDest.append(branch32(Equal, index, Imm32(m_checkedOffset.unsafeGet())));
979
980             readCharacter(m_checkedOffset - term->inputPosition + 1, character);
981             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
982             op.m_jumps.append(jump());
983
984             matchDest.link(this);
985         } else {
986             // Erk, really should poison out these alternatives early. :-/
987             if (term->inputPosition)
988                 op.m_jumps.append(jump());
989             else
990                 op.m_jumps.append(branch32(NotEqual, index, Imm32(m_checkedOffset.unsafeGet())));
991         }
992     }
993     void backtrackAssertionBOL(size_t opIndex)
994     {
995         backtrackTermDefault(opIndex);
996     }
997
998     void generateAssertionEOL(size_t opIndex)
999     {
1000         YarrOp& op = m_ops[opIndex];
1001         PatternTerm* term = op.m_term;
1002
1003         if (m_pattern.multiline()) {
1004             const RegisterID character = regT0;
1005
1006             JumpList matchDest;
1007             if (term->inputPosition == m_checkedOffset.unsafeGet())
1008                 matchDest.append(atEndOfInput());
1009
1010             readCharacter(m_checkedOffset - term->inputPosition, character);
1011             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
1012             op.m_jumps.append(jump());
1013
1014             matchDest.link(this);
1015         } else {
1016             if (term->inputPosition == m_checkedOffset.unsafeGet())
1017                 op.m_jumps.append(notAtEndOfInput());
1018             // Erk, really should poison out these alternatives early. :-/
1019             else
1020                 op.m_jumps.append(jump());
1021         }
1022     }
1023     void backtrackAssertionEOL(size_t opIndex)
1024     {
1025         backtrackTermDefault(opIndex);
1026     }
1027
1028     // Also falls though on nextIsNotWordChar.
1029     void matchAssertionWordchar(size_t opIndex, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
1030     {
1031         YarrOp& op = m_ops[opIndex];
1032         PatternTerm* term = op.m_term;
1033
1034         const RegisterID character = regT0;
1035
1036         if (term->inputPosition == m_checkedOffset.unsafeGet())
1037             nextIsNotWordChar.append(atEndOfInput());
1038
1039         readCharacter(m_checkedOffset - term->inputPosition, character);
1040
1041         CharacterClass* wordcharCharacterClass;
1042
1043         if (m_unicodeIgnoreCase)
1044             wordcharCharacterClass = m_pattern.wordUnicodeIgnoreCaseCharCharacterClass();
1045         else
1046             wordcharCharacterClass = m_pattern.wordcharCharacterClass();
1047
1048         matchCharacterClass(character, nextIsWordChar, wordcharCharacterClass);
1049     }
1050
1051     void generateAssertionWordBoundary(size_t opIndex)
1052     {
1053         YarrOp& op = m_ops[opIndex];
1054         PatternTerm* term = op.m_term;
1055
1056         const RegisterID character = regT0;
1057
1058         Jump atBegin;
1059         JumpList matchDest;
1060         if (!term->inputPosition)
1061             atBegin = branch32(Equal, index, Imm32(m_checkedOffset.unsafeGet()));
1062         readCharacter(m_checkedOffset - term->inputPosition + 1, character);
1063
1064         CharacterClass* wordcharCharacterClass;
1065
1066         if (m_unicodeIgnoreCase)
1067             wordcharCharacterClass = m_pattern.wordUnicodeIgnoreCaseCharCharacterClass();
1068         else
1069             wordcharCharacterClass = m_pattern.wordcharCharacterClass();
1070
1071         matchCharacterClass(character, matchDest, wordcharCharacterClass);
1072         if (!term->inputPosition)
1073             atBegin.link(this);
1074
1075         // We fall through to here if the last character was not a wordchar.
1076         JumpList nonWordCharThenWordChar;
1077         JumpList nonWordCharThenNonWordChar;
1078         if (term->invert()) {
1079             matchAssertionWordchar(opIndex, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
1080             nonWordCharThenWordChar.append(jump());
1081         } else {
1082             matchAssertionWordchar(opIndex, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
1083             nonWordCharThenNonWordChar.append(jump());
1084         }
1085         op.m_jumps.append(nonWordCharThenNonWordChar);
1086
1087         // We jump here if the last character was a wordchar.
1088         matchDest.link(this);
1089         JumpList wordCharThenWordChar;
1090         JumpList wordCharThenNonWordChar;
1091         if (term->invert()) {
1092             matchAssertionWordchar(opIndex, wordCharThenNonWordChar, wordCharThenWordChar);
1093             wordCharThenWordChar.append(jump());
1094         } else {
1095             matchAssertionWordchar(opIndex, wordCharThenWordChar, wordCharThenNonWordChar);
1096             // This can fall-though!
1097         }
1098
1099         op.m_jumps.append(wordCharThenWordChar);
1100
1101         nonWordCharThenWordChar.link(this);
1102         wordCharThenNonWordChar.link(this);
1103     }
1104     void backtrackAssertionWordBoundary(size_t opIndex)
1105     {
1106         backtrackTermDefault(opIndex);
1107     }
1108
1109     void generatePatternCharacterOnce(size_t opIndex)
1110     {
1111         YarrOp& op = m_ops[opIndex];
1112
1113         if (op.m_isDeadCode)
1114             return;
1115         
1116         // m_ops always ends with a OpBodyAlternativeEnd or OpMatchFailed
1117         // node, so there must always be at least one more node.
1118         ASSERT(opIndex + 1 < m_ops.size());
1119         YarrOp* nextOp = &m_ops[opIndex + 1];
1120
1121         PatternTerm* term = op.m_term;
1122         UChar32 ch = term->patternCharacter;
1123
1124         if ((ch > 0xff) && (m_charSize == Char8)) {
1125             // Have a 16 bit pattern character and an 8 bit string - short circuit
1126             op.m_jumps.append(jump());
1127             return;
1128         }
1129
1130         const RegisterID character = regT0;
1131 #if CPU(X86_64) || CPU(ARM64)
1132         unsigned maxCharactersAtOnce = m_charSize == Char8 ? 8 : 4;
1133 #else
1134         unsigned maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2;
1135 #endif
1136         uint64_t ignoreCaseMask = 0;
1137 #if CPU(BIG_ENDIAN)
1138         uint64_t allCharacters = ch << (m_charSize == Char8 ? 24 : 16);
1139 #else
1140         uint64_t allCharacters = ch;
1141 #endif
1142         unsigned numberCharacters;
1143         unsigned startTermPosition = term->inputPosition;
1144
1145         // For case-insesitive compares, non-ascii characters that have different
1146         // upper & lower case representations are converted to a character class.
1147         ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode));
1148
1149         if (m_pattern.ignoreCase() && isASCIIAlpha(ch)) {
1150 #if CPU(BIG_ENDIAN)
1151             ignoreCaseMask |= 32 << (m_charSize == Char8 ? 24 : 16);
1152 #else
1153             ignoreCaseMask |= 32;
1154 #endif
1155         }
1156
1157         for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) {
1158             PatternTerm* nextTerm = nextOp->m_term;
1159
1160             // YarrJIT handles decoded surrogate pair as one character if unicode flag is enabled.
1161             // Note that the numberCharacters become 1 while the width of the pattern character becomes 32bit in this case.
1162             if (nextTerm->type != PatternTerm::TypePatternCharacter
1163                 || nextTerm->quantityType != QuantifierFixedCount
1164                 || nextTerm->quantityMaxCount != 1
1165                 || nextTerm->inputPosition != (startTermPosition + numberCharacters)
1166                 || (U16_LENGTH(nextTerm->patternCharacter) != 1 && m_decodeSurrogatePairs))
1167                 break;
1168
1169             nextOp->m_isDeadCode = true;
1170
1171 #if CPU(BIG_ENDIAN)
1172             int shiftAmount = (m_charSize == Char8 ? 24 : 16) - ((m_charSize == Char8 ? 8 : 16) * numberCharacters);
1173 #else
1174             int shiftAmount = (m_charSize == Char8 ? 8 : 16) * numberCharacters;
1175 #endif
1176
1177             UChar32 currentCharacter = nextTerm->patternCharacter;
1178
1179             if ((currentCharacter > 0xff) && (m_charSize == Char8)) {
1180                 // Have a 16 bit pattern character and an 8 bit string - short circuit
1181                 op.m_jumps.append(jump());
1182                 return;
1183             }
1184
1185             // For case-insesitive compares, non-ascii characters that have different
1186             // upper & lower case representations are converted to a character class.
1187             ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(currentCharacter) || isCanonicallyUnique(currentCharacter, m_canonicalMode));
1188
1189             allCharacters |= (static_cast<uint64_t>(currentCharacter) << shiftAmount);
1190
1191             if ((m_pattern.ignoreCase()) && (isASCIIAlpha(currentCharacter)))
1192                 ignoreCaseMask |= 32ULL << shiftAmount;
1193         }
1194
1195         if (m_charSize == Char8) {
1196             auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) {
1197                 op.m_jumps.append(jumpIfCharNotEquals(characters, offset, character));
1198             };
1199
1200             auto check2 = [&] (Checked<unsigned> offset, uint16_t characters, uint16_t mask) {
1201                 load16Unaligned(negativeOffsetIndexedAddress(offset, character), character);
1202                 if (mask)
1203                     or32(Imm32(mask), character);
1204                 op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask)));
1205             };
1206
1207             auto check4 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) {
1208                 if (mask) {
1209                     load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(offset, character), character);
1210                     if (mask)
1211                         or32(Imm32(mask), character);
1212                     op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask)));
1213                     return;
1214                 }
1215                 op.m_jumps.append(branch32WithUnalignedHalfWords(NotEqual, negativeOffsetIndexedAddress(offset, character), TrustedImm32(characters)));
1216             };
1217
1218 #if CPU(X86_64) || CPU(ARM64)
1219             auto check8 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) {
1220                 load64(negativeOffsetIndexedAddress(offset, character), character);
1221                 if (mask)
1222                     or64(TrustedImm64(mask), character);
1223                 op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask)));
1224             };
1225 #endif
1226
1227             switch (numberCharacters) {
1228             case 1:
1229                 // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag.
1230                 check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff);
1231                 return;
1232             case 2: {
1233                 check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff);
1234                 return;
1235             }
1236             case 3: {
1237                 check2(m_checkedOffset - startTermPosition, allCharacters & 0xffff, ignoreCaseMask & 0xffff);
1238                 check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 16) & 0xff);
1239                 return;
1240             }
1241             case 4: {
1242                 check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
1243                 return;
1244             }
1245 #if CPU(X86_64) || CPU(ARM64)
1246             case 5: {
1247                 check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
1248                 check1(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xff);
1249                 return;
1250             }
1251             case 6: {
1252                 check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
1253                 check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff);
1254                 return;
1255             }
1256             case 7: {
1257                 check4(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
1258                 check2(m_checkedOffset - startTermPosition - 4, (allCharacters >> 32) & 0xffff, (ignoreCaseMask >> 32) & 0xffff);
1259                 check1(m_checkedOffset - startTermPosition - 6, (allCharacters >> 48) & 0xff);
1260                 return;
1261             }
1262             case 8: {
1263                 check8(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask);
1264                 return;
1265             }
1266 #endif
1267             }
1268         } else {
1269             auto check1 = [&] (Checked<unsigned> offset, UChar32 characters) {
1270                 op.m_jumps.append(jumpIfCharNotEquals(characters, offset, character));
1271             };
1272
1273             auto check2 = [&] (Checked<unsigned> offset, unsigned characters, unsigned mask) {
1274                 if (mask) {
1275                     load32WithUnalignedHalfWords(negativeOffsetIndexedAddress(offset, character), character);
1276                     if (mask)
1277                         or32(Imm32(mask), character);
1278                     op.m_jumps.append(branch32(NotEqual, character, Imm32(characters | mask)));
1279                     return;
1280                 }
1281                 op.m_jumps.append(branch32WithUnalignedHalfWords(NotEqual, negativeOffsetIndexedAddress(offset, character), TrustedImm32(characters)));
1282             };
1283
1284 #if CPU(X86_64) || CPU(ARM64)
1285             auto check4 = [&] (Checked<unsigned> offset, uint64_t characters, uint64_t mask) {
1286                 load64(negativeOffsetIndexedAddress(offset, character), character);
1287                 if (mask)
1288                     or64(TrustedImm64(mask), character);
1289                 op.m_jumps.append(branch64(NotEqual, character, TrustedImm64(characters | mask)));
1290             };
1291 #endif
1292
1293             switch (numberCharacters) {
1294             case 1:
1295                 // Use 32bit width of allCharacters since Yarr counts surrogate pairs as one character with unicode flag.
1296                 check1(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff);
1297                 return;
1298             case 2:
1299                 check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
1300                 return;
1301 #if CPU(X86_64) || CPU(ARM64)
1302             case 3:
1303                 check2(m_checkedOffset - startTermPosition, allCharacters & 0xffffffff, ignoreCaseMask & 0xffffffff);
1304                 check1(m_checkedOffset - startTermPosition - 2, (allCharacters >> 32) & 0xffff);
1305                 return;
1306             case 4:
1307                 check4(m_checkedOffset - startTermPosition, allCharacters, ignoreCaseMask);
1308                 return;
1309 #endif
1310             }
1311         }
1312     }
1313     void backtrackPatternCharacterOnce(size_t opIndex)
1314     {
1315         backtrackTermDefault(opIndex);
1316     }
1317
1318     void generatePatternCharacterFixed(size_t opIndex)
1319     {
1320         YarrOp& op = m_ops[opIndex];
1321         PatternTerm* term = op.m_term;
1322         UChar32 ch = term->patternCharacter;
1323
1324         const RegisterID character = regT0;
1325         const RegisterID countRegister = regT1;
1326
1327         move(index, countRegister);
1328         Checked<unsigned> scaledMaxCount = term->quantityMaxCount;
1329         scaledMaxCount *= U_IS_BMP(ch) ? 1 : 2;
1330         sub32(Imm32(scaledMaxCount.unsafeGet()), countRegister);
1331
1332         Label loop(this);
1333         readCharacter(m_checkedOffset - term->inputPosition - scaledMaxCount, character, countRegister);
1334         // For case-insesitive compares, non-ascii characters that have different
1335         // upper & lower case representations are converted to a character class.
1336         ASSERT(!m_pattern.ignoreCase() || isASCIIAlpha(ch) || isCanonicallyUnique(ch, m_canonicalMode));
1337         if (m_pattern.ignoreCase() && isASCIIAlpha(ch)) {
1338             or32(TrustedImm32(0x20), character);
1339             ch |= 0x20;
1340         }
1341
1342         op.m_jumps.append(branch32(NotEqual, character, Imm32(ch)));
1343 #ifdef JIT_UNICODE_EXPRESSIONS
1344         if (m_decodeSurrogatePairs && !U_IS_BMP(ch))
1345             add32(TrustedImm32(2), countRegister);
1346         else
1347 #endif
1348             add32(TrustedImm32(1), countRegister);
1349         branch32(NotEqual, countRegister, index).linkTo(loop, this);
1350     }
1351     void backtrackPatternCharacterFixed(size_t opIndex)
1352     {
1353         backtrackTermDefault(opIndex);
1354     }
1355
1356     void generatePatternCharacterGreedy(size_t opIndex)
1357     {
1358         YarrOp& op = m_ops[opIndex];
1359         PatternTerm* term = op.m_term;
1360         UChar32 ch = term->patternCharacter;
1361
1362         const RegisterID character = regT0;
1363         const RegisterID countRegister = regT1;
1364
1365         move(TrustedImm32(0), countRegister);
1366
1367         // Unless have a 16 bit pattern character and an 8 bit string - short circuit
1368         if (!((ch > 0xff) && (m_charSize == Char8))) {
1369             JumpList failures;
1370             Label loop(this);
1371             failures.append(atEndOfInput());
1372             failures.append(jumpIfCharNotEquals(ch, m_checkedOffset - term->inputPosition, character));
1373
1374             add32(TrustedImm32(1), index);
1375 #ifdef JIT_UNICODE_EXPRESSIONS
1376             if (m_decodeSurrogatePairs && !U_IS_BMP(ch)) {
1377                 Jump surrogatePairOk = notAtEndOfInput();
1378                 sub32(TrustedImm32(1), index);
1379                 failures.append(jump());
1380                 surrogatePairOk.link(this);
1381                 add32(TrustedImm32(1), index);
1382             }
1383 #endif
1384             add32(TrustedImm32(1), countRegister);
1385
1386             if (term->quantityMaxCount == quantifyInfinite)
1387                 jump(loop);
1388             else
1389                 branch32(NotEqual, countRegister, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(loop, this);
1390
1391             failures.link(this);
1392         }
1393         op.m_reentry = label();
1394
1395         storeToFrame(countRegister, term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex());
1396     }
1397     void backtrackPatternCharacterGreedy(size_t opIndex)
1398     {
1399         YarrOp& op = m_ops[opIndex];
1400         PatternTerm* term = op.m_term;
1401
1402         const RegisterID countRegister = regT1;
1403
1404         m_backtrackingState.link(this);
1405
1406         loadFromFrame(term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex(), countRegister);
1407         m_backtrackingState.append(branchTest32(Zero, countRegister));
1408         sub32(TrustedImm32(1), countRegister);
1409         if (!m_decodeSurrogatePairs || U_IS_BMP(term->patternCharacter))
1410             sub32(TrustedImm32(1), index);
1411         else
1412             sub32(TrustedImm32(2), index);
1413         jump(op.m_reentry);
1414     }
1415
1416     void generatePatternCharacterNonGreedy(size_t opIndex)
1417     {
1418         YarrOp& op = m_ops[opIndex];
1419         PatternTerm* term = op.m_term;
1420
1421         const RegisterID countRegister = regT1;
1422
1423         move(TrustedImm32(0), countRegister);
1424         op.m_reentry = label();
1425         storeToFrame(countRegister, term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex());
1426     }
1427     void backtrackPatternCharacterNonGreedy(size_t opIndex)
1428     {
1429         YarrOp& op = m_ops[opIndex];
1430         PatternTerm* term = op.m_term;
1431         UChar32 ch = term->patternCharacter;
1432
1433         const RegisterID character = regT0;
1434         const RegisterID countRegister = regT1;
1435
1436         m_backtrackingState.link(this);
1437
1438         loadFromFrame(term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex(), countRegister);
1439
1440         // Unless have a 16 bit pattern character and an 8 bit string - short circuit
1441         if (!((ch > 0xff) && (m_charSize == Char8))) {
1442             JumpList nonGreedyFailures;
1443             nonGreedyFailures.append(atEndOfInput());
1444             if (term->quantityMaxCount != quantifyInfinite)
1445                 nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityMaxCount.unsafeGet())));
1446             nonGreedyFailures.append(jumpIfCharNotEquals(ch, m_checkedOffset - term->inputPosition, character));
1447
1448             add32(TrustedImm32(1), index);
1449 #ifdef JIT_UNICODE_EXPRESSIONS
1450             if (m_decodeSurrogatePairs && !U_IS_BMP(ch)) {
1451                 Jump surrogatePairOk = notAtEndOfInput();
1452                 sub32(TrustedImm32(1), index);
1453                 nonGreedyFailures.append(jump());
1454                 surrogatePairOk.link(this);
1455                 add32(TrustedImm32(1), index);
1456             }
1457 #endif
1458             add32(TrustedImm32(1), countRegister);
1459
1460             jump(op.m_reentry);
1461             nonGreedyFailures.link(this);
1462         }
1463
1464         if (m_decodeSurrogatePairs && !U_IS_BMP(ch)) {
1465             // subtract countRegister*2 for non-BMP characters
1466             lshift32(TrustedImm32(1), countRegister);
1467         }
1468
1469         sub32(countRegister, index);
1470         m_backtrackingState.fallthrough();
1471     }
1472
1473     void generateCharacterClassOnce(size_t opIndex)
1474     {
1475         YarrOp& op = m_ops[opIndex];
1476         PatternTerm* term = op.m_term;
1477
1478         const RegisterID character = regT0;
1479
1480         if (m_decodeSurrogatePairs)
1481             storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex());
1482
1483         JumpList matchDest;
1484         readCharacter(m_checkedOffset - term->inputPosition, character);
1485         // If we are matching the "any character" builtin class we only need to read the
1486         // character and don't need to match as it will always succeed.
1487         if (term->invert() || !term->characterClass->m_anyCharacter) {
1488             matchCharacterClass(character, matchDest, term->characterClass);
1489
1490             if (term->invert())
1491                 op.m_jumps.append(matchDest);
1492             else {
1493                 op.m_jumps.append(jump());
1494                 matchDest.link(this);
1495             }
1496         }
1497 #ifdef JIT_UNICODE_EXPRESSIONS
1498         if (m_decodeSurrogatePairs) {
1499             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
1500             add32(TrustedImm32(1), index);
1501             isBMPChar.link(this);
1502         }
1503 #endif
1504     }
1505     void backtrackCharacterClassOnce(size_t opIndex)
1506     {
1507 #ifdef JIT_UNICODE_EXPRESSIONS
1508         if (m_decodeSurrogatePairs) {
1509             YarrOp& op = m_ops[opIndex];
1510             PatternTerm* term = op.m_term;
1511
1512             m_backtrackingState.link(this);
1513             loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), index);
1514             m_backtrackingState.fallthrough();
1515         }
1516 #endif
1517         backtrackTermDefault(opIndex);
1518     }
1519
1520     void generateCharacterClassFixed(size_t opIndex)
1521     {
1522         YarrOp& op = m_ops[opIndex];
1523         PatternTerm* term = op.m_term;
1524
1525         const RegisterID character = regT0;
1526         const RegisterID countRegister = regT1;
1527
1528         move(index, countRegister);
1529         sub32(Imm32(term->quantityMaxCount.unsafeGet()), countRegister);
1530
1531         Label loop(this);
1532         JumpList matchDest;
1533         readCharacter(m_checkedOffset - term->inputPosition - term->quantityMaxCount, character, countRegister);
1534         // If we are matching the "any character" builtin class we only need to read the
1535         // character and don't need to match as it will always succeed.
1536         if (term->invert() || !term->characterClass->m_anyCharacter) {
1537             matchCharacterClass(character, matchDest, term->characterClass);
1538
1539             if (term->invert())
1540                 op.m_jumps.append(matchDest);
1541             else {
1542                 op.m_jumps.append(jump());
1543                 matchDest.link(this);
1544             }
1545         }
1546
1547         add32(TrustedImm32(1), countRegister);
1548 #ifdef JIT_UNICODE_EXPRESSIONS
1549         if (m_decodeSurrogatePairs) {
1550             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
1551             op.m_jumps.append(atEndOfInput());
1552             add32(TrustedImm32(1), countRegister);
1553             add32(TrustedImm32(1), index);
1554             isBMPChar.link(this);
1555         }
1556 #endif
1557         branch32(NotEqual, countRegister, index).linkTo(loop, this);
1558     }
1559     void backtrackCharacterClassFixed(size_t opIndex)
1560     {
1561         backtrackTermDefault(opIndex);
1562     }
1563
1564     void generateCharacterClassGreedy(size_t opIndex)
1565     {
1566         YarrOp& op = m_ops[opIndex];
1567         PatternTerm* term = op.m_term;
1568
1569         const RegisterID character = regT0;
1570         const RegisterID countRegister = regT1;
1571
1572         if (m_decodeSurrogatePairs)
1573             storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex());
1574         move(TrustedImm32(0), countRegister);
1575
1576         JumpList failures;
1577         Label loop(this);
1578         failures.append(atEndOfInput());
1579
1580         if (term->invert()) {
1581             readCharacter(m_checkedOffset - term->inputPosition, character);
1582             matchCharacterClass(character, failures, term->characterClass);
1583         } else {
1584             JumpList matchDest;
1585             readCharacter(m_checkedOffset - term->inputPosition, character);
1586             // If we are matching the "any character" builtin class we only need to read the
1587             // character and don't need to match as it will always succeed.
1588             if (!term->characterClass->m_anyCharacter) {
1589                 matchCharacterClass(character, matchDest, term->characterClass);
1590                 failures.append(jump());
1591             }
1592             matchDest.link(this);
1593         }
1594
1595         add32(TrustedImm32(1), index);
1596 #ifdef JIT_UNICODE_EXPRESSIONS
1597         if (m_decodeSurrogatePairs) {
1598             failures.append(atEndOfInput());
1599             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
1600             add32(TrustedImm32(1), index);
1601             isBMPChar.link(this);
1602         }
1603 #endif
1604         add32(TrustedImm32(1), countRegister);
1605
1606         if (term->quantityMaxCount != quantifyInfinite) {
1607             branch32(NotEqual, countRegister, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(loop, this);
1608             failures.append(jump());
1609         } else
1610             jump(loop);
1611
1612         failures.link(this);
1613         op.m_reentry = label();
1614
1615         storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex());
1616     }
1617     void backtrackCharacterClassGreedy(size_t opIndex)
1618     {
1619         YarrOp& op = m_ops[opIndex];
1620         PatternTerm* term = op.m_term;
1621
1622         const RegisterID countRegister = regT1;
1623
1624         m_backtrackingState.link(this);
1625
1626         loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), countRegister);
1627         m_backtrackingState.append(branchTest32(Zero, countRegister));
1628         sub32(TrustedImm32(1), countRegister);
1629         if (!m_decodeSurrogatePairs)
1630             sub32(TrustedImm32(1), index);
1631         else {
1632             const RegisterID character = regT0;
1633
1634             loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), index);
1635             // Rematch one less
1636             storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex());
1637
1638             Label rematchLoop(this);
1639             readCharacter(m_checkedOffset - term->inputPosition, character);
1640
1641             sub32(TrustedImm32(1), countRegister);
1642             add32(TrustedImm32(1), index);
1643
1644 #ifdef JIT_UNICODE_EXPRESSIONS
1645             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
1646             add32(TrustedImm32(1), index);
1647             isBMPChar.link(this);
1648 #endif
1649
1650             branchTest32(Zero, countRegister).linkTo(rematchLoop, this);
1651
1652             loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), countRegister);
1653         }
1654         jump(op.m_reentry);
1655     }
1656
1657     void generateCharacterClassNonGreedy(size_t opIndex)
1658     {
1659         YarrOp& op = m_ops[opIndex];
1660         PatternTerm* term = op.m_term;
1661
1662         const RegisterID countRegister = regT1;
1663
1664         move(TrustedImm32(0), countRegister);
1665         op.m_reentry = label();
1666         if (m_decodeSurrogatePairs)
1667             storeToFrame(index, term->frameLocation + BackTrackInfoCharacterClass::beginIndex());
1668         storeToFrame(countRegister, term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex());
1669     }
1670
1671     void backtrackCharacterClassNonGreedy(size_t opIndex)
1672     {
1673         YarrOp& op = m_ops[opIndex];
1674         PatternTerm* term = op.m_term;
1675
1676         const RegisterID character = regT0;
1677         const RegisterID countRegister = regT1;
1678
1679         JumpList nonGreedyFailures;
1680
1681         m_backtrackingState.link(this);
1682
1683         if (m_decodeSurrogatePairs)
1684             loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::beginIndex(), index);
1685         loadFromFrame(term->frameLocation + BackTrackInfoCharacterClass::matchAmountIndex(), countRegister);
1686
1687         nonGreedyFailures.append(atEndOfInput());
1688         nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityMaxCount.unsafeGet())));
1689
1690         JumpList matchDest;
1691         readCharacter(m_checkedOffset - term->inputPosition, character);
1692         // If we are matching the "any character" builtin class we only need to read the
1693         // character and don't need to match as it will always succeed.
1694         if (term->invert() || !term->characterClass->m_anyCharacter) {
1695             matchCharacterClass(character, matchDest, term->characterClass);
1696
1697             if (term->invert())
1698                 nonGreedyFailures.append(matchDest);
1699             else {
1700                 nonGreedyFailures.append(jump());
1701                 matchDest.link(this);
1702             }
1703         }
1704
1705         add32(TrustedImm32(1), index);
1706 #ifdef JIT_UNICODE_EXPRESSIONS
1707         if (m_decodeSurrogatePairs) {
1708             nonGreedyFailures.append(atEndOfInput());
1709             Jump isBMPChar = branch32(LessThan, character, supplementaryPlanesBase);
1710             add32(TrustedImm32(1), index);
1711             isBMPChar.link(this);
1712         }
1713 #endif
1714         add32(TrustedImm32(1), countRegister);
1715
1716         jump(op.m_reentry);
1717
1718         nonGreedyFailures.link(this);
1719         sub32(countRegister, index);
1720         m_backtrackingState.fallthrough();
1721     }
1722
1723     void generateDotStarEnclosure(size_t opIndex)
1724     {
1725         YarrOp& op = m_ops[opIndex];
1726         PatternTerm* term = op.m_term;
1727
1728         const RegisterID character = regT0;
1729         const RegisterID matchPos = regT1;
1730 #ifndef HAVE_INITIAL_START_REG
1731         const RegisterID initialStart = character;
1732 #endif
1733
1734         JumpList foundBeginningNewLine;
1735         JumpList saveStartIndex;
1736         JumpList foundEndingNewLine;
1737
1738         if (m_pattern.dotAll()) {
1739             move(TrustedImm32(0), matchPos);
1740             setMatchStart(matchPos);
1741             move(length, index);
1742             return;
1743         }
1744
1745         ASSERT(!m_pattern.m_body->m_hasFixedSize);
1746         getMatchStart(matchPos);
1747
1748 #ifndef HAVE_INITIAL_START_REG
1749         loadFromFrame(m_pattern.m_initialStartValueFrameLocation, initialStart);
1750 #endif
1751         saveStartIndex.append(branch32(BelowOrEqual, matchPos, initialStart));
1752         Label findBOLLoop(this);
1753         sub32(TrustedImm32(1), matchPos);
1754         if (m_charSize == Char8)
1755             load8(BaseIndex(input, matchPos, TimesOne, 0), character);
1756         else
1757             load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
1758         matchCharacterClass(character, foundBeginningNewLine, m_pattern.newlineCharacterClass());
1759
1760 #ifndef HAVE_INITIAL_START_REG
1761         loadFromFrame(m_pattern.m_initialStartValueFrameLocation, initialStart);
1762 #endif
1763         branch32(Above, matchPos, initialStart).linkTo(findBOLLoop, this);
1764         saveStartIndex.append(jump());
1765
1766         foundBeginningNewLine.link(this);
1767         add32(TrustedImm32(1), matchPos); // Advance past newline
1768         saveStartIndex.link(this);
1769
1770         if (!m_pattern.multiline() && term->anchors.bolAnchor)
1771             op.m_jumps.append(branchTest32(NonZero, matchPos));
1772
1773         ASSERT(!m_pattern.m_body->m_hasFixedSize);
1774         setMatchStart(matchPos);
1775
1776         move(index, matchPos);
1777
1778         Label findEOLLoop(this);        
1779         foundEndingNewLine.append(branch32(Equal, matchPos, length));
1780         if (m_charSize == Char8)
1781             load8(BaseIndex(input, matchPos, TimesOne, 0), character);
1782         else
1783             load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
1784         matchCharacterClass(character, foundEndingNewLine, m_pattern.newlineCharacterClass());
1785         add32(TrustedImm32(1), matchPos);
1786         jump(findEOLLoop);
1787
1788         foundEndingNewLine.link(this);
1789
1790         if (!m_pattern.multiline() && term->anchors.eolAnchor)
1791             op.m_jumps.append(branch32(NotEqual, matchPos, length));
1792
1793         move(matchPos, index);
1794     }
1795
1796     void backtrackDotStarEnclosure(size_t opIndex)
1797     {
1798         backtrackTermDefault(opIndex);
1799     }
1800     
1801     // Code generation/backtracking for simple terms
1802     // (pattern characters, character classes, and assertions).
1803     // These methods farm out work to the set of functions above.
1804     void generateTerm(size_t opIndex)
1805     {
1806         YarrOp& op = m_ops[opIndex];
1807         PatternTerm* term = op.m_term;
1808
1809         switch (term->type) {
1810         case PatternTerm::TypePatternCharacter:
1811             switch (term->quantityType) {
1812             case QuantifierFixedCount:
1813                 if (term->quantityMaxCount == 1)
1814                     generatePatternCharacterOnce(opIndex);
1815                 else
1816                     generatePatternCharacterFixed(opIndex);
1817                 break;
1818             case QuantifierGreedy:
1819                 generatePatternCharacterGreedy(opIndex);
1820                 break;
1821             case QuantifierNonGreedy:
1822                 generatePatternCharacterNonGreedy(opIndex);
1823                 break;
1824             }
1825             break;
1826
1827         case PatternTerm::TypeCharacterClass:
1828             switch (term->quantityType) {
1829             case QuantifierFixedCount:
1830                 if (term->quantityMaxCount == 1)
1831                     generateCharacterClassOnce(opIndex);
1832                 else
1833                     generateCharacterClassFixed(opIndex);
1834                 break;
1835             case QuantifierGreedy:
1836                 generateCharacterClassGreedy(opIndex);
1837                 break;
1838             case QuantifierNonGreedy:
1839                 generateCharacterClassNonGreedy(opIndex);
1840                 break;
1841             }
1842             break;
1843
1844         case PatternTerm::TypeAssertionBOL:
1845             generateAssertionBOL(opIndex);
1846             break;
1847
1848         case PatternTerm::TypeAssertionEOL:
1849             generateAssertionEOL(opIndex);
1850             break;
1851
1852         case PatternTerm::TypeAssertionWordBoundary:
1853             generateAssertionWordBoundary(opIndex);
1854             break;
1855
1856         case PatternTerm::TypeForwardReference:
1857             break;
1858
1859         case PatternTerm::TypeParenthesesSubpattern:
1860         case PatternTerm::TypeParentheticalAssertion:
1861             RELEASE_ASSERT_NOT_REACHED();
1862         case PatternTerm::TypeBackReference:
1863             m_failureReason = JITFailureReason::BackReference;
1864             break;
1865         case PatternTerm::TypeDotStarEnclosure:
1866             generateDotStarEnclosure(opIndex);
1867             break;
1868         }
1869     }
1870     void backtrackTerm(size_t opIndex)
1871     {
1872         YarrOp& op = m_ops[opIndex];
1873         PatternTerm* term = op.m_term;
1874
1875         switch (term->type) {
1876         case PatternTerm::TypePatternCharacter:
1877             switch (term->quantityType) {
1878             case QuantifierFixedCount:
1879                 if (term->quantityMaxCount == 1)
1880                     backtrackPatternCharacterOnce(opIndex);
1881                 else
1882                     backtrackPatternCharacterFixed(opIndex);
1883                 break;
1884             case QuantifierGreedy:
1885                 backtrackPatternCharacterGreedy(opIndex);
1886                 break;
1887             case QuantifierNonGreedy:
1888                 backtrackPatternCharacterNonGreedy(opIndex);
1889                 break;
1890             }
1891             break;
1892
1893         case PatternTerm::TypeCharacterClass:
1894             switch (term->quantityType) {
1895             case QuantifierFixedCount:
1896                 if (term->quantityMaxCount == 1)
1897                     backtrackCharacterClassOnce(opIndex);
1898                 else
1899                     backtrackCharacterClassFixed(opIndex);
1900                 break;
1901             case QuantifierGreedy:
1902                 backtrackCharacterClassGreedy(opIndex);
1903                 break;
1904             case QuantifierNonGreedy:
1905                 backtrackCharacterClassNonGreedy(opIndex);
1906                 break;
1907             }
1908             break;
1909
1910         case PatternTerm::TypeAssertionBOL:
1911             backtrackAssertionBOL(opIndex);
1912             break;
1913
1914         case PatternTerm::TypeAssertionEOL:
1915             backtrackAssertionEOL(opIndex);
1916             break;
1917
1918         case PatternTerm::TypeAssertionWordBoundary:
1919             backtrackAssertionWordBoundary(opIndex);
1920             break;
1921
1922         case PatternTerm::TypeForwardReference:
1923             break;
1924
1925         case PatternTerm::TypeParenthesesSubpattern:
1926         case PatternTerm::TypeParentheticalAssertion:
1927             RELEASE_ASSERT_NOT_REACHED();
1928
1929         case PatternTerm::TypeDotStarEnclosure:
1930             backtrackDotStarEnclosure(opIndex);
1931             break;
1932
1933         case PatternTerm::TypeBackReference:
1934             m_failureReason = JITFailureReason::BackReference;
1935             break;
1936         }
1937     }
1938
1939     void generate()
1940     {
1941         // Forwards generate the matching code.
1942         ASSERT(m_ops.size());
1943         size_t opIndex = 0;
1944
1945         do {
1946             if (m_disassembler)
1947                 m_disassembler->setForGenerate(opIndex, label());
1948
1949             YarrOp& op = m_ops[opIndex];
1950             switch (op.m_op) {
1951
1952             case OpTerm:
1953                 generateTerm(opIndex);
1954                 break;
1955
1956             // OpBodyAlternativeBegin/Next/End
1957             //
1958             // These nodes wrap the set of alternatives in the body of the regular expression.
1959             // There may be either one or two chains of OpBodyAlternative nodes, one representing
1960             // the 'once through' sequence of alternatives (if any exist), and one representing
1961             // the repeating alternatives (again, if any exist).
1962             //
1963             // Upon normal entry to the Begin alternative, we will check that input is available.
1964             // Reentry to the Begin alternative will take place after the check has taken place,
1965             // and will assume that the input position has already been progressed as appropriate.
1966             //
1967             // Entry to subsequent Next/End alternatives occurs when the prior alternative has
1968             // successfully completed a match - return a success state from JIT code.
1969             //
1970             // Next alternatives allow for reentry optimized to suit backtracking from its
1971             // preceding alternative. It expects the input position to still be set to a position
1972             // appropriate to its predecessor, and it will only perform an input check if the
1973             // predecessor had a minimum size less than its own.
1974             //
1975             // In the case 'once through' expressions, the End node will also have a reentry
1976             // point to jump to when the last alternative fails. Again, this expects the input
1977             // position to still reflect that expected by the prior alternative.
1978             case OpBodyAlternativeBegin: {
1979                 PatternAlternative* alternative = op.m_alternative;
1980
1981                 // Upon entry at the head of the set of alternatives, check if input is available
1982                 // to run the first alternative. (This progresses the input position).
1983                 op.m_jumps.append(jumpIfNoAvailableInput(alternative->m_minimumSize));
1984                 // We will reenter after the check, and assume the input position to have been
1985                 // set as appropriate to this alternative.
1986                 op.m_reentry = label();
1987
1988                 m_checkedOffset += alternative->m_minimumSize;
1989                 break;
1990             }
1991             case OpBodyAlternativeNext:
1992             case OpBodyAlternativeEnd: {
1993                 PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
1994                 PatternAlternative* alternative = op.m_alternative;
1995
1996                 // If we get here, the prior alternative matched - return success.
1997                 
1998                 // Adjust the stack pointer to remove the pattern's frame.
1999                 removeCallFrame();
2000
2001                 // Load appropriate values into the return register and the first output
2002                 // slot, and return. In the case of pattern with a fixed size, we will
2003                 // not have yet set the value in the first 
2004                 ASSERT(index != returnRegister);
2005                 if (m_pattern.m_body->m_hasFixedSize) {
2006                     move(index, returnRegister);
2007                     if (priorAlternative->m_minimumSize)
2008                         sub32(Imm32(priorAlternative->m_minimumSize), returnRegister);
2009                     if (compileMode == IncludeSubpatterns)
2010                         store32(returnRegister, output);
2011                 } else
2012                     getMatchStart(returnRegister);
2013                 if (compileMode == IncludeSubpatterns)
2014                     store32(index, Address(output, 4));
2015                 move(index, returnRegister2);
2016
2017                 generateReturn();
2018
2019                 // This is the divide between the tail of the prior alternative, above, and
2020                 // the head of the subsequent alternative, below.
2021
2022                 if (op.m_op == OpBodyAlternativeNext) {
2023                     // This is the reentry point for the Next alternative. We expect any code
2024                     // that jumps here to do so with the input position matching that of the
2025                     // PRIOR alteranative, and we will only check input availability if we
2026                     // need to progress it forwards.
2027                     op.m_reentry = label();
2028                     if (alternative->m_minimumSize > priorAlternative->m_minimumSize) {
2029                         add32(Imm32(alternative->m_minimumSize - priorAlternative->m_minimumSize), index);
2030                         op.m_jumps.append(jumpIfNoAvailableInput());
2031                     } else if (priorAlternative->m_minimumSize > alternative->m_minimumSize)
2032                         sub32(Imm32(priorAlternative->m_minimumSize - alternative->m_minimumSize), index);
2033                 } else if (op.m_nextOp == notFound) {
2034                     // This is the reentry point for the End of 'once through' alternatives,
2035                     // jumped to when the last alternative fails to match.
2036                     op.m_reentry = label();
2037                     sub32(Imm32(priorAlternative->m_minimumSize), index);
2038                 }
2039
2040                 if (op.m_op == OpBodyAlternativeNext)
2041                     m_checkedOffset += alternative->m_minimumSize;
2042                 m_checkedOffset -= priorAlternative->m_minimumSize;
2043                 break;
2044             }
2045
2046             // OpSimpleNestedAlternativeBegin/Next/End
2047             // OpNestedAlternativeBegin/Next/End
2048             //
2049             // These nodes are used to handle sets of alternatives that are nested within
2050             // subpatterns and parenthetical assertions. The 'simple' forms are used where
2051             // we do not need to be able to backtrack back into any alternative other than
2052             // the last, the normal forms allow backtracking into any alternative.
2053             //
2054             // Each Begin/Next node is responsible for planting an input check to ensure
2055             // sufficient input is available on entry. Next nodes additionally need to
2056             // jump to the end - Next nodes use the End node's m_jumps list to hold this
2057             // set of jumps.
2058             //
2059             // In the non-simple forms, successful alternative matches must store a
2060             // 'return address' using a DataLabelPtr, used to store the address to jump
2061             // to when backtracking, to get to the code for the appropriate alternative.
2062             case OpSimpleNestedAlternativeBegin:
2063             case OpNestedAlternativeBegin: {
2064                 PatternTerm* term = op.m_term;
2065                 PatternAlternative* alternative = op.m_alternative;
2066                 PatternDisjunction* disjunction = term->parentheses.disjunction;
2067
2068                 // Calculate how much input we need to check for, and if non-zero check.
2069                 op.m_checkAdjust = Checked<unsigned>(alternative->m_minimumSize);
2070                 if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
2071                     op.m_checkAdjust -= disjunction->m_minimumSize;
2072                 if (op.m_checkAdjust)
2073                     op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust.unsafeGet()));
2074
2075                 m_checkedOffset += op.m_checkAdjust;
2076                 break;
2077             }
2078             case OpSimpleNestedAlternativeNext:
2079             case OpNestedAlternativeNext: {
2080                 PatternTerm* term = op.m_term;
2081                 PatternAlternative* alternative = op.m_alternative;
2082                 PatternDisjunction* disjunction = term->parentheses.disjunction;
2083
2084                 // In the non-simple case, store a 'return address' so we can backtrack correctly.
2085                 if (op.m_op == OpNestedAlternativeNext) {
2086                     unsigned parenthesesFrameLocation = term->frameLocation;
2087                     op.m_returnAddress = storeToFrameWithPatch(parenthesesFrameLocation + BackTrackInfoParentheses::returnAddressIndex());
2088                 }
2089
2090                 if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) {
2091                     // If the previous alternative matched without consuming characters then
2092                     // backtrack to try to match while consumming some input.
2093                     op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
2094                 }
2095
2096                 // If we reach here then the last alternative has matched - jump to the
2097                 // End node, to skip over any further alternatives.
2098                 //
2099                 // FIXME: this is logically O(N^2) (though N can be expected to be very
2100                 // small). We could avoid this either by adding an extra jump to the JIT
2101                 // data structures, or by making backtracking code that jumps to Next
2102                 // alternatives are responsible for checking that input is available (if
2103                 // we didn't need to plant the input checks, then m_jumps would be free).
2104                 YarrOp* endOp = &m_ops[op.m_nextOp];
2105                 while (endOp->m_nextOp != notFound) {
2106                     ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
2107                     endOp = &m_ops[endOp->m_nextOp];
2108                 }
2109                 ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
2110                 endOp->m_jumps.append(jump());
2111
2112                 // This is the entry point for the next alternative.
2113                 op.m_reentry = label();
2114
2115                 // Calculate how much input we need to check for, and if non-zero check.
2116                 op.m_checkAdjust = alternative->m_minimumSize;
2117                 if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
2118                     op.m_checkAdjust -= disjunction->m_minimumSize;
2119                 if (op.m_checkAdjust)
2120                     op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust.unsafeGet()));
2121
2122                 YarrOp& lastOp = m_ops[op.m_previousOp];
2123                 m_checkedOffset -= lastOp.m_checkAdjust;
2124                 m_checkedOffset += op.m_checkAdjust;
2125                 break;
2126             }
2127             case OpSimpleNestedAlternativeEnd:
2128             case OpNestedAlternativeEnd: {
2129                 PatternTerm* term = op.m_term;
2130
2131                 // In the non-simple case, store a 'return address' so we can backtrack correctly.
2132                 if (op.m_op == OpNestedAlternativeEnd) {
2133                     unsigned parenthesesFrameLocation = term->frameLocation;
2134                     op.m_returnAddress = storeToFrameWithPatch(parenthesesFrameLocation + BackTrackInfoParentheses::returnAddressIndex());
2135                 }
2136
2137                 if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) {
2138                     // If the previous alternative matched without consuming characters then
2139                     // backtrack to try to match while consumming some input.
2140                     op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
2141                 }
2142
2143                 // If this set of alternatives contains more than one alternative,
2144                 // then the Next nodes will have planted jumps to the End, and added
2145                 // them to this node's m_jumps list.
2146                 op.m_jumps.link(this);
2147                 op.m_jumps.clear();
2148
2149                 YarrOp& lastOp = m_ops[op.m_previousOp];
2150                 m_checkedOffset -= lastOp.m_checkAdjust;
2151                 break;
2152             }
2153
2154             // OpParenthesesSubpatternOnceBegin/End
2155             //
2156             // These nodes support (optionally) capturing subpatterns, that have a
2157             // quantity count of 1 (this covers fixed once, and ?/?? quantifiers). 
2158             case OpParenthesesSubpatternOnceBegin: {
2159                 PatternTerm* term = op.m_term;
2160                 unsigned parenthesesFrameLocation = term->frameLocation;
2161                 const RegisterID indexTemporary = regT0;
2162                 ASSERT(term->quantityMaxCount == 1);
2163
2164                 // Upon entry to a Greedy quantified set of parenthese store the index.
2165                 // We'll use this for two purposes:
2166                 //  - To indicate which iteration we are on of mathing the remainder of
2167                 //    the expression after the parentheses - the first, including the
2168                 //    match within the parentheses, or the second having skipped over them.
2169                 //  - To check for empty matches, which must be rejected.
2170                 //
2171                 // At the head of a NonGreedy set of parentheses we'll immediately set the
2172                 // value on the stack to -1 (indicating a match skipping the subpattern),
2173                 // and plant a jump to the end. We'll also plant a label to backtrack to
2174                 // to reenter the subpattern later, with a store to set up index on the
2175                 // second iteration.
2176                 //
2177                 // FIXME: for capturing parens, could use the index in the capture array?
2178                 if (term->quantityType == QuantifierGreedy)
2179                     storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex());
2180                 else if (term->quantityType == QuantifierNonGreedy) {
2181                     storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex());
2182                     op.m_jumps.append(jump());
2183                     op.m_reentry = label();
2184                     storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex());
2185                 }
2186
2187                 // If the parenthese are capturing, store the starting index value to the
2188                 // captures array, offsetting as necessary.
2189                 //
2190                 // FIXME: could avoid offsetting this value in JIT code, apply
2191                 // offsets only afterwards, at the point the results array is
2192                 // being accessed.
2193                 if (term->capture() && compileMode == IncludeSubpatterns) {
2194                     unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet();
2195                     if (term->quantityType == QuantifierFixedCount)
2196                         inputOffset += term->parentheses.disjunction->m_minimumSize;
2197                     if (inputOffset) {
2198                         move(index, indexTemporary);
2199                         sub32(Imm32(inputOffset), indexTemporary);
2200                         setSubpatternStart(indexTemporary, term->parentheses.subpatternId);
2201                     } else
2202                         setSubpatternStart(index, term->parentheses.subpatternId);
2203                 }
2204                 break;
2205             }
2206             case OpParenthesesSubpatternOnceEnd: {
2207                 PatternTerm* term = op.m_term;
2208                 const RegisterID indexTemporary = regT0;
2209                 ASSERT(term->quantityMaxCount == 1);
2210
2211                 // Runtime ASSERT to make sure that the nested alternative handled the
2212                 // "no input consumed" check.
2213                 if (!ASSERT_DISABLED && term->quantityType != QuantifierFixedCount && !term->parentheses.disjunction->m_minimumSize) {
2214                     Jump pastBreakpoint;
2215                     pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
2216                     abortWithReason(YARRNoInputConsumed);
2217                     pastBreakpoint.link(this);
2218                 }
2219
2220                 // If the parenthese are capturing, store the ending index value to the
2221                 // captures array, offsetting as necessary.
2222                 //
2223                 // FIXME: could avoid offsetting this value in JIT code, apply
2224                 // offsets only afterwards, at the point the results array is
2225                 // being accessed.
2226                 if (term->capture() && compileMode == IncludeSubpatterns) {
2227                     unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet();
2228                     if (inputOffset) {
2229                         move(index, indexTemporary);
2230                         sub32(Imm32(inputOffset), indexTemporary);
2231                         setSubpatternEnd(indexTemporary, term->parentheses.subpatternId);
2232                     } else
2233                         setSubpatternEnd(index, term->parentheses.subpatternId);
2234                 }
2235
2236                 // If the parentheses are quantified Greedy then add a label to jump back
2237                 // to if get a failed match from after the parentheses. For NonGreedy
2238                 // parentheses, link the jump from before the subpattern to here.
2239                 if (term->quantityType == QuantifierGreedy)
2240                     op.m_reentry = label();
2241                 else if (term->quantityType == QuantifierNonGreedy) {
2242                     YarrOp& beginOp = m_ops[op.m_previousOp];
2243                     beginOp.m_jumps.link(this);
2244                 }
2245                 break;
2246             }
2247
2248             // OpParenthesesSubpatternTerminalBegin/End
2249             case OpParenthesesSubpatternTerminalBegin: {
2250                 PatternTerm* term = op.m_term;
2251                 ASSERT(term->quantityType == QuantifierGreedy);
2252                 ASSERT(term->quantityMaxCount == quantifyInfinite);
2253                 ASSERT(!term->capture());
2254
2255                 // Upon entry set a label to loop back to.
2256                 op.m_reentry = label();
2257
2258                 // Store the start index of the current match; we need to reject zero
2259                 // length matches.
2260                 storeToFrame(index, term->frameLocation + BackTrackInfoParenthesesTerminal::beginIndex());
2261                 break;
2262             }
2263             case OpParenthesesSubpatternTerminalEnd: {
2264                 YarrOp& beginOp = m_ops[op.m_previousOp];
2265                 if (!ASSERT_DISABLED) {
2266                     PatternTerm* term = op.m_term;
2267                     
2268                     // Runtime ASSERT to make sure that the nested alternative handled the
2269                     // "no input consumed" check.
2270                     Jump pastBreakpoint;
2271                     pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
2272                     abortWithReason(YARRNoInputConsumed);
2273                     pastBreakpoint.link(this);
2274                 }
2275
2276                 // We know that the match is non-zero, we can accept it and
2277                 // loop back up to the head of the subpattern.
2278                 jump(beginOp.m_reentry);
2279
2280                 // This is the entry point to jump to when we stop matching - we will
2281                 // do so once the subpattern cannot match any more.
2282                 op.m_reentry = label();
2283                 break;
2284             }
2285
2286             // OpParenthesesSubpatternBegin/End
2287             //
2288             // These nodes support generic subpatterns.
2289             case OpParenthesesSubpatternBegin: {
2290 #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)
2291                 PatternTerm* term = op.m_term;
2292                 unsigned parenthesesFrameLocation = term->frameLocation;
2293
2294                 // Upon entry to a Greedy quantified set of parenthese store the index.
2295                 // We'll use this for two purposes:
2296                 //  - To indicate which iteration we are on of mathing the remainder of
2297                 //    the expression after the parentheses - the first, including the
2298                 //    match within the parentheses, or the second having skipped over them.
2299                 //  - To check for empty matches, which must be rejected.
2300                 //
2301                 // At the head of a NonGreedy set of parentheses we'll immediately set the
2302                 // value on the stack to -1 (indicating a match skipping the subpattern),
2303                 // and plant a jump to the end. We'll also plant a label to backtrack to
2304                 // to reenter the subpattern later, with a store to set up index on the
2305                 // second iteration.
2306                 //
2307                 // FIXME: for capturing parens, could use the index in the capture array?
2308                 if (term->quantityType == QuantifierGreedy || term->quantityType == QuantifierNonGreedy) {
2309                     storeToFrame(TrustedImm32(0), parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex());
2310                     storeToFrame(TrustedImmPtr(nullptr), parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex());
2311
2312                     if (term->quantityType == QuantifierNonGreedy) {
2313                         storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex());
2314                         op.m_jumps.append(jump());
2315                     }
2316                     
2317                     op.m_reentry = label();
2318                     RegisterID currParenContextReg = regT0;
2319                     RegisterID newParenContextReg = regT1;
2320
2321                     loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex(), currParenContextReg);
2322                     allocateParenContext(newParenContextReg);
2323                     storePtr(currParenContextReg, newParenContextReg);
2324                     storeToFrame(newParenContextReg, parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex());
2325                     saveParenContext(newParenContextReg, regT2, term->parentheses.subpatternId, term->parentheses.lastSubpatternId, parenthesesFrameLocation);
2326                     storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex());
2327                 }
2328
2329                 // If the parenthese are capturing, store the starting index value to the
2330                 // captures array, offsetting as necessary.
2331                 //
2332                 // FIXME: could avoid offsetting this value in JIT code, apply
2333                 // offsets only afterwards, at the point the results array is
2334                 // being accessed.
2335                 if (term->capture() && compileMode == IncludeSubpatterns) {
2336                     const RegisterID indexTemporary = regT0;
2337                     unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet();
2338                     if (term->quantityType == QuantifierFixedCount)
2339                         inputOffset += term->parentheses.disjunction->m_minimumSize;
2340                     if (inputOffset) {
2341                         move(index, indexTemporary);
2342                         sub32(Imm32(inputOffset), indexTemporary);
2343                         setSubpatternStart(indexTemporary, term->parentheses.subpatternId);
2344                     } else
2345                         setSubpatternStart(index, term->parentheses.subpatternId);
2346                 }
2347 #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS
2348                 RELEASE_ASSERT_NOT_REACHED();
2349 #endif
2350                 break;
2351             }
2352             case OpParenthesesSubpatternEnd: {
2353 #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)
2354                 PatternTerm* term = op.m_term;
2355                 unsigned parenthesesFrameLocation = term->frameLocation;
2356
2357                 // Runtime ASSERT to make sure that the nested alternative handled the
2358                 // "no input consumed" check.
2359                 if (!ASSERT_DISABLED && term->quantityType != QuantifierFixedCount && !term->parentheses.disjunction->m_minimumSize) {
2360                     Jump pastBreakpoint;
2361                     pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, parenthesesFrameLocation * sizeof(void*)));
2362                     abortWithReason(YARRNoInputConsumed);
2363                     pastBreakpoint.link(this);
2364                 }
2365
2366                 const RegisterID countTemporary = regT1;
2367
2368                 YarrOp& beginOp = m_ops[op.m_previousOp];
2369                 loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), countTemporary);
2370                 add32(TrustedImm32(1), countTemporary);
2371                 storeToFrame(countTemporary, parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex());
2372
2373                 // If the parenthese are capturing, store the ending index value to the
2374                 // captures array, offsetting as necessary.
2375                 //
2376                 // FIXME: could avoid offsetting this value in JIT code, apply
2377                 // offsets only afterwards, at the point the results array is
2378                 // being accessed.
2379                 if (term->capture() && compileMode == IncludeSubpatterns) {
2380                     const RegisterID indexTemporary = regT0;
2381                     
2382                     unsigned inputOffset = (m_checkedOffset - term->inputPosition).unsafeGet();
2383                     if (inputOffset) {
2384                         move(index, indexTemporary);
2385                         sub32(Imm32(inputOffset), indexTemporary);
2386                         setSubpatternEnd(indexTemporary, term->parentheses.subpatternId);
2387                     } else
2388                         setSubpatternEnd(index, term->parentheses.subpatternId);
2389                 }
2390
2391                 // If the parentheses are quantified Greedy then add a label to jump back
2392                 // to if get a failed match from after the parentheses. For NonGreedy
2393                 // parentheses, link the jump from before the subpattern to here.
2394                 if (term->quantityType == QuantifierGreedy) {
2395                     if (term->quantityMaxCount != quantifyInfinite)
2396                         branch32(Below, countTemporary, Imm32(term->quantityMaxCount.unsafeGet())).linkTo(beginOp.m_reentry, this);
2397                     else
2398                         jump(beginOp.m_reentry);
2399                     
2400                     op.m_reentry = label();
2401                 } else if (term->quantityType == QuantifierNonGreedy) {
2402                     YarrOp& beginOp = m_ops[op.m_previousOp];
2403                     beginOp.m_jumps.link(this);
2404                 }
2405 #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS
2406                 RELEASE_ASSERT_NOT_REACHED();
2407 #endif
2408                 break;
2409             }
2410
2411             // OpParentheticalAssertionBegin/End
2412             case OpParentheticalAssertionBegin: {
2413                 PatternTerm* term = op.m_term;
2414
2415                 // Store the current index - assertions should not update index, so
2416                 // we will need to restore it upon a successful match.
2417                 unsigned parenthesesFrameLocation = term->frameLocation;
2418                 storeToFrame(index, parenthesesFrameLocation + BackTrackInfoParentheticalAssertion::beginIndex());
2419
2420                 // Check 
2421                 op.m_checkAdjust = m_checkedOffset - term->inputPosition;
2422                 if (op.m_checkAdjust)
2423                     sub32(Imm32(op.m_checkAdjust.unsafeGet()), index);
2424
2425                 m_checkedOffset -= op.m_checkAdjust;
2426                 break;
2427             }
2428             case OpParentheticalAssertionEnd: {
2429                 PatternTerm* term = op.m_term;
2430
2431                 // Restore the input index value.
2432                 unsigned parenthesesFrameLocation = term->frameLocation;
2433                 loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheticalAssertion::beginIndex(), index);
2434
2435                 // If inverted, a successful match of the assertion must be treated
2436                 // as a failure, so jump to backtracking.
2437                 if (term->invert()) {
2438                     op.m_jumps.append(jump());
2439                     op.m_reentry = label();
2440                 }
2441
2442                 YarrOp& lastOp = m_ops[op.m_previousOp];
2443                 m_checkedOffset += lastOp.m_checkAdjust;
2444                 break;
2445             }
2446
2447             case OpMatchFailed:
2448                 removeCallFrame();
2449                 generateFailReturn();
2450                 break;
2451             }
2452
2453             ++opIndex;
2454         } while (opIndex < m_ops.size());
2455     }
2456
2457     void backtrack()
2458     {
2459         // Backwards generate the backtracking code.
2460         size_t opIndex = m_ops.size();
2461         ASSERT(opIndex);
2462
2463         do {
2464             --opIndex;
2465
2466             if (m_disassembler)
2467                 m_disassembler->setForBacktrack(opIndex, label());
2468
2469             YarrOp& op = m_ops[opIndex];
2470             switch (op.m_op) {
2471
2472             case OpTerm:
2473                 backtrackTerm(opIndex);
2474                 break;
2475
2476             // OpBodyAlternativeBegin/Next/End
2477             //
2478             // For each Begin/Next node representing an alternative, we need to decide what to do
2479             // in two circumstances:
2480             //  - If we backtrack back into this node, from within the alternative.
2481             //  - If the input check at the head of the alternative fails (if this exists).
2482             //
2483             // We treat these two cases differently since in the former case we have slightly
2484             // more information - since we are backtracking out of a prior alternative we know
2485             // that at least enough input was available to run it. For example, given the regular
2486             // expression /a|b/, if we backtrack out of the first alternative (a failed pattern
2487             // character match of 'a'), then we need not perform an additional input availability
2488             // check before running the second alternative.
2489             //
2490             // Backtracking required differs for the last alternative, which in the case of the
2491             // repeating set of alternatives must loop. The code generated for the last alternative
2492             // will also be used to handle all input check failures from any prior alternatives -
2493             // these require similar functionality, in seeking the next available alternative for
2494             // which there is sufficient input.
2495             //
2496             // Since backtracking of all other alternatives simply requires us to link backtracks
2497             // to the reentry point for the subsequent alternative, we will only be generating any
2498             // code when backtracking the last alternative.
2499             case OpBodyAlternativeBegin:
2500             case OpBodyAlternativeNext: {
2501                 PatternAlternative* alternative = op.m_alternative;
2502
2503                 if (op.m_op == OpBodyAlternativeNext) {
2504                     PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
2505                     m_checkedOffset += priorAlternative->m_minimumSize;
2506                 }
2507                 m_checkedOffset -= alternative->m_minimumSize;
2508
2509                 // Is this the last alternative? If not, then if we backtrack to this point we just
2510                 // need to jump to try to match the next alternative.
2511                 if (m_ops[op.m_nextOp].m_op != OpBodyAlternativeEnd) {
2512                     m_backtrackingState.linkTo(m_ops[op.m_nextOp].m_reentry, this);
2513                     break;
2514                 }
2515                 YarrOp& endOp = m_ops[op.m_nextOp];
2516
2517                 YarrOp* beginOp = &op;
2518                 while (beginOp->m_op != OpBodyAlternativeBegin) {
2519                     ASSERT(beginOp->m_op == OpBodyAlternativeNext);
2520                     beginOp = &m_ops[beginOp->m_previousOp];
2521                 }
2522
2523                 bool onceThrough = endOp.m_nextOp == notFound;
2524                 
2525                 JumpList lastStickyAlternativeFailures;
2526
2527                 // First, generate code to handle cases where we backtrack out of an attempted match
2528                 // of the last alternative. If this is a 'once through' set of alternatives then we
2529                 // have nothing to do - link this straight through to the End.
2530                 if (onceThrough)
2531                     m_backtrackingState.linkTo(endOp.m_reentry, this);
2532                 else {
2533                     // If we don't need to move the input poistion, and the pattern has a fixed size
2534                     // (in which case we omit the store of the start index until the pattern has matched)
2535                     // then we can just link the backtrack out of the last alternative straight to the
2536                     // head of the first alternative.
2537                     if (m_pattern.m_body->m_hasFixedSize
2538                         && (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize)
2539                         && (alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize == 1))
2540                         m_backtrackingState.linkTo(beginOp->m_reentry, this);
2541                     else if (m_pattern.sticky() && m_ops[op.m_nextOp].m_op == OpBodyAlternativeEnd) {
2542                         // It is a sticky pattern and the last alternative failed, jump to the end.
2543                         m_backtrackingState.takeBacktracksToJumpList(lastStickyAlternativeFailures, this);
2544                     } else {
2545                         // We need to generate a trampoline of code to execute before looping back
2546                         // around to the first alternative.
2547                         m_backtrackingState.link(this);
2548
2549                         // No need to advance and retry for a sticky pattern.
2550                         if (!m_pattern.sticky()) {
2551                             // If the pattern size is not fixed, then store the start index for use if we match.
2552                             if (!m_pattern.m_body->m_hasFixedSize) {
2553                                 if (alternative->m_minimumSize == 1)
2554                                     setMatchStart(index);
2555                                 else {
2556                                     move(index, regT0);
2557                                     if (alternative->m_minimumSize)
2558                                         sub32(Imm32(alternative->m_minimumSize - 1), regT0);
2559                                     else
2560                                         add32(TrustedImm32(1), regT0);
2561                                     setMatchStart(regT0);
2562                                 }
2563                             }
2564
2565                             // Generate code to loop. Check whether the last alternative is longer than the
2566                             // first (e.g. /a|xy/ or /a|xyz/).
2567                             if (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize) {
2568                                 // We want to loop, and increment input position. If the delta is 1, it is
2569                                 // already correctly incremented, if more than one then decrement as appropriate.
2570                                 unsigned delta = alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize;
2571                                 ASSERT(delta);
2572                                 if (delta != 1)
2573                                     sub32(Imm32(delta - 1), index);
2574                                 jump(beginOp->m_reentry);
2575                             } else {
2576                                 // If the first alternative has minimum size 0xFFFFFFFFu, then there cannot
2577                                 // be sufficent input available to handle this, so just fall through.
2578                                 unsigned delta = beginOp->m_alternative->m_minimumSize - alternative->m_minimumSize;
2579                                 if (delta != 0xFFFFFFFFu) {
2580                                     // We need to check input because we are incrementing the input.
2581                                     add32(Imm32(delta + 1), index);
2582                                     checkInput().linkTo(beginOp->m_reentry, this);
2583                                 }
2584                             }
2585                         }
2586                     }
2587                 }
2588
2589                 // We can reach this point in the code in two ways:
2590                 //  - Fallthrough from the code above (a repeating alternative backtracked out of its
2591                 //    last alternative, and did not have sufficent input to run the first).
2592                 //  - We will loop back up to the following label when a repeating alternative loops,
2593                 //    following a failed input check.
2594                 //
2595                 // Either way, we have just failed the input check for the first alternative.
2596                 Label firstInputCheckFailed(this);
2597
2598                 // Generate code to handle input check failures from alternatives except the last.
2599                 // prevOp is the alternative we're handling a bail out from (initially Begin), and
2600                 // nextOp is the alternative we will be attempting to reenter into.
2601                 // 
2602                 // We will link input check failures from the forwards matching path back to the code
2603                 // that can handle them.
2604                 YarrOp* prevOp = beginOp;
2605                 YarrOp* nextOp = &m_ops[beginOp->m_nextOp];
2606                 while (nextOp->m_op != OpBodyAlternativeEnd) {
2607                     prevOp->m_jumps.link(this);
2608
2609                     // We only get here if an input check fails, it is only worth checking again
2610                     // if the next alternative has a minimum size less than the last.
2611                     if (prevOp->m_alternative->m_minimumSize > nextOp->m_alternative->m_minimumSize) {
2612                         // FIXME: if we added an extra label to YarrOp, we could avoid needing to
2613                         // subtract delta back out, and reduce this code. Should performance test
2614                         // the benefit of this.
2615                         unsigned delta = prevOp->m_alternative->m_minimumSize - nextOp->m_alternative->m_minimumSize;
2616                         sub32(Imm32(delta), index);
2617                         Jump fail = jumpIfNoAvailableInput();
2618                         add32(Imm32(delta), index);
2619                         jump(nextOp->m_reentry);
2620                         fail.link(this);
2621                     } else if (prevOp->m_alternative->m_minimumSize < nextOp->m_alternative->m_minimumSize)
2622                         add32(Imm32(nextOp->m_alternative->m_minimumSize - prevOp->m_alternative->m_minimumSize), index);
2623                     prevOp = nextOp;
2624                     nextOp = &m_ops[nextOp->m_nextOp];
2625                 }
2626
2627                 // We fall through to here if there is insufficient input to run the last alternative.
2628
2629                 // If there is insufficient input to run the last alternative, then for 'once through'
2630                 // alternatives we are done - just jump back up into the forwards matching path at the End.
2631                 if (onceThrough) {
2632                     op.m_jumps.linkTo(endOp.m_reentry, this);
2633                     jump(endOp.m_reentry);
2634                     break;
2635                 }
2636
2637                 // For repeating alternatives, link any input check failure from the last alternative to
2638                 // this point.
2639                 op.m_jumps.link(this);
2640
2641                 bool needsToUpdateMatchStart = !m_pattern.m_body->m_hasFixedSize;
2642
2643                 // Check for cases where input position is already incremented by 1 for the last
2644                 // alternative (this is particularly useful where the minimum size of the body
2645                 // disjunction is 0, e.g. /a*|b/).
2646                 if (needsToUpdateMatchStart && alternative->m_minimumSize == 1) {
2647                     // index is already incremented by 1, so just store it now!
2648                     setMatchStart(index);
2649                     needsToUpdateMatchStart = false;
2650                 }
2651
2652                 if (!m_pattern.sticky()) {
2653                     // Check whether there is sufficient input to loop. Increment the input position by
2654                     // one, and check. Also add in the minimum disjunction size before checking - there
2655                     // is no point in looping if we're just going to fail all the input checks around
2656                     // the next iteration.
2657                     ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize);
2658                     if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) {
2659                         // If the last alternative had the same minimum size as the disjunction,
2660                         // just simply increment input pos by 1, no adjustment based on minimum size.
2661                         add32(TrustedImm32(1), index);
2662                     } else {
2663                         // If the minumum for the last alternative was one greater than than that
2664                         // for the disjunction, we're already progressed by 1, nothing to do!
2665                         unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1;
2666                         if (delta)
2667                             sub32(Imm32(delta), index);
2668                     }
2669                     Jump matchFailed = jumpIfNoAvailableInput();
2670
2671                     if (needsToUpdateMatchStart) {
2672                         if (!m_pattern.m_body->m_minimumSize)
2673                             setMatchStart(index);
2674                         else {
2675                             move(index, regT0);
2676                             sub32(Imm32(m_pattern.m_body->m_minimumSize), regT0);
2677                             setMatchStart(regT0);
2678                         }
2679                     }
2680
2681                     // Calculate how much more input the first alternative requires than the minimum
2682                     // for the body as a whole. If no more is needed then we dont need an additional
2683                     // input check here - jump straight back up to the start of the first alternative.
2684                     if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize)
2685                         jump(beginOp->m_reentry);
2686                     else {
2687                         if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize)
2688                             add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index);
2689                         else
2690                             sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index);
2691                         checkInput().linkTo(beginOp->m_reentry, this);
2692                         jump(firstInputCheckFailed);
2693                     }
2694
2695                     // We jump to here if we iterate to the point that there is insufficient input to
2696                     // run any matches, and need to return a failure state from JIT code.
2697                     matchFailed.link(this);
2698                 }
2699
2700                 lastStickyAlternativeFailures.link(this);
2701                 removeCallFrame();
2702                 generateFailReturn();
2703                 break;
2704             }
2705             case OpBodyAlternativeEnd: {
2706                 // We should never backtrack back into a body disjunction.
2707                 ASSERT(m_backtrackingState.isEmpty());
2708
2709                 PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
2710                 m_checkedOffset += priorAlternative->m_minimumSize;
2711                 break;
2712             }
2713
2714             // OpSimpleNestedAlternativeBegin/Next/End
2715             // OpNestedAlternativeBegin/Next/End
2716             //
2717             // Generate code for when we backtrack back out of an alternative into
2718             // a Begin or Next node, or when the entry input count check fails. If
2719             // there are more alternatives we need to jump to the next alternative,
2720             // if not we backtrack back out of the current set of parentheses.
2721             //
2722             // In the case of non-simple nested assertions we need to also link the
2723             // 'return address' appropriately to backtrack back out into the correct
2724             // alternative.
2725             case OpSimpleNestedAlternativeBegin:
2726             case OpSimpleNestedAlternativeNext:
2727             case OpNestedAlternativeBegin:
2728             case OpNestedAlternativeNext: {
2729                 YarrOp& nextOp = m_ops[op.m_nextOp];
2730                 bool isBegin = op.m_previousOp == notFound;
2731                 bool isLastAlternative = nextOp.m_nextOp == notFound;
2732                 ASSERT(isBegin == (op.m_op == OpSimpleNestedAlternativeBegin || op.m_op == OpNestedAlternativeBegin));
2733                 ASSERT(isLastAlternative == (nextOp.m_op == OpSimpleNestedAlternativeEnd || nextOp.m_op == OpNestedAlternativeEnd));
2734
2735                 // Treat an input check failure the same as a failed match.
2736                 m_backtrackingState.append(op.m_jumps);
2737
2738                 // Set the backtracks to jump to the appropriate place. We may need
2739                 // to link the backtracks in one of three different way depending on
2740                 // the type of alternative we are dealing with:
2741                 //  - A single alternative, with no simplings.
2742                 //  - The last alternative of a set of two or more.
2743                 //  - An alternative other than the last of a set of two or more.
2744                 //
2745                 // In the case of a single alternative on its own, we don't need to
2746                 // jump anywhere - if the alternative fails to match we can just
2747                 // continue to backtrack out of the parentheses without jumping.
2748                 //
2749                 // In the case of the last alternative in a set of more than one, we
2750                 // need to jump to return back out to the beginning. We'll do so by
2751                 // adding a jump to the End node's m_jumps list, and linking this
2752                 // when we come to generate the Begin node. For alternatives other
2753                 // than the last, we need to jump to the next alternative.
2754                 //
2755                 // If the alternative had adjusted the input position we must link
2756                 // backtracking to here, correct, and then jump on. If not we can
2757                 // link the backtracks directly to their destination.
2758                 if (op.m_checkAdjust) {
2759                     // Handle the cases where we need to link the backtracks here.
2760                     m_backtrackingState.link(this);
2761                     sub32(Imm32(op.m_checkAdjust.unsafeGet()), index);
2762                     if (!isLastAlternative) {
2763                         // An alternative that is not the last should jump to its successor.
2764                         jump(nextOp.m_reentry);
2765                     } else if (!isBegin) {
2766                         // The last of more than one alternatives must jump back to the beginning.
2767                         nextOp.m_jumps.append(jump());
2768                     } else {
2769                         // A single alternative on its own can fall through.
2770                         m_backtrackingState.fallthrough();
2771                     }
2772                 } else {
2773                     // Handle the cases where we can link the backtracks directly to their destinations.
2774                     if (!isLastAlternative) {
2775                         // An alternative that is not the last should jump to its successor.
2776                         m_backtrackingState.linkTo(nextOp.m_reentry, this);
2777                     } else if (!isBegin) {
2778                         // The last of more than one alternatives must jump back to the beginning.
2779                         m_backtrackingState.takeBacktracksToJumpList(nextOp.m_jumps, this);
2780                     }
2781                     // In the case of a single alternative on its own do nothing - it can fall through.
2782                 }
2783
2784                 // If there is a backtrack jump from a zero length match link it here.
2785                 if (op.m_zeroLengthMatch.isSet())
2786                     m_backtrackingState.append(op.m_zeroLengthMatch);
2787
2788                 // At this point we've handled the backtracking back into this node.
2789                 // Now link any backtracks that need to jump to here.
2790
2791                 // For non-simple alternatives, link the alternative's 'return address'
2792                 // so that we backtrack back out into the previous alternative.
2793                 if (op.m_op == OpNestedAlternativeNext)
2794                     m_backtrackingState.append(op.m_returnAddress);
2795
2796                 // If there is more than one alternative, then the last alternative will
2797                 // have planted a jump to be linked to the end. This jump was added to the
2798                 // End node's m_jumps list. If we are back at the beginning, link it here.
2799                 if (isBegin) {
2800                     YarrOp* endOp = &m_ops[op.m_nextOp];
2801                     while (endOp->m_nextOp != notFound) {
2802                         ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
2803                         endOp = &m_ops[endOp->m_nextOp];
2804                     }
2805                     ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
2806                     m_backtrackingState.append(endOp->m_jumps);
2807                 }
2808
2809                 if (!isBegin) {
2810                     YarrOp& lastOp = m_ops[op.m_previousOp];
2811                     m_checkedOffset += lastOp.m_checkAdjust;
2812                 }
2813                 m_checkedOffset -= op.m_checkAdjust;
2814                 break;
2815             }
2816             case OpSimpleNestedAlternativeEnd:
2817             case OpNestedAlternativeEnd: {
2818                 PatternTerm* term = op.m_term;
2819
2820                 // If there is a backtrack jump from a zero length match link it here.
2821                 if (op.m_zeroLengthMatch.isSet())
2822                     m_backtrackingState.append(op.m_zeroLengthMatch);
2823
2824                 // If we backtrack into the end of a simple subpattern do nothing;
2825                 // just continue through into the last alternative. If we backtrack
2826                 // into the end of a non-simple set of alterntives we need to jump
2827                 // to the backtracking return address set up during generation.
2828                 if (op.m_op == OpNestedAlternativeEnd) {
2829                     m_backtrackingState.link(this);
2830
2831                     // Plant a jump to the return address.
2832                     unsigned parenthesesFrameLocation = term->frameLocation;
2833                     loadFromFrameAndJump(parenthesesFrameLocation + BackTrackInfoParentheses::returnAddressIndex());
2834
2835                     // Link the DataLabelPtr associated with the end of the last
2836                     // alternative to this point.
2837                     m_backtrackingState.append(op.m_returnAddress);
2838                 }
2839
2840                 YarrOp& lastOp = m_ops[op.m_previousOp];
2841                 m_checkedOffset += lastOp.m_checkAdjust;
2842                 break;
2843             }
2844
2845             // OpParenthesesSubpatternOnceBegin/End
2846             //
2847             // When we are backtracking back out of a capturing subpattern we need
2848             // to clear the start index in the matches output array, to record that
2849             // this subpattern has not been captured.
2850             //
2851             // When backtracking back out of a Greedy quantified subpattern we need
2852             // to catch this, and try running the remainder of the alternative after
2853             // the subpattern again, skipping the parentheses.
2854             //
2855             // Upon backtracking back into a quantified set of parentheses we need to
2856             // check whether we were currently skipping the subpattern. If not, we
2857             // can backtrack into them, if we were we need to either backtrack back
2858             // out of the start of the parentheses, or jump back to the forwards
2859             // matching start, depending of whether the match is Greedy or NonGreedy.
2860             case OpParenthesesSubpatternOnceBegin: {
2861                 PatternTerm* term = op.m_term;
2862                 ASSERT(term->quantityMaxCount == 1);
2863
2864                 // We only need to backtrack to this point if capturing or greedy.
2865                 if ((term->capture() && compileMode == IncludeSubpatterns) || term->quantityType == QuantifierGreedy) {
2866                     m_backtrackingState.link(this);
2867
2868                     // If capturing, clear the capture (we only need to reset start).
2869                     if (term->capture() && compileMode == IncludeSubpatterns)
2870                         clearSubpatternStart(term->parentheses.subpatternId);
2871
2872                     // If Greedy, jump to the end.
2873                     if (term->quantityType == QuantifierGreedy) {
2874                         // Clear the flag in the stackframe indicating we ran through the subpattern.
2875                         unsigned parenthesesFrameLocation = term->frameLocation;
2876                         storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex());
2877                         // Jump to after the parentheses, skipping the subpattern.
2878                         jump(m_ops[op.m_nextOp].m_reentry);
2879                         // A backtrack from after the parentheses, when skipping the subpattern,
2880                         // will jump back to here.
2881                         op.m_jumps.link(this);
2882                     }
2883
2884                     m_backtrackingState.fallthrough();
2885                 }
2886                 break;
2887             }
2888             case OpParenthesesSubpatternOnceEnd: {
2889                 PatternTerm* term = op.m_term;
2890
2891                 if (term->quantityType != QuantifierFixedCount) {
2892                     m_backtrackingState.link(this);
2893
2894                     // Check whether we should backtrack back into the parentheses, or if we
2895                     // are currently in a state where we had skipped over the subpattern
2896                     // (in which case the flag value on the stack will be -1).
2897                     unsigned parenthesesFrameLocation = term->frameLocation;
2898                     Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, (parenthesesFrameLocation + BackTrackInfoParenthesesOnce::beginIndex()) * sizeof(void*)), TrustedImm32(-1));
2899
2900                     if (term->quantityType == QuantifierGreedy) {
2901                         // For Greedy parentheses, we skip after having already tried going
2902                         // through the subpattern, so if we get here we're done.
2903                         YarrOp& beginOp = m_ops[op.m_previousOp];
2904                         beginOp.m_jumps.append(hadSkipped);
2905                     } else {
2906                         // For NonGreedy parentheses, we try skipping the subpattern first,
2907                         // so if we get here we need to try running through the subpattern
2908                         // next. Jump back to the start of the parentheses in the forwards
2909                         // matching path.
2910                         ASSERT(term->quantityType == QuantifierNonGreedy);
2911                         YarrOp& beginOp = m_ops[op.m_previousOp];
2912                         hadSkipped.linkTo(beginOp.m_reentry, this);
2913                     }
2914
2915                     m_backtrackingState.fallthrough();
2916                 }
2917
2918                 m_backtrackingState.append(op.m_jumps);
2919                 break;
2920             }
2921
2922             // OpParenthesesSubpatternTerminalBegin/End
2923             //
2924             // Terminal subpatterns will always match - there is nothing after them to
2925             // force a backtrack, and they have a minimum count of 0, and as such will
2926             // always produce an acceptable result.
2927             case OpParenthesesSubpatternTerminalBegin: {
2928                 // We will backtrack to this point once the subpattern cannot match any
2929                 // more. Since no match is accepted as a successful match (we are Greedy
2930                 // quantified with a minimum of zero) jump back to the forwards matching
2931                 // path at the end.
2932                 YarrOp& endOp = m_ops[op.m_nextOp];
2933                 m_backtrackingState.linkTo(endOp.m_reentry, this);
2934                 break;
2935             }
2936             case OpParenthesesSubpatternTerminalEnd:
2937                 // We should never be backtracking to here (hence the 'terminal' in the name).
2938                 ASSERT(m_backtrackingState.isEmpty());
2939                 m_backtrackingState.append(op.m_jumps);
2940                 break;
2941
2942             // OpParenthesesSubpatternBegin/End
2943             //
2944             // When we are backtracking back out of a capturing subpattern we need
2945             // to clear the start index in the matches output array, to record that
2946             // this subpattern has not been captured.
2947             //
2948             // When backtracking back out of a Greedy quantified subpattern we need
2949             // to catch this, and try running the remainder of the alternative after
2950             // the subpattern again, skipping the parentheses.
2951             //
2952             // Upon backtracking back into a quantified set of parentheses we need to
2953             // check whether we were currently skipping the subpattern. If not, we
2954             // can backtrack into them, if we were we need to either backtrack back
2955             // out of the start of the parentheses, or jump back to the forwards
2956             // matching start, depending of whether the match is Greedy or NonGreedy.
2957             case OpParenthesesSubpatternBegin: {
2958 #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)
2959                 PatternTerm* term = op.m_term;
2960                 unsigned parenthesesFrameLocation = term->frameLocation;
2961
2962                 if (term->quantityType != QuantifierFixedCount) {
2963                     m_backtrackingState.link(this);
2964
2965                     if (term->quantityType == QuantifierGreedy) {
2966                         RegisterID currParenContextReg = regT0;
2967                         RegisterID newParenContextReg = regT1;
2968
2969                         loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex(), currParenContextReg);
2970
2971                         restoreParenContext(currParenContextReg, regT2, term->parentheses.subpatternId, term->parentheses.lastSubpatternId, parenthesesFrameLocation);
2972
2973                         freeParenContext(currParenContextReg, newParenContextReg);
2974                         storeToFrame(newParenContextReg, parenthesesFrameLocation + BackTrackInfoParentheses::parenContextHeadIndex());
2975                         const RegisterID countTemporary = regT0;
2976                         loadFromFrame(parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex(), countTemporary);
2977                         Jump zeroLengthMatch = branchTest32(Zero, countTemporary);
2978
2979                         sub32(TrustedImm32(1), countTemporary);
2980                         storeToFrame(countTemporary, parenthesesFrameLocation + BackTrackInfoParentheses::matchAmountIndex());
2981
2982                         jump(m_ops[op.m_nextOp].m_reentry);
2983
2984                         zeroLengthMatch.link(this);
2985
2986                         // Clear the flag in the stackframe indicating we didn't run through the subpattern.
2987                         storeToFrame(TrustedImm32(-1), parenthesesFrameLocation + BackTrackInfoParentheses::beginIndex());
2988
2989                         jump(m_ops[op.m_nextOp].m_reentry);
2990                     }
2991
2992                     // If Greedy, jump to the end.
2993                     if (term->quantityType == QuantifierGreedy) {
2994                         // A backtrack from after the parentheses, when skipping the subpattern,
2995                         // will jump back to here.
2996                         op.m_jumps.link(this);
2997                     }
2998
2999                     m_backtrackingState.fallthrough();
3000                 }
3001 #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS
3002                 RELEASE_ASSERT_NOT_REACHED();
3003 #endif
3004                 break;
3005             }
3006             case OpParenthesesSubpatternEnd: {
3007 #if ENABLE(YARR_JIT_ALL_PARENS_EXPRESSIONS)
3008                 PatternTerm* term = op.m_term;
3009
3010                 if (term->quantityType != QuantifierFixedCount) {
3011                     m_backtrackingState.link(this);
3012
3013                     // Check whether we should backtrack back into the parentheses, or if we
3014                     // are currently in a state where we had skipped over the subpattern
3015                     // (in which case the flag value on the stack will be -1).
3016                     unsigned parenthesesFrameLocation = term->frameLocation;
3017                     Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, (parenthesesFrameLocation  + BackTrackInfoParentheses::beginIndex()) * sizeof(void*)), TrustedImm32(-1));
3018
3019                     if (term->quantityType == QuantifierGreedy) {
3020                         // For Greedy parentheses, we skip after having already tried going
3021                         // through the subpattern, so if we get here we're done.
3022                         YarrOp& beginOp = m_ops[op.m_previousOp];
3023                         beginOp.m_jumps.append(hadSkipped);
3024                     } else {
3025                         // For NonGreedy parentheses, we try skipping the subpattern first,
3026                         // so if we get here we need to try running through the subpattern
3027                         // next. Jump back to the start of the parentheses in the forwards
3028                         // matching path.
3029                         ASSERT(term->quantityType == QuantifierNonGreedy);
3030                         YarrOp& beginOp = m_ops[op.m_previousOp];
3031                         hadSkipped.linkTo(beginOp.m_reentry, this);
3032                     }
3033
3034                     m_backtrackingState.fallthrough();
3035                 }
3036
3037                 m_backtrackingState.append(op.m_jumps);
3038 #else // !YARR_JIT_ALL_PARENS_EXPRESSIONS
3039                 RELEASE_ASSERT_NOT_REACHED();
3040 #endif
3041                 break;
3042             }
3043
3044             // OpParentheticalAssertionBegin/End
3045             case OpParentheticalAssertionBegin: {
3046    &nb