Changeset 88076 in webkit

Timestamp:

Jun 3, 2011 4:30:22 PM (13 years ago)

Author:

oliver@apple.com

Message:

2011-06-03 Oliver Hunt <​oliver@apple.com>

Reviewed by Geoffrey Garen.

Improve keyword lookup
​https://bugs.webkit.org/show_bug.cgi?id=61913

Rather than doing multiple hash lookups as we currently
do when trying to identify keywords we now use an
automatically generated decision tree (essentially it's
a hard coded patricia trie). We still use the regular
lookup table for the last few characters of an input as
this allows us to completely skip all bounds checks.

• CMakeLists.txt:
• DerivedSources.make:
• DerivedSources.pro:
• GNUmakefile.am:
• JavaScriptCore.gyp/JavaScriptCore.gyp:
• JavaScriptCore.xcodeproj/project.pbxproj:
• KeywordLookupGenerator.py: Added.
• make-generated-sources.sh:
• parser/Lexer.cpp: (JSC::Lexer::internalShift): (JSC::Lexer::shift): (JSC::Lexer::parseIdentifier):
• parser/Lexer.h:

Location:

trunk/Source/JavaScriptCore

Files:

• CMakeLists.txt (modified) (1 diff)
• ChangeLog (modified) (1 diff)
• DerivedSources.make (modified) (2 diffs)
• DerivedSources.pro (modified) (1 diff)
• GNUmakefile.am (modified) (1 diff)
• JavaScriptCore.gyp/JavaScriptCore.gyp (modified) (1 diff)
• JavaScriptCore.xcodeproj/project.pbxproj (modified) (5 diffs)
• KeywordLookupGenerator.py (added)
• make-generated-sources.sh (modified) (1 diff)
• parser/Lexer.cpp (modified) (5 diffs)
• parser/Lexer.h (modified) (1 diff)

trunk/Source/JavaScriptCore/CMakeLists.txt

@@ -220 +220 @@
 
 
+#GENERATOR: "KeywordLookup.h": keyword decision tree used by the lexer
+ADD_CUSTOM_COMMAND(
+    OUTPUT ${DERIVED_SOURCES_JAVASCRIPTCORE_DIR}/KeywordLookup.h
+    MAIN_DEPENDENCY ${JAVASCRIPTCORE_DIR}/KeywordLookupGenerator.py
+    COMMAND ${PYTHON_EXECUTABLE} ${JAVASCRIPTCORE_DIR}/KeywordLookupGenerator.py ${JAVASCRIPTCORE_DIR}/parser/Keywords.table > ${DERIVED_SOURCES_JAVASCRIPTCORE_DIR}/KeywordLookup.h
+    VERBATIM)
+ADD_SOURCE_DEPENDENCIES(${JAVASCRIPTCORE_DIR}/parser/Lexer.cpp ${DERIVED_SOURCES_JAVASCRIPTCORE_DIR}/KeywordLookup.h)
 
 IF (WTF_CPU_ARM)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2011-06-03  Oliver Hunt  <oliver@apple.com>
+
+        Reviewed by Geoffrey Garen.
+
+        Improve keyword lookup
+        https://bugs.webkit.org/show_bug.cgi?id=61913
+
+        Rather than doing multiple hash lookups as we currently
+        do when trying to identify keywords we now use an 
+        automatically generated decision tree (essentially it's
+        a hard coded patricia trie).  We still use the regular
+        lookup table for the last few characters of an input as
+        this allows us to completely skip all bounds checks.
+
+        * CMakeLists.txt:
+        * DerivedSources.make:
+        * DerivedSources.pro:
+        * GNUmakefile.am:
+        * JavaScriptCore.gyp/JavaScriptCore.gyp:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * KeywordLookupGenerator.py: Added.
+        * make-generated-sources.sh:
+        * parser/Lexer.cpp:
+        (JSC::Lexer::internalShift):
+        (JSC::Lexer::shift):
+        (JSC::Lexer::parseIdentifier):
+        * parser/Lexer.h:
+
 2011-06-03  Siddharth Mathur  <siddharth.mathur@nokia.com>
 

trunk/Source/JavaScriptCore/DerivedSources.make

@@ -47 +47 @@
     JavaScriptCore.JSVALUE64.exp \
     JSGlobalObject.lut.h \
+    KeywordLookup.h \
     Lexer.lut.h \
     MathObject.lut.h \
@@ -77 +78 @@
         python $^ > $@
 
+KeywordLookup.h: KeywordLookupGenerator.py Keywords.table
+        python $^ > $@
+
 # export files
 

trunk/Source/JavaScriptCore/DerivedSources.pro

@@ -100 +100 @@
 retgen.commands = python $$retgen.wkScript > ${QMAKE_FILE_OUT}
 addExtraCompiler(retgen)
+
+#GENERATOR: "KeywordLookup.h": decision tree used by the lexer
+klgen.output = $$JSC_GENERATED_SOURCES_DIR/KeywordLookup.h
+klgen.wkScript = $$PWD/KeywordLookupGenerator.py 
+klgen.input = KEYWORDLUT_FILES
+klgen.commands = python $$klgen.wkScript ${QMAKE_FILE_NAME} > ${QMAKE_FILE_OUT}
+addExtraCompiler(klgen)

trunk/Source/JavaScriptCore/GNUmakefile.am

@@ -78 +78 @@
 
 Source/JavaScriptCore/RegExpJitTables.h: $(srcdir)/Source/JavaScriptCore/create_regex_tables
+        $(AM_V_GEN)$(PYTHON) $^ > $@
+
+Source/JavaScriptCore/KeywordLookup.h: $(srcdir)/Source/JavaScriptCore/KeywordLookupGenerator.py $(srcdir)/Source/JavaScriptCore/parser/Keywords.table
         $(AM_V_GEN)$(PYTHON) $^ > $@
 

trunk/Source/JavaScriptCore/JavaScriptCore.gyp/JavaScriptCore.gyp

@@ -215 +215 @@
           'action': ['python', '<@(_inputs)', '<@(_arguments)', '<@(_outputs)'],
         },
+        {
+          'action_name': 'klgen',
+          'inputs': [
+            '../KeywordLookupGenerator.py',
+            '../parser/Keywords.table'
+          ],
+          'arguments': [
+          ],
+          'outputs': [
+            '<(INTERMEDIATE_DIR)/KeywordLookup.h',
+          ],
+          'action': ['python', '<@(_inputs)', '<@(_arguments)', '<@(_outputs)'],
+        },
       ],
       'include_dirs': [

trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

@@ -382 +382 @@
                 A727FF6B0DA3092200E548D7 /* JSPropertyNameIterator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A727FF660DA3053B00E548D7 /* JSPropertyNameIterator.cpp */; };
                 A7280A2811557E3000D56957 /* JSObjectRefPrivate.h in Headers */ = {isa = PBXBuildFile; fileRef = A79EDB0811531CD60019E912 /* JSObjectRefPrivate.h */; settings = {ATTRIBUTES = (Private, ); }; };
+                A72FFD64139985A800E5365A /* KeywordLookup.h in Headers */ = {isa = PBXBuildFile; fileRef = A7C225CD1399849C00FF1662 /* KeywordLookup.h */; };
                 A730B6121250068F009D25B1 /* StrictEvalActivation.h in Headers */ = {isa = PBXBuildFile; fileRef = A730B6101250068F009D25B1 /* StrictEvalActivation.h */; };
                 A730B6131250068F009D25B1 /* StrictEvalActivation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */; };
@@ -1120 +1121 @@
                 A7B48DB60EE74CFC00DCBDB6 /* ExecutableAllocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ExecutableAllocator.cpp; sourceTree = "<group>"; };
                 A7C1E8C8112E701C00A37F98 /* JITPropertyAccess32_64.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JITPropertyAccess32_64.cpp; sourceTree = "<group>"; };
+                A7C225CC139981F100FF1662 /* KeywordLookupGenerator.py */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.script.python; path = KeywordLookupGenerator.py; sourceTree = "<group>"; };
+                A7C225CD1399849C00FF1662 /* KeywordLookup.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = KeywordLookup.h; sourceTree = "<group>"; };
                 A7C40C07130B057D00D002A1 /* BlockStack.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BlockStack.h; sourceTree = "<group>"; };
                 A7C40C08130B057D00D002A1 /* SentinelLinkedList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SentinelLinkedList.h; sourceTree = "<group>"; };
@@ -1375 +1378 @@
                                 A718F8211178EB4B002465A7 /* create_regex_tables */,
                                 937B63CC09E766D200A671DD /* DerivedSources.make */,
+                                A7C225CC139981F100FF1662 /* KeywordLookupGenerator.py */,
                                 F692A8540255597D01FF60F7 /* create_hash_table */,
                                 14B8ECA60A5653980062BE54 /* JavaScriptCore.exp */,
@@ -1609 +1613 @@
                                 BC8149AF12F89F53007B2C32 /* HeaderDetection.h */,
                                 BC87CDB810712ACA000614CF /* JSONObject.lut.h */,
+                                A7C225CD1399849C00FF1662 /* KeywordLookup.h */,
                                 BC18C52D0E16FCE100B34460 /* Lexer.lut.h */,
                                 BC18C5290E16FCC200B34460 /* MathObject.lut.h */,
@@ -2548 +2553 @@
                                 14F97447138C853E00DA1C67 /* HeapRootVisitor.h in Headers */,
                                 86BB09C1138E381B0056702F /* DFGRepatch.h in Headers */,
+                                A72FFD64139985A800E5365A /* KeywordLookup.h in Headers */,
                         );
                         runOnlyForDeploymentPostprocessing = 0;

trunk/Source/JavaScriptCore/make-generated-sources.sh

@@ -5 +5 @@
 export CREATE_HASH_TABLE="$SRCROOT/create_hash_table"
 export CREATE_REGEXP_TABLES="$SRCROOT/create_regex_tables"
+export CREATE_KEYWORD_LOOKUP="$SRCROOT/KeywordLookupGenerator.py"
 
 mkdir -p DerivedSources/JavaScriptCore

trunk/Source/JavaScriptCore/parser/Lexer.cpp

@@ -41 +41 @@
 
 #include "JSParser.h"
+#include "KeywordLookup.h"
 #include "Lookup.h"
 #include "Lexer.lut.h"
@@ -272 +273 @@
 }
 
+template <int shiftAmount, Lexer::ShiftType shouldBoundsCheck> ALWAYS_INLINE void Lexer::internalShift()
+{
+    if (shouldBoundsCheck == DoBoundsCheck) {
+        // Faster than an if-else sequence
+        ASSERT(m_current != -1);
+        m_current = -1;
+        m_code += shiftAmount;
+        if (LIKELY(m_code < m_codeEnd))
+            m_current = *m_code;
+    } else {
+        m_code += shiftAmount;
+        m_current = *m_code;
+    }
+}
+
 ALWAYS_INLINE void Lexer::shift()
 {
-    // Faster than an if-else sequence
-    ASSERT(m_current != -1);
-    m_current = -1;
-    ++m_code;
-    if (LIKELY(m_code < m_codeEnd))
-        m_current = *m_code;
+    internalShift<1, DoBoundsCheck>();
 }
 
@@ -402 +413 @@
 template <bool shouldCreateIdentifier> ALWAYS_INLINE JSTokenType Lexer::parseIdentifier(JSTokenData* lvalp, unsigned lexType)
 {
+    static const ptrdiff_t remaining = m_codeEnd - m_code;
+    if ((remaining >= maxTokenLength) && !(lexType & IgnoreReservedWords)) {
+        JSTokenType keyword = parseKeyword();
+        if (keyword != IDENT)
+            return keyword;
+    }
+    const UChar* identifierStart = currentCharacter();
     bool bufferRequired = false;
-    const UChar* identifierStart = currentCharacter();
-    int identifierLength;
 
     while (true) {
@@ -431 +447 @@
         identifierStart = currentCharacter();
     }
-
+    
+    int identifierLength;
     const Identifier* ident = 0;
     if (shouldCreateIdentifier) {
@@ -453 +470 @@
         ASSERT(shouldCreateIdentifier);
         // Keywords must not be recognized if there was an \uXXXX in the identifier.
-        const HashEntry* entry = m_keywordTable.entry(m_globalData, *ident);
-        return entry ? static_cast<JSTokenType>(entry->lexerValue()) : IDENT;
+        if (remaining < maxTokenLength) {
+            const HashEntry* entry = m_keywordTable.entry(m_globalData, *ident);
+            ASSERT((remaining < maxTokenLength) || !entry);
+            return entry ? static_cast<JSTokenType>(entry->lexerValue()) : IDENT;
+        }
+        return IDENT;
     }
 

trunk/Source/JavaScriptCore/parser/Lexer.h

@@ -114 +114 @@
         ALWAYS_INLINE bool lastTokenWasRestrKeyword() const;
 
+        enum ShiftType { DoBoundsCheck, DoNotBoundsCheck };
+        template <int shiftAmount, ShiftType shouldBoundsCheck> void internalShift();
+        ALWAYS_INLINE JSTokenType parseKeyword();
         template <bool shouldBuildIdentifiers> ALWAYS_INLINE JSTokenType parseIdentifier(JSTokenData*, unsigned);
         template <bool shouldBuildStrings> ALWAYS_INLINE bool parseString(JSTokenData* lvalp, bool strictMode);