Changeset 130826 in webkit for trunk/Source/JavaScriptCore/dfg/DFGArrayMode.cpp

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:

• trunk/Source/JavaScriptCore/dfg/DFGArrayMode.cpp (modified) (6 diffs)

trunk/Source/JavaScriptCore/dfg/DFGArrayMode.cpp

@@ -40 +40 @@
     case asArrayModes(NonArray):
         if (action == Array::Write && !profile->mayInterceptIndexedAccesses())
-            return Array::BlankToArrayStorage; // FIXME: we don't know whether to go to slow put mode, or not. This is a decent guess.
-        return Array::Undecided;
+            return Array::BlankToContiguousOrArrayStorage; // FIXME: we don't know whether to go to slow put mode or not. We're guessing that we don't need slow put.
+        return Array::Undecided;
+    case asArrayModes(NonArrayWithContiguous):
+        return makeSafe ? Array::ContiguousOutOfBounds : (profile->mayStoreToHole() ? Array::ContiguousToTail : Array::Contiguous);
+    case asArrayModes(ArrayWithContiguous):
+        return makeSafe ? Array::ArrayWithContiguousOutOfBounds : (profile->mayStoreToHole() ? Array::ArrayWithContiguousToTail : Array::ArrayWithContiguous);
+    case asArrayModes(NonArrayWithContiguous) | asArrayModes(ArrayWithContiguous):
+        return makeSafe ? Array::PossiblyArrayWithContiguousOutOfBounds : (profile->mayStoreToHole() ? Array::PossiblyArrayWithContiguousToTail : Array::PossiblyArrayWithContiguous);
     case asArrayModes(NonArrayWithArrayStorage):
         return makeSafe ? Array::ArrayStorageOutOfBounds : (profile->mayStoreToHole() ? Array::ArrayStorageToHole : Array::ArrayStorage);
@@ -57 +63 @@
     case asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage):
         return Array::PossiblyArrayWithSlowPutArrayStorage;
+    case asArrayModes(NonArrayWithContiguous) | asArrayModes(NonArrayWithArrayStorage):
+        return Array::ContiguousOrArrayStorage;
+    case asArrayModes(ArrayWithContiguous) | asArrayModes(ArrayWithArrayStorage):
+        return Array::ArrayWithContiguousOrArrayStorage;
+    case asArrayModes(NonArrayWithContiguous) | asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithContiguous) | asArrayModes(ArrayWithArrayStorage):
+        return Array::PossiblyArrayWithContiguousOrArrayStorage;
+    case asArrayModes(NonArray) | asArrayModes(NonArrayWithContiguous):
+        if (action == Array::Write && !profile->mayInterceptIndexedAccesses())
+            return Array::BlankToContiguous;
+        return Array::Undecided;
+    case asArrayModes(NonArray) | asArrayModes(NonArrayWithContiguous) | asArrayModes(NonArrayWithArrayStorage):
+        if (action == Array::Write && !profile->mayInterceptIndexedAccesses())
+            return Array::BlankToContiguousOrArrayStorage;
+        return Array::Undecided;
     case asArrayModes(NonArray) | asArrayModes(NonArrayWithArrayStorage):
         if (action == Array::Write && !profile->mayInterceptIndexedAccesses())
@@ -145 +165 @@
         return isStringSpeculation(value.m_type);
         
+    case Array::Contiguous:
+    case Array::ContiguousToTail:
+    case Array::ContiguousOutOfBounds:
+    case Array::PossiblyArrayWithContiguous:
+    case Array::PossiblyArrayWithContiguousToTail:
+    case Array::PossiblyArrayWithContiguousOutOfBounds:
+        return value.m_currentKnownStructure.hasSingleton()
+            && (value.m_currentKnownStructure.singleton()->indexingType() & HasContiguous);
+        
+    case Array::ArrayWithContiguous:
+    case Array::ArrayWithContiguousToTail:
+    case Array::ArrayWithContiguousOutOfBounds:
+        return value.m_currentKnownStructure.hasSingleton()
+            && (value.m_currentKnownStructure.singleton()->indexingType() & HasContiguous)
+            && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray);
+
     case Array::ArrayStorage:
     case Array::ArrayStorageToHole:
@@ -171 +207 @@
             && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray);
         
-    case ALL_EFFECTFUL_ARRAY_STORAGE_MODES:
+    case ALL_EFFECTFUL_MODES:
+    case POLYMORPHIC_MODES:
         return false;
         
@@ -226 +263 @@
     case Array::String:
         return "String";
+    case Array::Contiguous:
+        return "Contiguous";
+    case Array::ContiguousToTail:
+        return "ContiguousToTail";
+    case Array::ContiguousOutOfBounds:
+        return "ContiguousOutOfBounds";
+    case Array::ArrayWithContiguous:
+        return "ArrayWithContiguous";
+    case Array::ArrayWithContiguousToTail:
+        return "ArrayWithContiguousToTail";
+    case Array::ArrayWithContiguousOutOfBounds:
+        return "ArrayWithContiguousOutOfBounds";
+    case Array::PossiblyArrayWithContiguous:
+        return "PossiblyArrayWithContiguous";
+    case Array::PossiblyArrayWithContiguousToTail:
+        return "PossiblyArrayWithContiguousToTail";
+    case Array::PossiblyArrayWithContiguousOutOfBounds:
+        return "PossiblyArrayWithContiguousOutOfBounds";
     case Array::ArrayStorage:
         return "ArrayStorage";
@@ -250 +305 @@
     case Array::PossiblyArrayWithArrayStorageOutOfBounds:
         return "PossiblyArrayWithArrayStorageOutOfBounds";
+    case Array::BlankToContiguous:
+        return "BlankToContiguous";
     case Array::BlankToArrayStorage:
         return "BlankToArrayStorage";
     case Array::BlankToSlowPutArrayStorage:
         return "BlankToSlowPutArrayStorage";
+    case Array::BlankToContiguousOrArrayStorage:
+        return "BlankToContiguousOrArrayStorage";
+    case Array::ContiguousOrArrayStorage:
+        return "ContiguousOrArrayStorage";
+    case Array::ArrayWithContiguousOrArrayStorage:
+        return "ArrayWithContiguousOrArrayStorage";
+    case Array::PossiblyArrayWithContiguousOrArrayStorage:
+        return "PossiblyArrayWithContiguousOrArrayStorage";
     case Array::Arguments:
         return "Arguments";