Ignore:
Timestamp:
Oct 9, 2012, 4:39:53 PM (13 years ago)
Author:
[email protected]
Message:

JSC should infer when indexed storage is contiguous, and optimize for it
​https://bugs.webkit.org/show_bug.cgi?id=97288

Reviewed by Mark Hahnenberg.

Source/JavaScriptCore:

This introduces a new kind of indexed property storage called Contiguous,
which has the following properties:

  • No header bits beyond IndexedHeader. This results in a 16 byte reduction in memory usage per array versus an ArrayStorage array. It also means that the total memory usage for an empty array is now just 3 * 8 on both 32-bit and 64-bit. Of that, only 8 bytes are array-specific; the rest is our standard object header overhead.


  • No need for hole checks on store. This results in a ~4% speed-up on Kraken and a ~1% speed-up on V8v7.


  • publicLength <= vectorLength. This means that doing new Array(blah) immediately allocates room for blah elements.


  • No sparse map or index bias.


If you ever do things to an array that would require publicLength >
vectorLength, a sparse map, or index bias, then we switch to ArrayStorage
mode. This seems to never happen in any benchmark we track, and is unlikely
to happen very frequently on any website.

  • CMakeLists.txt:
  • GNUmakefile.list.am:
  • JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • Target.pri:
  • assembler/AbstractMacroAssembler.h:

(JSC::AbstractMacroAssembler::JumpList::append):

  • assembler/MacroAssembler.h:

(MacroAssembler):
(JSC::MacroAssembler::patchableBranchTest32):

  • bytecode/ByValInfo.h: Added.

(JSC):
(JSC::isOptimizableIndexingType):
(JSC::jitArrayModeForIndexingType):
(JSC::ByValInfo::ByValInfo):
(ByValInfo):
(JSC::getByValInfoBytecodeIndex):

  • bytecode/CodeBlock.h:

(CodeBlock):
(JSC::CodeBlock::getByValInfo):
(JSC::CodeBlock::setNumberOfByValInfos):
(JSC::CodeBlock::numberOfByValInfos):
(JSC::CodeBlock::byValInfo):

  • bytecode/SamplingTool.h:
  • dfg/DFGAbstractState.cpp:

(JSC::DFG::AbstractState::execute):

  • dfg/DFGArrayMode.cpp:

(JSC::DFG::fromObserved):
(JSC::DFG::modeAlreadyChecked):
(JSC::DFG::modeToString):

  • dfg/DFGArrayMode.h:

(DFG):
(JSC::DFG::modeUsesButterfly):
(JSC::DFG::modeIsJSArray):
(JSC::DFG::isInBoundsAccess):
(JSC::DFG::mayStoreToTail):
(JSC::DFG::mayStoreToHole):
(JSC::DFG::modeIsPolymorphic):
(JSC::DFG::polymorphicIncludesContiguous):
(JSC::DFG::polymorphicIncludesArrayStorage):
(JSC::DFG::canCSEStorage):
(JSC::DFG::modeSupportsLength):
(JSC::DFG::benefitsFromStructureCheck):
(JSC::DFG::isEffectful):

  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::handleIntrinsic):

  • dfg/DFGCSEPhase.cpp:

(JSC::DFG::CSEPhase::getArrayLengthElimination):
(JSC::DFG::CSEPhase::getByValLoadElimination):
(JSC::DFG::CSEPhase::performNodeCSE):

  • dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::checkArray):
(JSC::DFG::FixupPhase::blessArrayOperation):

  • dfg/DFGGraph.h:

(JSC::DFG::Graph::byValIsPure):

  • dfg/DFGOperations.cpp:
  • dfg/DFGOperations.h:
  • dfg/DFGRepatch.cpp:

(JSC::DFG::tryCacheGetByID):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::checkArray):
(JSC::DFG::SpeculativeJIT::arrayify):
(JSC::DFG::SpeculativeJIT::compileGetArrayLength):
(JSC::DFG::SpeculativeJIT::temporaryRegisterForPutByVal):
(DFG):

  • dfg/DFGSpeculativeJIT.h:

(DFG):
(JSC::DFG::SpeculativeJIT::callOperation):
(SpeculativeJIT):
(JSC::DFG::SpeculativeJIT::putByValWillNeedExtraRegister):
(JSC::DFG::SpeculativeJIT::temporaryRegisterForPutByVal):

  • dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::compileContiguousGetByVal):
(DFG):
(JSC::DFG::SpeculativeJIT::compileArrayStorageGetByVal):
(JSC::DFG::SpeculativeJIT::compileContiguousPutByVal):
(JSC::DFG::SpeculativeJIT::compileArrayStoragePutByVal):
(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::compileContiguousGetByVal):
(DFG):
(JSC::DFG::SpeculativeJIT::compileArrayStorageGetByVal):
(JSC::DFG::SpeculativeJIT::compileContiguousPutByVal):
(JSC::DFG::SpeculativeJIT::compileArrayStoragePutByVal):
(JSC::DFG::SpeculativeJIT::compile):

  • interpreter/Interpreter.cpp:

(SamplingScope):
(JSC::SamplingScope::SamplingScope):
(JSC::SamplingScope::~SamplingScope):
(JSC):
(JSC::Interpreter::execute):

  • jit/JIT.cpp:

(JSC::JIT::privateCompileSlowCases):
(JSC::JIT::privateCompile):

  • jit/JIT.h:

(JSC::ByValCompilationInfo::ByValCompilationInfo):
(ByValCompilationInfo):
(JSC):
(JIT):
(JSC::JIT::compileGetByVal):
(JSC::JIT::compilePutByVal):

  • jit/JITInlineMethods.h:

(JSC::JIT::emitAllocateJSArray):
(JSC::JIT::emitArrayProfileStoreToHoleSpecialCase):
(JSC):
(JSC::arrayProfileSaw):
(JSC::JIT::chooseArrayMode):

  • jit/JITOpcodes.cpp:

(JSC::JIT::emitSlow_op_get_argument_by_val):
(JSC::JIT::emit_op_new_array):
(JSC::JIT::emitSlow_op_new_array):

  • jit/JITOpcodes32_64.cpp:

(JSC::JIT::emitSlow_op_get_argument_by_val):

  • jit/JITPropertyAccess.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC):
(JSC::JIT::emitContiguousGetByVal):
(JSC::JIT::emitArrayStorageGetByVal):
(JSC::JIT::emitSlow_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::emitContiguousPutByVal):
(JSC::JIT::emitArrayStoragePutByVal):
(JSC::JIT::emitSlow_op_put_by_val):
(JSC::JIT::privateCompilePatchGetArrayLength):
(JSC::JIT::privateCompileGetByVal):
(JSC::JIT::privateCompilePutByVal):

  • jit/JITPropertyAccess32_64.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC):
(JSC::JIT::emitContiguousGetByVal):
(JSC::JIT::emitArrayStorageGetByVal):
(JSC::JIT::emitSlow_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::emitContiguousPutByVal):
(JSC::JIT::emitArrayStoragePutByVal):
(JSC::JIT::emitSlow_op_put_by_val):

  • jit/JITStubs.cpp:

(JSC::getByVal):
(JSC):
(JSC::DEFINE_STUB_FUNCTION):
(JSC::putByVal):

  • jit/JITStubs.h:
  • llint/LowLevelInterpreter.asm:
  • llint/LowLevelInterpreter32_64.asm:
  • llint/LowLevelInterpreter64.asm:
  • runtime/ArrayConventions.h:

(JSC::isDenseEnoughForVector):

  • runtime/ArrayPrototype.cpp:

(JSC):
(JSC::shift):
(JSC::unshift):
(JSC::arrayProtoFuncPush):
(JSC::arrayProtoFuncShift):
(JSC::arrayProtoFuncSplice):
(JSC::arrayProtoFuncUnShift):

  • runtime/Butterfly.h:

(Butterfly):
(JSC::Butterfly::fromPointer):
(JSC::Butterfly::pointer):
(JSC::Butterfly::publicLength):
(JSC::Butterfly::vectorLength):
(JSC::Butterfly::setPublicLength):
(JSC::Butterfly::setVectorLength):
(JSC::Butterfly::contiguous):
(JSC::Butterfly::fromContiguous):

  • runtime/ButterflyInlineMethods.h:

(JSC::Butterfly::unshift):
(JSC::Butterfly::shift):

  • runtime/IndexingHeaderInlineMethods.h:

(JSC::IndexingHeader::indexingPayloadSizeInBytes):

  • runtime/IndexingType.cpp: Added.

(JSC):
(JSC::indexingTypeToString):

  • runtime/IndexingType.h:

(JSC):
(JSC::hasContiguous):

  • runtime/JSArray.cpp:

(JSC::JSArray::setLengthWithArrayStorage):
(JSC::JSArray::setLength):
(JSC):
(JSC::JSArray::pop):
(JSC::JSArray::push):
(JSC::JSArray::shiftCountWithArrayStorage):
(JSC::JSArray::shiftCountWithAnyIndexingType):
(JSC::JSArray::unshiftCountWithArrayStorage):
(JSC::JSArray::unshiftCountWithAnyIndexingType):
(JSC::JSArray::sortNumericVector):
(JSC::JSArray::sortNumeric):
(JSC::JSArray::sortCompactedVector):
(JSC::JSArray::sort):
(JSC::JSArray::sortVector):
(JSC::JSArray::fillArgList):
(JSC::JSArray::copyToArguments):
(JSC::JSArray::compactForSorting):

  • runtime/JSArray.h:

(JSC::JSArray::shiftCountForShift):
(JSC::JSArray::shiftCountForSplice):
(JSArray):
(JSC::JSArray::shiftCount):
(JSC::JSArray::unshiftCountForShift):
(JSC::JSArray::unshiftCountForSplice):
(JSC::JSArray::unshiftCount):
(JSC::JSArray::isLengthWritable):
(JSC::createContiguousArrayButterfly):
(JSC):
(JSC::JSArray::create):
(JSC::JSArray::tryCreateUninitialized):

  • runtime/JSGlobalObject.cpp:

(JSC::JSGlobalObject::reset):
(JSC):
(JSC::JSGlobalObject::haveABadTime):
(JSC::JSGlobalObject::visitChildren):

  • runtime/JSGlobalObject.h:

(JSGlobalObject):
(JSC::JSGlobalObject::arrayStructureWithArrayStorage):
(JSC::JSGlobalObject::addressOfArrayStructureWithArrayStorage):
(JSC::constructEmptyArray):

  • runtime/JSObject.cpp:

(JSC::JSObject::visitButterfly):
(JSC::JSObject::getOwnPropertySlotByIndex):
(JSC::JSObject::putByIndex):
(JSC::JSObject::enterDictionaryIndexingMode):
(JSC::JSObject::createInitialContiguous):
(JSC):
(JSC::JSObject::createArrayStorage):
(JSC::JSObject::convertContiguousToArrayStorage):
(JSC::JSObject::ensureContiguousSlow):
(JSC::JSObject::ensureArrayStorageSlow):
(JSC::JSObject::ensureIndexedStorageSlow):
(JSC::JSObject::ensureArrayStorageExistsAndEnterDictionaryIndexingMode):
(JSC::JSObject::switchToSlowPutArrayStorage):
(JSC::JSObject::setPrototype):
(JSC::JSObject::deletePropertyByIndex):
(JSC::JSObject::getOwnPropertyNames):
(JSC::JSObject::defineOwnIndexedProperty):
(JSC::JSObject::putByIndexBeyondVectorLengthContiguousWithoutAttributes):
(JSC::JSObject::putByIndexBeyondVectorLength):
(JSC::JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage):
(JSC::JSObject::putDirectIndexBeyondVectorLength):
(JSC::JSObject::getNewVectorLength):
(JSC::JSObject::countElementsInContiguous):
(JSC::JSObject::increaseVectorLength):
(JSC::JSObject::ensureContiguousLengthSlow):
(JSC::JSObject::getOwnPropertyDescriptor):

  • runtime/JSObject.h:

(JSC::JSObject::getArrayLength):
(JSC::JSObject::getVectorLength):
(JSC::JSObject::canGetIndexQuickly):
(JSC::JSObject::getIndexQuickly):
(JSC::JSObject::tryGetIndexQuickly):
(JSC::JSObject::canSetIndexQuickly):
(JSC::JSObject::canSetIndexQuicklyForPutDirect):
(JSC::JSObject::setIndexQuickly):
(JSC::JSObject::initializeIndex):
(JSC::JSObject::hasSparseMap):
(JSC::JSObject::inSparseIndexingMode):
(JSObject):
(JSC::JSObject::ensureContiguous):
(JSC::JSObject::ensureIndexedStorage):
(JSC::JSObject::ensureContiguousLength):
(JSC::JSObject::indexingData):
(JSC::JSObject::relevantLength):

  • runtime/JSValue.cpp:

(JSC::JSValue::description):

  • runtime/Options.cpp:

(JSC::Options::initialize):

  • runtime/Structure.cpp:

(JSC::Structure::needsSlowPutIndexing):
(JSC):
(JSC::Structure::suggestedArrayStorageTransition):

  • runtime/Structure.h:

(Structure):

  • runtime/StructureTransitionTable.h:

(JSC::newIndexingType):

Source/WTF:

Moved out this helpful math utility to MathExtras, since we now use it in
multiple places.

  • wtf/MathExtras.h:

(timesThreePlusOneDividedByTwo):

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/dfg/DFGAbstractState.cpp

    r129588 r130826  
    860860            forNode(nodeIndex).makeTop();
    861861            break;
     862        case IN_BOUNDS_CONTIGUOUS_MODES:
    862863        case IN_BOUNDS_ARRAY_STORAGE_MODES:
    863864            forNode(node.child2()).filter(SpecInt32);
    864865            forNode(nodeIndex).makeTop();
    865866            break;
     867        case OUT_OF_BOUNDS_CONTIGUOUS_MODES:
    866868        case OUT_OF_BOUNDS_ARRAY_STORAGE_MODES:
    867         case ALL_EFFECTFUL_ARRAY_STORAGE_MODES:
     869        case SLOW_PUT_ARRAY_STORAGE_MODES:
     870        case ALL_EFFECTFUL_MODES:
     871        case POLYMORPHIC_MODES:
     872            forNode(node.child1()).filter(SpecCell);
    868873            forNode(node.child2()).filter(SpecInt32);
    869874            clobberWorld(node.codeOrigin, indexInBlock);
    … …  
    909914            forNode(nodeIndex).set(SpecDouble);
    910915            break;
     916        default:
     917            ASSERT_NOT_REACHED();
     918            break;
    911919        }
    912920        break;
    … …  
    916924    case PutByValAlias: {
    917925        node.setCanExit(true);
     926        Edge child1 = m_graph.varArgChild(node, 0);
    918927        Edge child2 = m_graph.varArgChild(node, 1);
    919928        Edge child3 = m_graph.varArgChild(node, 2);
    … …  
    925934            clobberWorld(node.codeOrigin, indexInBlock);
    926935            break;
     936        case IN_BOUNDS_CONTIGUOUS_MODES:
     937        case CONTIGUOUS_TO_TAIL_MODES:
    927938        case IN_BOUNDS_ARRAY_STORAGE_MODES:
    928939            forNode(child2).filter(SpecInt32);
    929940            break;
     941        case OUT_OF_BOUNDS_CONTIGUOUS_MODES:
     942        case ARRAY_STORAGE_TO_HOLE_MODES:
    930943        case OUT_OF_BOUNDS_ARRAY_STORAGE_MODES:
    931         case ALL_EFFECTFUL_ARRAY_STORAGE_MODES:
     944        case SLOW_PUT_ARRAY_STORAGE_MODES:
     945        case ALL_EFFECTFUL_MODES:
     946        case POLYMORPHIC_MODES:
     947            forNode(child1).filter(SpecCell);
    932948            forNode(child2).filter(SpecInt32);
    933949            clobberWorld(node.codeOrigin, indexInBlock);
    … …  
    13681384            forNode(node.child1()).filter(SpecString);
    13691385            break;
     1386        case ALL_CONTIGUOUS_MODES:
    13701387        case ALL_ARRAY_STORAGE_MODES:
     1388        case POLYMORPHIC_MODES: // These only get a CheckArray for GetArrayLength
    13711389            // This doesn't filter anything meaningful right now. We may want to add
    13721390            // CFA tracking of array mode speculations, but we don't have that, yet.
    … …  
    14111429    case Arrayify: {
    14121430        switch (node.arrayMode()) {
    1413         case EFFECTFUL_NON_ARRAY_ARRAY_STORAGE_MODES:
     1431        case ALL_EFFECTFUL_MODES:
    14141432            node.setCanExit(true);
    14151433            forNode(node.child1()).filter(SpecCell);
     1434            forNode(node.child2()).filter(SpecInt32);
    14161435            forNode(nodeIndex).clear();
    14171436            clobberStructures(indexInBlock);
Note: See TracChangeset for help on using the changeset viewer.