diff options
Diffstat (limited to 'JavaScriptCore/yarr/RegexJIT.cpp')
| -rw-r--r-- | JavaScriptCore/yarr/RegexJIT.cpp | 467 |
1 files changed, 298 insertions, 169 deletions
diff --git a/JavaScriptCore/yarr/RegexJIT.cpp b/JavaScriptCore/yarr/RegexJIT.cpp index fcb8d86..acbd458 100644 --- a/JavaScriptCore/yarr/RegexJIT.cpp +++ b/JavaScriptCore/yarr/RegexJIT.cpp @@ -31,8 +31,7 @@ #include "LinkBuffer.h" #include "MacroAssembler.h" #include "RegexCompiler.h" - -#include "pcre.h" // temporary, remove when fallback is removed. +#include "RegexInterpreter.h" // temporary, remove when fallback is removed. #if ENABLE(YARR_JIT) @@ -40,7 +39,6 @@ using namespace WTF; namespace JSC { namespace Yarr { - class RegexGenerator : private MacroAssembler { friend void jitCompileRegex(JSGlobalData* globalData, RegexCodeBlock& jitObject, const UString& pattern, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline); @@ -54,6 +52,16 @@ class RegexGenerator : private MacroAssembler { static const RegisterID regT1 = ARMRegisters::r6; static const RegisterID returnRegister = ARMRegisters::r0; +#elif 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; #elif CPU(X86) static const RegisterID input = X86Registers::eax; static const RegisterID index = X86Registers::edx; @@ -145,6 +153,11 @@ class RegexGenerator : private MacroAssembler { void matchCharacterClass(RegisterID character, JumpList& matchDest, const CharacterClass* charClass) { + if (charClass->m_table) { + ExtendedAddress tableEntry(character, reinterpret_cast<intptr_t>(charClass->m_table->m_table)); + matchDest.append(branchTest8(charClass->m_table->m_inverted ? Zero : NonZero, tableEntry)); + return; + } Jump unicodeFail; if (charClass->m_matchesUnicode.size() || charClass->m_rangesUnicode.size()) { Jump isAscii = branch32(LessThanOrEqual, character, Imm32(0x7f)); @@ -331,6 +344,15 @@ class RegexGenerator : private MacroAssembler { ASSERT(alternativeValid()); return alternative()->m_terms[t]; } + bool isLastTerm() + { + ASSERT(alternativeValid()); + return (t + 1) == alternative()->m_terms.size(); + } + bool isMainDisjunction() + { + return !disjunction->m_parent; + } PatternTerm& lookaheadTerm() { @@ -599,10 +621,14 @@ class RegexGenerator : private MacroAssembler { ASSERT(!m_pattern.m_ignoreCase || (Unicode::toLower(ch) == Unicode::toUpper(ch))); failures.append(jumpIfCharNotEquals(ch, state.inputOffset())); } + add32(Imm32(1), countRegister); add32(Imm32(1), index); - branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this); - failures.append(jump()); + if (term.quantityCount != 0xffffffff) { + branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this); + failures.append(jump()); + } else + jump(loop); Label backtrackBegin(this); loadFromFrame(term.frameLocation, countRegister); @@ -636,7 +662,8 @@ class RegexGenerator : private MacroAssembler { loadFromFrame(term.frameLocation, countRegister); atEndOfInput().linkTo(hardFail, this); - branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail); + if (term.quantityCount != 0xffffffff) + branch32(Equal, countRegister, Imm32(term.quantityCount), hardFail); if (m_pattern.m_ignoreCase && isASCIIAlpha(ch)) { readCharacter(state.inputOffset(), character); or32(Imm32(32), character); @@ -722,8 +749,11 @@ class RegexGenerator : private MacroAssembler { add32(Imm32(1), countRegister); add32(Imm32(1), index); - branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this); - failures.append(jump()); + if (term.quantityCount != 0xffffffff) { + branch32(NotEqual, countRegister, Imm32(term.quantityCount)).linkTo(loop, this); + failures.append(jump()); + } else + jump(loop); Label backtrackBegin(this); loadFromFrame(term.frameLocation, countRegister); @@ -880,7 +910,7 @@ class RegexGenerator : private MacroAssembler { PatternDisjunction* disjunction = term.parentheses.disjunction; ASSERT(term.quantityCount == 1); - unsigned preCheckedCount = ((term.quantityCount == 1) && (term.quantityType == QuantifierFixedCount)) ? disjunction->m_minimumSize : 0; + unsigned preCheckedCount = (term.quantityType == QuantifierFixedCount) ? disjunction->m_minimumSize : 0; unsigned parenthesesFrameLocation = term.frameLocation; unsigned alternativeFrameLocation = parenthesesFrameLocation; @@ -899,12 +929,12 @@ class RegexGenerator : private MacroAssembler { Jump nonGreedySkipParentheses; Label nonGreedyTryParentheses; if (term.quantityType == QuantifierGreedy) - storeToFrame(Imm32(1), parenthesesFrameLocation); + storeToFrame(index, parenthesesFrameLocation); else if (term.quantityType == QuantifierNonGreedy) { - storeToFrame(Imm32(0), parenthesesFrameLocation); + storeToFrame(Imm32(-1), parenthesesFrameLocation); nonGreedySkipParentheses = jump(); nonGreedyTryParentheses = label(); - storeToFrame(Imm32(1), parenthesesFrameLocation); + storeToFrame(index, parenthesesFrameLocation); } // store the match start index @@ -922,41 +952,31 @@ class RegexGenerator : private MacroAssembler { TermGenerationState parenthesesState(disjunction, state.checkedTotal); generateParenthesesDisjunction(state.term(), parenthesesState, alternativeFrameLocation); - // store the match end index - if (term.invertOrCapture) { - int inputOffset = state.inputOffset(); - if (inputOffset) { - move(index, indexTemporary); - add32(Imm32(state.inputOffset()), indexTemporary); - store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int))); - } else - store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int))); - } - Jump success = jump(); + Jump success = (term.quantityType == QuantifierFixedCount) ? + jump() : + branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesFrameLocation * sizeof(void*)))); // A failure AFTER the parens jumps here Label backtrackFromAfterParens(this); if (term.quantityType == QuantifierGreedy) { - // If this is zero we have now tested with both with and without the parens. + // If this is -1 we have now tested with both with and without the parens. loadFromFrame(parenthesesFrameLocation, indexTemporary); - state.jumpToBacktrack(branchTest32(Zero, indexTemporary), this); + state.jumpToBacktrack(branch32(Equal, indexTemporary, Imm32(-1)), this); } else if (term.quantityType == QuantifierNonGreedy) { - // If this is zero we have now tested with both with and without the parens. + // If this is -1 we have now tested without the parens, now test with. loadFromFrame(parenthesesFrameLocation, indexTemporary); - branchTest32(Zero, indexTemporary).linkTo(nonGreedyTryParentheses, this); + branch32(Equal, indexTemporary, Imm32(-1)).linkTo(nonGreedyTryParentheses, this); } parenthesesState.plantJumpToBacktrackIfExists(this); // A failure WITHIN the parens jumps here parenthesesState.linkAlternativeBacktracks(this); - if (term.invertOrCapture) { + if (term.invertOrCapture) store32(Imm32(-1), Address(output, (term.parentheses.subpatternId << 1) * sizeof(int))); - store32(Imm32(-1), Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int))); - } if (term.quantityType == QuantifierGreedy) - storeToFrame(Imm32(0), parenthesesFrameLocation); + storeToFrame(Imm32(-1), parenthesesFrameLocation); else state.jumpToBacktrack(jump(), this); @@ -964,9 +984,67 @@ class RegexGenerator : private MacroAssembler { if (term.quantityType == QuantifierNonGreedy) nonGreedySkipParentheses.link(this); success.link(this); + + // store the match end index + if (term.invertOrCapture) { + int inputOffset = state.inputOffset(); + if (inputOffset) { + move(index, indexTemporary); + add32(Imm32(state.inputOffset()), indexTemporary); + store32(indexTemporary, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int))); + } else + store32(index, Address(output, ((term.parentheses.subpatternId << 1) + 1) * sizeof(int))); + } } } + void generateParenthesesGreedyNoBacktrack(TermGenerationState& state) + { + PatternTerm& parenthesesTerm = state.term(); + PatternDisjunction* disjunction = parenthesesTerm.parentheses.disjunction; + ASSERT(parenthesesTerm.type == PatternTerm::TypeParenthesesSubpattern); + ASSERT(parenthesesTerm.quantityCount != 1); // Handled by generateParenthesesSingle. + + TermGenerationState parenthesesState(disjunction, state.checkedTotal); + + Label matchAgain(this); + + storeToFrame(index, parenthesesTerm.frameLocation); // Save the current index to check for zero len matches later. + + for (parenthesesState.resetAlternative(); parenthesesState.alternativeValid(); parenthesesState.nextAlternative()) { + + PatternAlternative* alternative = parenthesesState.alternative(); + optimizeAlternative(alternative); + + int countToCheck = alternative->m_minimumSize; + if (countToCheck) { + parenthesesState.addBacktrackJump(jumpIfNoAvailableInput(countToCheck)); + parenthesesState.checkedTotal += countToCheck; + } + + for (parenthesesState.resetTerm(); parenthesesState.termValid(); parenthesesState.nextTerm()) + generateTerm(parenthesesState); + + // If we get here, we matched! If the index advanced then try to match more since limit isn't supported yet. + branch32(NotEqual, index, Address(stackPointerRegister, (parenthesesTerm.frameLocation * sizeof(void*))), matchAgain); + + // If we get here we matched, but we matched "" - cannot accept this alternative as is, so either backtrack, + // or fall through to try the next alternative if no backtrack is available. + parenthesesState.plantJumpToBacktrackIfExists(this); + + parenthesesState.linkAlternativeBacktracks(this); + // We get here if the alternative fails to match - fall through to the next iteration, or out of the loop. + + if (countToCheck) { + sub32(Imm32(countToCheck), index); + parenthesesState.checkedTotal -= countToCheck; + } + } + + // If the last alternative falls through to here, we have a failed match... + // Which means that we match whatever we have matched up to this point (even if nothing). + } + void generateParentheticalAssertion(TermGenerationState& state) { PatternTerm& term = state.term(); @@ -1078,17 +1156,19 @@ class RegexGenerator : private MacroAssembler { break; case PatternTerm::TypeBackReference: - m_generationFailed = true; + m_shouldFallBack = true; break; case PatternTerm::TypeForwardReference: break; case PatternTerm::TypeParenthesesSubpattern: - if ((term.quantityCount == 1) && !term.parentheses.isCopy) + if (term.quantityCount == 1 && !term.parentheses.isCopy) generateParenthesesSingle(state); + else if (term.parentheses.isTerminal) + generateParenthesesGreedyNoBacktrack(state); else - m_generationFailed = true; + m_shouldFallBack = true; break; case PatternTerm::TypeParentheticalAssertion: @@ -1102,21 +1182,26 @@ class RegexGenerator : private MacroAssembler { TermGenerationState state(disjunction, 0); state.resetAlternative(); - // Plant a check to see if there is sufficient input available to run the first alternative. - // Jumping back to the label 'firstAlternative' will get to this check, jumping to - // 'firstAlternativeInputChecked' will jump directly to matching the alternative having - // skipped this check. - - Label firstAlternative(this); - // check availability for the next alternative int countCheckedForCurrentAlternative = 0; int countToCheckForFirstAlternative = 0; bool hasShorterAlternatives = false; + bool setRepeatAlternativeLabels = false; JumpList notEnoughInputForPreviousAlternative; + Label firstAlternative; + Label firstAlternativeInputChecked; + // The label 'firstAlternative' is used to plant a check to see if there is + // sufficient input available to run the first repeating alternative. + // The label 'firstAlternativeInputChecked' will jump directly to matching + // the first repeating alternative having skipped this check. + if (state.alternativeValid()) { PatternAlternative* alternative = state.alternative(); + if (!alternative->onceThrough()) { + firstAlternative = Label(this); + setRepeatAlternativeLabels = true; + } countToCheckForFirstAlternative = alternative->m_minimumSize; state.checkedTotal += countToCheckForFirstAlternative; if (countToCheckForFirstAlternative) @@ -1124,31 +1209,35 @@ class RegexGenerator : private MacroAssembler { countCheckedForCurrentAlternative = countToCheckForFirstAlternative; } - Label firstAlternativeInputChecked(this); + if (setRepeatAlternativeLabels) + firstAlternativeInputChecked = Label(this); while (state.alternativeValid()) { - // Track whether any alternatives are shorter than the first one. - hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative); - PatternAlternative* alternative = state.alternative(); optimizeAlternative(alternative); + // Track whether any alternatives are shorter than the first one. + if (!alternative->onceThrough()) + hasShorterAlternatives = hasShorterAlternatives || (countCheckedForCurrentAlternative < countToCheckForFirstAlternative); + for (state.resetTerm(); state.termValid(); state.nextTerm()) generateTerm(state); // If we get here, the alternative matched. if (m_pattern.m_body->m_callFrameSize) addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister); - + ASSERT(index != returnRegister); if (m_pattern.m_body->m_hasFixedSize) { move(index, returnRegister); if (alternative->m_minimumSize) sub32(Imm32(alternative->m_minimumSize), returnRegister); + + store32(returnRegister, output); } else - pop(returnRegister); + load32(Address(output), returnRegister); + store32(index, Address(output, 4)); - store32(returnRegister, output); generateReturn(); @@ -1157,47 +1246,75 @@ class RegexGenerator : private MacroAssembler { // if there are any more alternatives, plant the check for input before looping. if (state.alternativeValid()) { PatternAlternative* nextAlternative = state.alternative(); - int countToCheckForNextAlternative = nextAlternative->m_minimumSize; - - if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one. + if (!setRepeatAlternativeLabels && !nextAlternative->onceThrough()) { + // We have handled non-repeating alternatives, jump to next iteration + // and loop over repeating alternatives. + state.jumpToBacktrack(jump(), this); + + countToCheckForFirstAlternative = nextAlternative->m_minimumSize; + // If we get here, there the last input checked failed. notEnoughInputForPreviousAlternative.link(this); - - // Check if sufficent input available to run the next alternative - notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative)); - // We are now in the correct state to enter the next alternative; this add is only required - // to mirror and revert operation of the sub32, just below. - add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index); - - // If we get here, there the last input checked passed. + state.linkAlternativeBacktracks(this); - // No need to check if we can run the next alternative, since it is shorter - - // just update index. - sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index); - } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one. - // If we get here, there the last input checked failed. - // If there is insufficient input to run the current alternative, and the next alternative is longer, - // then there is definitely not enough input to run it - don't even check. Just adjust index, as if - // we had checked. - notEnoughInputForPreviousAlternative.link(this); - add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index); - notEnoughInputForPreviousAlternative.append(jump()); - // The next alternative is longer than the current one; check the difference. - state.linkAlternativeBacktracks(this); - notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative)); - } else { // CASE 3: Both alternatives are the same length. - ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative); + // Back up to start the looping alternatives. + if (countCheckedForCurrentAlternative) + sub32(Imm32(countCheckedForCurrentAlternative), index); + + firstAlternative = Label(this); + + state.checkedTotal = countToCheckForFirstAlternative; + if (countToCheckForFirstAlternative) + notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForFirstAlternative)); + + countCheckedForCurrentAlternative = countToCheckForFirstAlternative; + + firstAlternativeInputChecked = Label(this); - // If the next alterative is the same length as this one, then no need to check the input - - // if there was sufficent input to run the current alternative then there is sufficient - // input to run the next one; if not, there isn't. - state.linkAlternativeBacktracks(this); + setRepeatAlternativeLabels = true; + } else { + int countToCheckForNextAlternative = nextAlternative->m_minimumSize; + + if (countCheckedForCurrentAlternative > countToCheckForNextAlternative) { // CASE 1: current alternative was longer than the next one. + // If we get here, then the last input checked failed. + notEnoughInputForPreviousAlternative.link(this); + + // Check if sufficent input available to run the next alternative + notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative)); + // We are now in the correct state to enter the next alternative; this add is only required + // to mirror and revert operation of the sub32, just below. + add32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index); + + // If we get here, then the last input checked passed. + state.linkAlternativeBacktracks(this); + // No need to check if we can run the next alternative, since it is shorter - + // just update index. + sub32(Imm32(countCheckedForCurrentAlternative - countToCheckForNextAlternative), index); + } else if (countCheckedForCurrentAlternative < countToCheckForNextAlternative) { // CASE 2: next alternative is longer than the current one. + // If we get here, then the last input checked failed. + // If there is insufficient input to run the current alternative, and the next alternative is longer, + // then there is definitely not enough input to run it - don't even check. Just adjust index, as if + // we had checked. + notEnoughInputForPreviousAlternative.link(this); + add32(Imm32(countToCheckForNextAlternative - countCheckedForCurrentAlternative), index); + notEnoughInputForPreviousAlternative.append(jump()); + + // The next alternative is longer than the current one; check the difference. + state.linkAlternativeBacktracks(this); + notEnoughInputForPreviousAlternative.append(jumpIfNoAvailableInput(countToCheckForNextAlternative - countCheckedForCurrentAlternative)); + } else { // CASE 3: Both alternatives are the same length. + ASSERT(countCheckedForCurrentAlternative == countToCheckForNextAlternative); + + // If the next alterative is the same length as this one, then no need to check the input - + // if there was sufficent input to run the current alternative then there is sufficient + // input to run the next one; if not, there isn't. + state.linkAlternativeBacktracks(this); + } + state.checkedTotal -= countCheckedForCurrentAlternative; + countCheckedForCurrentAlternative = countToCheckForNextAlternative; + state.checkedTotal += countCheckedForCurrentAlternative; } - - state.checkedTotal -= countCheckedForCurrentAlternative; - countCheckedForCurrentAlternative = countToCheckForNextAlternative; - state.checkedTotal += countCheckedForCurrentAlternative; } } @@ -1205,81 +1322,86 @@ class RegexGenerator : private MacroAssembler { state.checkedTotal -= countCheckedForCurrentAlternative; - // How much more input need there be to be able to retry from the first alternative? - // examples: - // /yarr_jit/ or /wrec|pcre/ - // In these examples we need check for one more input before looping. - // /yarr_jit|pcre/ - // In this case we need check for 5 more input to loop (+4 to allow for the first alterative - // being four longer than the last alternative checked, and another +1 to effectively move - // the start position along by one). - // /yarr|rules/ or /wrec|notsomuch/ - // In these examples, provided that there was sufficient input to have just been matching for - // the second alternative we can loop without checking for available input (since the second - // alternative is longer than the first). In the latter example we need to decrement index - // (by 4) so the start position is only progressed by 1 from the last iteration. - int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1; - - // First, deal with the cases where there was sufficient input to try the last alternative. - if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below. - state.linkAlternativeBacktracks(this); - else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop! - state.linkAlternativeBacktracksTo(firstAlternativeInputChecked, this); - else { // no need to check the input, but we do have some bookkeeping to do first. + if (!setRepeatAlternativeLabels) { + // If there are no alternatives that need repeating (all are marked 'onceThrough') then just link + // the match failures to this point, and fall through to the return below. state.linkAlternativeBacktracks(this); + notEnoughInputForPreviousAlternative.link(this); + } else { + // How much more input need there be to be able to retry from the first alternative? + // examples: + // /yarr_jit/ or /wrec|pcre/ + // In these examples we need check for one more input before looping. + // /yarr_jit|pcre/ + // In this case we need check for 5 more input to loop (+4 to allow for the first alterative + // being four longer than the last alternative checked, and another +1 to effectively move + // the start position along by one). + // /yarr|rules/ or /wrec|notsomuch/ + // In these examples, provided that there was sufficient input to have just been matching for + // the second alternative we can loop without checking for available input (since the second + // alternative is longer than the first). In the latter example we need to decrement index + // (by 4) so the start position is only progressed by 1 from the last iteration. + int incrementForNextIter = (countToCheckForFirstAlternative - countCheckedForCurrentAlternative) + 1; + + // First, deal with the cases where there was sufficient input to try the last alternative. + if (incrementForNextIter > 0) // We need to check for more input anyway, fall through to the checking below. + state.linkAlternativeBacktracks(this); + else if (m_pattern.m_body->m_hasFixedSize && !incrementForNextIter) // No need to update anything, link these backtracks straight to the to pof the loop! + state.linkAlternativeBacktracksTo(firstAlternativeInputChecked, this); + else { // no need to check the input, but we do have some bookkeeping to do first. + state.linkAlternativeBacktracks(this); - // Where necessary update our preserved start position. - if (!m_pattern.m_body->m_hasFixedSize) { - move(index, regT0); - sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0); - poke(regT0, m_pattern.m_body->m_callFrameSize); + // Where necessary update our preserved start position. + if (!m_pattern.m_body->m_hasFixedSize) { + move(index, regT0); + sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0); + store32(regT0, Address(output)); + } + + // Update index if necessary, and loop (without checking). + if (incrementForNextIter) + add32(Imm32(incrementForNextIter), index); + jump().linkTo(firstAlternativeInputChecked, this); } - // Update index if necessary, and loop (without checking). - if (incrementForNextIter) - add32(Imm32(incrementForNextIter), index); - jump().linkTo(firstAlternativeInputChecked, this); + notEnoughInputForPreviousAlternative.link(this); + // Update our idea of the start position, if we're tracking this. + if (!m_pattern.m_body->m_hasFixedSize) { + if (countCheckedForCurrentAlternative - 1) { + move(index, regT0); + sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0); + store32(regT0, Address(output)); + } else + store32(index, Address(output)); + } + + // Check if there is sufficent input to run the first alternative again. + jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this); + // No - insufficent input to run the first alteranative, are there any other alternatives we + // might need to check? If so, the last check will have left the index incremented by + // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative + // LESS input is available, to have the effect of just progressing the start position by 1 + // from the last iteration. If this check passes we can just jump up to the check associated + // with the first alternative in the loop. This is a bit sad, since we'll end up trying the + // first alternative again, and this check will fail (otherwise the check planted just above + // here would have passed). This is a bit sad, however it saves trying to do something more + // complex here in compilation, and in the common case we should end up coallescing the checks. + // + // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least + // of the minimum-alternative-lengths. E.g. if I have two alternatives of length 200 and 150, + // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there + // is sufficient input to run either alternative (constantly failing). If there had been only + // one alternative, or if the shorter alternative had come first, we would have terminated + // immediately. :-/ + if (hasShorterAlternatives) + jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this); + // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true, + // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ... + // but since we're about to return a failure this doesn't really matter!) } - notEnoughInputForPreviousAlternative.link(this); - // Update our idea of the start position, if we're tracking this. - if (!m_pattern.m_body->m_hasFixedSize) { - if (countCheckedForCurrentAlternative - 1) { - move(index, regT0); - sub32(Imm32(countCheckedForCurrentAlternative - 1), regT0); - poke(regT0, m_pattern.m_body->m_callFrameSize); - } else - poke(index, m_pattern.m_body->m_callFrameSize); - } - // Check if there is sufficent input to run the first alternative again. - jumpIfAvailableInput(incrementForNextIter).linkTo(firstAlternativeInputChecked, this); - // No - insufficent input to run the first alteranative, are there any other alternatives we - // might need to check? If so, the last check will have left the index incremented by - // (countToCheckForFirstAlternative + 1), so we need test whether countToCheckForFirstAlternative - // LESS input is available, to have the effect of just progressing the start position by 1 - // from the last iteration. If this check passes we can just jump up to the check associated - // with the first alternative in the loop. This is a bit sad, since we'll end up trying the - // first alternative again, and this check will fail (otherwise the check planted just above - // here would have passed). This is a bit sad, however it saves trying to do something more - // complex here in compilation, and in the common case we should end up coallescing the checks. - // - // FIXME: a nice improvement here may be to stop trying to match sooner, based on the least - // of the minimum-alternative-lengths. E.g. if I have two alternatives of length 200 and 150, - // and a string of length 100, we'll end up looping index from 0 to 100, checking whether there - // is sufficient input to run either alternative (constantly failing). If there had been only - // one alternative, or if the shorter alternative had come first, we would have terminated - // immediately. :-/ - if (hasShorterAlternatives) - jumpIfAvailableInput(-countToCheckForFirstAlternative).linkTo(firstAlternative, this); - // index will now be a bit garbled (depending on whether 'hasShorterAlternatives' is true, - // it has either been incremented by 1 or by (countToCheckForFirstAlternative + 1) ... - // but since we're about to return a failure this doesn't really matter!) - - unsigned frameSize = m_pattern.m_body->m_callFrameSize; - if (!m_pattern.m_body->m_hasFixedSize) - ++frameSize; - if (frameSize) - addPtr(Imm32(frameSize * sizeof(void*)), stackPointerRegister); + if (m_pattern.m_body->m_callFrameSize) + addPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister); move(Imm32(-1), returnRegister); @@ -1312,7 +1434,12 @@ class RegexGenerator : private MacroAssembler { push(ARMRegisters::r4); push(ARMRegisters::r5); push(ARMRegisters::r6); +#if CPU(ARM_TRADITIONAL) + push(ARMRegisters::r8); // scratch register +#endif move(ARMRegisters::r3, output); +#elif CPU(MIPS) + // Do nothing. #endif } @@ -1327,9 +1454,14 @@ class RegexGenerator : private MacroAssembler { pop(X86Registers::ebx); pop(X86Registers::ebp); #elif CPU(ARM) +#if CPU(ARM_TRADITIONAL) + pop(ARMRegisters::r8); // scratch register +#endif pop(ARMRegisters::r6); pop(ARMRegisters::r5); pop(ARMRegisters::r4); +#elif CPU(MIPS) + // Do nothing #endif ret(); } @@ -1337,7 +1469,7 @@ class RegexGenerator : private MacroAssembler { public: RegexGenerator(RegexPattern& pattern) : m_pattern(pattern) - , m_generationFailed(false) + , m_shouldFallBack(false) { } @@ -1345,9 +1477,8 @@ public: { generateEnter(); - // TODO: do I really want this on the stack? if (!m_pattern.m_body->m_hasFixedSize) - push(index); + store32(index, Address(output)); if (m_pattern.m_body->m_callFrameSize) subPtr(Imm32(m_pattern.m_body->m_callFrameSize * sizeof(void*)), stackPointerRegister); @@ -1359,7 +1490,7 @@ public: { generate(); - LinkBuffer patchBuffer(this, globalData->executableAllocator.poolForSize(size())); + LinkBuffer patchBuffer(this, globalData->executableAllocator.poolForSize(size()), 0); for (unsigned i = 0; i < m_backtrackRecords.size(); ++i) patchBuffer.patch(m_backtrackRecords[i].dataLabel, patchBuffer.locationOf(m_backtrackRecords[i].backtrackLocation)); @@ -1367,34 +1498,32 @@ public: jitObject.set(patchBuffer.finalizeCode()); } - bool generationFailed() + bool shouldFallBack() { - return m_generationFailed; + return m_shouldFallBack; } private: RegexPattern& m_pattern; + bool m_shouldFallBack; Vector<AlternativeBacktrackRecord> m_backtrackRecords; - bool m_generationFailed; }; -void jitCompileRegex(JSGlobalData* globalData, RegexCodeBlock& jitObject, const UString& patternString, unsigned& numSubpatterns, const char*& error, bool ignoreCase, bool multiline) +void jitCompileRegex(JSGlobalData* globalData, RegexCodeBlock& jitObject, const UString& patternString, unsigned& numSubpatterns, const char*& error, BumpPointerAllocator* allocator, bool ignoreCase, bool multiline) { RegexPattern pattern(ignoreCase, multiline); - if ((error = compileRegex(patternString, pattern))) return; - numSubpatterns = pattern.m_numSubpatterns; - RegexGenerator generator(pattern); - generator.compile(globalData, jitObject); - - if (generator.generationFailed()) { - JSRegExpIgnoreCaseOption ignoreCaseOption = ignoreCase ? JSRegExpIgnoreCase : JSRegExpDoNotIgnoreCase; - JSRegExpMultilineOption multilineOption = multiline ? JSRegExpMultiline : JSRegExpSingleLine; - jitObject.setFallback(jsRegExpCompile(reinterpret_cast<const UChar*>(patternString.data()), patternString.size(), ignoreCaseOption, multilineOption, &numSubpatterns, &error)); + if (!pattern.m_containsBackreferences && globalData->canUseJIT()) { + RegexGenerator generator(pattern); + generator.compile(globalData, jitObject); + if (!generator.shouldFallBack()) + return; } + + jitObject.setFallback(byteCompileRegex(pattern, allocator)); } }} |