Changeset 37831 in webkit for trunk/JavaScriptCore/VM


Ignore:
Timestamp:
Oct 23, 2008, 3:29:54 PM (17 years ago)
Author:
[email protected]
Message:

2008-10-23 Gavin Barraclough <​[email protected]>

Reviewed by Oliver Hunt.

Fix hideous pathological case performance when looking up repatch info, bug #21727.

When repatching JIT code to optimize we look up records providing information about
the generated code (also used to track recsources used in linking to be later released).
The lookup was being performed using a linear scan of all such records.

(1) Split up the different types of reptach information. This means we can search them

separately, and in some cases should reduce their size.

(2) In the case of property accesses, search with a binary chop over the data.
(3) In the case of calls, pass a pointer to the repatch info into the relink function.

  • VM/CTI.cpp: (JSC::CTI::CTI): (JSC::CTI::compileOpCall): (JSC::CTI::privateCompileMainPass): (JSC::CTI::privateCompileSlowCases): (JSC::CTI::privateCompile): (JSC::CTI::unlinkCall): (JSC::CTI::linkCall):
  • VM/CTI.h:
  • VM/CodeBlock.cpp: (JSC::CodeBlock::dump): (JSC::CodeBlock::~CodeBlock): (JSC::CodeBlock::unlinkCallers): (JSC::CodeBlock::derefStructureIDs):
  • VM/CodeBlock.h: (JSC::StructureStubInfo::StructureStubInfo): (JSC::CallLinkInfo::CallLinkInfo): (JSC::CallLinkInfo::setUnlinked): (JSC::CallLinkInfo::isLinked): (JSC::getStructureStubInfoReturnLocation): (JSC::binaryChop): (JSC::CodeBlock::addCaller): (JSC::CodeBlock::getStubInfo):
  • VM/CodeGenerator.cpp: (JSC::CodeGenerator::emitResolve): (JSC::CodeGenerator::emitGetById): (JSC::CodeGenerator::emitPutById): (JSC::CodeGenerator::emitCall): (JSC::CodeGenerator::emitConstruct):
  • VM/Machine.cpp: (JSC::Machine::cti_vm_lazyLinkCall):
Location:
trunk/JavaScriptCore/VM
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/VM/CTI.cpp

    r37812 r37831  
    514514    , m_codeBlock(codeBlock)
    515515    , m_labels(codeBlock ? codeBlock->instructions.size() : 0)
    516     , m_structureStubCompilationInfo(codeBlock ? codeBlock->structureIDInstructions.size() : 0)
     516    , m_propertyAccessCompilationInfo(codeBlock ? codeBlock->propertyAccessInstructions.size() : 0)
     517    , m_callStructureStubCompilationInfo(codeBlock ? codeBlock->callLinkInfos.size() : 0)
    517518{
    518519}
    … …  
    577578}
    578579
    579 void CTI::compileOpCall(Instruction* instruction, unsigned i, unsigned structureIDInstructionIndex, CompileOpCallType type)
     580void CTI::compileOpCall(Instruction* instruction, unsigned i, unsigned callLinkInfoIndex, CompileOpCallType type)
    580581{
    581582    int dst = instruction[1].u.operand;
    … …  
    615616    m_slowCases.append(SlowCaseEntry(m_jit.emitUnlinkedJne(), i));
    616617    ASSERT(X86Assembler::getDifferenceBetweenLabels(addressOfLinkedFunctionCheck, m_jit.label()) == repatchOffsetOpCallCall);
    617     m_structureStubCompilationInfo[structureIDInstructionIndex].hotPathBegin = addressOfLinkedFunctionCheck;
     618    m_callStructureStubCompilationInfo[callLinkInfoIndex].hotPathBegin = addressOfLinkedFunctionCheck;
    618619
    619620    // The following is the fast case, only used whan a callee can be linked.
    … …  
    639640
    640641    // Call to the callee
    641     m_structureStubCompilationInfo[structureIDInstructionIndex].hotPathOther = emitNakedCall(i, unreachable);
     642    m_callStructureStubCompilationInfo[callLinkInfoIndex].hotPathOther = emitNakedCall(i, unreachable);
    642643   
    643644    if (type == OpCallEval)
    … …  
    950951    unsigned instructionCount = m_codeBlock->instructions.size();
    951952
    952     unsigned structureIDInstructionIndex = 0;
     953    unsigned propertyAccessInstructionIndex = 0;
     954    unsigned callLinkInfoIndex = 0;
    953955
    954956    for (unsigned i = 0; i < instructionCount; ) {
    … …  
    10951097            emitGetArg(instruction[i + 3].u.operand, X86::edx);
    10961098
    1097             ASSERT(m_codeBlock->structureIDInstructions[structureIDInstructionIndex].opcodeIndex == i);
     1099            ASSERT(m_codeBlock->propertyAccessInstructions[propertyAccessInstructionIndex].opcodeIndex == i);
    10981100            X86Assembler::JmpDst hotPathBegin = m_jit.label();
    1099             m_structureStubCompilationInfo[structureIDInstructionIndex].hotPathBegin = hotPathBegin;
    1100             ++structureIDInstructionIndex;
     1101            m_propertyAccessCompilationInfo[propertyAccessInstructionIndex].hotPathBegin = hotPathBegin;
     1102            ++propertyAccessInstructionIndex;
    11011103
    11021104            // Jump to a slow case if either the base object is an immediate, or if the StructureID does not match.
    … …  
    11231125            emitGetArg(instruction[i + 2].u.operand, X86::eax);
    11241126
    1125             ASSERT(m_codeBlock->structureIDInstructions[structureIDInstructionIndex].opcodeIndex == i);
     1127            ASSERT(m_codeBlock->propertyAccessInstructions[propertyAccessInstructionIndex].opcodeIndex == i);
    11261128
    11271129            X86Assembler::JmpDst hotPathBegin = m_jit.label();
    1128             m_structureStubCompilationInfo[structureIDInstructionIndex].hotPathBegin = hotPathBegin;
    1129             ++structureIDInstructionIndex;
     1130            m_propertyAccessCompilationInfo[propertyAccessInstructionIndex].hotPathBegin = hotPathBegin;
     1131            ++propertyAccessInstructionIndex;
    11301132
    11311133            emitJumpSlowCaseIfNotJSCell(X86::eax, i);
    … …  
    12531255        }
    12541256        case op_call: {
    1255             compileOpCall(instruction + i, i, structureIDInstructionIndex++);
     1257            compileOpCall(instruction + i, i, callLinkInfoIndex++);
    12561258            i += 7;
    12571259            break;
    … …  
    13491351        }
    13501352        case op_construct: {
    1351             compileOpCall(instruction + i, i, structureIDInstructionIndex++, OpConstruct);
     1353            compileOpCall(instruction + i, i, callLinkInfoIndex++, OpConstruct);
    13521354            i += 7;
    13531355            break;
    … …  
    14911493            m_jit.movl_mr(structureIDAddr, X86::edx);
    14921494            m_jit.cmpl_rm(X86::edx, OBJECT_OFFSET(JSCell, m_structureID), X86::eax);
    1493             X86Assembler::JmpSrc slowCase = m_jit.emitUnlinkedJne(); // StructureIDs don't match
    1494             m_slowCases.append(SlowCaseEntry(slowCase, i));
     1495            X86Assembler::JmpSrc noMatch = m_jit.emitUnlinkedJne(); // StructureIDs don't match
    14951496
    14961497            // Load cached property
    … …  
    15021503
    15031504            // Slow case
    1504             m_jit.link(slowCase, m_jit.label());
     1505            m_jit.link(noMatch, m_jit.label());
    15051506            emitPutArgConstant(globalObject, 0);
    15061507            emitPutArgConstant(reinterpret_cast<unsigned>(ident), 4);
    … …  
    15101511            m_jit.link(end, m_jit.label());
    15111512            i += 6;
    1512             ++structureIDInstructionIndex;
    15131513            break;
    15141514        }
    … …  
    18421842        }
    18431843        case op_call_eval: {
    1844             compileOpCall(instruction + i, i, structureIDInstructionIndex++, OpCallEval);
     1844            compileOpCall(instruction + i, i, callLinkInfoIndex++, OpCallEval);
    18451845            i += 7;
    18461846            break;
    … …  
    21932193    }
    21942194
    2195     ASSERT(structureIDInstructionIndex == m_codeBlock->structureIDInstructions.size());
     2195    ASSERT(propertyAccessInstructionIndex == m_codeBlock->propertyAccessInstructions.size());
     2196    ASSERT(callLinkInfoIndex == m_codeBlock->callLinkInfos.size());
    21962197}
    21972198
    … …  
    22182219void CTI::privateCompileSlowCases()
    22192220{
    2220     unsigned structureIDInstructionIndex = 0;
     2221    unsigned propertyAccessInstructionIndex = 0;
     2222    unsigned callLinkInfoIndex = 0;
    22212223
    22222224    Instruction* instruction = m_codeBlock->instructions.begin();
    … …  
    23622364
    23632365            // Track the location of the call; this will be used to recover repatch information.
    2364             ASSERT(m_codeBlock->structureIDInstructions[structureIDInstructionIndex].opcodeIndex == i);
    2365             m_structureStubCompilationInfo[structureIDInstructionIndex].callReturnLocation = call;
    2366             ++structureIDInstructionIndex;
     2366            ASSERT(m_codeBlock->propertyAccessInstructions[propertyAccessInstructionIndex].opcodeIndex == i);
     2367            m_propertyAccessCompilationInfo[propertyAccessInstructionIndex].callReturnLocation = call;
     2368            ++propertyAccessInstructionIndex;
    23672369
    23682370            i += 8;
    … …  
    23902392
    23912393            // Track the location of the call; this will be used to recover repatch information.
    2392             ASSERT(m_codeBlock->structureIDInstructions[structureIDInstructionIndex].opcodeIndex == i);
    2393             m_structureStubCompilationInfo[structureIDInstructionIndex].callReturnLocation = call;
    2394             ++structureIDInstructionIndex;
     2394            ASSERT(m_codeBlock->propertyAccessInstructions[propertyAccessInstructionIndex].opcodeIndex == i);
     2395            m_propertyAccessCompilationInfo[propertyAccessInstructionIndex].callReturnLocation = call;
     2396            ++propertyAccessInstructionIndex;
    23952397
    23962398            i += 8;
    2397             break;
    2398         }
    2399         case op_resolve_global: {
    2400             ++structureIDInstructionIndex;
    2401             i += 6;
    24022399            break;
    24032400        }
    … …  
    27112708
    27122709            // Try to link & repatch this call.
    2713             m_structureStubCompilationInfo[structureIDInstructionIndex].callReturnLocation =
     2710            CallLinkInfo* info = &(m_codeBlock->callLinkInfos[callLinkInfoIndex]);
     2711            emitPutArgConstant(reinterpret_cast<unsigned>(info), 4);
     2712            m_callStructureStubCompilationInfo[callLinkInfoIndex].callReturnLocation =
    27142713                emitCTICall(i, Machine::cti_vm_lazyLinkCall);
    27152714            emitNakedCall(i, X86::eax);
    … …  
    27172716
    27182717            // This is the address for the cold path *after* the first run (which tries to link the call).
    2719             m_structureStubCompilationInfo[structureIDInstructionIndex].coldPathOther = m_jit.label();
     2718            m_callStructureStubCompilationInfo[callLinkInfoIndex].coldPathOther = m_jit.label();
    27202719
    27212720            // The arguments have been set up on the hot path for op_call_eval
    … …  
    27642763            emitPutResult(dst);
    27652764
    2766             ++structureIDInstructionIndex;
     2765            ++callLinkInfoIndex;
    27672766            i += 7;
    27682767            break;
    … …  
    27882787    }
    27892788
    2790     ASSERT(structureIDInstructionIndex == m_codeBlock->structureIDInstructions.size());
     2789    ASSERT(propertyAccessInstructionIndex == m_codeBlock->propertyAccessInstructions.size());
     2790    ASSERT(callLinkInfoIndex == m_codeBlock->callLinkInfos.size());
    27912791}
    27922792
    … …  
    28672867        X86Assembler::linkAbsoluteAddress(code, iter->addrPosition, iter->target);
    28682868
    2869     for (unsigned i = 0; i < m_codeBlock->structureIDInstructions.size(); ++i) {
    2870         StructureStubInfo& info = m_codeBlock->structureIDInstructions[i];
    2871         info.callReturnLocation = X86Assembler::getRelocatedAddress(code, m_structureStubCompilationInfo[i].callReturnLocation);
    2872         info.hotPathBegin = X86Assembler::getRelocatedAddress(code, m_structureStubCompilationInfo[i].hotPathBegin);
    2873         info.hotPathOther = X86Assembler::getRelocatedAddress(code, m_structureStubCompilationInfo[i].hotPathOther);
    2874         info.coldPathOther = X86Assembler::getRelocatedAddress(code, m_structureStubCompilationInfo[i].coldPathOther);
     2869    for (unsigned i = 0; i < m_codeBlock->propertyAccessInstructions.size(); ++i) {
     2870        StructureStubInfo& info = m_codeBlock->propertyAccessInstructions[i];
     2871        info.callReturnLocation = X86Assembler::getRelocatedAddress(code, m_propertyAccessCompilationInfo[i].callReturnLocation);
     2872        info.hotPathBegin = X86Assembler::getRelocatedAddress(code, m_propertyAccessCompilationInfo[i].hotPathBegin);
     2873    }
     2874    for (unsigned i = 0; i < m_codeBlock->callLinkInfos.size(); ++i) {
     2875        CallLinkInfo& info = m_codeBlock->callLinkInfos[i];
     2876        info.callReturnLocation = X86Assembler::getRelocatedAddress(code, m_callStructureStubCompilationInfo[i].callReturnLocation);
     2877        info.hotPathBegin = X86Assembler::getRelocatedAddress(code, m_callStructureStubCompilationInfo[i].hotPathBegin);
     2878        info.hotPathOther = X86Assembler::getRelocatedAddress(code, m_callStructureStubCompilationInfo[i].hotPathOther);
     2879        info.coldPathOther = X86Assembler::getRelocatedAddress(code, m_callStructureStubCompilationInfo[i].coldPathOther);
    28752880    }
    28762881
    … …  
    31553160}
    31563161
    3157 void CTI::unlinkCall(StructureStubInfo* structureStubInfo)
     3162void CTI::unlinkCall(CallLinkInfo* callLinkInfo)
    31583163{
    31593164    // When the JSFunction is deleted the pointer embedded in the instruction stream will no longer be valid
    31603165    // (and, if a new JSFunction happened to be constructed at the same location, we could get a false positive
    31613166    // match).  Reset the check so it no longer matches.
    3162     reinterpret_cast<void**>(structureStubInfo->hotPathBegin)[-1] = asPointer(JSImmediate::impossibleValue());
    3163 }
    3164 
    3165 void CTI::linkCall(CodeBlock* callerCodeBlock, JSFunction* callee, CodeBlock* calleeCodeBlock, void* ctiCode, void* returnAddress, int callerArgCount)
    3166 {
    3167     StructureStubInfo& stubInfo = callerCodeBlock->getStubInfo(returnAddress);
    3168 
     3167    reinterpret_cast<void**>(callLinkInfo->hotPathBegin)[-1] = asPointer(JSImmediate::impossibleValue());
     3168}
     3169
     3170void CTI::linkCall(JSFunction* callee, CodeBlock* calleeCodeBlock, void* ctiCode, CallLinkInfo* callLinkInfo, int callerArgCount)
     3171{
    31693172    // Currently we only link calls with the exact number of arguments.
    31703173    if (callerArgCount == calleeCodeBlock->numParameters) {
    3171         ASSERT(!stubInfo.linkInfoPtr);
     3174        ASSERT(!callLinkInfo->isLinked());
    31723175   
    3173         calleeCodeBlock->addCaller(&stubInfo);
     3176        calleeCodeBlock->addCaller(callLinkInfo);
    31743177   
    3175         reinterpret_cast<void**>(stubInfo.hotPathBegin)[-1] = callee;
    3176         ctiRepatchCallByReturnAddress(stubInfo.hotPathOther, ctiCode);
     3178        reinterpret_cast<void**>(callLinkInfo->hotPathBegin)[-1] = callee;
     3179        ctiRepatchCallByReturnAddress(callLinkInfo->hotPathOther, ctiCode);
    31773180    }
    31783181
    31793182    // repatch the instruction that jumps out to the cold path, so that we only try to link once.
    3180     void* repatchCheck = reinterpret_cast<void*>(reinterpret_cast<ptrdiff_t>(stubInfo.hotPathBegin) + repatchOffsetOpCallCall);
    3181     ctiRepatchCallByReturnAddress(repatchCheck, stubInfo.coldPathOther);
     3183    void* repatchCheck = reinterpret_cast<void*>(reinterpret_cast<ptrdiff_t>(callLinkInfo->hotPathBegin) + repatchOffsetOpCallCall);
     3184    ctiRepatchCallByReturnAddress(repatchCheck, callLinkInfo->coldPathOther);
    31823185}
    31833186

  • trunk/JavaScriptCore/VM/CTI.h

    r37728 r37831  
    8080#define ARG_instr5 static_cast<Instruction*>(ARGS[5])
    8181#define ARG_instr6 static_cast<Instruction*>(ARGS[6])
     82#define ARG_linkInfo2 static_cast<CallLinkInfo*>(ARGS[2])
    8283
    8384#define CTI_RETURN_ADDRESS_SLOT (ARGS[-1])
    … …  
    9596    class StructureIDChain;
    9697
     98    struct CallLinkInfo;
    9799    struct Instruction;
    98100    struct OperandTypes;
    99     struct StructureStubInfo;
    100101
    101102    typedef JSValue* (SFX_CALL *CTIHelper_j)(CTI_ARGS);
    … …  
    335336        }
    336337
    337         static void linkCall(CodeBlock* callerCodeBlock, JSFunction* callee, CodeBlock* calleeCodeBlock, void* ctiCode, void* returnAddress, int callerArgCount);
    338         static void unlinkCall(StructureStubInfo*);
     338        static void linkCall(JSFunction* callee, CodeBlock* calleeCodeBlock, void* ctiCode, CallLinkInfo* callLinkInfo, int callerArgCount);
     339        static void unlinkCall(CallLinkInfo*);
    339340
    340341        inline static JSValuePtr execute(void* code, RegisterFile* registerFile, CallFrame* callFrame, JSGlobalData* globalData, JSValuePtr* exception)
    … …  
    434435        Vector<CallRecord> m_calls;
    435436        Vector<X86Assembler::JmpDst> m_labels;
    436         Vector<StructureStubCompilationInfo> m_structureStubCompilationInfo;
     437        Vector<StructureStubCompilationInfo> m_propertyAccessCompilationInfo;
     438        Vector<StructureStubCompilationInfo> m_callStructureStubCompilationInfo;
    437439        Vector<JmpTable> m_jmpTable;
    438440

  • trunk/JavaScriptCore/VM/CodeBlock.cpp

    r37804 r37831  
    276276    }
    277277
    278     if (structureIDInstructions.size()) {
     278    if (globalResolveInstructions.size() || propertyAccessInstructions.size())
    279279        printf("\nStructureIDs:\n");
     280
     281    if (globalResolveInstructions.size()) {
    280282        size_t i = 0;
    281283        do {
    282              printStructureIDs(&instructions[structureIDInstructions[i].opcodeIndex]);
     284             printStructureIDs(&instructions[globalResolveInstructions[i]]);
    283285             ++i;
    284         } while (i < structureIDInstructions.size());
     286        } while (i < globalResolveInstructions.size());
     287    }
     288    if (propertyAccessInstructions.size()) {
     289        size_t i = 0;
     290        do {
     291             printStructureIDs(&instructions[propertyAccessInstructions[i].opcodeIndex]);
     292             ++i;
     293        } while (i < propertyAccessInstructions.size());
    285294    }
    286295 
    … …  
    942951CodeBlock::~CodeBlock()
    943952{
    944     size_t size = structureIDInstructions.size();
    945     for (size_t i = 0; i < size; ++i) {
    946         derefStructureIDs(&instructions[structureIDInstructions[i].opcodeIndex]);
    947         if (structureIDInstructions[i].stubRoutine)
    948             WTF::fastFreeExecutable(structureIDInstructions[i].stubRoutine);
    949         if (CallLinkInfo* callLinkInfo = structureIDInstructions[i].linkInfoPtr) {
     953    for (size_t size = globalResolveInstructions.size(), i = 0; i < size; ++i) {
     954        derefStructureIDs(&instructions[globalResolveInstructions[i]]);
     955    }
     956
     957    for (size_t size = propertyAccessInstructions.size(), i = 0; i < size; ++i) {
     958        derefStructureIDs(&instructions[propertyAccessInstructions[i].opcodeIndex]);
     959        if (propertyAccessInstructions[i].stubRoutine)
     960            WTF::fastFreeExecutable(propertyAccessInstructions[i].stubRoutine);
     961    }
     962
     963    for (size_t size = callLinkInfos.size(), i = 0; i < size; ++i) {
     964        CallLinkInfo* callLinkInfo = &callLinkInfos[i];
     965        if (callLinkInfo->isLinked())
    950966            callLinkInfo->callee->removeCaller(callLinkInfo);
    951             delete callLinkInfo;
    952         }
    953967    }
    954968
    … …  
    967981    for (size_t i = 0; i < size; ++i) {
    968982        CallLinkInfo* currentCaller = linkedCallerList[i];
    969         CTI::unlinkCall(currentCaller->callerStructureStubInfo);
    970         currentCaller->callerStructureStubInfo->linkInfoPtr = 0;
    971         delete currentCaller;
     983        CTI::unlinkCall(currentCaller);
     984        currentCaller->setUnlinked();
    972985    }
    973986    linkedCallerList.clear();
    … …  
    10101023   
    10111024    // These instructions don't ref their StructureIDs.
    1012     ASSERT(vPC[0].u.opcode == machine->getOpcode(op_get_by_id) || vPC[0].u.opcode == machine->getOpcode(op_put_by_id) || vPC[0].u.opcode == machine->getOpcode(op_get_by_id_generic) || vPC[0].u.opcode == machine->getOpcode(op_put_by_id_generic) || vPC[0].u.opcode == machine->getOpcode(op_get_array_length) || vPC[0].u.opcode == machine->getOpcode(op_get_string_length)
    1013         || vPC[0].u.opcode == machine->getOpcode(op_call_eval) || vPC[0].u.opcode == machine->getOpcode(op_call) || vPC[0].u.opcode == machine->getOpcode(op_construct));
     1025    ASSERT(vPC[0].u.opcode == machine->getOpcode(op_get_by_id) || vPC[0].u.opcode == machine->getOpcode(op_put_by_id) || vPC[0].u.opcode == machine->getOpcode(op_get_by_id_generic) || vPC[0].u.opcode == machine->getOpcode(op_put_by_id_generic) || vPC[0].u.opcode == machine->getOpcode(op_get_array_length) || vPC[0].u.opcode == machine->getOpcode(op_get_string_length));
    10141026}
    10151027

  • trunk/JavaScriptCore/VM/CodeBlock.h

    r37684 r37831  
    7979    };
    8080
    81     struct CallLinkInfo;
    82 
    8381    struct StructureStubInfo {
    8482        StructureStubInfo(unsigned opcodeIndex)
    … …  
    8785            , callReturnLocation(0)
    8886            , hotPathBegin(0)
    89             , hotPathOther(0)
    90             , coldPathOther(0)
    91             , linkInfoPtr(0)
    9287        {
    9388        }
    … …  
    9792        void* callReturnLocation;
    9893        void* hotPathBegin;
     94    };
     95
     96    struct CallLinkInfo {
     97        CallLinkInfo()
     98            : callReturnLocation(0)
     99            , hotPathBegin(0)
     100            , hotPathOther(0)
     101            , coldPathOther(0)
     102            , callee(0)
     103        {
     104        }
     105   
     106        unsigned opcodeIndex;
     107        void* callReturnLocation;
     108        void* hotPathBegin;
    99109        void* hotPathOther;
    100110        void* coldPathOther;
    101         CallLinkInfo* linkInfoPtr;
    102     };
    103 
    104     struct CallLinkInfo {
    105111        CodeBlock* callee;
    106         StructureStubInfo* callerStructureStubInfo;
    107112        unsigned position;
    108 
    109         CallLinkInfo(CodeBlock* c, StructureStubInfo* css)
    110         {
    111             callee = c;
    112             callerStructureStubInfo = css;
    113         }
    114     };
     113       
     114        void setUnlinked() { callee = 0; }
     115        bool isLinked() { return callee; }
     116    };
     117
     118    inline void* getStructureStubInfoReturnLocation(StructureStubInfo* structureStubInfo)
     119    {
     120        return structureStubInfo->callReturnLocation;
     121    }
     122
     123    // Binary chop algorithm, calls valueAtPosition on pre-sorted elements in array,
     124    // compares result with key (KeyTypes should be comparable with '--', '<', '>').
     125    // Optimized for cases where the array contains the key, checked by assertions.
     126    template<typename ArrayType, typename KeyType, KeyType(*valueAtPosition)(ArrayType*)>
     127    inline ArrayType* binaryChop(ArrayType* array, size_t size, KeyType key)
     128    {
     129        // The array must contain at least one element (pre-condition, array does conatin key).
     130        // If the array only contains one element, no need to do the comparison.
     131        while (size > 1) {
     132            // Pick an element to check, half way through the array, and read the value.
     133            int pos = (size - 1) >> 1;
     134            KeyType val = valueAtPosition(&array[pos]);
     135           
     136            // If the key matches, success!
     137            if (val == key)
     138                return &array[pos];
     139            // The item we are looking for is smaller than the item being check; reduce the value of 'size',
     140            // chopping off the right hand half of the array.
     141            else if (key < val)
     142                size = pos;
     143            // Discard all values in the left hand half of the array, up to and including the item at pos.
     144            else {
     145                size -= (pos + 1);
     146                array += (pos + 1);
     147            }
     148
     149            // 'size' should never reach zero.
     150            ASSERT(size);
     151        }
     152       
     153        // If we reach this point we've chopped down to one element, no need to check it matches
     154        ASSERT(size == 1);
     155        ASSERT(key == valueAtPosition(&array[0]));
     156        return &array[0];
     157    }
    115158
    116159    struct StringJumpTable {
    … …  
    228271#endif
    229272
    230         void addCaller(StructureStubInfo* caller)
    231         {
    232             CallLinkInfo* callLinkInfo = new CallLinkInfo(this, caller);
    233             caller->linkInfoPtr = callLinkInfo;
    234             callLinkInfo->position = linkedCallerList.size();
    235             linkedCallerList.append(callLinkInfo);
     273        void addCaller(CallLinkInfo* caller)
     274        {
     275            caller->callee = this;
     276            caller->position = linkedCallerList.size();
     277            linkedCallerList.append(caller);
    236278        }
    237279
    … …  
    264306        StructureStubInfo& getStubInfo(void* returnAddress)
    265307        {
    266             // FIXME: would a binary chop be faster here?
    267             for (unsigned i = 0; ; ++i) {
    268                 ASSERT(i < structureIDInstructions.size());
    269                 if (structureIDInstructions[i].callReturnLocation == returnAddress)
    270                     return structureIDInstructions[i];
    271             }
     308            return *(binaryChop<StructureStubInfo, void*, getStructureStubInfoReturnLocation>(propertyAccessInstructions.begin(), propertyAccessInstructions.size(), returnAddress));
    272309        }
    273310
    … …  
    296333
    297334        Vector<Instruction> instructions;
    298         Vector<StructureStubInfo> structureIDInstructions;
     335        Vector<unsigned> globalResolveInstructions;
     336        Vector<StructureStubInfo> propertyAccessInstructions;
     337        Vector<CallLinkInfo> callLinkInfos;
    299338        Vector<CallLinkInfo*> linkedCallerList;
    300339

  • trunk/JavaScriptCore/VM/CodeGenerator.cpp

    r37812 r37831  
    966966
    967967    if (globalObject) {
    968         m_codeBlock->structureIDInstructions.append(instructions().size());
     968        m_codeBlock->globalResolveInstructions.append(instructions().size());
    969969        emitOpcode(op_resolve_global);
    970970        instructions().append(dst->index());
    … …  
    10461046RegisterID* CodeGenerator::emitGetById(RegisterID* dst, RegisterID* base, const Identifier& property)
    10471047{
    1048     m_codeBlock->structureIDInstructions.append(instructions().size());
     1048    m_codeBlock->propertyAccessInstructions.append(instructions().size());
    10491049
    10501050    emitOpcode(op_get_by_id);
    … …  
    10611061RegisterID* CodeGenerator::emitPutById(RegisterID* base, const Identifier& property, RegisterID* value)
    10621062{
    1063     m_codeBlock->structureIDInstructions.append(instructions().size());
     1063    m_codeBlock->propertyAccessInstructions.append(instructions().size());
    10641064
    10651065    emitOpcode(op_put_by_id);
    … …  
    12201220
    12211221    emitExpressionInfo(divot, startOffset, endOffset);
    1222     m_codeBlock->structureIDInstructions.append(instructions().size());
     1222    m_codeBlock->callLinkInfos.append(CallLinkInfo());
    12231223    emitOpcode(opcodeID);
    12241224    instructions().append(dst->index());
    … …  
    12841284
    12851285    emitExpressionInfo(divot, startOffset, endOffset);
    1286     m_codeBlock->structureIDInstructions.append(instructions().size());
     1286    m_codeBlock->callLinkInfos.append(CallLinkInfo());
    12871287    emitOpcode(op_construct);
    12881288    instructions().append(dst->index());

  • trunk/JavaScriptCore/VM/Machine.cpp

    r37812 r37831  
    47424742    Machine* machine = ARG_globalData->machine;
    47434743    CallFrame* callFrame = CallFrame::create(ARG_callFrame);
    4744     CallFrame* callerCallFrame = callFrame->callerFrame();
    4745     CodeBlock* callerCodeBlock = callerCallFrame->codeBlock();
    47464744
    47474745    JSFunction* callee = asFunction(ARG_src1);
    … …  
    47504748        CTI::compile(machine, callFrame, codeBlock);
    47514749
    4752     int argCount = ARG_int3;
    4753     CTI::linkCall(callerCodeBlock, callee, codeBlock, codeBlock->ctiCode, CTI_RETURN_ADDRESS, argCount);
     4750    CTI::linkCall(callee, codeBlock, codeBlock->ctiCode, ARG_linkInfo2, ARG_int3);
    47544751
    47554752    return codeBlock->ctiCode;
Note: See TracChangeset for help on using the changeset viewer.