The Tor Browser: js/src/yarr/YarrJIT.cpp@6474c204b198 (annotated)

js/src/yarr/YarrJIT.cpp@6474c204b198 (annotated)

js/src/yarr/YarrJIT.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  *
  * Copyright (C) 2009 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 #include "yarr/YarrJIT.h"
 #include "assembler/assembler/LinkBuffer.h"
 #include "yarr/Yarr.h"
 #include "yarr/YarrCanonicalizeUCS2.h"
 #if ENABLE_YARR_JIT
 using namespace WTF;
 namespace JSC { namespace Yarr {
 template<YarrJITCompileMode compileMode>
 class YarrGenerator : private MacroAssembler {
     friend void jitCompile(JSGlobalData*, YarrCodeBlock& jitObject, const String& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline);
 #if WTF_CPU_ARM
     static const RegisterID input = ARMRegisters::r0;
     static const RegisterID index = ARMRegisters::r1;
     static const RegisterID length = ARMRegisters::r2;
     static const RegisterID output = ARMRegisters::r4;
     static const RegisterID regT0 = ARMRegisters::r5;
     static const RegisterID regT1 = ARMRegisters::r6;
     static const RegisterID returnRegister = ARMRegisters::r0;
     static const RegisterID returnRegister2 = ARMRegisters::r1;
 #elif WTF_CPU_MIPS
     static const RegisterID input = MIPSRegisters::a0;
     static const RegisterID index = MIPSRegisters::a1;
     static const RegisterID length = MIPSRegisters::a2;
     static const RegisterID output = MIPSRegisters::a3;
     static const RegisterID regT0 = MIPSRegisters::t4;
     static const RegisterID regT1 = MIPSRegisters::t5;
     static const RegisterID returnRegister = MIPSRegisters::v0;
     static const RegisterID returnRegister2 = MIPSRegisters::v1;
 #elif WTF_CPU_SH4
     static const RegisterID input = SH4Registers::r4;
     static const RegisterID index = SH4Registers::r5;
     static const RegisterID length = SH4Registers::r6;
     static const RegisterID output = SH4Registers::r7;
     static const RegisterID regT0 = SH4Registers::r0;
     static const RegisterID regT1 = SH4Registers::r1;
     static const RegisterID returnRegister = SH4Registers::r0;
     static const RegisterID returnRegister2 = SH4Registers::r1;
 #elif WTF_CPU_SPARC
     static const RegisterID input = SparcRegisters::i0;
     static const RegisterID index = SparcRegisters::i1;
     static const RegisterID length = SparcRegisters::i2;
     static const RegisterID output = SparcRegisters::i3;
     static const RegisterID regT0 = SparcRegisters::i4;
     static const RegisterID regT1 = SparcRegisters::i5;
     static const RegisterID returnRegister = SparcRegisters::i0;
 #elif WTF_CPU_X86
     static const RegisterID input = X86Registers::eax;
     static const RegisterID index = X86Registers::edx;
     static const RegisterID length = X86Registers::ecx;
     static const RegisterID output = X86Registers::edi;
     static const RegisterID regT0 = X86Registers::ebx;
     static const RegisterID regT1 = X86Registers::esi;
     static const RegisterID returnRegister = X86Registers::eax;
     static const RegisterID returnRegister2 = X86Registers::edx;
 #elif WTF_CPU_X86_64
 # if WTF_PLATFORM_WIN
     static const RegisterID input = X86Registers::ecx;
     static const RegisterID index = X86Registers::edx;
     static const RegisterID length = X86Registers::r8;
     static const RegisterID output = X86Registers::r9;
 # else
     static const RegisterID input = X86Registers::edi;
     static const RegisterID index = X86Registers::esi;
     static const RegisterID length = X86Registers::edx;
     static const RegisterID output = X86Registers::ecx;
 # endif
     static const RegisterID regT0 = X86Registers::eax;
     static const RegisterID regT1 = X86Registers::ebx;
     static const RegisterID returnRegister = X86Registers::eax;
 # if !WTF_PLATFORM_WIN
     // no way to use int128_t as return value on Win64 ABI
     static const RegisterID returnRegister2 = X86Registers::edx;
 # endif
 #endif
     void optimizeAlternative(PatternAlternative* alternative)
     {
         if (!alternative->m_terms.size())
             return;
         for (unsigned i = 0; i < alternative->m_terms.size() - 1; ++i) {
             PatternTerm& term = alternative->m_terms[i];
             PatternTerm& nextTerm = alternative->m_terms[i + 1];
             if ((term.type == PatternTerm::TypeCharacterClass)
                 && (term.quantityType == QuantifierFixedCount)
                 && (nextTerm.type == PatternTerm::TypePatternCharacter)
                 && (nextTerm.quantityType == QuantifierFixedCount)) {
                 PatternTerm termCopy = term;
                 alternative->m_terms[i] = nextTerm;
                 alternative->m_terms[i + 1] = termCopy;
             }
         }
     }
     void matchCharacterClassRange(RegisterID character, JumpList& failures, JumpList& matchDest, const CharacterRange* ranges, unsigned count, unsigned* matchIndex, const UChar* matches, unsigned matchCount)
     {
         do {
             // pick which range we're going to generate
             int which = count >> 1;
             char lo = ranges[which].begin;
             char hi = ranges[which].end;
             // check if there are any ranges or matches below lo.  If not, just jl to failure -
             // if there is anything else to check, check that first, if it falls through jmp to failure.
             if ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
                 // generate code for all ranges before this one
                 if (which)
                     matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
                 while ((*matchIndex < matchCount) && (matches[*matchIndex] < lo)) {
                     matchDest.append(branch32(Equal, character, Imm32((unsigned short)matches[*matchIndex])));
                     ++*matchIndex;
                 }
                 failures.append(jump());
                 loOrAbove.link(this);
             } else if (which) {
                 Jump loOrAbove = branch32(GreaterThanOrEqual, character, Imm32((unsigned short)lo));
                 matchCharacterClassRange(character, failures, matchDest, ranges, which, matchIndex, matches, matchCount);
                 failures.append(jump());
                 loOrAbove.link(this);
             } else
                 failures.append(branch32(LessThan, character, Imm32((unsigned short)lo)));
             while ((*matchIndex < matchCount) && (matches[*matchIndex] <= hi))
                 ++*matchIndex;
             matchDest.append(branch32(LessThanOrEqual, character, Imm32((unsigned short)hi)));
             // fall through to here, the value is above hi.
             // shuffle along & loop around if there are any more matches to handle.
             unsigned next = which + 1;
             ranges += next;
             count -= next;
         } while (count);
     }
     void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass)
     {
         if (charClass->m_table) {
             ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table));
             matchDest.append(branchTest8(charClass->m_tableInverted ? Zero : NonZero, tableEntry));
             return;
         }
         Jump unicodeFail;
         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) {
             Jump isAscii = branch32(LessThanOrEqual, character, TrustedImm32(0x7f));
             if (charClass->m_matchesUnicode.size()) {
                 for (unsigned i = 0; i < charClass->m_matchesUnicode.size(); ++i) {
                     UChar ch = charClass->m_matchesUnicode[i];
                     matchDest.append(branch32(Equal, character, Imm32(ch)));
                 }
             }
             if (charClass->m_rangesUnicode.size()) {
                 for (unsigned i = 0; i < charClass->m_rangesUnicode.size(); ++i) {
                     UChar lo = charClass->m_rangesUnicode[i].begin;
                     UChar hi = charClass->m_rangesUnicode[i].end;
                     Jump below = branch32(LessThan, character, Imm32(lo));
                     matchDest.append(branch32(LessThanOrEqual, character, Imm32(hi)));
                     below.link(this);
                 }
             }
             unicodeFail = jump();
             isAscii.link(this);
         }
         if (charClass->m_ranges.size()) {
             unsigned matchIndex = 0;
             JumpList failures;
             matchCharacterClassRange(character, failures, matchDest, charClass->m_ranges.begin(), charClass->m_ranges.size(), &matchIndex, charClass->m_matches.begin(), charClass->m_matches.size());
             while (matchIndex < charClass->m_matches.size())
                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)charClass->m_matches[matchIndex++])));
             failures.link(this);
         } else if (charClass->m_matches.size()) {
             // optimization: gather 'a','A' etc back together, can mask & test once.
             Vector<char> matchesAZaz;
             for (unsigned i = 0; i < charClass->m_matches.size(); ++i) {
                 char ch = charClass->m_matches[i];
                 if (m_pattern.m_ignoreCase) {
                     if (isASCIILower(ch)) {
                         matchesAZaz.append(ch);
                         continue;
                     }
                     if (isASCIIUpper(ch))
                         continue;
                 }
                 matchDest.append(branch32(Equal, character, Imm32((unsigned short)ch)));
             }
             if (unsigned countAZaz = matchesAZaz.size()) {
                 or32(TrustedImm32(32), character);
                 for (unsigned i = 0; i < countAZaz; ++i)
                     matchDest.append(branch32(Equal, character, TrustedImm32(matchesAZaz[i])));
             }
         }
         if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size())
             unicodeFail.link(this);
     }
     // Jumps if input not available; will have (incorrectly) incremented already!
     Jump jumpIfNoAvailableInput(unsigned countToCheck = 0)
     {
         if (countToCheck)
             add32(Imm32(countToCheck), index);
         return branch32(Above, index, length);
     }
     Jump jumpIfAvailableInput(unsigned countToCheck)
     {
         add32(Imm32(countToCheck), index);
         return branch32(BelowOrEqual, index, length);
     }
     Jump checkInput()
     {
         return branch32(BelowOrEqual, index, length);
     }
     Jump atEndOfInput()
     {
         return branch32(Equal, index, length);
     }
     Jump notAtEndOfInput()
     {
         return branch32(NotEqual, index, length);
     }
     Jump jumpIfCharNotEquals(UChar ch, int inputPosition, RegisterID character)
     {
         readCharacter(inputPosition, character);
         // For case-insesitive compares, non-ascii characters that have different
         // upper & lower case representations are converted to a character class.
         ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));
         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
             or32(TrustedImm32(0x20), character);
             ch |= 0x20;
         }
         return branch32(NotEqual, character, Imm32(ch));
     }
     void readCharacter(int inputPosition, RegisterID reg)
     {
         if (m_charSize == Char8)
             load8(BaseIndex(input, index, TimesOne, inputPosition * sizeof(char)), reg);
         else
             load16(BaseIndex(input, index, TimesTwo, inputPosition * sizeof(UChar)), reg);
     }
     void storeToFrame(RegisterID reg, unsigned frameLocation)
     {
         poke(reg, frameLocation);
     }
     void storeToFrame(TrustedImm32 imm, unsigned frameLocation)
     {
         poke(imm, frameLocation);
     }
     DataLabelPtr storeToFrameWithPatch(unsigned frameLocation)
     {
         return storePtrWithPatch(TrustedImmPtr(0), Address(stackPointerRegister, frameLocation * sizeof(void*)));
     }
     void loadFromFrame(unsigned frameLocation, RegisterID reg)
     {
         peek(reg, frameLocation);
     }
     void loadFromFrameAndJump(unsigned frameLocation)
     {
         jump(Address(stackPointerRegister, frameLocation * sizeof(void*)));
     }
     void initCallFrame()
     {
         unsigned callFrameSize = m_pattern.m_body->m_callFrameSize;
         if (callFrameSize)
             subPtr(Imm32(callFrameSize * sizeof(void*)), stackPointerRegister);
     }
     void removeCallFrame()
     {
         unsigned callFrameSize = m_pattern.m_body->m_callFrameSize;
         if (callFrameSize)
             addPtr(Imm32(callFrameSize * sizeof(void*)), stackPointerRegister);
     }
     // Used to record subpatters, should only be called if compileMode is IncludeSubpatterns.
     void setSubpatternStart(RegisterID reg, unsigned subpattern)
     {
         ASSERT(subpattern);
         // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
         store32(reg, Address(output, (subpattern << 1) * sizeof(int)));
     }
     void setSubpatternEnd(RegisterID reg, unsigned subpattern)
     {
         ASSERT(subpattern);
         // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
         store32(reg, Address(output, ((subpattern << 1) + 1) * sizeof(int)));
     }
     void clearSubpatternStart(unsigned subpattern)
     {
         ASSERT(subpattern);
         // FIXME: should be able to ASSERT(compileMode == IncludeSubpatterns), but then this function is conditionally NORETURN. :-(
         store32(TrustedImm32(-1), Address(output, (subpattern << 1) * sizeof(int)));
     }
     // We use one of three different strategies to track the start of the current match,
     // while matching.
     // 1) If the pattern has a fixed size, do nothing! - we calculate the value lazily
     //    at the end of matching. This is irrespective of compileMode, and in this case
     //    these methods should never be called.
     // 2) If we're compiling IncludeSubpatterns, 'output' contains a pointer to an output
     //    vector, store the match start in the output vector.
     // 3) If we're compiling MatchOnly, 'output' is unused, store the match start directly
     //    in this register.
     void setMatchStart(RegisterID reg)
     {
         ASSERT(!m_pattern.m_body->m_hasFixedSize);
         if (compileMode == IncludeSubpatterns)
             store32(reg, output);
         else
             move(reg, output);
     }
     void getMatchStart(RegisterID reg)
     {
         ASSERT(!m_pattern.m_body->m_hasFixedSize);
         if (compileMode == IncludeSubpatterns)
             load32(output, reg);
         else
             move(output, reg);
     }
     enum YarrOpCode {
         // These nodes wrap body alternatives - those in the main disjunction,
         // rather than subpatterns or assertions. These are chained together in
         // a doubly linked list, with a 'begin' node for the first alternative,
         // a 'next' node for each subsequent alternative, and an 'end' node at
         // the end. In the case of repeating alternatives, the 'end' node also
         // has a reference back to 'begin'.
         OpBodyAlternativeBegin,
         OpBodyAlternativeNext,
         OpBodyAlternativeEnd,
         // Similar to the body alternatives, but used for subpatterns with two
         // or more alternatives.
         OpNestedAlternativeBegin,
         OpNestedAlternativeNext,
         OpNestedAlternativeEnd,
         // Used for alternatives in subpatterns where there is only a single
         // alternative (backtrackingis easier in these cases), or for alternatives
         // which never need to be backtracked (those in parenthetical assertions,
         // terminal subpatterns).
         OpSimpleNestedAlternativeBegin,
         OpSimpleNestedAlternativeNext,
         OpSimpleNestedAlternativeEnd,
         // Used to wrap 'Once' subpattern matches (quantityCount == 1).
         OpParenthesesSubpatternOnceBegin,
         OpParenthesesSubpatternOnceEnd,
         // Used to wrap 'Terminal' subpattern matches (at the end of the regexp).
         OpParenthesesSubpatternTerminalBegin,
         OpParenthesesSubpatternTerminalEnd,
         // Used to wrap parenthetical assertions.
         OpParentheticalAssertionBegin,
         OpParentheticalAssertionEnd,
         // Wraps all simple terms (pattern characters, character classes).
         OpTerm,
         // Where an expression contains only 'once through' body alternatives
         // and no repeating ones, this op is used to return match failure.
         OpMatchFailed
     };
     // This structure is used to hold the compiled opcode information,
     // including reference back to the original PatternTerm/PatternAlternatives,
     // and JIT compilation data structures.
     struct YarrOp {
         explicit YarrOp(PatternTerm* term)
             : m_op(OpTerm)
             , m_term(term)
             , m_isDeadCode(false)
         {
         }
         explicit YarrOp(YarrOpCode op)
             : m_op(op)
             , m_isDeadCode(false)
         {
         }
         // The operation, as a YarrOpCode, and also a reference to the PatternTerm.
         YarrOpCode m_op;
         PatternTerm* m_term;
         // For alternatives, this holds the PatternAlternative and doubly linked
         // references to this alternative's siblings. In the case of the
         // OpBodyAlternativeEnd node at the end of a section of repeating nodes,
         // m_nextOp will reference the OpBodyAlternativeBegin node of the first
         // repeating alternative.
         PatternAlternative* m_alternative;
         size_t m_previousOp;
         size_t m_nextOp;
         // Used to record a set of Jumps out of the generated code, typically
         // used for jumps out to backtracking code, and a single reentry back
         // into the code for a node (likely where a backtrack will trigger
         // rematching).
         Label m_reentry;
         JumpList m_jumps;
         // Used for backtracking when the prior alternative did not consume any
         // characters but matched.
         Jump m_zeroLengthMatch;
         // This flag is used to null out the second pattern character, when
         // two are fused to match a pair together.
         bool m_isDeadCode;
         // Currently used in the case of some of the more complex management of
         // 'm_checked', to cache the offset used in this alternative, to avoid
         // recalculating it.
         int m_checkAdjust;
         // Used by OpNestedAlternativeNext/End to hold the pointer to the
         // value that will be pushed into the pattern's frame to return to,
         // upon backtracking back into the disjunction.
         DataLabelPtr m_returnAddress;
     };
     // BacktrackingState
     // This class encapsulates information about the state of code generation
     // whilst generating the code for backtracking, when a term fails to match.
     // Upon entry to code generation of the backtracking code for a given node,
     // the Backtracking state will hold references to all control flow sources
     // that are outputs in need of further backtracking from the prior node
     // generated (which is the subsequent operation in the regular expression,
     // and in the m_ops Vector, since we generated backtracking backwards).
     // These references to control flow take the form of:
     //  - A jump list of jumps, to be linked to code that will backtrack them
     //    further.
     //  - A set of DataLabelPtr values, to be populated with values to be
     //    treated effectively as return addresses backtracking into complex
     //    subpatterns.
     //  - A flag indicating that the current sequence of generated code up to
     //    this point requires backtracking.
     class BacktrackingState {
     public:
         BacktrackingState()
             : m_pendingFallthrough(false)
         {
         }
         // Add a jump or jumps, a return address, or set the flag indicating
         // that the current 'fallthrough' control flow requires backtracking.
         void append(const Jump& jump)
         {
             m_laterFailures.append(jump);
         }
         void append(JumpList& jumpList)
         {
             m_laterFailures.append(jumpList);
         }
         void append(const DataLabelPtr& returnAddress)
         {
             m_pendingReturns.append(returnAddress);
         }
         void fallthrough()
         {
             ASSERT(!m_pendingFallthrough);
             m_pendingFallthrough = true;
         }
         // These methods clear the backtracking state, either linking to the
         // current location, a provided label, or copying the backtracking out
         // to a JumpList. All actions may require code generation to take place,
         // and as such are passed a pointer to the assembler.
         void link(MacroAssembler* assembler)
         {
             if (m_pendingReturns.size()) {
                 Label here(assembler);
                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
                 m_pendingReturns.clear();
             }
             m_laterFailures.link(assembler);
             m_laterFailures.clear();
             m_pendingFallthrough = false;
         }
         void linkTo(Label label, MacroAssembler* assembler)
         {
             if (m_pendingReturns.size()) {
                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], label));
                 m_pendingReturns.clear();
             }
             if (m_pendingFallthrough)
                 assembler->jump(label);
             m_laterFailures.linkTo(label, assembler);
             m_laterFailures.clear();
             m_pendingFallthrough = false;
         }
         void takeBacktracksToJumpList(JumpList& jumpList, MacroAssembler* assembler)
         {
             if (m_pendingReturns.size()) {
                 Label here(assembler);
                 for (unsigned i = 0; i < m_pendingReturns.size(); ++i)
                     m_backtrackRecords.append(ReturnAddressRecord(m_pendingReturns[i], here));
                 m_pendingReturns.clear();
                 m_pendingFallthrough = true;
             }
             if (m_pendingFallthrough)
                 jumpList.append(assembler->jump());
             jumpList.append(m_laterFailures);
             m_laterFailures.clear();
             m_pendingFallthrough = false;
         }
         bool isEmpty()
         {
             return m_laterFailures.empty() && m_pendingReturns.isEmpty() && !m_pendingFallthrough;
         }
         // Called at the end of code generation to link all return addresses.
         void linkDataLabels(LinkBuffer& linkBuffer)
         {
             ASSERT(isEmpty());
             for (unsigned i = 0; i < m_backtrackRecords.size(); ++i)
                 linkBuffer.patch(m_backtrackRecords[i].m_dataLabel, linkBuffer.locationOf(m_backtrackRecords[i].m_backtrackLocation));
         }
     private:
         struct ReturnAddressRecord {
             ReturnAddressRecord(DataLabelPtr dataLabel, Label backtrackLocation)
                 : m_dataLabel(dataLabel)
                 , m_backtrackLocation(backtrackLocation)
             {
             }
             DataLabelPtr m_dataLabel;
             Label m_backtrackLocation;
         };
         JumpList m_laterFailures;
         bool m_pendingFallthrough;
         Vector<DataLabelPtr, 4> m_pendingReturns;
         Vector<ReturnAddressRecord, 4> m_backtrackRecords;
     };
     // Generation methods:
     // ===================
     // This method provides a default implementation of backtracking common
     // to many terms; terms commonly jump out of the forwards  matching path
     // on any failed conditions, and add these jumps to the m_jumps list. If
     // no special handling is required we can often just backtrack to m_jumps.
     bool backtrackTermDefault(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         m_backtrackingState.append(op.m_jumps);
         return true;
     }
     bool generateAssertionBOL(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         if (m_pattern.m_multiline) {
             const RegisterID character = regT0;
             JumpList matchDest;
             if (!term->inputPosition)
                 matchDest.append(branch32(Equal, index, Imm32(m_checked)));
             readCharacter((term->inputPosition - m_checked) - 1, character);
             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
             op.m_jumps.append(jump());
             matchDest.link(this);
         } else {
             // Erk, really should poison out these alternatives early. :-/
             if (term->inputPosition)
                 op.m_jumps.append(jump());
             else
                 op.m_jumps.append(branch32(NotEqual, index, Imm32(m_checked)));
         }
         return true;
     }
     bool backtrackAssertionBOL(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     bool generateAssertionEOL(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         if (m_pattern.m_multiline) {
             const RegisterID character = regT0;
             JumpList matchDest;
             if (term->inputPosition == m_checked)
                 matchDest.append(atEndOfInput());
             readCharacter(term->inputPosition - m_checked, character);
             matchCharacterClass(character, matchDest, m_pattern.newlineCharacterClass());
             op.m_jumps.append(jump());
             matchDest.link(this);
         } else {
             if (term->inputPosition == m_checked)
                 op.m_jumps.append(notAtEndOfInput());
             // Erk, really should poison out these alternatives early. :-/
             else
                 op.m_jumps.append(jump());
         }
         return true;
     }
     bool backtrackAssertionEOL(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     // Also falls though on nextIsNotWordChar.
     void matchAssertionWordchar(size_t opIndex, JumpList& nextIsWordChar, JumpList& nextIsNotWordChar)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID character = regT0;
         if (term->inputPosition == m_checked)
             nextIsNotWordChar.append(atEndOfInput());
         readCharacter((term->inputPosition - m_checked), character);
         matchCharacterClass(character, nextIsWordChar, m_pattern.wordcharCharacterClass());
     }
     bool generateAssertionWordBoundary(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID character = regT0;
         Jump atBegin;
         JumpList matchDest;
         if (!term->inputPosition)
             atBegin = branch32(Equal, index, Imm32(m_checked));
         readCharacter((term->inputPosition - m_checked) - 1, character);
         matchCharacterClass(character, matchDest, m_pattern.wordcharCharacterClass());
         if (!term->inputPosition)
             atBegin.link(this);
         // We fall through to here if the last character was not a wordchar.
         JumpList nonWordCharThenWordChar;
         JumpList nonWordCharThenNonWordChar;
         if (term->invert()) {
             matchAssertionWordchar(opIndex, nonWordCharThenNonWordChar, nonWordCharThenWordChar);
             nonWordCharThenWordChar.append(jump());
         } else {
             matchAssertionWordchar(opIndex, nonWordCharThenWordChar, nonWordCharThenNonWordChar);
             nonWordCharThenNonWordChar.append(jump());
         }
         op.m_jumps.append(nonWordCharThenNonWordChar);
         // We jump here if the last character was a wordchar.
         matchDest.link(this);
         JumpList wordCharThenWordChar;
         JumpList wordCharThenNonWordChar;
         if (term->invert()) {
             matchAssertionWordchar(opIndex, wordCharThenNonWordChar, wordCharThenWordChar);
             wordCharThenWordChar.append(jump());
         } else {
             matchAssertionWordchar(opIndex, wordCharThenWordChar, wordCharThenNonWordChar);
             // This can fall-though!
         }
         op.m_jumps.append(wordCharThenWordChar);
         nonWordCharThenWordChar.link(this);
         wordCharThenNonWordChar.link(this);
         return true;
     }
     bool backtrackAssertionWordBoundary(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     bool generatePatternCharacterOnce(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         if (op.m_isDeadCode)
             return true;
         // m_ops always ends with a OpBodyAlternativeEnd or OpMatchFailed
         // node, so there must always be at least one more node.
         ASSERT(opIndex + 1 < m_ops.size());
         YarrOp* nextOp = &m_ops[opIndex + 1];
         PatternTerm* term = op.m_term;
         UChar ch = term->patternCharacter;
         if ((ch > 0xff) && (m_charSize == Char8)) {
             // Have a 16 bit pattern character and an 8 bit string - short circuit
             op.m_jumps.append(jump());
             return true;
         }
         const RegisterID character = regT0;
         int maxCharactersAtOnce = m_charSize == Char8 ? 4 : 2;
         unsigned ignoreCaseMask = 0;
 #if CPU(BIG_ENDIAN)
         int allCharacters = ch << (m_charSize == Char8 ? 24 : 16);
 #else
         int allCharacters = ch;
 #endif
         int numberCharacters;
         int startTermPosition = term->inputPosition;
         // For case-insesitive compares, non-ascii characters that have different
         // upper & lower case representations are converted to a character class.
         ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));
         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch))
 #if CPU(BIG_ENDIAN)
             ignoreCaseMask |= 32 << (m_charSize == Char8 ? 24 : 16);
 #else
             ignoreCaseMask |= 32;
 #endif
         for (numberCharacters = 1; numberCharacters < maxCharactersAtOnce && nextOp->m_op == OpTerm; ++numberCharacters, nextOp = &m_ops[opIndex + numberCharacters]) {
             PatternTerm* nextTerm = nextOp->m_term;
             if (nextTerm->type != PatternTerm::TypePatternCharacter
                 || nextTerm->quantityType != QuantifierFixedCount
                 || nextTerm->quantityCount != 1
                 || nextTerm->inputPosition != (startTermPosition + numberCharacters))
                 break;
             nextOp->m_isDeadCode = true;
 #if CPU(BIG_ENDIAN)
             int shiftAmount = (m_charSize == Char8 ? 24 : 16) - ((m_charSize == Char8 ? 8 : 16) * numberCharacters);
 #else
             int shiftAmount = (m_charSize == Char8 ? 8 : 16) * numberCharacters;
 #endif
             UChar currentCharacter = nextTerm->patternCharacter;
             if ((currentCharacter > 0xff) && (m_charSize == Char8)) {
                 // Have a 16 bit pattern character and an 8 bit string - short circuit
                 op.m_jumps.append(jump());
                 return true;
             }
             // For case-insesitive compares, non-ascii characters that have different
             // upper & lower case representations are converted to a character class.
             ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(currentCharacter) || isCanonicallyUnique(currentCharacter));
             allCharacters |= (currentCharacter << shiftAmount);
             if ((m_pattern.m_ignoreCase) && (isASCIIAlpha(currentCharacter)))
                 ignoreCaseMask |= 32 << shiftAmount;
         }
         if (m_charSize == Char8) {
             switch (numberCharacters) {
             case 1:
                 op.m_jumps.append(jumpIfCharNotEquals(ch, startTermPosition - m_checked, character));
                 return true;
             case 2: {
                 BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
                 load16Unaligned(address, character);
                 break;
             }
             case 3: {
                 BaseIndex highAddress(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
                 load16Unaligned(highAddress, character);
                 if (ignoreCaseMask)
                     or32(Imm32(ignoreCaseMask), character);
                 op.m_jumps.append(branch32(NotEqual, character, Imm32((allCharacters & 0xffff) | ignoreCaseMask)));
                 op.m_jumps.append(jumpIfCharNotEquals(allCharacters >> 16, startTermPosition + 2 - m_checked, character));
                 return true;
             }
             case 4: {
                 BaseIndex address(input, index, TimesOne, (startTermPosition - m_checked) * sizeof(LChar));
                 load32WithUnalignedHalfWords(address, character);
                 break;
             }
             }
         } else {
             switch (numberCharacters) {
             case 1:
                 op.m_jumps.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
                 return true;
             case 2:
                 BaseIndex address(input, index, TimesTwo, (term->inputPosition - m_checked) * sizeof(UChar));
                 load32WithUnalignedHalfWords(address, character);
                 break;
             }
         }
         if (ignoreCaseMask)
             or32(Imm32(ignoreCaseMask), character);
         op.m_jumps.append(branch32(NotEqual, character, Imm32(allCharacters | ignoreCaseMask)));
         return true;
     }
     bool backtrackPatternCharacterOnce(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     bool generatePatternCharacterFixed(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         UChar ch = term->patternCharacter;
         const RegisterID character = regT0;
         const RegisterID countRegister = regT1;
         move(index, countRegister);
         if (term->quantityCount.hasOverflowed())
             return false;
         sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
         Label loop(this);
         int offset;
         if ((Checked<int>(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount)) * static_cast<int>(m_charSize == Char8 ? sizeof(char) : sizeof(UChar))).safeGet(offset))
             return false;
         BaseIndex address(input, countRegister, m_charScale, offset);
         if (m_charSize == Char8)
             load8(address, character);
         else
             load16(address, character);
         // For case-insesitive compares, non-ascii characters that have different
         // upper & lower case representations are converted to a character class.
         ASSERT(!m_pattern.m_ignoreCase || isASCIIAlpha(ch) || isCanonicallyUnique(ch));
         if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) {
             or32(TrustedImm32(0x20), character);
             ch |= 0x20;
         }
         op.m_jumps.append(branch32(NotEqual, character, Imm32(ch)));
         add32(TrustedImm32(1), countRegister);
         branch32(NotEqual, countRegister, index).linkTo(loop, this);
         return true;
     }
     bool backtrackPatternCharacterFixed(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     bool generatePatternCharacterGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         UChar ch = term->patternCharacter;
         const RegisterID character = regT0;
         const RegisterID countRegister = regT1;
         move(TrustedImm32(0), countRegister);
         // Unless have a 16 bit pattern character and an 8 bit string - short circuit
         if (!((ch > 0xff) && (m_charSize == Char8))) {
             JumpList failures;
             Label loop(this);
             failures.append(atEndOfInput());
             failures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
             add32(TrustedImm32(1), countRegister);
             add32(TrustedImm32(1), index);
             if (term->quantityCount == quantifyInfinite) {
                 jump(loop);
             } else {
                 if (term->quantityCount.hasOverflowed())
                     return false;
                 branch32(NotEqual, countRegister, Imm32(term->quantityCount.unsafeGet())).linkTo(loop, this);
             }
             failures.link(this);
         }
         op.m_reentry = label();
         storeToFrame(countRegister, term->frameLocation);
         return true;
     }
     bool backtrackPatternCharacterGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID countRegister = regT1;
         m_backtrackingState.link(this);
         loadFromFrame(term->frameLocation, countRegister);
         m_backtrackingState.append(branchTest32(Zero, countRegister));
         sub32(TrustedImm32(1), countRegister);
         sub32(TrustedImm32(1), index);
         jump(op.m_reentry);
         return true;
     }
     bool generatePatternCharacterNonGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID countRegister = regT1;
         move(TrustedImm32(0), countRegister);
         op.m_reentry = label();
         storeToFrame(countRegister, term->frameLocation);
         return true;
     }
     bool backtrackPatternCharacterNonGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         UChar ch = term->patternCharacter;
         const RegisterID character = regT0;
         const RegisterID countRegister = regT1;
         m_backtrackingState.link(this);
         loadFromFrame(term->frameLocation, countRegister);
         // Unless have a 16 bit pattern character and an 8 bit string - short circuit
         if (!((ch > 0xff) && (m_charSize == Char8))) {
             JumpList nonGreedyFailures;
             nonGreedyFailures.append(atEndOfInput());
             if (term->quantityCount != quantifyInfinite) {
                 if (term->quantityCount.hasOverflowed())
                     return false;
                 nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
             }
             nonGreedyFailures.append(jumpIfCharNotEquals(ch, term->inputPosition - m_checked, character));
             add32(TrustedImm32(1), countRegister);
             add32(TrustedImm32(1), index);
             jump(op.m_reentry);
             nonGreedyFailures.link(this);
         }
         sub32(countRegister, index);
         m_backtrackingState.fallthrough();
         return true;
     }
     bool generateCharacterClassOnce(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID character = regT0;
         JumpList matchDest;
         readCharacter(term->inputPosition - m_checked, character);
         matchCharacterClass(character, matchDest, term->characterClass);
         if (term->invert())
             op.m_jumps.append(matchDest);
         else {
             op.m_jumps.append(jump());
             matchDest.link(this);
         }
         return true;
     }
     bool backtrackCharacterClassOnce(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     bool generateCharacterClassFixed(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID character = regT0;
         const RegisterID countRegister = regT1;
         move(index, countRegister);
         if (term->quantityCount.hasOverflowed())
             return false;
         sub32(Imm32(term->quantityCount.unsafeGet()), countRegister);
         Label loop(this);
         JumpList matchDest;
         int offset;
         Checked<int64_t> checkedOffset(term->inputPosition - m_checked + Checked<int64_t>(term->quantityCount));
         if (m_charSize == Char8) {
             if ((Checked<int>(checkedOffset) * static_cast<int>(sizeof(char))).safeGet(offset))
                 return false;
             load8(BaseIndex(input, countRegister, TimesOne, offset), character);
         } else {
             if ((Checked<int>(checkedOffset) * static_cast<int>(sizeof(UChar))).safeGet(offset))
                 return false;
             load16(BaseIndex(input, countRegister, TimesTwo, offset), character);
         }
         matchCharacterClass(character, matchDest, term->characterClass);
         if (term->invert())
             op.m_jumps.append(matchDest);
         else {
             op.m_jumps.append(jump());
             matchDest.link(this);
         }
         add32(TrustedImm32(1), countRegister);
         branch32(NotEqual, countRegister, index).linkTo(loop, this);
         return true;
     }
     bool backtrackCharacterClassFixed(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     bool generateCharacterClassGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID character = regT0;
         const RegisterID countRegister = regT1;
         move(TrustedImm32(0), countRegister);
         JumpList failures;
         Label loop(this);
         failures.append(atEndOfInput());
         if (term->invert()) {
             readCharacter(term->inputPosition - m_checked, character);
             matchCharacterClass(character, failures, term->characterClass);
         } else {
             JumpList matchDest;
             readCharacter(term->inputPosition - m_checked, character);
             matchCharacterClass(character, matchDest, term->characterClass);
             failures.append(jump());
             matchDest.link(this);
         }
         add32(TrustedImm32(1), countRegister);
         add32(TrustedImm32(1), index);
         if (term->quantityCount != quantifyInfinite) {
             unsigned quantityCount;
             if (term->quantityCount.safeGet(quantityCount))
                 return false;
             branch32(NotEqual, countRegister, Imm32(quantityCount)).linkTo(loop, this);
             failures.append(jump());
         } else
             jump(loop);
         failures.link(this);
         op.m_reentry = label();
         storeToFrame(countRegister, term->frameLocation);
         return true;
     }
     bool backtrackCharacterClassGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID countRegister = regT1;
         m_backtrackingState.link(this);
         loadFromFrame(term->frameLocation, countRegister);
         m_backtrackingState.append(branchTest32(Zero, countRegister));
         sub32(TrustedImm32(1), countRegister);
         sub32(TrustedImm32(1), index);
         jump(op.m_reentry);
         return true;
     }
     bool generateCharacterClassNonGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID countRegister = regT1;
         move(TrustedImm32(0), countRegister);
         op.m_reentry = label();
         storeToFrame(countRegister, term->frameLocation);
         return true;
     }
     bool backtrackCharacterClassNonGreedy(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID character = regT0;
         const RegisterID countRegister = regT1;
         JumpList nonGreedyFailures;
         m_backtrackingState.link(this);
         loadFromFrame(term->frameLocation, countRegister);
         nonGreedyFailures.append(atEndOfInput());
         if (term->quantityCount.hasOverflowed())
             return false;
         nonGreedyFailures.append(branch32(Equal, countRegister, Imm32(term->quantityCount.unsafeGet())));
         JumpList matchDest;
         readCharacter(term->inputPosition - m_checked, character);
         matchCharacterClass(character, matchDest, term->characterClass);
         if (term->invert())
             nonGreedyFailures.append(matchDest);
         else {
             nonGreedyFailures.append(jump());
             matchDest.link(this);
         }
         add32(TrustedImm32(1), countRegister);
         add32(TrustedImm32(1), index);
         jump(op.m_reentry);
         nonGreedyFailures.link(this);
         sub32(countRegister, index);
         m_backtrackingState.fallthrough();
         return true;
     }
     bool generateDotStarEnclosure(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         const RegisterID character = regT0;
         const RegisterID matchPos = regT1;
         JumpList foundBeginningNewLine;
         JumpList saveStartIndex;
         JumpList foundEndingNewLine;
         ASSERT(!m_pattern.m_body->m_hasFixedSize);
         getMatchStart(matchPos);
         saveStartIndex.append(branchTest32(Zero, matchPos));
         Label findBOLLoop(this);
         sub32(TrustedImm32(1), matchPos);
         if (m_charSize == Char8)
             load8(BaseIndex(input, matchPos, TimesOne, 0), character);
         else
             load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
         matchCharacterClass(character, foundBeginningNewLine, m_pattern.newlineCharacterClass());
         branchTest32(NonZero, matchPos).linkTo(findBOLLoop, this);
         saveStartIndex.append(jump());
         foundBeginningNewLine.link(this);
         add32(TrustedImm32(1), matchPos); // Advance past newline
         saveStartIndex.link(this);
         if (!m_pattern.m_multiline && term->anchors.bolAnchor)
             op.m_jumps.append(branchTest32(NonZero, matchPos));
         ASSERT(!m_pattern.m_body->m_hasFixedSize);
         setMatchStart(matchPos);
         move(index, matchPos);
         Label findEOLLoop(this);
         foundEndingNewLine.append(branch32(Equal, matchPos, length));
         if (m_charSize == Char8)
             load8(BaseIndex(input, matchPos, TimesOne, 0), character);
         else
             load16(BaseIndex(input, matchPos, TimesTwo, 0), character);
         matchCharacterClass(character, foundEndingNewLine, m_pattern.newlineCharacterClass());
         add32(TrustedImm32(1), matchPos);
         jump(findEOLLoop);
         foundEndingNewLine.link(this);
         if (!m_pattern.m_multiline && term->anchors.eolAnchor)
             op.m_jumps.append(branch32(NotEqual, matchPos, length));
         move(matchPos, index);
         return true;
     }
     bool backtrackDotStarEnclosure(size_t opIndex)
     {
         return backtrackTermDefault(opIndex);
     }
     // Code generation/backtracking for simple terms
     // (pattern characters, character classes, and assertions).
     // These methods farm out work to the set of functions above.
     bool generateTerm(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         switch (term->type) {
         case PatternTerm::TypePatternCharacter:
             switch (term->quantityType) {
             case QuantifierFixedCount:
                 if (term->quantityCount == 1)
                     return generatePatternCharacterOnce(opIndex);
                 else
                     return generatePatternCharacterFixed(opIndex);
                 break;
             case QuantifierGreedy:
                 return generatePatternCharacterGreedy(opIndex);
             case QuantifierNonGreedy:
                 return generatePatternCharacterNonGreedy(opIndex);
             }
             break;
         case PatternTerm::TypeCharacterClass:
             switch (term->quantityType) {
             case QuantifierFixedCount:
                 if (term->quantityCount == 1)
                     return generateCharacterClassOnce(opIndex);
                 else
                     return generateCharacterClassFixed(opIndex);
                 break;
             case QuantifierGreedy:
                 return generateCharacterClassGreedy(opIndex);
             case QuantifierNonGreedy:
                 return generateCharacterClassNonGreedy(opIndex);
             }
             break;
         case PatternTerm::TypeAssertionBOL:
             return generateAssertionBOL(opIndex);
         case PatternTerm::TypeAssertionEOL:
             return generateAssertionEOL(opIndex);
         case PatternTerm::TypeAssertionWordBoundary:
             return generateAssertionWordBoundary(opIndex);
         case PatternTerm::TypeForwardReference:
             return true;
         case PatternTerm::TypeParenthesesSubpattern:
         case PatternTerm::TypeParentheticalAssertion:
             ASSERT_NOT_REACHED();
             return false;
         case PatternTerm::TypeBackReference:
             return false;
         case PatternTerm::TypeDotStarEnclosure:
             return generateDotStarEnclosure(opIndex);
         }
         return false;
     }
     bool backtrackTerm(size_t opIndex)
     {
         YarrOp& op = m_ops[opIndex];
         PatternTerm* term = op.m_term;
         switch (term->type) {
         case PatternTerm::TypePatternCharacter:
             switch (term->quantityType) {
             case QuantifierFixedCount:
                 if (term->quantityCount == 1)
                     return backtrackPatternCharacterOnce(opIndex);
                 else
                     return backtrackPatternCharacterFixed(opIndex);
             case QuantifierGreedy:
                 return backtrackPatternCharacterGreedy(opIndex);
             case QuantifierNonGreedy:
                 return backtrackPatternCharacterNonGreedy(opIndex);
             }
             break;
         case PatternTerm::TypeCharacterClass:
             switch (term->quantityType) {
             case QuantifierFixedCount:
                 if (term->quantityCount == 1)
                     return backtrackCharacterClassOnce(opIndex);
                 else
                     return backtrackCharacterClassFixed(opIndex);
             case QuantifierGreedy:
                 return backtrackCharacterClassGreedy(opIndex);
             case QuantifierNonGreedy:
                 return backtrackCharacterClassNonGreedy(opIndex);
             }
             break;
         case PatternTerm::TypeAssertionBOL:
             return backtrackAssertionBOL(opIndex);
         case PatternTerm::TypeAssertionEOL:
             return backtrackAssertionEOL(opIndex);
         case PatternTerm::TypeAssertionWordBoundary:
             return backtrackAssertionWordBoundary(opIndex);
         case PatternTerm::TypeForwardReference:
             return true;
         case PatternTerm::TypeParenthesesSubpattern:
         case PatternTerm::TypeParentheticalAssertion:
             ASSERT_NOT_REACHED();
             return false;
         case PatternTerm::TypeDotStarEnclosure:
             return backtrackDotStarEnclosure(opIndex);
         case PatternTerm::TypeBackReference:
             return false;
         }
         return true;
     }
     bool generate()
     {
         // Forwards generate the matching code.
         ASSERT(m_ops.size());
         size_t opIndex = 0;
         do {
             YarrOp& op = m_ops[opIndex];
             switch (op.m_op) {
             case OpTerm:
                 if (!generateTerm(opIndex))
                     return false;
                 break;
             // OpBodyAlternativeBegin/Next/End
             //
             // These nodes wrap the set of alternatives in the body of the regular expression.
             // There may be either one or two chains of OpBodyAlternative nodes, one representing
             // the 'once through' sequence of alternatives (if any exist), and one representing
             // the repeating alternatives (again, if any exist).
             //
             // Upon normal entry to the Begin alternative, we will check that input is available.
             // Reentry to the Begin alternative will take place after the check has taken place,
             // and will assume that the input position has already been progressed as appropriate.
             //
             // Entry to subsequent Next/End alternatives occurs when the prior alternative has
             // successfully completed a match - return a success state from JIT code.
             //
             // Next alternatives allow for reentry optimized to suit backtracking from its
             // preceding alternative. It expects the input position to still be set to a position
             // appropriate to its predecessor, and it will only perform an input check if the
             // predecessor had a minimum size less than its own.
             //
             // In the case 'once through' expressions, the End node will also have a reentry
             // point to jump to when the last alternative fails. Again, this expects the input
             // position to still reflect that expected by the prior alternative.
             case OpBodyAlternativeBegin: {
                 PatternAlternative* alternative = op.m_alternative;
                 // Upon entry at the head of the set of alternatives, check if input is available
                 // to run the first alternative. (This progresses the input position).
                 op.m_jumps.append(jumpIfNoAvailableInput(alternative->m_minimumSize));
                 // We will reenter after the check, and assume the input position to have been
                 // set as appropriate to this alternative.
                 op.m_reentry = label();
                 if (alternative->m_minimumSize > INT_MAX)
                     return false;
                 m_checked = alternative->m_minimumSize;
                 break;
             }
             case OpBodyAlternativeNext:
             case OpBodyAlternativeEnd: {
                 PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
                 PatternAlternative* alternative = op.m_alternative;
                 // If we get here, the prior alternative matched - return success.
                 // Adjust the stack pointer to remove the pattern's frame.
 #if !WTF_CPU_SPARC
                 removeCallFrame();
 #endif
                 // Load appropriate values into the return register and the first output
                 // slot, and return. In the case of pattern with a fixed size, we will
                 // not have yet set the value in the first
                 ASSERT(index != returnRegister);
                 if (m_pattern.m_body->m_hasFixedSize) {
                     move(index, returnRegister);
                     if (priorAlternative->m_minimumSize)
                         sub32(Imm32(priorAlternative->m_minimumSize), returnRegister);
                     if (compileMode == IncludeSubpatterns)
                         store32(returnRegister, output);
                 } else
                     getMatchStart(returnRegister);
                 if (compileMode == IncludeSubpatterns)
                     store32(index, Address(output, 4));
 #if WTF_CPU_X86_64
                 // upper 32bit to 0
                 move32(returnRegister, returnRegister);
                 lshiftPtr(Imm32(32), index);
                 orPtr(index, returnRegister);
 #else
                 move(index, returnRegister2);
 #endif
                 generateReturn();
                 // This is the divide between the tail of the prior alternative, above, and
                 // the head of the subsequent alternative, below.
                 if (op.m_op == OpBodyAlternativeNext) {
                     // This is the reentry point for the Next alternative. We expect any code
                     // that jumps here to do so with the input position matching that of the
                     // PRIOR alteranative, and we will only check input availability if we
                     // need to progress it forwards.
                     op.m_reentry = label();
                     if (alternative->m_minimumSize > priorAlternative->m_minimumSize) {
                         add32(Imm32(alternative->m_minimumSize - priorAlternative->m_minimumSize), index);
                         op.m_jumps.append(jumpIfNoAvailableInput());
                     } else if (priorAlternative->m_minimumSize > alternative->m_minimumSize)
                         sub32(Imm32(priorAlternative->m_minimumSize - alternative->m_minimumSize), index);
                 } else if (op.m_nextOp == notFound) {
                     // This is the reentry point for the End of 'once through' alternatives,
                     // jumped to when the last alternative fails to match.
                     op.m_reentry = label();
                     sub32(Imm32(priorAlternative->m_minimumSize), index);
                 }
                 if (op.m_op == OpBodyAlternativeNext)
                     m_checked += alternative->m_minimumSize;
                 m_checked -= priorAlternative->m_minimumSize;
                 break;
             }
             // OpSimpleNestedAlternativeBegin/Next/End
             // OpNestedAlternativeBegin/Next/End
             //
             // These nodes are used to handle sets of alternatives that are nested within
             // subpatterns and parenthetical assertions. The 'simple' forms are used where
             // we do not need to be able to backtrack back into any alternative other than
             // the last, the normal forms allow backtracking into any alternative.
             //
             // Each Begin/Next node is responsible for planting an input check to ensure
             // sufficient input is available on entry. Next nodes additionally need to
             // jump to the end - Next nodes use the End node's m_jumps list to hold this
             // set of jumps.
             //
             // In the non-simple forms, successful alternative matches must store a
             // 'return address' using a DataLabelPtr, used to store the address to jump
             // to when backtracking, to get to the code for the appropriate alternative.
             case OpSimpleNestedAlternativeBegin:
             case OpNestedAlternativeBegin: {
                 PatternTerm* term = op.m_term;
                 PatternAlternative* alternative = op.m_alternative;
                 PatternDisjunction* disjunction = term->parentheses.disjunction;
                 // Calculate how much input we need to check for, and if non-zero check.
                 op.m_checkAdjust = alternative->m_minimumSize;
                 if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
                     op.m_checkAdjust -= disjunction->m_minimumSize;
                 if (op.m_checkAdjust)
                     op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust));
                 m_checked += op.m_checkAdjust;
                 break;
             }
             case OpSimpleNestedAlternativeNext:
             case OpNestedAlternativeNext: {
                 PatternTerm* term = op.m_term;
                 PatternAlternative* alternative = op.m_alternative;
                 PatternDisjunction* disjunction = term->parentheses.disjunction;
                 // In the non-simple case, store a 'return address' so we can backtrack correctly.
                 if (op.m_op == OpNestedAlternativeNext) {
                     unsigned parenthesesFrameLocation = term->frameLocation;
                     unsigned alternativeFrameLocation = parenthesesFrameLocation;
                     if (term->quantityType != QuantifierFixedCount)
                         alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
                     op.m_returnAddress = storeToFrameWithPatch(alternativeFrameLocation);
                 }
                 if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) {
                     // If the previous alternative matched without consuming characters then
                     // backtrack to try to match while consumming some input.
                     op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
                 }
                 // If we reach here then the last alternative has matched - jump to the
                 // End node, to skip over any further alternatives.
                 //
                 // FIXME: this is logically O(N^2) (though N can be expected to be very
                 // small). We could avoid this either by adding an extra jump to the JIT
                 // data structures, or by making backtracking code that jumps to Next
                 // alternatives are responsible for checking that input is available (if
                 // we didn't need to plant the input checks, then m_jumps would be free).
                 YarrOp* endOp = &m_ops[op.m_nextOp];
                 while (endOp->m_nextOp != notFound) {
                     ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
                     endOp = &m_ops[endOp->m_nextOp];
                 }
                 ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
                 endOp->m_jumps.append(jump());
                 // This is the entry point for the next alternative.
                 op.m_reentry = label();
                 // Calculate how much input we need to check for, and if non-zero check.
                 op.m_checkAdjust = alternative->m_minimumSize;
                 if ((term->quantityType == QuantifierFixedCount) && (term->type != PatternTerm::TypeParentheticalAssertion))
                     op.m_checkAdjust -= disjunction->m_minimumSize;
                 if (op.m_checkAdjust)
                     op.m_jumps.append(jumpIfNoAvailableInput(op.m_checkAdjust));
                 YarrOp& lastOp = m_ops[op.m_previousOp];
                 m_checked -= lastOp.m_checkAdjust;
                 m_checked += op.m_checkAdjust;
                 break;
             }
             case OpSimpleNestedAlternativeEnd:
             case OpNestedAlternativeEnd: {
                 PatternTerm* term = op.m_term;
                 // In the non-simple case, store a 'return address' so we can backtrack correctly.
                 if (op.m_op == OpNestedAlternativeEnd) {
                     unsigned parenthesesFrameLocation = term->frameLocation;
                     unsigned alternativeFrameLocation = parenthesesFrameLocation;
                     if (term->quantityType != QuantifierFixedCount)
                         alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
                     op.m_returnAddress = storeToFrameWithPatch(alternativeFrameLocation);
                 }
                 if (term->quantityType != QuantifierFixedCount && !m_ops[op.m_previousOp].m_alternative->m_minimumSize) {
                     // If the previous alternative matched without consuming characters then
                     // backtrack to try to match while consumming some input.
                     op.m_zeroLengthMatch = branch32(Equal, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
                 }
                 // If this set of alternatives contains more than one alternative,
                 // then the Next nodes will have planted jumps to the End, and added
                 // them to this node's m_jumps list.
                 op.m_jumps.link(this);
                 op.m_jumps.clear();
                 YarrOp& lastOp = m_ops[op.m_previousOp];
                 m_checked -= lastOp.m_checkAdjust;
                 break;
             }
             // OpParenthesesSubpatternOnceBegin/End
             //
             // These nodes support (optionally) capturing subpatterns, that have a
             // quantity count of 1 (this covers fixed once, and ?/?? quantifiers).
             case OpParenthesesSubpatternOnceBegin: {
                 PatternTerm* term = op.m_term;
                 unsigned parenthesesFrameLocation = term->frameLocation;
                 const RegisterID indexTemporary = regT0;
                 ASSERT(term->quantityCount == 1);
                 // Upon entry to a Greedy quantified set of parenthese store the index.
                 // We'll use this for two purposes:
                 //  - To indicate which iteration we are on of mathing the remainder of
                 //    the expression after the parentheses - the first, including the
                 //    match within the parentheses, or the second having skipped over them.
                 //  - To check for empty matches, which must be rejected.
                 //
                 // At the head of a NonGreedy set of parentheses we'll immediately set the
                 // value on the stack to -1 (indicating a match skipping the subpattern),
                 // and plant a jump to the end. We'll also plant a label to backtrack to
                 // to reenter the subpattern later, with a store to set up index on the
                 // second iteration.
                 //
                 // FIXME: for capturing parens, could use the index in the capture array?
                 if (term->quantityType == QuantifierGreedy)
                     storeToFrame(index, parenthesesFrameLocation);
                 else if (term->quantityType == QuantifierNonGreedy) {
                     storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
                     op.m_jumps.append(jump());
                     op.m_reentry = label();
                     storeToFrame(index, parenthesesFrameLocation);
                 }
                 // If the parenthese are capturing, store the starting index value to the
                 // captures array, offsetting as necessary.
                 //
                 // FIXME: could avoid offsetting this value in JIT code, apply
                 // offsets only afterwards, at the point the results array is
                 // being accessed.
                 if (term->capture() && compileMode == IncludeSubpatterns) {
                     int inputOffset = term->inputPosition - m_checked;
                     if (term->quantityType == QuantifierFixedCount)
                         inputOffset -= term->parentheses.disjunction->m_minimumSize;
                     if (inputOffset) {
                         move(index, indexTemporary);
                         add32(Imm32(inputOffset), indexTemporary);
                         setSubpatternStart(indexTemporary, term->parentheses.subpatternId);
                     } else
                         setSubpatternStart(index, term->parentheses.subpatternId);
                 }
                 break;
             }
             case OpParenthesesSubpatternOnceEnd: {
                 PatternTerm* term = op.m_term;
                 const RegisterID indexTemporary = regT0;
                 ASSERT(term->quantityCount == 1);
 #ifndef NDEBUG
                 // Runtime ASSERT to make sure that the nested alternative handled the
                 // "no input consumed" check.
                 if (term->quantityType != QuantifierFixedCount && !term->parentheses.disjunction->m_minimumSize) {
                     Jump pastBreakpoint;
                     pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
                     breakpoint();
                     pastBreakpoint.link(this);
                 }
 #endif
                 // If the parenthese are capturing, store the ending index value to the
                 // captures array, offsetting as necessary.
                 //
                 // FIXME: could avoid offsetting this value in JIT code, apply
                 // offsets only afterwards, at the point the results array is
                 // being accessed.
                 if (term->capture() && compileMode == IncludeSubpatterns) {
                     int inputOffset = term->inputPosition - m_checked;
                     if (inputOffset) {
                         move(index, indexTemporary);
                         add32(Imm32(inputOffset), indexTemporary);
                         setSubpatternEnd(indexTemporary, term->parentheses.subpatternId);
                     } else
                         setSubpatternEnd(index, term->parentheses.subpatternId);
                 }
                 // If the parentheses are quantified Greedy then add a label to jump back
                 // to if get a failed match from after the parentheses. For NonGreedy
                 // parentheses, link the jump from before the subpattern to here.
                 if (term->quantityType == QuantifierGreedy)
                     op.m_reentry = label();
                 else if (term->quantityType == QuantifierNonGreedy) {
                     YarrOp& beginOp = m_ops[op.m_previousOp];
                     beginOp.m_jumps.link(this);
                 }
                 break;
             }
             // OpParenthesesSubpatternTerminalBegin/End
             case OpParenthesesSubpatternTerminalBegin: {
                 PatternTerm* term = op.m_term;
                 ASSERT(term->quantityType == QuantifierGreedy);
                 ASSERT(term->quantityCount == quantifyInfinite);
                 ASSERT(!term->capture());
                 // Upon entry set a label to loop back to.
                 op.m_reentry = label();
                 // Store the start index of the current match; we need to reject zero
                 // length matches.
                 storeToFrame(index, term->frameLocation);
                 break;
             }
             case OpParenthesesSubpatternTerminalEnd: {
                 YarrOp& beginOp = m_ops[op.m_previousOp];
 #ifndef NDEBUG
                 PatternTerm* term = op.m_term;
                 // Runtime ASSERT to make sure that the nested alternative handled the
                 // "no input consumed" check.
                 Jump pastBreakpoint;
                 pastBreakpoint = branch32(NotEqual, index, Address(stackPointerRegister, term->frameLocation * sizeof(void*)));
                 breakpoint();
                 pastBreakpoint.link(this);
 #endif
                 // We know that the match is non-zero, we can accept it  and
                 // loop back up to the head of the subpattern.
                 jump(beginOp.m_reentry);
                 // This is the entry point to jump to when we stop matching - we will
                 // do so once the subpattern cannot match any more.
                 op.m_reentry = label();
                 break;
             }
             // OpParentheticalAssertionBegin/End
             case OpParentheticalAssertionBegin: {
                 PatternTerm* term = op.m_term;
                 // Store the current index - assertions should not update index, so
                 // we will need to restore it upon a successful match.
                 unsigned parenthesesFrameLocation = term->frameLocation;
                 storeToFrame(index, parenthesesFrameLocation);
                 // Check
                 op.m_checkAdjust = m_checked - term->inputPosition;
                 if (op.m_checkAdjust)
                     sub32(Imm32(op.m_checkAdjust), index);
                 m_checked -= op.m_checkAdjust;
                 break;
             }
             case OpParentheticalAssertionEnd: {
                 PatternTerm* term = op.m_term;
                 // Restore the input index value.
                 unsigned parenthesesFrameLocation = term->frameLocation;
                 loadFromFrame(parenthesesFrameLocation, index);
                 // If inverted, a successful match of the assertion must be treated
                 // as a failure, so jump to backtracking.
                 if (term->invert()) {
                     op.m_jumps.append(jump());
                     op.m_reentry = label();
                 }
                 YarrOp& lastOp = m_ops[op.m_previousOp];
                 m_checked += lastOp.m_checkAdjust;
                 break;
             }
             case OpMatchFailed:
 #if !WTF_CPU_SPARC
                 removeCallFrame();
 #endif
 #if WTF_CPU_X86_64
                 move(TrustedImm32(int(WTF::notFound)), returnRegister);
 #else
                 move(TrustedImmPtr((void*)WTF::notFound), returnRegister);
                 move(TrustedImm32(0), returnRegister2);
 #endif
                 generateReturn();
                 break;
             }
             ++opIndex;
         } while (opIndex < m_ops.size());
         return true;
     }
     bool backtrack()
     {
         // Backwards generate the backtracking code.
         size_t opIndex = m_ops.size();
         ASSERT(opIndex);
         do {
             --opIndex;
             YarrOp& op = m_ops[opIndex];
             switch (op.m_op) {
             case OpTerm:
                 if (!backtrackTerm(opIndex))
                     return false;
                 break;
             // OpBodyAlternativeBegin/Next/End
             //
             // For each Begin/Next node representing an alternative, we need to decide what to do
             // in two circumstances:
             //  - If we backtrack back into this node, from within the alternative.
             //  - If the input check at the head of the alternative fails (if this exists).
             //
             // We treat these two cases differently since in the former case we have slightly
             // more information - since we are backtracking out of a prior alternative we know
             // that at least enough input was available to run it. For example, given the regular
             // expression /a|b/, if we backtrack out of the first alternative (a failed pattern
             // character match of 'a'), then we need not perform an additional input availability
             // check before running the second alternative.
             //
             // Backtracking required differs for the last alternative, which in the case of the
             // repeating set of alternatives must loop. The code generated for the last alternative
             // will also be used to handle all input check failures from any prior alternatives -
             // these require similar functionality, in seeking the next available alternative for
             // which there is sufficient input.
             //
             // Since backtracking of all other alternatives simply requires us to link backtracks
             // to the reentry point for the subsequent alternative, we will only be generating any
             // code when backtracking the last alternative.
             case OpBodyAlternativeBegin:
             case OpBodyAlternativeNext: {
                 PatternAlternative* alternative = op.m_alternative;
                 if (op.m_op == OpBodyAlternativeNext) {
                     PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
                     m_checked += priorAlternative->m_minimumSize;
                 }
                 m_checked -= alternative->m_minimumSize;
                 // Is this the last alternative? If not, then if we backtrack to this point we just
                 // need to jump to try to match the next alternative.
                 if (m_ops[op.m_nextOp].m_op != OpBodyAlternativeEnd) {
                     m_backtrackingState.linkTo(m_ops[op.m_nextOp].m_reentry, this);
                     break;
                 }
                 YarrOp& endOp = m_ops[op.m_nextOp];
                 YarrOp* beginOp = &op;
                 while (beginOp->m_op != OpBodyAlternativeBegin) {
                     ASSERT(beginOp->m_op == OpBodyAlternativeNext);
                     beginOp = &m_ops[beginOp->m_previousOp];
                 }
                 bool onceThrough = endOp.m_nextOp == notFound;
                 // First, generate code to handle cases where we backtrack out of an attempted match
                 // of the last alternative. If this is a 'once through' set of alternatives then we
                 // have nothing to do - link this straight through to the End.
                 if (onceThrough)
                     m_backtrackingState.linkTo(endOp.m_reentry, this);
                 else {
                     // If we don't need to move the input poistion, and the pattern has a fixed size
                     // (in which case we omit the store of the start index until the pattern has matched)
                     // then we can just link the backtrack out of the last alternative straight to the
                     // head of the first alternative.
                     if (m_pattern.m_body->m_hasFixedSize
                         && (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize)
                         && (alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize == 1))
                         m_backtrackingState.linkTo(beginOp->m_reentry, this);
                     else {
                         // We need to generate a trampoline of code to execute before looping back
                         // around to the first alternative.
                         m_backtrackingState.link(this);
                         // If the pattern size is not fixed, then store the start index, for use if we match.
                         if (!m_pattern.m_body->m_hasFixedSize) {
                             if (alternative->m_minimumSize == 1)
                                 setMatchStart(index);
                             else {
                                 move(index, regT0);
                                 if (alternative->m_minimumSize)
                                     sub32(Imm32(alternative->m_minimumSize - 1), regT0);
                                 else
                                     add32(TrustedImm32(1), regT0);
                                 setMatchStart(regT0);
                             }
                         }
                         // Generate code to loop. Check whether the last alternative is longer than the
                         // first (e.g. /a|xy/ or /a|xyz/).
                         if (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize) {
                             // We want to loop, and increment input position. If the delta is 1, it is
                             // already correctly incremented, if more than one then decrement as appropriate.
                             unsigned delta = alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize;
                             ASSERT(delta);
                             if (delta != 1)
                                 sub32(Imm32(delta - 1), index);
                             jump(beginOp->m_reentry);
                         } else {
                             // If the first alternative has minimum size 0xFFFFFFFFu, then there cannot
                             // be sufficent input available to handle this, so just fall through.
                             unsigned delta = beginOp->m_alternative->m_minimumSize - alternative->m_minimumSize;
                             if (delta != 0xFFFFFFFFu) {
                                 // We need to check input because we are incrementing the input.
                                 add32(Imm32(delta + 1), index);
                                 checkInput().linkTo(beginOp->m_reentry, this);
                             }
                         }
                     }
                 }
                 // We can reach this point in the code in two ways:
                 //  - Fallthrough from the code above (a repeating alternative backtracked out of its
                 //    last alternative, and did not have sufficent input to run the first).
                 //  - We will loop back up to the following label when a releating alternative loops,
                 //    following a failed input check.
                 //
                 // Either way, we have just failed the input check for the first alternative.
                 Label firstInputCheckFailed(this);
                 // Generate code to handle input check failures from alternatives except the last.
                 // prevOp is the alternative we're handling a bail out from (initially Begin), and
                 // nextOp is the alternative we will be attempting to reenter into.
                 //
                 // We will link input check failures from the forwards matching path back to the code
                 // that can handle them.
                 YarrOp* prevOp = beginOp;
                 YarrOp* nextOp = &m_ops[beginOp->m_nextOp];
                 while (nextOp->m_op != OpBodyAlternativeEnd) {
                     prevOp->m_jumps.link(this);
                     // We only get here if an input check fails, it is only worth checking again
                     // if the next alternative has a minimum size less than the last.
                     if (prevOp->m_alternative->m_minimumSize > nextOp->m_alternative->m_minimumSize) {
                         // FIXME: if we added an extra label to YarrOp, we could avoid needing to
                         // subtract delta back out, and reduce this code. Should performance test
                         // the benefit of this.
                         unsigned delta = prevOp->m_alternative->m_minimumSize - nextOp->m_alternative->m_minimumSize;
                         sub32(Imm32(delta), index);
                         Jump fail = jumpIfNoAvailableInput();
                         add32(Imm32(delta), index);
                         jump(nextOp->m_reentry);
                         fail.link(this);
                     } else if (prevOp->m_alternative->m_minimumSize < nextOp->m_alternative->m_minimumSize)
                         add32(Imm32(nextOp->m_alternative->m_minimumSize - prevOp->m_alternative->m_minimumSize), index);
                     prevOp = nextOp;
                     nextOp = &m_ops[nextOp->m_nextOp];
                 }
                 // We fall through to here if there is insufficient input to run the last alternative.
                 // If there is insufficient input to run the last alternative, then for 'once through'
                 // alternatives we are done - just jump back up into the forwards matching path at the End.
                 if (onceThrough) {
                     op.m_jumps.linkTo(endOp.m_reentry, this);
                     jump(endOp.m_reentry);
                     break;
                 }
                 // For repeating alternatives, link any input check failure from the last alternative to
                 // this point.
                 op.m_jumps.link(this);
                 bool needsToUpdateMatchStart = !m_pattern.m_body->m_hasFixedSize;
                 // Check for cases where input position is already incremented by 1 for the last
                 // alternative (this is particularly useful where the minimum size of the body
                 // disjunction is 0, e.g. /a*|b/).
                 if (needsToUpdateMatchStart && alternative->m_minimumSize == 1) {
                     // index is already incremented by 1, so just store it now!
                     setMatchStart(index);
                     needsToUpdateMatchStart = false;
                 }
                 // Check whether there is sufficient input to loop. Increment the input position by
                 // one, and check. Also add in the minimum disjunction size before checking - there
                 // is no point in looping if we're just going to fail all the input checks around
                 // the next iteration.
                 ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize);
                 if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) {
                     // If the last alternative had the same minimum size as the disjunction,
                     // just simply increment input pos by 1, no adjustment based on minimum size.
                     add32(TrustedImm32(1), index);
                 } else {
                     // If the minumum for the last alternative was one greater than than that
                     // for the disjunction, we're already progressed by 1, nothing to do!
                     unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1;
                     if (delta)
                         sub32(Imm32(delta), index);
                 }
                 Jump matchFailed = jumpIfNoAvailableInput();
                 if (needsToUpdateMatchStart) {
                     if (!m_pattern.m_body->m_minimumSize)
                         setMatchStart(index);
                     else {
                         move(index, regT0);
                         sub32(Imm32(m_pattern.m_body->m_minimumSize), regT0);
                         setMatchStart(regT0);
                     }
                 }
                 // Calculate how much more input the first alternative requires than the minimum
                 // for the body as a whole. If no more is needed then we dont need an additional
                 // input check here - jump straight back up to the start of the first alternative.
                 if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize)
                     jump(beginOp->m_reentry);
                 else {
                     if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize)
                         add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index);
                     else
                         sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index);
                     checkInput().linkTo(beginOp->m_reentry, this);
                     jump(firstInputCheckFailed);
                 }
                 // We jump to here if we iterate to the point that there is insufficient input to
                 // run any matches, and need to return a failure state from JIT code.
                 matchFailed.link(this);
 #if !WTF_CPU_SPARC
                 removeCallFrame();
 #endif
 #if WTF_CPU_X86_64
                 move(TrustedImm32(int(WTF::notFound)), returnRegister);
 #else
                 move(TrustedImmPtr((void*)WTF::notFound), returnRegister);
                 move(TrustedImm32(0), returnRegister2);
 #endif
                 generateReturn();
                 break;
             }
             case OpBodyAlternativeEnd: {
                 // We should never backtrack back into a body disjunction.
                 ASSERT(m_backtrackingState.isEmpty());
                 PatternAlternative* priorAlternative = m_ops[op.m_previousOp].m_alternative;
                 m_checked += priorAlternative->m_minimumSize;
                 break;
             }
             // OpSimpleNestedAlternativeBegin/Next/End
             // OpNestedAlternativeBegin/Next/End
             //
             // Generate code for when we backtrack back out of an alternative into
             // a Begin or Next node, or when the entry input count check fails. If
             // there are more alternatives we need to jump to the next alternative,
             // if not we backtrack back out of the current set of parentheses.
             //
             // In the case of non-simple nested assertions we need to also link the
             // 'return address' appropriately to backtrack back out into the correct
             // alternative.
             case OpSimpleNestedAlternativeBegin:
             case OpSimpleNestedAlternativeNext:
             case OpNestedAlternativeBegin:
             case OpNestedAlternativeNext: {
                 YarrOp& nextOp = m_ops[op.m_nextOp];
                 bool isBegin = op.m_previousOp == notFound;
                 bool isLastAlternative = nextOp.m_nextOp == notFound;
                 ASSERT(isBegin == (op.m_op == OpSimpleNestedAlternativeBegin || op.m_op == OpNestedAlternativeBegin));
                 ASSERT(isLastAlternative == (nextOp.m_op == OpSimpleNestedAlternativeEnd || nextOp.m_op == OpNestedAlternativeEnd));
                 // Treat an input check failure the same as a failed match.
                 m_backtrackingState.append(op.m_jumps);
                 // Set the backtracks to jump to the appropriate place. We may need
                 // to link the backtracks in one of three different way depending on
                 // the type of alternative we are dealing with:
                 //  - A single alternative, with no simplings.
                 //  - The last alternative of a set of two or more.
                 //  - An alternative other than the last of a set of two or more.
                 //
                 // In the case of a single alternative on its own, we don't need to
                 // jump anywhere - if the alternative fails to match we can just
                 // continue to backtrack out of the parentheses without jumping.
                 //
                 // In the case of the last alternative in a set of more than one, we
                 // need to jump to return back out to the beginning. We'll do so by
                 // adding a jump to the End node's m_jumps list, and linking this
                 // when we come to generate the Begin node. For alternatives other
                 // than the last, we need to jump to the next alternative.
                 //
                 // If the alternative had adjusted the input position we must link
                 // backtracking to here, correct, and then jump on. If not we can
                 // link the backtracks directly to their destination.
                 if (op.m_checkAdjust) {
                     // Handle the cases where we need to link the backtracks here.
                     m_backtrackingState.link(this);
                     sub32(Imm32(op.m_checkAdjust), index);
                     if (!isLastAlternative) {
                         // An alternative that is not the last should jump to its successor.
                         jump(nextOp.m_reentry);
                     } else if (!isBegin) {
                         // The last of more than one alternatives must jump back to the beginning.
                         nextOp.m_jumps.append(jump());
                     } else {
                         // A single alternative on its own can fall through.
                         m_backtrackingState.fallthrough();
                     }
                 } else {
                     // Handle the cases where we can link the backtracks directly to their destinations.
                     if (!isLastAlternative) {
                         // An alternative that is not the last should jump to its successor.
                         m_backtrackingState.linkTo(nextOp.m_reentry, this);
                     } else if (!isBegin) {
                         // The last of more than one alternatives must jump back to the beginning.
                         m_backtrackingState.takeBacktracksToJumpList(nextOp.m_jumps, this);
                     }
                     // In the case of a single alternative on its own do nothing - it can fall through.
                 }
                 // If there is a backtrack jump from a zero length match link it here.
                 if (op.m_zeroLengthMatch.isSet())
                     m_backtrackingState.append(op.m_zeroLengthMatch);
                 // At this point we've handled the backtracking back into this node.
                 // Now link any backtracks that need to jump to here.
                 // For non-simple alternatives, link the alternative's 'return address'
                 // so that we backtrack back out into the previous alternative.
                 if (op.m_op == OpNestedAlternativeNext)
                     m_backtrackingState.append(op.m_returnAddress);
                 // If there is more than one alternative, then the last alternative will
                 // have planted a jump to be linked to the end. This jump was added to the
                 // End node's m_jumps list. If we are back at the beginning, link it here.
                 if (isBegin) {
                     YarrOp* endOp = &m_ops[op.m_nextOp];
                     while (endOp->m_nextOp != notFound) {
                         ASSERT(endOp->m_op == OpSimpleNestedAlternativeNext || endOp->m_op == OpNestedAlternativeNext);
                         endOp = &m_ops[endOp->m_nextOp];
                     }
                     ASSERT(endOp->m_op == OpSimpleNestedAlternativeEnd || endOp->m_op == OpNestedAlternativeEnd);
                     m_backtrackingState.append(endOp->m_jumps);
                 }
                 if (!isBegin) {
                     YarrOp& lastOp = m_ops[op.m_previousOp];
                     m_checked += lastOp.m_checkAdjust;
                 }
                 m_checked -= op.m_checkAdjust;
                 break;
             }
             case OpSimpleNestedAlternativeEnd:
             case OpNestedAlternativeEnd: {
                 PatternTerm* term = op.m_term;
                 // If there is a backtrack jump from a zero length match link it here.
                 if (op.m_zeroLengthMatch.isSet())
                     m_backtrackingState.append(op.m_zeroLengthMatch);
                 // If we backtrack into the end of a simple subpattern do nothing;
                 // just continue through into the last alternative. If we backtrack
                 // into the end of a non-simple set of alterntives we need to jump
                 // to the backtracking return address set up during generation.
                 if (op.m_op == OpNestedAlternativeEnd) {
                     m_backtrackingState.link(this);
                     // Plant a jump to the return address.
                     unsigned parenthesesFrameLocation = term->frameLocation;
                     unsigned alternativeFrameLocation = parenthesesFrameLocation;
                     if (term->quantityType != QuantifierFixedCount)
                         alternativeFrameLocation += YarrStackSpaceForBackTrackInfoParenthesesOnce;
                     loadFromFrameAndJump(alternativeFrameLocation);
                     // Link the DataLabelPtr associated with the end of the last
                     // alternative to this point.
                     m_backtrackingState.append(op.m_returnAddress);
                 }
                 YarrOp& lastOp = m_ops[op.m_previousOp];
                 m_checked += lastOp.m_checkAdjust;
                 break;
             }
             // OpParenthesesSubpatternOnceBegin/End
             //
             // When we are backtracking back out of a capturing subpattern we need
             // to clear the start index in the matches output array, to record that
             // this subpattern has not been captured.
             //
             // When backtracking back out of a Greedy quantified subpattern we need
             // to catch this, and try running the remainder of the alternative after
             // the subpattern again, skipping the parentheses.
             //
             // Upon backtracking back into a quantified set of parentheses we need to
             // check whether we were currently skipping the subpattern. If not, we
             // can backtrack into them, if we were we need to either backtrack back
             // out of the start of the parentheses, or jump back to the forwards
             // matching start, depending of whether the match is Greedy or NonGreedy.
             case OpParenthesesSubpatternOnceBegin: {
                 PatternTerm* term = op.m_term;
                 ASSERT(term->quantityCount == 1);
                 // We only need to backtrack to thispoint if capturing or greedy.
                 if ((term->capture() && compileMode == IncludeSubpatterns) || term->quantityType == QuantifierGreedy) {
                     m_backtrackingState.link(this);
                     // If capturing, clear the capture (we only need to reset start).
                     if (term->capture() && compileMode == IncludeSubpatterns)
                         clearSubpatternStart(term->parentheses.subpatternId);
                     // If Greedy, jump to the end.
                     if (term->quantityType == QuantifierGreedy) {
                         // Clear the flag in the stackframe indicating we ran through the subpattern.
                         unsigned parenthesesFrameLocation = term->frameLocation;
                         storeToFrame(TrustedImm32(-1), parenthesesFrameLocation);
                         // Jump to after the parentheses, skipping the subpattern.
                         jump(m_ops[op.m_nextOp].m_reentry);
                         // A backtrack from after the parentheses, when skipping the subpattern,
                         // will jump back to here.
                         op.m_jumps.link(this);
                     }
                     m_backtrackingState.fallthrough();
                 }
                 break;
             }
             case OpParenthesesSubpatternOnceEnd: {
                 PatternTerm* term = op.m_term;
                 if (term->quantityType != QuantifierFixedCount) {
                     m_backtrackingState.link(this);
                     // Check whether we should backtrack back into the parentheses, or if we
                     // are currently in a state where we had skipped over the subpattern
                     // (in which case the flag value on the stack will be -1).
                     unsigned parenthesesFrameLocation = term->frameLocation;
                     Jump hadSkipped = branch32(Equal, Address(stackPointerRegister, parenthesesFrameLocation * sizeof(void*)), TrustedImm32(-1));
                     if (term->quantityType == QuantifierGreedy) {
                         // For Greedy parentheses, we skip after having already tried going
                         // through the subpattern, so if we get here we're done.
                         YarrOp& beginOp = m_ops[op.m_previousOp];
                         beginOp.m_jumps.append(hadSkipped);
                     } else {
                         // For NonGreedy parentheses, we try skipping the subpattern first,
                         // so if we get here we need to try running through the subpattern
                         // next. Jump back to the start of the parentheses in the forwards
                         // matching path.
                         ASSERT(term->quantityType == QuantifierNonGreedy);
                         YarrOp& beginOp = m_ops[op.m_previousOp];
                         hadSkipped.linkTo(beginOp.m_reentry, this);
                     }
                     m_backtrackingState.fallthrough();
                 }
                 m_backtrackingState.append(op.m_jumps);
                 break;
             }
             // OpParenthesesSubpatternTerminalBegin/End
             //
             // Terminal subpatterns will always match - there is nothing after them to
             // force a backtrack, and they have a minimum count of 0, and as such will
             // always produce an acceptable result.
             case OpParenthesesSubpatternTerminalBegin: {
                 // We will backtrack to this point once the subpattern cannot match any
                 // more. Since no match is accepted as a successful match (we are Greedy
                 // quantified with a minimum of zero) jump back to the forwards matching
                 // path at the end.
                 YarrOp& endOp = m_ops[op.m_nextOp];
                 m_backtrackingState.linkTo(endOp.m_reentry, this);
                 break;
             }
             case OpParenthesesSubpatternTerminalEnd:
                 // We should never be backtracking to here (hence the 'terminal' in the name).
                 ASSERT(m_backtrackingState.isEmpty());
                 m_backtrackingState.append(op.m_jumps);
                 break;
             // OpParentheticalAssertionBegin/End
             case OpParentheticalAssertionBegin: {
                 PatternTerm* term = op.m_term;
                 YarrOp& endOp = m_ops[op.m_nextOp];
                 // We need to handle the backtracks upon backtracking back out
                 // of a parenthetical assertion if either we need to correct
                 // the input index, or the assertion was inverted.
                 if (op.m_checkAdjust || term->invert()) {
                      m_backtrackingState.link(this);
                     if (op.m_checkAdjust)
                         add32(Imm32(op.m_checkAdjust), index);
                     // In an inverted assertion failure to match the subpattern
                     // is treated as a successful match - jump to the end of the
                     // subpattern. We already have adjusted the input position
                     // back to that before the assertion, which is correct.
                     if (term->invert())
                         jump(endOp.m_reentry);
                     m_backtrackingState.fallthrough();
                 }
                 // The End node's jump list will contain any backtracks into
                 // the end of the assertion. Also, if inverted, we will have
                 // added the failure caused by a successful match to this.
                 m_backtrackingState.append(endOp.m_jumps);
                 m_checked += op.m_checkAdjust;
                 break;
             }
             case OpParentheticalAssertionEnd: {
                 // FIXME: We should really be clearing any nested subpattern
                 // matches on bailing out from after the pattern. Firefox has
                 // this bug too (presumably because they use YARR!)
                 // Never backtrack into an assertion; later failures bail to before the begin.
                 m_backtrackingState.takeBacktracksToJumpList(op.m_jumps, this);
                 YarrOp& lastOp = m_ops[op.m_previousOp];
                 m_checked -= lastOp.m_checkAdjust;
                 break;
             }
             case OpMatchFailed:
                 break;
             }
         } while (opIndex);
         return true;
     }
     // Compilation methods:
     // ====================
     // opCompileParenthesesSubpattern
     // Emits ops for a subpattern (set of parentheses). These consist
     // of a set of alternatives wrapped in an outer set of nodes for
     // the parentheses.
     // Supported types of parentheses are 'Once' (quantityCount == 1)
     // and 'Terminal' (non-capturing parentheses quantified as greedy
     // and infinite).
     // Alternatives will use the 'Simple' set of ops if either the
     // subpattern is terminal (in which case we will never need to
     // backtrack), or if the subpattern only contains one alternative.
     void opCompileParenthesesSubpattern(PatternTerm* term)
     {
         YarrOpCode parenthesesBeginOpCode;
         YarrOpCode parenthesesEndOpCode;
         YarrOpCode alternativeBeginOpCode = OpSimpleNestedAlternativeBegin;
         YarrOpCode alternativeNextOpCode = OpSimpleNestedAlternativeNext;
         YarrOpCode alternativeEndOpCode = OpSimpleNestedAlternativeEnd;
         // We can currently only compile quantity 1 subpatterns that are
         // not copies. We generate a copy in the case of a range quantifier,
         // e.g. /(?:x){3,9}/, or /(?:x)+/ (These are effectively expanded to
         // /(?:x){3,3}(?:x){0,6}/ and /(?:x)(?:x)*/ repectively). The problem
         // comes where the subpattern is capturing, in which case we would
         // need to restore the capture from the first subpattern upon a
         // failure in the second.
         if (term->quantityCount == 1 && !term->parentheses.isCopy) {
             // Select the 'Once' nodes.
             parenthesesBeginOpCode = OpParenthesesSubpatternOnceBegin;
             parenthesesEndOpCode = OpParenthesesSubpatternOnceEnd;
             // If there is more than one alternative we cannot use the 'simple' nodes.
             if (term->parentheses.disjunction->m_alternatives.size() != 1) {
                 alternativeBeginOpCode = OpNestedAlternativeBegin;
                 alternativeNextOpCode = OpNestedAlternativeNext;
                 alternativeEndOpCode = OpNestedAlternativeEnd;
             }
         } else if (term->parentheses.isTerminal) {
             // Terminal groups are optimized on the assumption that matching will never
             // backtrack into the terminal group. But this is false if there is more
             // than one alternative and one of the alternatives can match empty. In that
             // case, the empty match is counted as a failure, so we would need to backtrack.
             // The backtracking code doesn't handle this case correctly, so we fall back
             // to the interpreter.
             Vector<PatternAlternative*>& alternatives = term->parentheses.disjunction->m_alternatives;
             if (alternatives.size() != 1) {
                 for (unsigned i = 0; i < alternatives.size(); ++i) {
                     if (alternatives[i]->m_minimumSize == 0) {
                         m_shouldFallBack = true;
                         return;
                     }
                 }
             }
             // Select the 'Terminal' nodes.
             parenthesesBeginOpCode = OpParenthesesSubpatternTerminalBegin;
             parenthesesEndOpCode = OpParenthesesSubpatternTerminalEnd;
         } else {
             // This subpattern is not supported by the JIT.
             m_shouldFallBack = true;
             return;
         }
         size_t parenBegin = m_ops.size();
         m_ops.append(parenthesesBeginOpCode);
         m_ops.append(alternativeBeginOpCode);
         m_ops.last().m_previousOp = notFound;
         m_ops.last().m_term = term;
         Vector<PatternAlternative*>& alternatives =  term->parentheses.disjunction->m_alternatives;
         for (unsigned i = 0; i < alternatives.size(); ++i) {
             size_t lastOpIndex = m_ops.size() - 1;
             PatternAlternative* nestedAlternative = alternatives[i];
             opCompileAlternative(nestedAlternative);
             size_t thisOpIndex = m_ops.size();
             m_ops.append(YarrOp(alternativeNextOpCode));
             YarrOp& lastOp = m_ops[lastOpIndex];
             YarrOp& thisOp = m_ops[thisOpIndex];
             lastOp.m_alternative = nestedAlternative;
             lastOp.m_nextOp = thisOpIndex;
             thisOp.m_previousOp = lastOpIndex;
             thisOp.m_term = term;
         }
         YarrOp& lastOp = m_ops.last();
         ASSERT(lastOp.m_op == alternativeNextOpCode);
         lastOp.m_op = alternativeEndOpCode;
         lastOp.m_alternative = 0;
         lastOp.m_nextOp = notFound;
         size_t parenEnd = m_ops.size();
         m_ops.append(parenthesesEndOpCode);
         m_ops[parenBegin].m_term = term;
         m_ops[parenBegin].m_previousOp = notFound;
         m_ops[parenBegin].m_nextOp = parenEnd;
         m_ops[parenEnd].m_term = term;
         m_ops[parenEnd].m_previousOp = parenBegin;
         m_ops[parenEnd].m_nextOp = notFound;
     }
     // opCompileParentheticalAssertion
     // Emits ops for a parenthetical assertion. These consist of an
     // OpSimpleNestedAlternativeBegin/Next/End set of nodes wrapping
     // the alternatives, with these wrapped by an outer pair of
     // OpParentheticalAssertionBegin/End nodes.
     // We can always use the OpSimpleNestedAlternative nodes in the
     // case of parenthetical assertions since these only ever match
     // once, and will never backtrack back into the assertion.
     void opCompileParentheticalAssertion(PatternTerm* term)
     {
         size_t parenBegin = m_ops.size();
         m_ops.append(OpParentheticalAssertionBegin);
         m_ops.append(OpSimpleNestedAlternativeBegin);
         m_ops.last().m_previousOp = notFound;
         m_ops.last().m_term = term;
         Vector<PatternAlternative*>& alternatives =  term->parentheses.disjunction->m_alternatives;
         for (unsigned i = 0; i < alternatives.size(); ++i) {
             size_t lastOpIndex = m_ops.size() - 1;
             PatternAlternative* nestedAlternative = alternatives[i];
             opCompileAlternative(nestedAlternative);
             size_t thisOpIndex = m_ops.size();
             m_ops.append(YarrOp(OpSimpleNestedAlternativeNext));
             YarrOp& lastOp = m_ops[lastOpIndex];
             YarrOp& thisOp = m_ops[thisOpIndex];
             lastOp.m_alternative = nestedAlternative;
             lastOp.m_nextOp = thisOpIndex;
             thisOp.m_previousOp = lastOpIndex;
             thisOp.m_term = term;
         }
         YarrOp& lastOp = m_ops.last();
         ASSERT(lastOp.m_op == OpSimpleNestedAlternativeNext);
         lastOp.m_op = OpSimpleNestedAlternativeEnd;
         lastOp.m_alternative = 0;
         lastOp.m_nextOp = notFound;
         size_t parenEnd = m_ops.size();
         m_ops.append(OpParentheticalAssertionEnd);
         m_ops[parenBegin].m_term = term;
         m_ops[parenBegin].m_previousOp = notFound;
         m_ops[parenBegin].m_nextOp = parenEnd;
         m_ops[parenEnd].m_term = term;
         m_ops[parenEnd].m_previousOp = parenBegin;
         m_ops[parenEnd].m_nextOp = notFound;
     }
     // opCompileAlternative
     // Called to emit nodes for all terms in an alternative.
     void opCompileAlternative(PatternAlternative* alternative)
     {
         optimizeAlternative(alternative);
         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
             PatternTerm* term = &alternative->m_terms[i];
             switch (term->type) {
             case PatternTerm::TypeParenthesesSubpattern:
                 opCompileParenthesesSubpattern(term);
                 break;
             case PatternTerm::TypeParentheticalAssertion:
                 opCompileParentheticalAssertion(term);
                 break;
             default:
                 m_ops.append(term);
             }
         }
     }
     // opCompileBody
     // This method compiles the body disjunction of the regular expression.
     // The body consists of two sets of alternatives - zero or more 'once
     // through' (BOL anchored) alternatives, followed by zero or more
     // repeated alternatives.
     // For each of these two sets of alteratives, if not empty they will be
     // wrapped in a set of OpBodyAlternativeBegin/Next/End nodes (with the
     // 'begin' node referencing the first alternative, and 'next' nodes
     // referencing any further alternatives. The begin/next/end nodes are
     // linked together in a doubly linked list. In the case of repeating
     // alternatives, the end node is also linked back to the beginning.
     // If no repeating alternatives exist, then a OpMatchFailed node exists
     // to return the failing result.
     void opCompileBody(PatternDisjunction* disjunction)
     {
         Vector<PatternAlternative*>& alternatives =  disjunction->m_alternatives;
         size_t currentAlternativeIndex = 0;
         // Emit the 'once through' alternatives.
         if (alternatives.size() && alternatives[0]->onceThrough()) {
             m_ops.append(YarrOp(OpBodyAlternativeBegin));
             m_ops.last().m_previousOp = notFound;
             do {
                 size_t lastOpIndex = m_ops.size() - 1;
                 PatternAlternative* alternative = alternatives[currentAlternativeIndex];
                 opCompileAlternative(alternative);
                 size_t thisOpIndex = m_ops.size();
                 m_ops.append(YarrOp(OpBodyAlternativeNext));
                 YarrOp& lastOp = m_ops[lastOpIndex];
                 YarrOp& thisOp = m_ops[thisOpIndex];
                 lastOp.m_alternative = alternative;
                 lastOp.m_nextOp = thisOpIndex;
                 thisOp.m_previousOp = lastOpIndex;
                 ++currentAlternativeIndex;
             } while (currentAlternativeIndex < alternatives.size() && alternatives[currentAlternativeIndex]->onceThrough());
             YarrOp& lastOp = m_ops.last();
             ASSERT(lastOp.m_op == OpBodyAlternativeNext);
             lastOp.m_op = OpBodyAlternativeEnd;
             lastOp.m_alternative = 0;
             lastOp.m_nextOp = notFound;
         }
         if (currentAlternativeIndex == alternatives.size()) {
             m_ops.append(YarrOp(OpMatchFailed));
             return;
         }
         // Emit the repeated alternatives.
         size_t repeatLoop = m_ops.size();
         m_ops.append(YarrOp(OpBodyAlternativeBegin));
         m_ops.last().m_previousOp = notFound;
         do {
             size_t lastOpIndex = m_ops.size() - 1;
             PatternAlternative* alternative = alternatives[currentAlternativeIndex];
             ASSERT(!alternative->onceThrough());
             opCompileAlternative(alternative);
             size_t thisOpIndex = m_ops.size();
             m_ops.append(YarrOp(OpBodyAlternativeNext));
             YarrOp& lastOp = m_ops[lastOpIndex];
             YarrOp& thisOp = m_ops[thisOpIndex];
             lastOp.m_alternative = alternative;
             lastOp.m_nextOp = thisOpIndex;
             thisOp.m_previousOp = lastOpIndex;
             ++currentAlternativeIndex;
         } while (currentAlternativeIndex < alternatives.size());
         YarrOp& lastOp = m_ops.last();
         ASSERT(lastOp.m_op == OpBodyAlternativeNext);
         lastOp.m_op = OpBodyAlternativeEnd;
         lastOp.m_alternative = 0;
         lastOp.m_nextOp = repeatLoop;
     }
     void generateEnter()
     {
 #if WTF_CPU_X86_64
         push(X86Registers::ebp);
         move(stackPointerRegister, X86Registers::ebp);
         push(X86Registers::ebx);
         // The ABI doesn't guarantee the upper bits are zero on unsigned arguments, so clear them ourselves.
         zeroExtend32ToPtr(index, index);
         zeroExtend32ToPtr(length, length);
 #elif WTF_CPU_X86
         push(X86Registers::ebp);
         move(stackPointerRegister, X86Registers::ebp);
         // TODO: do we need spill registers to fill the output pointer if there are no sub captures?
         push(X86Registers::ebx);
         push(X86Registers::edi);
         push(X86Registers::esi);
         // load output into edi (2 = saved ebp + return address).
 # if WTF_COMPILER_MSVC || WTF_COMPILER_SUNCC
         loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), input);
         loadPtr(Address(X86Registers::ebp, 3 * sizeof(void*)), index);
         loadPtr(Address(X86Registers::ebp, 4 * sizeof(void*)), length);
         if (compileMode == IncludeSubpatterns)
             loadPtr(Address(X86Registers::ebp, 5 * sizeof(void*)), output);
 # else
         if (compileMode == IncludeSubpatterns)
             loadPtr(Address(X86Registers::ebp, 2 * sizeof(void*)), output);
 # endif
 #elif WTF_CPU_ARM
         push(ARMRegisters::r4);
         push(ARMRegisters::r5);
         push(ARMRegisters::r6);
 # if WTF_CPU_ARM_TRADITIONAL
         push(ARMRegisters::r8); // scratch register
 # endif
         if (compileMode == IncludeSubpatterns)
             move(ARMRegisters::r3, output);
 #elif WTF_CPU_SH4
         push(SH4Registers::r11);
         push(SH4Registers::r13);
 #elif WTF_CPU_SPARC
         save(Imm32(-m_pattern.m_body->m_callFrameSize * sizeof(void*)));
 #elif WTF_CPU_MIPS
         // Do nothing.
 #endif
     }
     void generateReturn()
     {
 #if WTF_CPU_X86_64
         pop(X86Registers::ebx);
         pop(X86Registers::ebp);
 #elif WTF_CPU_X86
         pop(X86Registers::esi);
         pop(X86Registers::edi);
         pop(X86Registers::ebx);
         pop(X86Registers::ebp);
 #elif WTF_CPU_ARM
 # if WTF_CPU_ARM_TRADITIONAL
         pop(ARMRegisters::r8); // scratch register
 # endif
         pop(ARMRegisters::r6);
         pop(ARMRegisters::r5);
         pop(ARMRegisters::r4);
 #elif WTF_CPU_SH4
         pop(SH4Registers::r13);
         pop(SH4Registers::r11);
 #elif WTF_CPU_SPARC
         ret_and_restore();
         return;
 #elif WTF_CPU_MIPS
         // Do nothing
 #endif
         ret();
     }
 public:
     YarrGenerator(YarrPattern& pattern, YarrCharSize charSize)
         : m_pattern(pattern)
         , m_charSize(charSize)
         , m_charScale(m_charSize == Char8 ? TimesOne: TimesTwo)
         , m_shouldFallBack(false)
         , m_checked(0)
     {
     }
     void compile(JSGlobalData* globalData, YarrCodeBlock& jitObject)
     {
         generateEnter();
         Jump hasInput = checkInput();
 #if WTF_CPU_X86_64
         move(TrustedImm32(int(WTF::notFound)), returnRegister);
 #else
         move(TrustedImmPtr((void*)WTF::notFound), returnRegister);
         move(TrustedImm32(0), returnRegister2);
 #endif
         generateReturn();
         hasInput.link(this);
         if (compileMode == IncludeSubpatterns) {
             for (unsigned i = 0; i < m_pattern.m_numSubpatterns + 1; ++i)
                 store32(TrustedImm32(-1), Address(output, (i << 1) * sizeof(int)));
         }
         if (!m_pattern.m_body->m_hasFixedSize)
             setMatchStart(index);
         initCallFrame();
         // Compile the pattern to the internal 'YarrOp' representation.
         opCompileBody(m_pattern.m_body);
         // If we encountered anything we can't handle in the JIT code
         // (e.g. backreferences) then return early.
         if (m_shouldFallBack) {
             jitObject.setFallBack(true);
             return;
         }
         if (!generate() || !backtrack()) {
             jitObject.setFallBack(true);
             return;
         }
         // Link & finalize the code.
         ExecutablePool *pool;
         bool ok;
         LinkBuffer linkBuffer(this, globalData->regexAllocator, &pool, &ok, REGEXP_CODE);
         // Attempt to detect OOM during linkBuffer creation.
         if (linkBuffer.unsafeCode() == nullptr) {
             jitObject.setFallBack(true);
             return;
         }
         m_backtrackingState.linkDataLabels(linkBuffer);
         if (compileMode == MatchOnly) {
 #if YARR_8BIT_CHAR_SUPPORT
             if (m_charSize == Char8)
                 jitObject.set8BitCodeMatchOnly(linkBuffer.finalizeCode());
             else
 #endif
                 jitObject.set16BitCodeMatchOnly(linkBuffer.finalizeCode());
         } else {
 #if YARR_8BIT_CHAR_SUPPORT
             if (m_charSize == Char8)
                 jitObject.set8BitCode(linkBuffer.finalizeCode());
             else
 #endif
                 jitObject.set16BitCode(linkBuffer.finalizeCode());
         }
         jitObject.setFallBack(m_shouldFallBack);
     }
 private:
     YarrPattern& m_pattern;
     YarrCharSize m_charSize;
     Scale m_charScale;
     // Used to detect regular expression constructs that are not currently
     // supported in the JIT; fall back to the interpreter when this is detected.
     bool m_shouldFallBack;
     // The regular expression expressed as a linear sequence of operations.
     Vector<YarrOp, 128> m_ops;
     // This records the current input offset being applied due to the current
     // set of alternatives we are nested within. E.g. when matching the
     // character 'b' within the regular expression /abc/, we will know that
     // the minimum size for the alternative is 3, checked upon entry to the
     // alternative, and that 'b' is at offset 1 from the start, and as such
     // when matching 'b' we need to apply an offset of -2 to the load.
     //
     // FIXME: This should go away. Rather than tracking this value throughout
     // code generation, we should gather this information up front & store it
     // on the YarrOp structure.
     int m_checked;
     // This class records state whilst generating the backtracking path of code.
     BacktrackingState m_backtrackingState;
 };
 void jitCompile(YarrPattern& pattern, YarrCharSize charSize, JSGlobalData* globalData, YarrCodeBlock& jitObject, YarrJITCompileMode mode)
 {
     if (mode == MatchOnly)
         YarrGenerator<MatchOnly>(pattern, charSize).compile(globalData, jitObject);
     else
         YarrGenerator<IncludeSubpatterns>(pattern, charSize).compile(globalData, jitObject);
 }
 }}
 #endif

The Tor Browser / annotate

js/src/yarr/YarrJIT.cpp@6474c204b198 (annotated)

js/src/yarr/YarrJIT.cpp