Generate jump table for JSOP_TABLESWITCH (bug 591972, r=dvander)
authorJan de Mooij <jandemooij@gmail.com>
Wed, 15 Dec 2010 19:19:11 +0100
changeset 59979 673ae0e2f656e20dd858a59a14be50f68201d64c
parent 59978 e0fc487c23f492e8f9a530ca1188627575063c02
child 59980 74eea2c10449583222a2d37fb9e5c23999478edc
push id17820
push usercleary@mozilla.com
push dateTue, 04 Jan 2011 21:40:57 +0000
treeherdermozilla-central@969691cfe40e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdvander
bugs591972
milestone2.0b9pre
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Generate jump table for JSOP_TABLESWITCH (bug 591972, r=dvander)
js/src/assembler/assembler/MacroAssemblerX86Common.h
js/src/assembler/assembler/X86Assembler.h
js/src/jit-test/tests/jaeger/tableSwitchConst.js
js/src/jit-test/tests/jaeger/tableSwitchDouble.js
js/src/jit-test/tests/jaeger/tableSwitchEmpty.js
js/src/jit-test/tests/jaeger/tableSwitchFloat.js
js/src/jit-test/tests/jaeger/tableSwitchNeg.js
js/src/methodjit/Compiler.cpp
js/src/methodjit/Compiler.h
js/src/methodjit/StubCalls.cpp
--- a/js/src/assembler/assembler/MacroAssemblerX86Common.h
+++ b/js/src/assembler/assembler/MacroAssemblerX86Common.h
@@ -852,17 +852,21 @@ public:
     }
 
     // Address is a memory location containing the address to jump to
     void jump(Address address)
     {
         m_assembler.jmp_m(address.offset, address.base);
     }
 
-    
+    void jump(BaseIndex address)
+    {
+        m_assembler.jmp_m(address.offset, address.base, address.index, address.scale);
+    }
+
     // Arithmetic control flow operations:
     //
     // This set of conditional branch operations branch based
     // on the result of an arithmetic operation.  The operation
     // is performed as normal, storing the result.
     //
     // * jz operations branch if the result is zero.
     // * jo operations branch if the (signed) arithmetic
--- a/js/src/assembler/assembler/X86Assembler.h
+++ b/js/src/assembler/assembler/X86Assembler.h
@@ -1675,16 +1675,23 @@ public:
     }
     
     void jmp_m(int offset, RegisterID base)
     {
         FIXME_INSN_PRINTING;
         m_formatter.oneByteOp(OP_GROUP5_Ev, GROUP5_OP_JMPN, base, offset);
     }
 
+    void jmp_m(int offset, RegisterID base, RegisterID index, int scale) {
+        js::JaegerSpew(js::JSpew_Insns,
+                       IPFX "jmp       ((%d(%s,%s,%d)))\n", MAYBE_PAD,
+                       offset, nameIReg(base), nameIReg(index), scale);
+        m_formatter.oneByteOp(OP_GROUP5_Ev, GROUP5_OP_JMPN, base, index, scale, offset);
+    }
+
     JmpSrc jne()
     {
         return jCC(ConditionNE);
     }
     
     JmpSrc jnz()
     {
         // printing done by jne()
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/tableSwitchConst.js
@@ -0,0 +1,18 @@
+function f() {
+    switch(2) {
+        case 1: return 1;
+        case 2: return 2;
+        default: return -1;
+    }
+}
+assertEq(f(), 2);
+
+function g() {
+    switch(3.14) {
+        case 3: return 3;
+        case 4: return 4;
+        default: return -1;
+    }
+}
+assertEq(g(), -1);
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/tableSwitchDouble.js
@@ -0,0 +1,13 @@
+
+function f(a) {
+    switch(a) {
+        case 3: return 3;
+        case 4: return 4;
+        default: return -1;
+    }
+}
+
+assertEq(f(-0.0), -1);
+assertEq(f(3.14), -1);
+assertEq(f(12.34), -1);
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/tableSwitchEmpty.js
@@ -0,0 +1,14 @@
+
+function f(a) {
+    switch(a) {
+    }
+    switch(a) {
+        default: return 0;
+    }
+    assertEq(0, 1);
+}
+
+assertEq(f(), 0);
+assertEq(f(0), 0);
+assertEq(f(1.1), 0);
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/tableSwitchFloat.js
@@ -0,0 +1,18 @@
+function f() {
+    switch(2) {
+        case 1: return 1;
+        case 2: return 2;
+        default: return -1;
+    }
+}
+assertEq(f(), 2);
+
+function g() {
+    switch(3.14) {
+        case 3: return 3;
+        case 4: return 4;
+        default: return -1;
+    }
+}
+assertEq(g(), -1);
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/tableSwitchNeg.js
@@ -0,0 +1,27 @@
+
+function f(a) {
+    switch(a) {
+        case -1: return 1;
+        case -2: return 2;
+        case -5: return 5;
+        default: return 10;
+    }
+}
+
+assertEq(f(-1), 1);
+assertEq(f(-2), 2);
+assertEq(f(-5), 5);
+
+assertEq(f(-3), 10);
+assertEq(f(-6), 10);
+assertEq(f(0), 10);
+assertEq(f(1), 10);
+
+assertEq(f(-2147483647), 10);
+assertEq(f(-2147483648), 10);
+assertEq(f(-2147483649), 10);
+
+assertEq(f(2147483647), 10);
+assertEq(f(2147483648), 10);
+assertEq(f(2147483649), 10);
+
--- a/js/src/methodjit/Compiler.cpp
+++ b/js/src/methodjit/Compiler.cpp
@@ -105,16 +105,18 @@ mjit::Compiler::Compiler(JSContext *cx, 
 #if defined JS_POLYIC
     pics(CompilerAllocPolicy(cx, *thisFromCtor())), 
     getElemICs(CompilerAllocPolicy(cx, *thisFromCtor())),
     setElemICs(CompilerAllocPolicy(cx, *thisFromCtor())),
 #endif
     callPatches(CompilerAllocPolicy(cx, *thisFromCtor())),
     callSites(CompilerAllocPolicy(cx, *thisFromCtor())), 
     doubleList(CompilerAllocPolicy(cx, *thisFromCtor())),
+    jumpTables(CompilerAllocPolicy(cx, *thisFromCtor())),
+    jumpTableOffsets(CompilerAllocPolicy(cx, *thisFromCtor())),
     stubcc(cx, *thisFromCtor(), frame, script),
     debugMode_(cx->compartment->debugMode),
 #if defined JS_TRACER
     addTraceHints(cx->traceJitEnabled),
 #endif
     oomInVector(false),
     applyTricks(NoApplyTricks)
 {
@@ -388,17 +390,18 @@ mjit::Compiler::finishThisUp(JITScript *
 #ifdef JS_CPU_ARM
     masm.forceFlushConstantPool();
     stubcc.masm.forceFlushConstantPool();
 #endif
     JaegerSpew(JSpew_Insns, "## Fast code (masm) size = %u, Slow code (stubcc) size = %u.\n", masm.size(), stubcc.size());
 
     size_t totalSize = masm.size() +
                        stubcc.size() +
-                       doubleList.length() * sizeof(double);
+                       doubleList.length() * sizeof(double) +
+                       jumpTableOffsets.length() * sizeof(void *);
 
     JSC::ExecutablePool *execPool = getExecPool(script, totalSize);
     if (!execPool)
         return Compile_Abort;
 
     uint8 *result = (uint8 *)execPool->alloc(totalSize);
     JSC::ExecutableAllocator::makeWritable(result, totalSize);
     masm.executableCopy(result);
@@ -761,16 +764,31 @@ mjit::Compiler::finishThisUp(JITScript *
         DoublePatch &patch = doubleList[i];
         doubleVec[i] = patch.d;
         if (patch.ool)
             stubCode.patch(patch.label, &doubleVec[i]);
         else
             fullCode.patch(patch.label, &doubleVec[i]);
     }
 
+    /* Generate jump tables. */
+    void **jumpVec = (void **)(doubleVec + doubleList.length());
+
+    for (size_t i = 0; i < jumpTableOffsets.length(); i++) {
+        uint32 offset = jumpTableOffsets[i];
+        JS_ASSERT(jumpMap[offset].isValid());
+        jumpVec[i] = (void *)(result + masm.distanceOf(jumpMap[offset]));
+    }
+
+    /* Patch jump table references. */
+    for (size_t i = 0; i < jumpTables.length(); i++) {
+        JumpTable &jumpTable = jumpTables[i];
+        fullCode.patch(jumpTable.label, &jumpVec[jumpTable.offsetIndex]);
+    }
+
     /* Patch all outgoing calls. */
     masm.finalize(fullCode);
     stubcc.masm.finalize(stubCode);
 
     JSC::ExecutableAllocator::makeExecutable(result, masm.size() + stubcc.size());
     JSC::ExecutableAllocator::cacheFlush(result, masm.size() + stubcc.size());
 
     /* Build the table of call sites. */
@@ -1423,24 +1441,28 @@ mjit::Compiler::generateMethod()
 
           BEGIN_CASE(JSOP_OR)
           BEGIN_CASE(JSOP_AND)
             if (!jsop_andor(op, PC + GET_JUMP_OFFSET(PC)))
                 return Compile_Error;
           END_CASE(JSOP_AND)
 
           BEGIN_CASE(JSOP_TABLESWITCH)
+#if defined JS_CPU_ARM /* Need to implement jump(BaseIndex) for ARM */
             frame.syncAndForgetEverything();
             masm.move(ImmPtr(PC), Registers::ArgReg1);
 
             /* prepareStubCall() is not needed due to syncAndForgetEverything() */
             INLINE_STUBCALL(stubs::TableSwitch);
             frame.pop();
 
             masm.jump(Registers::ReturnReg);
+#else
+            jsop_tableswitch(PC);
+#endif
             PC += js_GetVariableBytecodeLength(PC);
             break;
           END_CASE(JSOP_TABLESWITCH)
 
           BEGIN_CASE(JSOP_LOOKUPSWITCH)
             frame.syncAndForgetEverything();
             masm.move(ImmPtr(PC), Registers::ArgReg1);
 
@@ -4938,16 +4960,102 @@ mjit::Compiler::constructThis()
     if (protoReg != Registers::ArgReg1)
         masm.move(protoReg, Registers::ArgReg1);
     INLINE_STUBCALL(stubs::CreateThis);
     frame.freeReg(protoReg);
     return true;
 }
 
 void
+mjit::Compiler::jsop_tableswitch(jsbytecode *pc)
+{
+#if defined JS_CPU_ARM
+    JS_NOT_REACHED("Implement jump(BaseIndex) for ARM");
+#else
+    jsbytecode *originalPC = pc;
+
+    uint32 defaultTarget = GET_JUMP_OFFSET(pc);
+    pc += JUMP_OFFSET_LEN;
+
+    jsint low = GET_JUMP_OFFSET(pc);
+    pc += JUMP_OFFSET_LEN;
+    jsint high = GET_JUMP_OFFSET(pc);
+    pc += JUMP_OFFSET_LEN;
+    int numJumps = high + 1 - low;
+    JS_ASSERT(numJumps >= 0);
+
+    /*
+     * If there are no cases, this is a no-op. The default case immediately
+     * follows in the bytecode and is always taken.
+     */
+    if (numJumps == 0) {
+        frame.pop();
+        return;
+    }
+
+    FrameEntry *fe = frame.peek(-1);
+    if (fe->isNotType(JSVAL_TYPE_INT32) || numJumps > 256) {
+        frame.syncAndForgetEverything();
+        masm.move(ImmPtr(originalPC), Registers::ArgReg1);
+
+        /* prepareStubCall() is not needed due to forgetEverything() */
+        INLINE_STUBCALL(stubs::TableSwitch);
+        frame.pop();
+        masm.jump(Registers::ReturnReg);
+        return;
+    }
+
+    RegisterID dataReg;
+    if (fe->isConstant()) {
+        JS_ASSERT(fe->isType(JSVAL_TYPE_INT32));
+        dataReg = frame.allocReg();
+        masm.move(Imm32(fe->getValue().toInt32()), dataReg);
+    } else {
+        dataReg = frame.copyDataIntoReg(fe);
+    }
+
+    RegisterID reg = frame.allocReg();
+    frame.syncAndForgetEverything();
+
+    MaybeJump notInt;
+    if (!fe->isType(JSVAL_TYPE_INT32))
+        notInt = masm.testInt32(Assembler::NotEqual, frame.addressOf(fe));
+
+    JumpTable jt;
+    jt.offsetIndex = jumpTableOffsets.length();
+    jt.label = masm.moveWithPatch(ImmPtr(NULL), reg);
+    jumpTables.append(jt);
+
+    for (int i = 0; i < numJumps; i++) {
+        uint32 target = GET_JUMP_OFFSET(pc);
+        if (!target)
+            target = defaultTarget;
+        uint32 offset = (originalPC + target) - script->code;
+        jumpTableOffsets.append(offset);
+        pc += JUMP_OFFSET_LEN;
+    }
+    if (low != 0)
+        masm.sub32(Imm32(low), dataReg);
+    Jump defaultCase = masm.branch32(Assembler::AboveOrEqual, dataReg, Imm32(numJumps));
+    BaseIndex jumpTarget(reg, dataReg, Assembler::ScalePtr);
+    masm.jump(jumpTarget);
+
+    if (notInt.isSet()) {
+        stubcc.linkExitDirect(notInt.get(), stubcc.masm.label());
+        stubcc.leave();
+        stubcc.masm.move(ImmPtr(originalPC), Registers::ArgReg1);
+        OOL_STUBCALL(stubs::TableSwitch);
+        stubcc.masm.jump(Registers::ReturnReg);
+    }
+    frame.pop();
+    jumpAndTrace(defaultCase, originalPC + defaultTarget);
+#endif
+}
+
+void
 mjit::Compiler::jsop_callelem_slow()
 {
     prepareStubCall(Uses(2));
     INLINE_STUBCALL(stubs::CallElem);
     frame.popn(2);
     frame.pushSynced();
     frame.pushSynced();
 }
--- a/js/src/methodjit/Compiler.h
+++ b/js/src/methodjit/Compiler.h
@@ -261,16 +261,21 @@ class Compiler : public BaseCompiler
     };
 
     struct DoublePatch {
         double d;
         DataLabelPtr label;
         bool ool;
     };
 
+    struct JumpTable {
+        DataLabelPtr label;
+        size_t offsetIndex;
+    };
+
     JSStackFrame *fp;
     JSScript *script;
     JSObject *scopeChain;
     JSObject *globalObj;
     JSFunction *fun;
     bool isConstructing;
     analyze::Script *analysis;
     Label *jumpMap;
@@ -288,16 +293,18 @@ class Compiler : public BaseCompiler
 #if defined JS_POLYIC
     js::Vector<PICGenInfo, 16, CompilerAllocPolicy> pics;
     js::Vector<GetElementICInfo, 16, CompilerAllocPolicy> getElemICs;
     js::Vector<SetElementICInfo, 16, CompilerAllocPolicy> setElemICs;
 #endif
     js::Vector<CallPatchInfo, 64, CompilerAllocPolicy> callPatches;
     js::Vector<InternalCallSite, 64, CompilerAllocPolicy> callSites;
     js::Vector<DoublePatch, 16, CompilerAllocPolicy> doubleList;
+    js::Vector<JumpTable, 16> jumpTables;
+    js::Vector<uint32, 16> jumpTableOffsets;
     StubCompiler stubcc;
     Label invokeLabel;
     Label arityLabel;
     bool debugMode_;
     bool addTraceHints;
     bool oomInVector;       // True if we have OOM'd appending to a vector. 
     enum { NoApplyTricks, LazyArgsObj } applyTricks;
 
@@ -401,16 +408,17 @@ class Compiler : public BaseCompiler
     bool jsop_callprop_generic(JSAtom *atom);
     bool jsop_instanceof();
     void jsop_name(JSAtom *atom);
     bool jsop_xname(JSAtom *atom);
     void enterBlock(JSObject *obj);
     void leaveBlock();
     void emitEval(uint32 argc);
     void jsop_arguments();
+    void jsop_tableswitch(jsbytecode *pc);
 
     /* Fast arithmetic. */
     void jsop_binary(JSOp op, VoidStub stub);
     void jsop_binary_full(FrameEntry *lhs, FrameEntry *rhs, JSOp op, VoidStub stub);
     void jsop_binary_full_simple(FrameEntry *fe, JSOp op, VoidStub stub);
     void jsop_binary_double(FrameEntry *lhs, FrameEntry *rhs, JSOp op, VoidStub stub);
     void slowLoadConstantDouble(Assembler &masm, FrameEntry *fe,
                                 FPRegisterID fpreg);
--- a/js/src/methodjit/StubCalls.cpp
+++ b/js/src/methodjit/StubCalls.cpp
@@ -2571,19 +2571,19 @@ stubs::TableSwitch(VMFrame &f, jsbytecod
         } else if (!JSDOUBLE_IS_INT32(d, (int32_t *)&tableIdx)) {
             goto finally;
         }
     } else {
         goto finally;
     }
 
     {
-        uint32 low = GET_JUMP_OFFSET(pc);
+        jsint low = GET_JUMP_OFFSET(pc);
         pc += JUMP_OFFSET_LEN;
-        uint32 high = GET_JUMP_OFFSET(pc);
+        jsint high = GET_JUMP_OFFSET(pc);
         pc += JUMP_OFFSET_LEN;
 
         tableIdx -= low;
         if ((jsuint) tableIdx < (jsuint)(high - low + 1)) {
             pc += JUMP_OFFSET_LEN * tableIdx;
             uint32 candidateOffset = GET_JUMP_OFFSET(pc);
             if (candidateOffset)
                 jumpOffset = candidateOffset;