Improve switch performance.
authoroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 24 Jul 2008 00:49:46 +0000 (00:49 +0000)
committeroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 24 Jul 2008 00:49:46 +0000 (00:49 +0000)
Reviewed by Geoff Garen and Sam Weinig.

Improve switch performance by converting to a hashmap based jump
table to avoid the sequence of dispatches that would otherwise be
needed.  This results in a 9-19x performance win for string switches
based on ad hoc testing, and a 6x improvement for integer switch
statements.  SunSpider reports a 1.2% progression.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@35309 268f45cc-cd09-0410-ab3c-d52691b4dbfc

15 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/VM/CodeBlock.cpp
JavaScriptCore/VM/CodeBlock.h
JavaScriptCore/VM/CodeGenerator.cpp
JavaScriptCore/VM/CodeGenerator.h
JavaScriptCore/VM/Machine.cpp
JavaScriptCore/VM/Opcode.cpp
JavaScriptCore/VM/Opcode.h
JavaScriptCore/kjs/JSImmediate.h
JavaScriptCore/kjs/nodes.cpp
JavaScriptCore/kjs/nodes.h
LayoutTests/ChangeLog
LayoutTests/fast/js/resources/switch-behaviour.js [new file with mode: 0644]
LayoutTests/fast/js/switch-behaviour-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/switch-behaviour.html [new file with mode: 0644]

index b95ec81..fc672fe 100644 (file)
@@ -1,3 +1,41 @@
+2008-07-23  Oliver Hunt  <oliver@apple.com>
+
+        Reviewed by Geoff Garen and Sam Weinig.
+
+        Improve switch performance.
+
+        Improve switch performance by converting to a hashmap based jump
+        table to avoid the sequence of dispatches that would otherwise be
+        needed.  This results in a 9-19x performance win for string switches
+        based on ad hoc testing, and a 6x improvement for integer switch
+        statements.  SunSpider reports a 1.2% progression.
+
+        * VM/CodeBlock.cpp:
+        (KJS::CodeBlock::dump):
+        (KJS::SimpleJumpTable::offsetForValue):
+        * VM/CodeBlock.h:
+        * VM/CodeGenerator.cpp:
+        (KJS::CodeGenerator::beginSwitch):
+        (KJS::prepareJumpTableForImmediateSwitch):
+        (KJS::prepareJumpTableForCharacterSwitch):
+        (KJS::prepareJumpTableForStringSwitch):
+        (KJS::CodeGenerator::endSwitch):
+        * VM/CodeGenerator.h:
+        * VM/Machine.cpp:
+        (KJS::offsetForStringSwitch):
+        (KJS::Machine::privateExecute):
+        * VM/Opcode.cpp:
+        (KJS::):
+        * VM/Opcode.h:
+        * kjs/JSImmediate.h:
+        * kjs/nodes.cpp:
+        (KJS::):
+        (KJS::processClauseList):
+        (KJS::CaseBlockNode::tryOptimisedSwitch):
+        (KJS::CaseBlockNode::emitCodeForBlock):
+        * kjs/nodes.h:
+        (KJS::SwitchInfo::):
+
 2008-07-23  Gavin Barraclough  <barraclough@apple.com>
 
         Reviewed by Geoff Garen.
index 29601af..5c7665f 100644 (file)
@@ -197,7 +197,52 @@ void CodeBlock::dump(ExecState* exec) const
             ++i;
         } while (i < exceptionHandlers.size());
     }
-        
+    
+    if (immediateSwitchJumpTables.size()) {
+        printf("immediate switch jump tables:\n");
+        unsigned i = 0;
+        do {
+            printf("\t{\n");
+            int entry = 0;
+            Vector<int32_t>::const_iterator end = immediateSwitchJumpTables[i].branchOffsets.end();
+            for (Vector<int32_t>::const_iterator iter = immediateSwitchJumpTables[i].branchOffsets.begin(); iter != end; ++iter, ++entry)
+                if (*iter)
+                    printf("\t\t%4d => %04d\n", entry + immediateSwitchJumpTables[i].min, *iter);
+            printf("\t}\n");
+            ++i;
+        } while (i < immediateSwitchJumpTables.size());
+    }
+    
+    if (characterSwitchJumpTables.size()) {
+        printf("\ncharacter switch jump tables:\n");
+        unsigned i = 0;
+        do {
+            printf("\t{\n");
+            int entry = 0;
+            Vector<int32_t>::const_iterator end = characterSwitchJumpTables[i].branchOffsets.end();
+            for (Vector<int32_t>::const_iterator iter = characterSwitchJumpTables[i].branchOffsets.begin(); iter != end; ++iter, ++entry) {
+                ASSERT(!((i + characterSwitchJumpTables[i].min) & ~0xFFFF));
+                UChar ch = static_cast<UChar>(i + characterSwitchJumpTables[i].min);
+                printf("\t\t\"%s\" => %04d\n", UString(&ch, 1).ascii(), *iter);
+            }
+            printf("\t}\n");
+            ++i;
+        } while (i < characterSwitchJumpTables.size());
+    }
+    
+    if (stringSwitchJumpTables.size()) {
+        printf("\nstring switch jump tables:\n");
+        unsigned i = 0;
+        do {
+            printf("\t{\n");
+            StringJumpTable::const_iterator end = stringSwitchJumpTables[i].end();
+            for (StringJumpTable::const_iterator iter = stringSwitchJumpTables[i].begin(); iter != end; ++iter)
+                printf("\t\t\"%s\" => %04d\n", UString(iter->first).ascii(), iter->second);
+            printf("\t}\n");
+            ++i;
+        } while (i < stringSwitchJumpTables.size());
+    }
+
     printf("\n");
 }
 
@@ -502,6 +547,27 @@ void CodeBlock::dump(ExecState* exec, const Vector<Instruction>::const_iterator&
             printf("[%4d] loop_if_less %s, %s, %d(->%d)\n", location, registerName(r0).c_str(), registerName(r1).c_str(), offset, jumpTarget(begin, it, offset));
             break;
         }
+        case op_switch_imm: {
+            int tableIndex = (++it)->u.operand;
+            int defaultTarget = (++it)->u.operand;
+            int scrutineeRegister = (++it)->u.operand;
+            printf("[%4d] switch_imm\t %d, %d(->%d), %s\n", location, tableIndex, defaultTarget, jumpTarget(begin, it, defaultTarget), registerName(scrutineeRegister).c_str());
+            break;
+        }
+        case op_switch_char: {
+            int tableIndex = (++it)->u.operand;
+            int defaultTarget = (++it)->u.operand;
+            int scrutineeRegister = (++it)->u.operand;
+            printf("[%4d] switch_char\t %d, %d(->%d), %s\n", location, tableIndex, defaultTarget, jumpTarget(begin, it, defaultTarget), registerName(scrutineeRegister).c_str());
+            break;
+        }
+        case op_switch_string: {
+            int tableIndex = (++it)->u.operand;
+            int defaultTarget = (++it)->u.operand;
+            int scrutineeRegister = (++it)->u.operand;
+            printf("[%4d] switch_string\t %d, %d(->%d), %s\n", location, tableIndex, defaultTarget, jumpTarget(begin, it, defaultTarget), registerName(scrutineeRegister).c_str());
+            break;
+        }
         case op_new_func: {
             int r0 = (++it)->u.operand;
             int f0 = (++it)->u.operand;
@@ -710,4 +776,14 @@ int CodeBlock::expressionRangeForVPC(const Instruction* vPC, int& divot, int& st
     return lineNumberForVPC(vPC);
 }
 
+int32_t SimpleJumpTable::offsetForValue(int32_t value, int32_t defaultOffset)
+{
+    if (value >= min && static_cast<uint32_t>(value - min) < branchOffsets.size()) {
+        int32_t offset = branchOffsets[value - min];
+        if (offset)
+            return offset;
+    }
+    return defaultOffset;        
+}
+
 } // namespace KJS
index 6bdbe73..56be52b 100644 (file)
@@ -66,6 +66,17 @@ namespace KJS {
         int32_t lineNumber;
     };
 
+    typedef HashMap<RefPtr<UString::Rep>, int32_t> StringJumpTable;
+    struct SimpleJumpTable {
+        Vector<int32_t> branchOffsets;
+        int32_t min;
+        int32_t offsetForValue(int32_t value, int32_t defaultOffset);
+        void add(int32_t key, int32_t offset) {
+            if (!branchOffsets[key])
+                branchOffsets[key] = offset;
+        }
+    };
+
     struct CodeBlock {
         CodeBlock(ScopeNode* ownerNode_, CodeType codeType_, PassRefPtr<SourceProvider> source_, unsigned sourceOffset_)
             : ownerNode(ownerNode_)
@@ -112,6 +123,10 @@ namespace KJS {
         Vector<ExpressionRangeInfo> expressionInfo;
         Vector<LineInfo> lineInfo;
 
+        Vector<SimpleJumpTable> immediateSwitchJumpTables;
+        Vector<SimpleJumpTable> characterSwitchJumpTables;
+        Vector<StringJumpTable> stringSwitchJumpTables;
+
     private:
         void dump(ExecState*, const Vector<Instruction>::const_iterator& begin, Vector<Instruction>::const_iterator&) const;
     };
index 07cb873..c53d61d 100644 (file)
@@ -32,6 +32,7 @@
 
 #include "JSFunction.h"
 #include "Machine.h"
+#include "ustring.h"
 
 using namespace std;
 
@@ -1144,4 +1145,124 @@ void CodeGenerator::emitSubroutineReturn(RegisterID* retAddrSrc)
     instructions().append(retAddrSrc->index());
 }
 
+void CodeGenerator::beginSwitch(RegisterID* scrutineeRegister, SwitchInfo::SwitchType type)
+{
+    SwitchInfo info = { instructions().size(), type };
+    switch (type) {
+        case SwitchInfo::SwitchImmediate:
+            emitOpcode(op_switch_imm);
+            break;
+        case SwitchInfo::SwitchCharacter:
+            emitOpcode(op_switch_char);
+            break;
+        case SwitchInfo::SwitchString:
+            emitOpcode(op_switch_string);
+            break;
+        default:
+            ASSERT_NOT_REACHED();
+    }
+
+    instructions().append(0); // place holder for table index
+    instructions().append(0); // place holder for default target    
+    instructions().append(scrutineeRegister->index());
+    m_switchContextStack.append(info);
+}
+
+static int32_t keyForImmediateSwitch(ExpressionNode* node, int32_t min, int32_t max)
+{
+    UNUSED_PARAM(max);
+    ASSERT(node->isNumber());
+    double value = static_cast<NumberNode*>(node)->value();
+    ASSERT(JSImmediate::from(value));
+    int32_t key = static_cast<int32_t>(value);
+    ASSERT(key == value);
+    ASSERT(key >= min);
+    ASSERT(key <= max);
+    return key - min;
+}
+
+static void prepareJumpTableForImmediateSwitch(SimpleJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, int32_t min, int32_t max)
+{
+    jumpTable.min = min;
+    jumpTable.branchOffsets.resize(max - min + 1);
+    jumpTable.branchOffsets.fill(0);
+    for (uint32_t i = 0; i < clauseCount; ++i) {
+        // We're emitting this after the clause labels should have been fixed, so 
+        // the labels should not be "forward" references
+        ASSERT(!labels[i]->isForwardLabel());
+        jumpTable.add(keyForImmediateSwitch(nodes[i], min, max), labels[i]->offsetFrom(switchAddress)); 
+    }
+}
+
+static int32_t keyForCharacterSwitch(ExpressionNode* node, int32_t min, int32_t max)
+{
+    UNUSED_PARAM(max);
+    ASSERT(node->isString());
+    UString::Rep* clause = static_cast<StringNode*>(node)->value().rep();
+    ASSERT(clause->size() == 1);
+    
+    int32_t key = clause->data()[0];
+    ASSERT(key >= min);
+    ASSERT(key <= max);
+    return key - min;
+}
+
+static void prepareJumpTableForCharacterSwitch(SimpleJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, int32_t min, int32_t max)
+{
+    jumpTable.min = min;
+    jumpTable.branchOffsets.resize(max - min + 1);
+    jumpTable.branchOffsets.fill(0);
+    for (uint32_t i = 0; i < clauseCount; ++i) {
+        // We're emitting this after the clause labels should have been fixed, so 
+        // the labels should not be "forward" references
+        ASSERT(!labels[i]->isForwardLabel());
+        jumpTable.add(keyForCharacterSwitch(nodes[i], min, max), labels[i]->offsetFrom(switchAddress)); 
+    }
+}
+
+static void prepareJumpTableForStringSwitch(StringJumpTable& jumpTable, int32_t switchAddress, uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes)
+{
+    for (uint32_t i = 0; i < clauseCount; ++i) {
+        // We're emitting this after the clause labels should have been fixed, so 
+        // the labels should not be "forward" references
+        ASSERT(!labels[i]->isForwardLabel());
+        
+        ASSERT(nodes[i]->isString());
+        UString::Rep* clause = static_cast<StringNode*>(nodes[i])->value().rep();
+        jumpTable.add(clause, labels[i]->offsetFrom(switchAddress)); 
+    }
+}
+
+void CodeGenerator::endSwitch(uint32_t clauseCount, RefPtr<LabelID>* labels, ExpressionNode** nodes, LabelID* defaultLabel, int32_t min, int32_t max)
+{
+    SwitchInfo switchInfo = m_switchContextStack.last();
+    m_switchContextStack.removeLast();
+    if (switchInfo.switchType == SwitchInfo::SwitchImmediate) {
+        instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->immediateSwitchJumpTables.size();
+        instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
+
+        m_codeBlock->immediateSwitchJumpTables.append(SimpleJumpTable());
+        SimpleJumpTable& jumpTable = m_codeBlock->immediateSwitchJumpTables.last();
+
+        prepareJumpTableForImmediateSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes, min, max);
+    } else if (switchInfo.switchType == SwitchInfo::SwitchCharacter) {
+        instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->characterSwitchJumpTables.size();
+        instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
+        
+        m_codeBlock->characterSwitchJumpTables.append(SimpleJumpTable());
+        SimpleJumpTable& jumpTable = m_codeBlock->characterSwitchJumpTables.last();
+
+        prepareJumpTableForCharacterSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes, min, max);
+    } else {
+        ASSERT(switchInfo.switchType == SwitchInfo::SwitchString);
+        instructions()[switchInfo.opcodeOffset + 1] = m_codeBlock->stringSwitchJumpTables.size();
+        instructions()[switchInfo.opcodeOffset + 2] = defaultLabel->offsetFrom(switchInfo.opcodeOffset + 3);
+
+        m_codeBlock->stringSwitchJumpTables.append(StringJumpTable());
+        StringJumpTable& jumpTable = m_codeBlock->stringSwitchJumpTables.last();
+
+        prepareJumpTableForStringSwitch(jumpTable, switchInfo.opcodeOffset + 3, clauseCount, labels, nodes);
+    }
+}
+
 } // namespace KJS
index ee1b239..5d18860 100644 (file)
@@ -313,6 +313,9 @@ namespace KJS {
         JumpContext* jumpContextForContinue(const Identifier&);
         JumpContext* jumpContextForBreak(const Identifier&);
 
+        void beginSwitch(RegisterID*, SwitchInfo::SwitchType);
+        void endSwitch(uint32_t clauseCount, RefPtr<LabelID>*, ExpressionNode**, LabelID* defaultLabel, int32_t min, int32_t range);
+
         CodeType codeType() const { return m_codeType; }
 
         ExecState* globalExec() { return m_scopeChain->globalObject()->globalExec(); }
@@ -401,6 +404,7 @@ namespace KJS {
         Vector<JumpContext> m_jumpContextStack;
         int m_continueDepth;
         Vector<ControlFlowContext> m_scopeContextStack;
+        Vector<SwitchInfo> m_switchContextStack;
 
         int m_nextVar;
         int m_nextParameter;
index 7d39f7b..fbbc12b 100644 (file)
@@ -985,7 +985,16 @@ ALWAYS_INLINE JSValue* Machine::checkTimeout(JSGlobalObject* globalObject)
     
     return 0;
 }
-    
+
+static int32_t offsetForStringSwitch(StringJumpTable& jumpTable, JSValue* scrutinee, int32_t defaultOffset) {
+    StringJumpTable::const_iterator end = jumpTable.end();
+    UString::Rep* value = static_cast<JSString*>(scrutinee)->value().rep();
+    StringJumpTable::const_iterator loc = jumpTable.find(value);
+    if (loc == end)
+        return defaultOffset;
+    return loc->second;
+}
+
 JSValue* Machine::privateExecute(ExecutionFlag flag, ExecState* exec, RegisterFile* registerFile, Register* r, ScopeChainNode* scopeChain, CodeBlock* codeBlock, JSValue** exception)
 {
     // One-time initialization of our address tables. We have to put this code
@@ -2134,6 +2143,67 @@ JSValue* Machine::privateExecute(ExecutionFlag flag, ExecState* exec, RegisterFi
         ++vPC;
         NEXT_OPCODE;
     }
+    BEGIN_OPCODE(op_switch_imm) {
+        /* switch_imm tableIndex(n) defaultOffset(offset) scrutinee(r)
+
+           Performs a range checked switch on the scrutinee value, using
+           the tableIndex-th immediate switch jump table.  If the scrutinee value
+           is an immediate number in the range covered by the referenced jump
+           table, and the value at jumpTable[scrutinee value] is non-zero, then
+           that value is used as the jump offset, otherwise defaultOffset is used.
+         */
+        int tableIndex = (++vPC)->u.operand;
+        int defaultOffset = (++vPC)->u.operand;
+        JSValue* scrutinee = r[(++vPC)->u.operand].jsValue(exec);
+        if (!JSImmediate::isNumber(scrutinee))
+            vPC += defaultOffset;
+        else {
+            int32_t value = JSImmediate::getTruncatedInt32(scrutinee);
+            vPC += codeBlock->immediateSwitchJumpTables[tableIndex].offsetForValue(value, defaultOffset);
+        }
+        NEXT_OPCODE;
+    }
+    BEGIN_OPCODE(op_switch_char) {
+        /* switch_char tableIndex(n) defaultOffset(offset) scrutinee(r)
+
+           Performs a range checked switch on the scrutinee value, using
+           the tableIndex-th character switch jump table.  If the scrutinee value
+           is a single character string in the range covered by the referenced jump
+           table, and the value at jumpTable[scrutinee value] is non-zero, then
+           that value is used as the jump offset, otherwise defaultOffset is used.
+         */
+        int tableIndex = (++vPC)->u.operand;
+        int defaultOffset = (++vPC)->u.operand;
+        JSValue* scrutinee = r[(++vPC)->u.operand].jsValue(exec);
+        if (scrutinee->type() != StringType)
+            vPC += defaultOffset;
+        else {
+            UString::Rep* value = static_cast<JSString*>(scrutinee)->value().rep();
+            if (value->size() != 1)
+                vPC += defaultOffset;
+            else
+                vPC += codeBlock->characterSwitchJumpTables[tableIndex].offsetForValue(value->data()[0], defaultOffset);
+        }
+        NEXT_OPCODE;
+    }
+    BEGIN_OPCODE(op_switch_string) {
+        /* switch_string tableIndex(n) defaultOffset(offset) scrutinee(r)
+
+           Performs a sparse hashmap based switch on the value in the scrutinee
+           register, using the tableIndex-th string switch jump table.  If the 
+           scrutinee value is a string that exists as a key in the referenced 
+           jump table, then the value associated with the string is used as the 
+           jump offset, otherwise defaultOffset is used.
+         */
+        int tableIndex = (++vPC)->u.operand;
+        int defaultOffset = (++vPC)->u.operand;
+        JSValue* scrutinee = r[(++vPC)->u.operand].jsValue(exec);
+        if (scrutinee->type() != StringType)
+            vPC += defaultOffset;
+        else 
+            vPC += offsetForStringSwitch(codeBlock->stringSwitchJumpTables[tableIndex], scrutinee, defaultOffset);
+        NEXT_OPCODE;
+    }
     BEGIN_OPCODE(op_new_func) {
         /* new_func dst(r) func(f)
 
index 72f55bc..af6e780 100644 (file)
@@ -105,6 +105,9 @@ static const char* opcodeNames[] = {
     "loop             ",
     "loop_if_true     ",
     "loop_if_less     ",
+    "switch_imm       ",
+    "switch_char      ",
+    "switch_string    ",
 
     "new_func         ",
     "new_func_exp     ",
index 60ac844..a2e2733 100644 (file)
@@ -103,6 +103,9 @@ namespace KJS {
         macro(op_loop) \
         macro(op_loop_if_true) \
         macro(op_loop_if_less) \
+        macro(op_switch_imm) \
+        macro(op_switch_char) \
+        macro(op_switch_string) \
         \
         macro(op_new_func) \
         macro(op_new_func_exp) \
index cda2aeb..7b34442 100644 (file)
@@ -70,7 +70,7 @@ namespace KJS {
         {
             return (getTag(v) == NumberType);
         }
-        
+
         static ALWAYS_INLINE bool isPositiveNumber(const JSValue* v)
         {
             // A single mask to check for the sign bit and the number tag all at once.
index 54ff419..406777f 100644 (file)
@@ -1393,31 +1393,118 @@ RegisterID* WithNode::emitCode(CodeGenerator& generator, RegisterID* dst)
 }
 
 // ------------------------------ CaseBlockNode --------------------------------
-
-RegisterID* CaseBlockNode::emitCodeForBlock(CodeGenerator& generator, RegisterID* switchExpression, RegisterID* dst)
+enum SwitchKind { 
+    SwitchUnset = 0,
+    SwitchNumber = 1, 
+    SwitchString = 2, 
+    SwitchNeither = 3 
+};
+
+static void processClauseList(ClauseListNode* list, Vector<ExpressionNode*, 8>& literalVector, SwitchKind& typeForTable, bool& singleCharacterSwitch, int32_t& min_num, int32_t& max_num)
+{
+    for (; list; list = list->getNext()) {
+        ExpressionNode* clauseExpression = list->getClause()->expr();
+        literalVector.append(clauseExpression);
+        if (clauseExpression->isNumber()) {
+            double value = static_cast<NumberNode*>(clauseExpression)->value();
+            if ((typeForTable & ~SwitchNumber) || !JSImmediate::from(value)) {
+                typeForTable = SwitchNeither;
+                break;
+            }
+            int32_t intVal = static_cast<int32_t>(value);
+            ASSERT(intVal == value);
+            if (intVal < min_num)
+                min_num = intVal;
+            if (intVal > max_num)
+                max_num = intVal;
+            typeForTable = SwitchNumber;
+            continue;
+        }
+        if (clauseExpression->isString()) {
+            if (typeForTable & ~SwitchString) {
+                typeForTable = SwitchNeither;
+                break;
+            }
+            UString& value = static_cast<StringNode*>(clauseExpression)->value();
+            if (singleCharacterSwitch &= value.size() == 1) {
+                int32_t intVal = value.rep()->data()[0];
+                if (intVal < min_num)
+                    min_num = intVal;
+                if (intVal > max_num)
+                    max_num = intVal;
+            }
+            typeForTable = SwitchString;
+            continue;
+        }
+        typeForTable = SwitchNeither;
+        break;        
+    }
+}
+    
+SwitchInfo::SwitchType CaseBlockNode::tryOptimizedSwitch(Vector<ExpressionNode*, 8>& literalVector, int32_t& min_num, int32_t& max_num)
 {
-    Vector<RefPtr<LabelID>, 8> labelVector;
-
-    // Setup jumps
-    for (ClauseListNode* list = m_list1.get(); list; list = list->getNext()) {
-        RefPtr<RegisterID> clauseVal = generator.newTemporary();
-        generator.emitNode(clauseVal.get(), list->getClause()->expr());
-        generator.emitBinaryOp(op_stricteq, clauseVal.get(), clauseVal.get(), switchExpression);
-        labelVector.append(generator.newLabel());
-        generator.emitJumpIfTrue(clauseVal.get(), labelVector[labelVector.size() - 1].get());
+    SwitchKind typeForTable = SwitchUnset;
+    bool singleCharacterSwitch = true;
+    
+    processClauseList(m_list1.get(), literalVector, typeForTable, singleCharacterSwitch, min_num, max_num);
+    processClauseList(m_list2.get(), literalVector, typeForTable, singleCharacterSwitch, min_num, max_num);
+    
+    if (typeForTable == SwitchUnset || typeForTable == SwitchNeither)
+        return SwitchInfo::SwitchNone;
+    
+    if (typeForTable == SwitchNumber) {
+        int32_t range = max_num - min_num;
+        if (min_num <= max_num && range <= 1000 && (range / literalVector.size()) < 10)
+            return SwitchInfo::SwitchImmediate;
+        return SwitchInfo::SwitchNone;
+    } 
+    
+    ASSERT(typeForTable == SwitchString);
+    
+    if (singleCharacterSwitch) {
+        int32_t range = max_num - min_num;
+        if (min_num <= max_num && range <= 1000 && (range / literalVector.size()) < 10)
+            return SwitchInfo::SwitchCharacter;
     }
 
-    for (ClauseListNode* list = m_list2.get(); list; list = list->getNext()) {
-        RefPtr<RegisterID> clauseVal = generator.newTemporary();
-        generator.emitNode(clauseVal.get(), list->getClause()->expr());
-        generator.emitBinaryOp(op_stricteq, clauseVal.get(), clauseVal.get(), switchExpression);
-        labelVector.append(generator.newLabel());
-        generator.emitJumpIfTrue(clauseVal.get(), labelVector[labelVector.size() - 1].get());
-    }
+    return SwitchInfo::SwitchString;
+}
 
+RegisterID* CaseBlockNode::emitCodeForBlock(CodeGenerator& generator, RegisterID* switchExpression, RegisterID* dst)
+{
     RefPtr<LabelID> defaultLabel;
-    defaultLabel = generator.newLabel();
-    generator.emitJump(defaultLabel.get());
+    Vector<RefPtr<LabelID>, 8> labelVector;
+    Vector<ExpressionNode*, 8> literalVector;
+    int32_t min_num = std::numeric_limits<int32_t>::max();
+    int32_t max_num = std::numeric_limits<int32_t>::min();
+    SwitchInfo::SwitchType switchType = tryOptimizedSwitch(literalVector, min_num, max_num);
+
+    if (switchType != SwitchInfo::SwitchNone) {
+        // Prepare the various labels
+        for (uint32_t i = 0; i < literalVector.size(); i++)
+            labelVector.append(generator.newLabel());
+        defaultLabel = generator.newLabel();
+        generator.beginSwitch(switchExpression, switchType);
+    } else {
+        // Setup jumps
+        for (ClauseListNode* list = m_list1.get(); list; list = list->getNext()) {
+            RefPtr<RegisterID> clauseVal = generator.newTemporary();
+            generator.emitNode(clauseVal.get(), list->getClause()->expr());
+            generator.emitBinaryOp(op_stricteq, clauseVal.get(), clauseVal.get(), switchExpression);
+            labelVector.append(generator.newLabel());
+            generator.emitJumpIfTrue(clauseVal.get(), labelVector[labelVector.size() - 1].get());
+        }
+        
+        for (ClauseListNode* list = m_list2.get(); list; list = list->getNext()) {
+            RefPtr<RegisterID> clauseVal = generator.newTemporary();
+            generator.emitNode(clauseVal.get(), list->getClause()->expr());
+            generator.emitBinaryOp(op_stricteq, clauseVal.get(), clauseVal.get(), switchExpression);
+            labelVector.append(generator.newLabel());
+            generator.emitJumpIfTrue(clauseVal.get(), labelVector[labelVector.size() - 1].get());
+        }
+        defaultLabel = generator.newLabel();
+        generator.emitJump(defaultLabel.get());
+    }
 
     RegisterID* result = 0;
 
@@ -1440,7 +1527,10 @@ RegisterID* CaseBlockNode::emitCodeForBlock(CodeGenerator& generator, RegisterID
         generator.emitLabel(defaultLabel.get());
 
     ASSERT(i == labelVector.size());
-
+    if (switchType != SwitchInfo::SwitchNone) {
+        ASSERT(labelVector.size() == literalVector.size());
+        generator.endSwitch(labelVector.size(), labelVector.data(), literalVector.data(), defaultLabel.get(), min_num, max_num);
+    }
     return result;
 }
 
index c959bb1..5a7c8fc 100644 (file)
@@ -121,6 +121,12 @@ namespace KJS {
         FunctionStack& functionStack;
     };
 
+    struct SwitchInfo {
+        enum SwitchType { SwitchNone, SwitchImmediate, SwitchCharacter, SwitchString };
+        uint32_t opcodeOffset;
+        SwitchType switchType;
+    };
+
     class ParserRefCounted : Noncopyable {
     protected:
         ParserRefCounted(JSGlobalData*) KJS_FAST_CALL;
@@ -200,6 +206,7 @@ namespace KJS {
         }
 
         virtual bool isNumber() const KJS_FAST_CALL { return false; }
+        virtual bool isString() const KJS_FAST_CALL { return false; }
         virtual bool isPure(CodeGenerator&) const KJS_FAST_CALL { return false; }        
         virtual bool isLocation() const KJS_FAST_CALL { return false; }
         virtual bool isResolveNode() const KJS_FAST_CALL { return false; }
@@ -307,7 +314,9 @@ namespace KJS {
         }
 
         virtual RegisterID* emitCode(CodeGenerator&, RegisterID* = 0) KJS_FAST_CALL;
-
+        
+        virtual bool isString() const KJS_FAST_CALL { return true; }
+        UString& value() { return m_value; }
         virtual bool isPure(CodeGenerator&) const KJS_FAST_CALL { return true; }
         virtual void streamTo(SourceStream&) const KJS_FAST_CALL;
         virtual Precedence precedence() const { return PrecPrimary; }
@@ -2379,6 +2388,7 @@ namespace KJS {
         virtual Precedence precedence() const { ASSERT_NOT_REACHED(); return PrecExpression; }
 
     private:
+        SwitchInfo::SwitchType tryOptimizedSwitch(Vector<ExpressionNode*, 8>& literalVector, int32_t& min_num, int32_t& max_num);
         RefPtr<ClauseListNode> m_list1;
         RefPtr<CaseClauseNode> m_defaultClause;
         RefPtr<ClauseListNode> m_list2;
index 7744c42..f566caa 100644 (file)
@@ -1,3 +1,14 @@
+2008-07-23  Oliver Hunt  <oliver@apple.com>
+
+        Reviewed by Geoff Garen.
+
+        Test cases to cover the behaviour of switch statements, to make sure our
+        fast switch paths have not broken things.
+
+        * fast/js/resources/switch-behaviour.js: Added.
+        * fast/js/switch-behaviour-expected.txt: Added.
+        * fast/js/switch-behaviour.html: Added.
+
 2008-07-23  Dean Jackson  <dino@apple.com>
 
         Reviewed by Dan Bernstein.
diff --git a/LayoutTests/fast/js/resources/switch-behaviour.js b/LayoutTests/fast/js/resources/switch-behaviour.js
new file mode 100644 (file)
index 0000000..2b0872d
--- /dev/null
@@ -0,0 +1,336 @@
+description('This test covers the correctness and behaviour of switch statements.');
+
+// To make sure that there are no jump table indexing problems each of these functions
+// has multiple no-op switch statements to force not trivial jump table offsets for the
+// primary switch being tested.
+function characterSwitch(scrutinee) {
+    switch(null){
+        case '_':
+    }
+    switch(scrutinee) {
+        case '\0':
+            return '\0';
+        case 'A':
+            return 'A';
+        case 'a':
+            return 'a';
+        case 'A':
+            return 'Should not hit second \'A\'';
+        case '1':
+            return '1';
+        default:
+            return 'default';
+        case 'B':
+            return 'B';
+            switch(null){
+                case '1':
+            }
+    }
+    switch(null){
+        case '_':
+    }
+    return 'Did not reach default clause';
+}
+
+function sparseCharacterSwitch(scrutinee) {
+    switch(null){
+        case '1':
+    }
+    switch(null){
+        case '12':
+    }
+    switch(scrutinee) {
+        case '\0':
+            return '\0';
+        case 'A':
+            return 'A';
+        case 'a':
+            return 'a';
+        case 'A':
+            return 'Should not hit second \'A\'';
+        case '1':
+            return '1';
+        default:
+            return 'default';
+        case 'B':
+            return 'B';
+        case '\uffff':
+            return '\uffff';
+            switch(null){
+                case '1':
+            }
+            switch(null){
+                case '12':
+            }
+    }
+    return 'Did not reach default clause';
+    switch(null){
+        case '1':
+    }
+    switch(null){
+        case '12':
+    }
+}
+
+function stringSwitch(scrutinee) {
+    switch(null){
+        case '12':
+    }
+    switch(scrutinee) {
+        case '\0':
+            return '\0';
+        case 'A':
+            return 'A';
+        case 'a':
+            return 'a';
+        case 'A':
+            return 'Should not hit second \'A\'';
+        case '1':
+            return '1';
+        case '-1':
+            return '-1';
+        case '[object Object]':
+            return '[object Object]';
+        case 'some string':
+            return 'some string';
+        default:
+            return 'default';
+        case 'B':
+            return 'B';
+        case '\uffff':
+            return '\uffff'
+            switch(null){
+                case '12':
+            }
+    }
+    return 'Did not reach default clause';
+    switch(null){
+        case '12':
+    }
+}
+
+function numberSwitch(scrutinee) {
+    switch(null){
+        case 1:
+    }
+    switch(scrutinee) {
+        case  0:
+            return 0;
+        case  1:
+            return 1;
+        case  1:
+            return 'Should not hit second 1';
+        default:
+            return 'default';
+        case -1:
+            return -1;
+        switch(null){
+            case 1:
+        }
+    }
+    return 'Did not reach default clause';
+    switch(null){
+        case 1:
+    }
+}
+
+function sparseNumberSwitch(scrutinee) {
+    switch(null){
+        case 1:
+    }
+    switch(scrutinee) {
+        case  0:
+            return 0;
+        case  1:
+            return 1;
+        case  1:
+            return 'Should not hit second 1';
+        default:
+            return 'default';
+        case -1:
+            return -1;
+        case -1000000000:
+            return -1000000000;
+        case 1000000000:
+            return 1000000000;
+        switch(null){
+            case 1:
+        }
+    }
+    return 'Did not reach default clause';
+    switch(null){
+        case 1:
+    }
+}
+
+function generalSwitch(scrutinee) {
+    switch(null){
+        case 1:
+    }
+    switch(null){
+        case '1':
+    }
+    switch(null){
+        case '12':
+    }
+    switch(scrutinee) {
+        case  0:
+            return 0;
+        case  1:
+            return 1;
+        case  1:
+            return 'Should not hit second 1';
+        default:
+            return 'default';
+        case -1:
+            return -1;
+        case -1000000000:
+            return -1000000000;
+        case 1000000000:
+            return 1000000000;
+        case '\0':
+            return '\0';
+        case 'A':
+            return 'A';
+        case 'a':
+            return 'a';
+        case 'A':
+            return 'Should not hit second \'A\'';
+        case '1':
+            return '1';
+        case '-1':
+            return '-1';
+        case '[object Object]':
+            return '[object Object]';
+        case 'some string':
+            return 'some string';
+        case 'B':
+            return 'B';
+        case '\uffff':
+            return '\uffff'
+            switch(null){
+                case 1:
+            }
+            switch(null){
+                case '1':
+            }
+            switch(null){
+                case '12':
+            }
+    }
+    return 'Did not reach default clause';
+    switch(null){
+        case 1:
+    }
+    switch(null){
+        case '1':
+    }
+    switch(null){
+        case '12':
+    }
+}
+
+// Character switch
+shouldBe("characterSwitch('\0')", '"\0"');
+shouldBe("characterSwitch('A')", '"A"');
+shouldBe("characterSwitch('a')", '"a"');
+shouldBe("characterSwitch('1')", '"1"');
+shouldBe("characterSwitch('-1')", '"default"');
+shouldBe("characterSwitch('B')", '"B"');
+shouldBe("characterSwitch('\uffff')", '"default"');
+shouldBe("characterSwitch({toString: function(){return 'B'}})", '"default"');
+shouldBe("characterSwitch(0)", '"default"');
+shouldBe("characterSwitch(1)", '"default"');
+shouldBe("characterSwitch(-1)", '"default"');
+shouldBe("characterSwitch(-1000000000)", '"default"');
+shouldBe("characterSwitch(1000000000)", '"default"');
+shouldBe("characterSwitch({})", '"default"');
+
+// Sparse character switch
+shouldBe("sparseCharacterSwitch('\0')", '"\0"');
+shouldBe("sparseCharacterSwitch('A')", '"A"');
+shouldBe("sparseCharacterSwitch('a')", '"a"');
+shouldBe("sparseCharacterSwitch('1')", '"1"');
+shouldBe("sparseCharacterSwitch('-1')", '"default"');
+shouldBe("sparseCharacterSwitch('B')", '"B"');
+shouldBe("sparseCharacterSwitch('\uffff')", '"\uffff"');
+shouldBe("sparseCharacterSwitch({toString: function(){return 'B'}})", '"default"');
+shouldBe("sparseCharacterSwitch(0)", '"default"');
+shouldBe("sparseCharacterSwitch(1)", '"default"');
+shouldBe("sparseCharacterSwitch(-1)", '"default"');
+shouldBe("sparseCharacterSwitch(-1000000000)", '"default"');
+shouldBe("sparseCharacterSwitch(1000000000)", '"default"');
+shouldBe("sparseCharacterSwitch({})", '"default"');
+
+// String switch
+shouldBe("stringSwitch('\0')", '"\0"');
+shouldBe("stringSwitch('A')", '"A"');
+shouldBe("stringSwitch('a')", '"a"');
+shouldBe("stringSwitch('1')", '"1"');
+shouldBe("stringSwitch('-1')", '"-1"');
+shouldBe("stringSwitch('B')", '"B"');
+shouldBe("stringSwitch('\uffff')", '"\uffff"');
+shouldBe("stringSwitch('some string')", '"some string"');
+shouldBe("stringSwitch({toString: function(){return 'some string'}})", '"default"');
+shouldBe("stringSwitch('s')", '"default"');
+shouldBe("stringSwitch(0)", '"default"');
+shouldBe("stringSwitch(1)", '"default"');
+shouldBe("stringSwitch(-1)", '"default"');
+shouldBe("stringSwitch(-1000000000)", '"default"');
+shouldBe("stringSwitch(1000000000)", '"default"');
+shouldBe("stringSwitch({})", '"default"');
+
+// Number switch
+shouldBe("numberSwitch('\0')", '"default"');
+shouldBe("numberSwitch('A')", '"default"');
+shouldBe("numberSwitch('a')", '"default"');
+shouldBe("numberSwitch('1')", '"default"');
+shouldBe("numberSwitch('-1')", '"default"');
+shouldBe("numberSwitch('B')", '"default"');
+shouldBe("numberSwitch('\uffff')", '"default"');
+shouldBe("numberSwitch('some string')", '"default"');
+shouldBe("numberSwitch({valueOf: function(){return 0}})", '"default"');
+shouldBe("numberSwitch('s')", '"default"');
+shouldBe("numberSwitch(0)", '0');
+shouldBe("numberSwitch(1)", '1');
+shouldBe("numberSwitch(-1)", '-1');
+shouldBe("numberSwitch(-1000000000)", '"default"');
+shouldBe("numberSwitch(1000000000)", '"default"');
+shouldBe("numberSwitch({})", '"default"');
+
+// Sparse number switch
+shouldBe("sparseNumberSwitch('\0')", '"default"');
+shouldBe("sparseNumberSwitch('A')", '"default"');
+shouldBe("sparseNumberSwitch('a')", '"default"');
+shouldBe("sparseNumberSwitch('1')", '"default"');
+shouldBe("sparseNumberSwitch('-1')", '"default"');
+shouldBe("sparseNumberSwitch('B')", '"default"');
+shouldBe("sparseNumberSwitch('\uffff')", '"default"');
+shouldBe("sparseNumberSwitch('some string')", '"default"');
+shouldBe("sparseNumberSwitch({valueOf: function(){return 0}})", '"default"');
+shouldBe("sparseNumberSwitch('s')", '"default"');
+shouldBe("sparseNumberSwitch(0)", '0');
+shouldBe("sparseNumberSwitch(1)", '1');
+shouldBe("sparseNumberSwitch(-1)", '-1');
+shouldBe("sparseNumberSwitch(-1000000000)", '-1000000000');
+shouldBe("sparseNumberSwitch(1000000000)", '1000000000');
+shouldBe("sparseNumberSwitch({})", '"default"');
+
+// General switch
+shouldBe("generalSwitch('\0')", '"\0"');
+shouldBe("generalSwitch('A')", '"A"');
+shouldBe("generalSwitch('a')", '"a"');
+shouldBe("generalSwitch('1')", '"1"');
+shouldBe("generalSwitch('-1')", '"-1"');
+shouldBe("generalSwitch('B')", '"B"');
+shouldBe("generalSwitch('\uffff')", '"\uffff"');
+shouldBe("generalSwitch('some string')", '"some string"');
+shouldBe("generalSwitch({valueOf: function(){return 0}})", '"default"');
+shouldBe("generalSwitch('s')", '"default"');
+shouldBe("generalSwitch(0)", '0');
+shouldBe("generalSwitch(1)", '1');
+shouldBe("generalSwitch(-1)", '-1');
+shouldBe("generalSwitch(-1000000000)", '-1000000000');
+shouldBe("generalSwitch(1000000000)", '1000000000');
+shouldBe("generalSwitch({})", '"default"');
+var successfullyParsed = true;
diff --git a/LayoutTests/fast/js/switch-behaviour-expected.txt b/LayoutTests/fast/js/switch-behaviour-expected.txt
new file mode 100644 (file)
index 0000000..ab56b86
--- /dev/null
@@ -0,0 +1,101 @@
+This test covers the correctness and behaviour of switch statements.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS characterSwitch('') is ""
+PASS characterSwitch('A') is "A"
+PASS characterSwitch('a') is "a"
+PASS characterSwitch('1') is "1"
+PASS characterSwitch('-1') is "default"
+PASS characterSwitch('B') is "B"
+PASS characterSwitch('￿') is "default"
+PASS characterSwitch({toString: function(){return 'B'}}) is "default"
+PASS characterSwitch(0) is "default"
+PASS characterSwitch(1) is "default"
+PASS characterSwitch(-1) is "default"
+PASS characterSwitch(-1000000000) is "default"
+PASS characterSwitch(1000000000) is "default"
+PASS characterSwitch({}) is "default"
+PASS sparseCharacterSwitch('') is ""
+PASS sparseCharacterSwitch('A') is "A"
+PASS sparseCharacterSwitch('a') is "a"
+PASS sparseCharacterSwitch('1') is "1"
+PASS sparseCharacterSwitch('-1') is "default"
+PASS sparseCharacterSwitch('B') is "B"
+PASS sparseCharacterSwitch('￿') is "￿"
+PASS sparseCharacterSwitch({toString: function(){return 'B'}}) is "default"
+PASS sparseCharacterSwitch(0) is "default"
+PASS sparseCharacterSwitch(1) is "default"
+PASS sparseCharacterSwitch(-1) is "default"
+PASS sparseCharacterSwitch(-1000000000) is "default"
+PASS sparseCharacterSwitch(1000000000) is "default"
+PASS sparseCharacterSwitch({}) is "default"
+PASS stringSwitch('') is ""
+PASS stringSwitch('A') is "A"
+PASS stringSwitch('a') is "a"
+PASS stringSwitch('1') is "1"
+PASS stringSwitch('-1') is "-1"
+PASS stringSwitch('B') is "B"
+PASS stringSwitch('￿') is "￿"
+PASS stringSwitch('some string') is "some string"
+PASS stringSwitch({toString: function(){return 'some string'}}) is "default"
+PASS stringSwitch('s') is "default"
+PASS stringSwitch(0) is "default"
+PASS stringSwitch(1) is "default"
+PASS stringSwitch(-1) is "default"
+PASS stringSwitch(-1000000000) is "default"
+PASS stringSwitch(1000000000) is "default"
+PASS stringSwitch({}) is "default"
+PASS numberSwitch('') is "default"
+PASS numberSwitch('A') is "default"
+PASS numberSwitch('a') is "default"
+PASS numberSwitch('1') is "default"
+PASS numberSwitch('-1') is "default"
+PASS numberSwitch('B') is "default"
+PASS numberSwitch('￿') is "default"
+PASS numberSwitch('some string') is "default"
+PASS numberSwitch({valueOf: function(){return 0}}) is "default"
+PASS numberSwitch('s') is "default"
+PASS numberSwitch(0) is 0
+PASS numberSwitch(1) is 1
+PASS numberSwitch(-1) is -1
+PASS numberSwitch(-1000000000) is "default"
+PASS numberSwitch(1000000000) is "default"
+PASS numberSwitch({}) is "default"
+PASS sparseNumberSwitch('') is "default"
+PASS sparseNumberSwitch('A') is "default"
+PASS sparseNumberSwitch('a') is "default"
+PASS sparseNumberSwitch('1') is "default"
+PASS sparseNumberSwitch('-1') is "default"
+PASS sparseNumberSwitch('B') is "default"
+PASS sparseNumberSwitch('￿') is "default"
+PASS sparseNumberSwitch('some string') is "default"
+PASS sparseNumberSwitch({valueOf: function(){return 0}}) is "default"
+PASS sparseNumberSwitch('s') is "default"
+PASS sparseNumberSwitch(0) is 0
+PASS sparseNumberSwitch(1) is 1
+PASS sparseNumberSwitch(-1) is -1
+PASS sparseNumberSwitch(-1000000000) is -1000000000
+PASS sparseNumberSwitch(1000000000) is 1000000000
+PASS sparseNumberSwitch({}) is "default"
+PASS generalSwitch('') is ""
+PASS generalSwitch('A') is "A"
+PASS generalSwitch('a') is "a"
+PASS generalSwitch('1') is "1"
+PASS generalSwitch('-1') is "-1"
+PASS generalSwitch('B') is "B"
+PASS generalSwitch('￿') is "￿"
+PASS generalSwitch('some string') is "some string"
+PASS generalSwitch({valueOf: function(){return 0}}) is "default"
+PASS generalSwitch('s') is "default"
+PASS generalSwitch(0) is 0
+PASS generalSwitch(1) is 1
+PASS generalSwitch(-1) is -1
+PASS generalSwitch(-1000000000) is -1000000000
+PASS generalSwitch(1000000000) is 1000000000
+PASS generalSwitch({}) is "default"
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/js/switch-behaviour.html b/LayoutTests/fast/js/switch-behaviour.html
new file mode 100644 (file)
index 0000000..ead9703
--- /dev/null
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/switch-behaviour.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>