Changeset 73307 in webkit for trunk/JavaScriptCore/yarr/RegexInterpreter.h

Timestamp:

Dec 3, 2010, 2:48:19 PM (15 years ago)

Author:

[email protected]

Message:

2010-12-03 Michael Saboff <​[email protected]>

Reviewed by Gavin Barraclough

Changes to significantly reduce branches to branches in JIT'ed
parentheses backtrack processing. The changes include the following:

• Taking the backtracking processing out of line and adding it as code at the end of the JIT'ed routine.
• Allow backtracks to be direct via an indirect branch for an address pushed onto the stack. If the use of an indirect branch is from a conditional jump, then we emit a trampoline at the end of the routine.
• Propogate backtracks instead of adding trampolines. Backtracks are propogated to where they are used. This change also eliminated trampoline branch code that aren't used.
• Added global expression state to keep track of parentheses tail code and indirect branches. Other changes made to support these changes.
• Split invertOrCapture flag on Patterns to two separate flags. Added getters for these flags. Rippled these changes to both the JIT and interpreter code.
• Split BacktrackDestination out off TermGenerationState struct. This is done to hold references to a backtrack for later code generation. ​https://bugs.webkit.org/show_bug.cgi?id=50295

• assembler/ARMAssembler.h: (JSC::ARMAssembler::JmpDst::isSet):
• assembler/ARMv7Assembler.h: (JSC::ARMv7Assembler::JmpDst::isSet):
• assembler/AbstractMacroAssembler.h: (JSC::AbstractMacroAssembler::Label::isSet): (JSC::AbstractMacroAssembler::DataLabelPtr::isUsed): (JSC::AbstractMacroAssembler::DataLabelPtr::used): (JSC::AbstractMacroAssembler::JumpList::clear):
• assembler/MIPSAssembler.h: (JSC::MIPSAssembler::JmpDst::isSet):
• assembler/X86Assembler.h: (JSC::X86Assembler::JmpDst::isSet):
• yarr/RegexCompiler.cpp: (JSC::Yarr::RegexPatternConstructor::atomParenthesesSubpatternBegin): (JSC::Yarr::RegexPatternConstructor::atomParentheticalAssertionBegin): (JSC::Yarr::RegexPatternConstructor::atomBackReference): (JSC::Yarr::RegexPatternConstructor::setupAlternativeBeginTerms):
• yarr/RegexInterpreter.cpp: (JSC::Yarr::ByteCompiler::atomParenthesesOnceBegin): (JSC::Yarr::ByteCompiler::atomParenthesesTerminalBegin): (JSC::Yarr::ByteCompiler::atomParenthesesSubpatternBegin): (JSC::Yarr::ByteCompiler::atomParentheticalAssertionBegin): (JSC::Yarr::ByteCompiler::atomParentheticalAssertionEnd): (JSC::Yarr::ByteCompiler::atomParenthesesSubpatternEnd): (JSC::Yarr::ByteCompiler::atomParenthesesOnceEnd): (JSC::Yarr::ByteCompiler::atomParenthesesTerminalEnd): (JSC::Yarr::ByteCompiler::emitDisjunction):
• yarr/RegexInterpreter.h: (JSC::Yarr::ByteTerm::ByteTerm): (JSC::Yarr::ByteTerm::BackReference): (JSC::Yarr::ByteTerm::invert): (JSC::Yarr::ByteTerm::capture):
• yarr/RegexJIT.cpp: (JSC::Yarr::RegexGenerator::IndirectJumpEntry::IndirectJumpEntry): (JSC::Yarr::RegexGenerator::IndirectJumpEntry::addJump): (JSC::Yarr::RegexGenerator::GenerationState::GenerationState): (JSC::Yarr::RegexGenerator::GenerationState::addIndirectJumpEntry): (JSC::Yarr::RegexGenerator::GenerationState::emitIndirectJumpTable): (JSC::Yarr::RegexGenerator::GenerationState::addParenthesesTail): (JSC::Yarr::RegexGenerator::GenerationState::emitParenthesesTail): (JSC::Yarr::RegexGenerator::GenerationState::addJumpToNextInteration): (JSC::Yarr::RegexGenerator::GenerationState::addJumpsToNextInteration): (JSC::Yarr::RegexGenerator::GenerationState::addDataLabelToNextIteration): (JSC::Yarr::RegexGenerator::GenerationState::linkToNextIteration): (JSC::Yarr::RegexGenerator::BacktrackDestination::BacktrackDestination): (JSC::Yarr::RegexGenerator::BacktrackDestination::clear): (JSC::Yarr::RegexGenerator::BacktrackDestination::clearDataLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::haveDestination): (JSC::Yarr::RegexGenerator::BacktrackDestination::isStackOffset): (JSC::Yarr::RegexGenerator::BacktrackDestination::isLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::isJumpList): (JSC::Yarr::RegexGenerator::BacktrackDestination::haveDataLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::copyTarget): (JSC::Yarr::RegexGenerator::BacktrackDestination::copyTo): (JSC::Yarr::RegexGenerator::BacktrackDestination::addBacktrackJump): (JSC::Yarr::RegexGenerator::BacktrackDestination::setStackOffset): (JSC::Yarr::RegexGenerator::BacktrackDestination::setLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::setNextBacktrackLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackToLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackJumpList): (JSC::Yarr::RegexGenerator::BacktrackDestination::setBacktrackSourceLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::setDataLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::setSubDataLabelPtr): (JSC::Yarr::RegexGenerator::BacktrackDestination::linkToNextBacktrack): (JSC::Yarr::RegexGenerator::BacktrackDestination::getStackOffset): (JSC::Yarr::RegexGenerator::BacktrackDestination::getLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::getBacktrackJumps): (JSC::Yarr::RegexGenerator::BacktrackDestination::getDataLabel): (JSC::Yarr::RegexGenerator::BacktrackDestination::jumpToBacktrack): (JSC::Yarr::RegexGenerator::BacktrackDestination::linkDataLabelToHereIfExists): (JSC::Yarr::RegexGenerator::BacktrackDestination::plantJumpToBacktrackIfExists): (JSC::Yarr::RegexGenerator::BacktrackDestination::linkAlternativeBacktracks): (JSC::Yarr::RegexGenerator::BacktrackDestination::linkAlternativeBacktracksTo): (JSC::Yarr::RegexGenerator::TermGenerationState::TermGenerationState): (JSC::Yarr::RegexGenerator::TermGenerationState::resetAlternative): (JSC::Yarr::RegexGenerator::TermGenerationState::isLastAlternative): (JSC::Yarr::RegexGenerator::TermGenerationState::clearBacktrack): (JSC::Yarr::RegexGenerator::TermGenerationState::jumpToBacktrack): (JSC::Yarr::RegexGenerator::TermGenerationState::plantJumpToBacktrackIfExists): (JSC::Yarr::RegexGenerator::TermGenerationState::linkDataLabelToBacktrackIfExists): (JSC::Yarr::RegexGenerator::TermGenerationState::addBacktrackJump): (JSC::Yarr::RegexGenerator::TermGenerationState::setDataLabelPtr): (JSC::Yarr::RegexGenerator::TermGenerationState::setBackTrackStackOffset): (JSC::Yarr::RegexGenerator::TermGenerationState::setBacktrackLabel): (JSC::Yarr::RegexGenerator::TermGenerationState::linkAlternativeBacktracks): (JSC::Yarr::RegexGenerator::TermGenerationState::linkAlternativeBacktracksTo): (JSC::Yarr::RegexGenerator::TermGenerationState::setBacktrackLink): (JSC::Yarr::RegexGenerator::TermGenerationState::chainBacktracks): (JSC::Yarr::RegexGenerator::TermGenerationState::chainBacktrackJumps): (JSC::Yarr::RegexGenerator::TermGenerationState::getBacktrackDestination): (JSC::Yarr::RegexGenerator::TermGenerationState::propagateBacktrackingFrom): (JSC::Yarr::RegexGenerator::ParenthesesTail::ParenthesesTail): (JSC::Yarr::RegexGenerator::ParenthesesTail::processBacktracks): (JSC::Yarr::RegexGenerator::ParenthesesTail::setNextIteration): (JSC::Yarr::RegexGenerator::ParenthesesTail::generateCode): (JSC::Yarr::RegexGenerator::generateAssertionBOL): (JSC::Yarr::RegexGenerator::generateAssertionEOL): (JSC::Yarr::RegexGenerator::generateAssertionWordBoundary): (JSC::Yarr::RegexGenerator::generatePatternCharacterSingle): (JSC::Yarr::RegexGenerator::generatePatternCharacterPair): (JSC::Yarr::RegexGenerator::generatePatternCharacterFixed): (JSC::Yarr::RegexGenerator::generatePatternCharacterGreedy): (JSC::Yarr::RegexGenerator::generatePatternCharacterNonGreedy): (JSC::Yarr::RegexGenerator::generateCharacterClassSingle): (JSC::Yarr::RegexGenerator::generateCharacterClassFixed): (JSC::Yarr::RegexGenerator::generateCharacterClassGreedy): (JSC::Yarr::RegexGenerator::generateCharacterClassNonGreedy): (JSC::Yarr::RegexGenerator::generateParenthesesDisjunction): (JSC::Yarr::RegexGenerator::generateParenthesesSingle): (JSC::Yarr::RegexGenerator::generateParenthesesGreedyNoBacktrack): (JSC::Yarr::RegexGenerator::generateParentheticalAssertion): (JSC::Yarr::RegexGenerator::generateDisjunction): (JSC::Yarr::RegexGenerator::compile):
• yarr/RegexPattern.h: (JSC::Yarr::PatternTerm::PatternTerm): (JSC::Yarr::PatternTerm::invert): (JSC::Yarr::PatternTerm::capture):

2010-12-03 Michael Saboff <​[email protected]>

Reviewed by Gavin Barraclough

Added new tests to support changes to Regexp JIT code handling
of parentheses. Tests focused on backtracking and nested
subexpressions.
​https://bugs.webkit.org/show_bug.cgi?id=50295

• fast/regex/parentheses-expected.txt: Added.
• fast/regex/parentheses.html: Added.
• fast/regex/script-tests/parentheses.js: Added.

File:

• trunk/JavaScriptCore/yarr/RegexInterpreter.h (modified) (9 diffs)

trunk/JavaScriptCore/yarr/RegexInterpreter.h

@@ -88 +88 @@
         TypeCheckInput,
     } type;
-    bool invertOrCapture;
     union {
         struct {
@@ -115 +114 @@
     };
     unsigned frameLocation;
+    bool m_capture : 1;
+    bool m_invert : 1;
     int inputPosition;
 
     ByteTerm(UChar ch, int inputPos, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
         : frameLocation(frameLocation)
+        , m_capture(false)
+        , m_invert(false)
     {
         switch (quantityType) {
@@ -140 +143 @@
     ByteTerm(UChar lo, UChar hi, int inputPos, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType)
         : frameLocation(frameLocation)
+        , m_capture(false)
+        , m_invert(false)
     {
         switch (quantityType) {
@@ -162 +167 @@
     ByteTerm(CharacterClass* characterClass, bool invert, int inputPos)
         : type(ByteTerm::TypeCharacterClass)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         atom.characterClass = characterClass;
@@ -170 +176 @@
     }
 
-    ByteTerm(Type type, unsigned subpatternId, ByteDisjunction* parenthesesInfo, bool invertOrCapture, int inputPos)
+    ByteTerm(Type type, unsigned subpatternId, ByteDisjunction* parenthesesInfo, bool capture, int inputPos)
         : type(type)
-        , invertOrCapture(invertOrCapture)
+        , m_capture(capture)
+        , m_invert(false)
     {
         atom.subpatternId = subpatternId;
@@ -183 +190 @@
     ByteTerm(Type type, bool invert = false)
         : type(type)
-        , invertOrCapture(invert)
+        , m_capture(false)
+        , m_invert(invert)
     {
         atom.quantityType = QuantifierFixedCount;
@@ -189 +197 @@
     }
 
-    ByteTerm(Type type, unsigned subpatternId, bool invertOrCapture, int inputPos)
+    ByteTerm(Type type, unsigned subpatternId, bool capture, bool invert, int inputPos)
         : type(type)
-        , invertOrCapture(invertOrCapture)
+        , m_capture(capture)
+        , m_invert(invert)
     {
         atom.subpatternId = subpatternId;
@@ -229 +238 @@
     static ByteTerm BackReference(unsigned subpatternId, int inputPos)
     {
-        return ByteTerm(TypeBackReference, subpatternId, false, inputPos);
+        return ByteTerm(TypeBackReference, subpatternId, false, false, inputPos);
     }
 
@@ -298 +307 @@
     bool invert()
     {
-        return invertOrCapture;
+        return m_invert;
     }
 
     bool capture()
     {
-        return invertOrCapture;
+        return m_capture;
     }
 };