Changeset 128790 in webkit


Ignore:
Timestamp:
Sep 17, 2012 12:07:32 PM (12 years ago)
Author:
fpizlo@apple.com
Message:

Array profiling has convergence issues
​https://bugs.webkit.org/show_bug.cgi?id=96891

Reviewed by Gavin Barraclough.

Source/JavaScriptCore:

Now each array profiling site merges in the indexing type it observed into
the m_observedArrayModes bitset. The ArrayProfile also uses this to detect
cases where the structure must have gone polymorphic (if the bitset is
polymorphic then the structure must be). This achieves something like the
best of both worlds: on the one hand, we get a probabilistic structure that
we can use to optimize the monomorphic structure case, but on the other hand,
we get an accurate view of the set of types that were encountered.

  • assembler/MacroAssemblerARMv7.h:

(JSC::MacroAssemblerARMv7::or32):
(MacroAssemblerARMv7):

  • assembler/MacroAssemblerX86.h:

(JSC::MacroAssemblerX86::or32):
(MacroAssemblerX86):

  • assembler/MacroAssemblerX86_64.h:

(JSC::MacroAssemblerX86_64::or32):
(MacroAssemblerX86_64):

  • assembler/X86Assembler.h:

(X86Assembler):
(JSC::X86Assembler::orl_rm):

  • bytecode/ArrayProfile.cpp:

(JSC::ArrayProfile::computeUpdatedPrediction):

  • bytecode/ArrayProfile.h:

(JSC::ArrayProfile::addressOfArrayModes):
(JSC::ArrayProfile::structureIsPolymorphic):

  • jit/JIT.h:

(JIT):

  • jit/JITInlineMethods.h:

(JSC):
(JSC::JIT::emitArrayProfilingSite):

  • jit/JITPropertyAccess.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::privateCompilePatchGetArrayLength):

  • jit/JITPropertyAccess32_64.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::privateCompilePatchGetArrayLength):

  • llint/LowLevelInterpreter.asm:
  • llint/LowLevelInterpreter32_64.asm:
  • llint/LowLevelInterpreter64.asm:

Source/WTF:

Added functions for testing if something is a power of 2.

  • wtf/MathExtras.h:

(hasZeroOrOneBitsSet):
(hasTwoOrMoreBitsSet):

Location:
trunk/Source
Files:
16 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r128777 r128790  
     12012-09-17  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Array profiling has convergence issues
     4        https://bugs.webkit.org/show_bug.cgi?id=96891
     5
     6        Reviewed by Gavin Barraclough.
     7
     8        Now each array profiling site merges in the indexing type it observed into
     9        the m_observedArrayModes bitset. The ArrayProfile also uses this to detect
     10        cases where the structure must have gone polymorphic (if the bitset is
     11        polymorphic then the structure must be). This achieves something like the
     12        best of both worlds: on the one hand, we get a probabilistic structure that
     13        we can use to optimize the monomorphic structure case, but on the other hand,
     14        we get an accurate view of the set of types that were encountered.
     15
     16        * assembler/MacroAssemblerARMv7.h:
     17        (JSC::MacroAssemblerARMv7::or32):
     18        (MacroAssemblerARMv7):
     19        * assembler/MacroAssemblerX86.h:
     20        (JSC::MacroAssemblerX86::or32):
     21        (MacroAssemblerX86):
     22        * assembler/MacroAssemblerX86_64.h:
     23        (JSC::MacroAssemblerX86_64::or32):
     24        (MacroAssemblerX86_64):
     25        * assembler/X86Assembler.h:
     26        (X86Assembler):
     27        (JSC::X86Assembler::orl_rm):
     28        * bytecode/ArrayProfile.cpp:
     29        (JSC::ArrayProfile::computeUpdatedPrediction):
     30        * bytecode/ArrayProfile.h:
     31        (JSC::ArrayProfile::addressOfArrayModes):
     32        (JSC::ArrayProfile::structureIsPolymorphic):
     33        * jit/JIT.h:
     34        (JIT):
     35        * jit/JITInlineMethods.h:
     36        (JSC):
     37        (JSC::JIT::emitArrayProfilingSite):
     38        * jit/JITPropertyAccess.cpp:
     39        (JSC::JIT::emit_op_get_by_val):
     40        (JSC::JIT::emit_op_put_by_val):
     41        (JSC::JIT::privateCompilePatchGetArrayLength):
     42        * jit/JITPropertyAccess32_64.cpp:
     43        (JSC::JIT::emit_op_get_by_val):
     44        (JSC::JIT::emit_op_put_by_val):
     45        (JSC::JIT::privateCompilePatchGetArrayLength):
     46        * llint/LowLevelInterpreter.asm:
     47        * llint/LowLevelInterpreter32_64.asm:
     48        * llint/LowLevelInterpreter64.asm:
     49
    1502012-09-17  Mark Lam  <mark.lam@apple.com>
    251

  • trunk/Source/JavaScriptCore/assembler/MacroAssemblerARMv7.h

    r126214 r128790  
    314314        m_assembler.orr(dest, dest, src);
    315315    }
     316   
     317    void or32(RegisterID src, AbsoluteAddress dest)
     318    {
     319        move(TrustedImmPtr(dest.m_ptr), addressTempRegister);
     320        load32(addressTempRegister, dataTempRegister);
     321        or32(src, dataTempRegister);
     322        store32(dataTempRegister, addressTempRegister);
     323    }
    316324
    317325    void or32(TrustedImm32 imm, RegisterID dest)

  • trunk/Source/JavaScriptCore/assembler/MacroAssemblerX86.h

    r126214 r128790  
    8585    }
    8686   
     87    void or32(RegisterID reg, AbsoluteAddress address)
     88    {
     89        m_assembler.orl_rm(reg, address.m_ptr);
     90    }
     91   
    8792    void sub32(TrustedImm32 imm, AbsoluteAddress address)
    8893    {

  • trunk/Source/JavaScriptCore/assembler/MacroAssemblerX86_64.h

    r126214 r128790  
    7676    }
    7777
     78    void or32(RegisterID reg, AbsoluteAddress address)
     79    {
     80        move(TrustedImmPtr(address.m_ptr), scratchRegister);
     81        or32(reg, Address(scratchRegister));
     82    }
     83
    7884    void sub32(TrustedImm32 imm, AbsoluteAddress address)
    7985    {

  • trunk/Source/JavaScriptCore/assembler/X86Assembler.h

    r123417 r128790  
    542542        }
    543543    }
     544
     545    void orl_rm(RegisterID src, const void* addr)
     546    {
     547        m_formatter.oneByteOp(OP_OR_EvGv, src, addr);
     548    }
    544549#endif
    545550

  • trunk/Source/JavaScriptCore/bytecode/ArrayProfile.cpp

    r125637 r128790  
    4444    }
    4545   
     46    if (hasTwoOrMoreBitsSet(m_observedArrayModes)) {
     47        m_structureIsPolymorphic = true;
     48        m_expectedStructure = 0;
     49    }
     50   
    4651    if (operation == Collection
    4752        && m_expectedStructure

  • trunk/Source/JavaScriptCore/bytecode/ArrayProfile.h

    r128400 r128790  
    7171   
    7272    Structure** addressOfLastSeenStructure() { return &m_lastSeenStructure; }
     73    ArrayModes* addressOfArrayModes() { return &m_observedArrayModes; }
    7374   
    7475    void observeStructure(Structure* structure)
    … …  
    8081   
    8182    Structure* expectedStructure() const { return m_expectedStructure; }
    82     bool structureIsPolymorphic() const { return m_structureIsPolymorphic; }
     83    bool structureIsPolymorphic() const
     84    {
     85        return m_structureIsPolymorphic;
     86    }
    8387    bool hasDefiniteStructure() const
    8488    {

  • trunk/Source/JavaScriptCore/jit/JIT.h

    r128400 r128790  
    450450        void emitValueProfilingSite() { }
    451451#endif
     452        void emitArrayProfilingSite(RegisterID structureAndIndexingType, RegisterID scratch, ArrayProfile*);
     453        void emitArrayProfilingSiteForBytecodeIndex(RegisterID structureAndIndexingType, RegisterID scratch, unsigned bytecodeIndex);
    452454
    453455        enum FinalObjectMode { MayBeFinal, KnownNotFinal };

  • trunk/Source/JavaScriptCore/jit/JITInlineMethods.h

    r128400 r128790  
    530530    emitValueProfilingSite(m_bytecodeOffset);
    531531}
    532 #endif
     532#endif // ENABLE(VALUE_PROFILER)
     533
     534inline void JIT::emitArrayProfilingSite(RegisterID structureAndIndexingType, RegisterID scratch, ArrayProfile* arrayProfile)
     535{
     536    RegisterID structure = structureAndIndexingType;
     537    RegisterID indexingType = structureAndIndexingType;
     538   
     539    if (canBeOptimized()) {
     540        storePtr(structure, arrayProfile->addressOfLastSeenStructure());
     541        load8(Address(structure, Structure::indexingTypeOffset()), indexingType);
     542        move(TrustedImm32(1), scratch);
     543        lshift32(indexingType, scratch);
     544        or32(scratch, AbsoluteAddress(arrayProfile->addressOfArrayModes()));
     545    } else
     546        load8(Address(structure, Structure::indexingTypeOffset()), indexingType);
     547}
     548
     549inline void JIT::emitArrayProfilingSiteForBytecodeIndex(RegisterID structureAndIndexingType, RegisterID scratch, unsigned bytecodeIndex)
     550{
     551#if ENABLE(VALUE_PROFILER)
     552    emitArrayProfilingSite(structureAndIndexingType, scratch, m_codeBlock->getOrAddArrayProfile(bytecodeIndex));
     553#else
     554    emitArrayProfilingSite(structureAndIndexingType, scratch, 0);
     555#endif
     556}
    533557
    534558#if USE(JSVALUE32_64)

  • trunk/Source/JavaScriptCore/jit/JITPropertyAccess.cpp

    r128425 r128790  
    112112    emitJumpSlowCaseIfNotJSCell(regT0, base);
    113113    loadPtr(Address(regT0, JSCell::structureOffset()), regT2);
    114 #if ENABLE(VALUE_PROFILER)
    115     storePtr(regT2, currentInstruction[4].u.arrayProfile->addressOfLastSeenStructure());
    116 #endif
    117     addSlowCase(branchTest8(Zero, Address(regT2, Structure::indexingTypeOffset()), TrustedImm32(HasArrayStorage)));
     114    emitArrayProfilingSite(regT2, regT3, currentInstruction[4].u.arrayProfile);
     115    addSlowCase(branchTest32(Zero, regT2, TrustedImm32(HasArrayStorage)));
    118116
    119117    loadPtr(Address(regT0, JSObject::butterflyOffset()), regT2);
    … …  
    237235    emitJumpSlowCaseIfNotJSCell(regT0, base);
    238236    loadPtr(Address(regT0, JSCell::structureOffset()), regT2);
    239 #if ENABLE(VALUE_PROFILER)
    240     storePtr(regT2, currentInstruction[4].u.arrayProfile->addressOfLastSeenStructure());
    241 #endif
    242     addSlowCase(branchTest8(Zero, Address(regT2, Structure::indexingTypeOffset()), TrustedImm32(HasArrayStorage)));
     237    emitArrayProfilingSite(regT2, regT3, currentInstruction[4].u.arrayProfile);
     238    addSlowCase(branchTest32(Zero, regT2, TrustedImm32(HasArrayStorage)));
    243239    loadPtr(Address(regT0, JSObject::butterflyOffset()), regT2);
    244240    addSlowCase(branch32(AboveOrEqual, regT1, Address(regT2, ArrayStorage::vectorLengthOffset())));
    … …  
    657653
    658654    // Check eax is an array
    659     loadPtr(Address(regT0, JSCell::structureOffset()), regT3);
    660 #if ENABLE(VALUE_PROFILER)
    661     storePtr(regT3, m_codeBlock->getOrAddArrayProfile(stubInfo->bytecodeIndex)->addressOfLastSeenStructure());
    662 #endif
    663     load8(Address(regT3, Structure::indexingTypeOffset()), regT3);
    664     Jump failureCases1 = branchTest32(Zero, regT3, TrustedImm32(IsArray));
    665     Jump failureCases2 = branchTest32(Zero, regT3, TrustedImm32(HasArrayStorage));
     655    loadPtr(Address(regT0, JSCell::structureOffset()), regT2);
     656    emitArrayProfilingSiteForBytecodeIndex(regT2, regT1, stubInfo->bytecodeIndex);
     657    Jump failureCases1 = branchTest32(Zero, regT2, TrustedImm32(IsArray));
     658    Jump failureCases2 = branchTest32(Zero, regT2, TrustedImm32(HasArrayStorage));
    666659
    667660    // Checks out okay! - get the length from the storage

  • trunk/Source/JavaScriptCore/jit/JITPropertyAccess32_64.cpp

    r128425 r128790  
    211211    emitJumpSlowCaseIfNotJSCell(base, regT1);
    212212    loadPtr(Address(regT0, JSCell::structureOffset()), regT1);
    213 #if ENABLE(VALUE_PROFILER)
    214     storePtr(regT1, currentInstruction[4].u.arrayProfile->addressOfLastSeenStructure());
    215 #endif
    216     addSlowCase(branchTest8(Zero, Address(regT1, Structure::indexingTypeOffset()), TrustedImm32(HasArrayStorage)));
     213    emitArrayProfilingSite(regT1, regT3, currentInstruction[4].u.arrayProfile);
     214    addSlowCase(branchTest32(Zero, regT1, TrustedImm32(HasArrayStorage)));
    217215   
    218216    loadPtr(Address(regT0, JSObject::butterflyOffset()), regT3);
    … …  
    270268    emitJumpSlowCaseIfNotJSCell(base, regT1);
    271269    loadPtr(Address(regT0, JSCell::structureOffset()), regT1);
    272 #if ENABLE(VALUE_PROFILER)
    273     storePtr(regT1, currentInstruction[4].u.arrayProfile->addressOfLastSeenStructure());
    274 #endif
    275     addSlowCase(branchTest8(Zero, Address(regT1, Structure::indexingTypeOffset()), TrustedImm32(HasArrayStorage)));
     270    emitArrayProfilingSite(regT1, regT3, currentInstruction[4].u.arrayProfile);
     271    addSlowCase(branchTest32(Zero, regT1, TrustedImm32(HasArrayStorage)));
    276272    loadPtr(Address(regT0, JSObject::butterflyOffset()), regT3);
    277273    addSlowCase(branch32(AboveOrEqual, regT2, Address(regT3, ArrayStorage::vectorLengthOffset())));
    … …  
    618614    // Check for array
    619615    loadPtr(Address(regT0, JSCell::structureOffset()), regT2);
    620 #if ENABLE(VALUE_PROFILER)
    621     storePtr(regT2, m_codeBlock->getOrAddArrayProfile(stubInfo->bytecodeIndex)->addressOfLastSeenStructure());
    622 #endif
    623     load8(Address(regT2, Structure::indexingTypeOffset()), regT3);
     616    emitArrayProfilingSiteForBytecodeIndex(regT2, regT3, stubInfo->bytecodeIndex);
    624617    Jump failureCases1 = branchTest32(Zero, regT2, TrustedImm32(IsArray));
    625618    Jump failureCases2 = branchTest32(Zero, regT2, TrustedImm32(HasArrayStorage));

  • trunk/Source/JavaScriptCore/llint/LowLevelInterpreter.asm

    r128400 r128790  
    186186            end
    187187        end)
     188end
     189
     190macro arrayProfile(structureAndIndexingType, profile, scratch)
     191    const structure = structureAndIndexingType
     192    const indexingType = structureAndIndexingType
     193    if VALUE_PROFILER
     194        storep structure, ArrayProfile::m_lastSeenStructure[profile]
     195        loadb Structure::m_indexingType[structure], indexingType
     196        move 1, scratch
     197        lshifti indexingType, scratch
     198        ori scratch, ArrayProfile::m_observedArrayModes[profile]
     199    else
     200        loadb Structure::m_indexingType[structure], indexingType
     201    end
    188202end
    189203

  • trunk/Source/JavaScriptCore/llint/LowLevelInterpreter32_64.asm

    r128534 r128790  
    11771177    loadConstantOrVariablePayload(t0, CellTag, t3, .opGetArrayLengthSlow)
    11781178    loadp JSCell::m_structure[t3], t2
    1179     if VALUE_PROFILER
    1180         storep t2, ArrayProfile::m_lastSeenStructure[t1]
    1181     end
    1182     loadb Structure::m_indexingType[t2], t1
    1183     btiz t1, IsArray, .opGetArrayLengthSlow
    1184     btiz t1, HasArrayStorage, .opGetArrayLengthSlow
     1179    arrayProfile(t2, t1, t0)
     1180    btiz t2, IsArray, .opGetArrayLengthSlow
     1181    btiz t2, HasArrayStorage, .opGetArrayLengthSlow
    11851182    loadi 4[PC], t1
    11861183    loadp 32[PC], t2
    … …  
    13091306    traceExecution()
    13101307    loadi 8[PC], t2
     1308    loadConstantOrVariablePayload(t2, CellTag, t0, .opGetByValSlow)
     1309    loadp JSCell::m_structure[t0], t2
     1310    loadp 16[PC], t3
     1311    arrayProfile(t2, t3, t1)
     1312    btiz t2, HasArrayStorage, .opGetByValSlow
    13111313    loadi 12[PC], t3
    1312     loadConstantOrVariablePayload(t2, CellTag, t0, .opGetByValSlow)
    13131314    loadConstantOrVariablePayload(t3, Int32Tag, t1, .opGetByValSlow)
    1314     loadp JSCell::m_structure[t0], t3
    1315     loadp 16[PC], t2
    1316     if VALUE_PROFILER
    1317         storep t3, ArrayProfile::m_lastSeenStructure[t2]
    1318     end
    1319     btpz Structure::m_indexingType[t3], HasArrayStorage, .opGetByValSlow
    13201315    loadp JSObject::m_butterfly[t0], t3
    13211316    biaeq t1, -sizeof IndexingHeader + IndexingHeader::m_vectorLength[t0], .opGetByValSlow
    … …  
    13931388    loadi 4[PC], t0
    13941389    loadConstantOrVariablePayload(t0, CellTag, t1, .opPutByValSlow)
     1390    loadp JSCell::m_structure[t1], t2
     1391    loadp 16[PC], t0
     1392    arrayProfile(t2, t0, t3)
     1393    btiz t2, HasArrayStorage, .opPutByValSlow
    13951394    loadi 8[PC], t0
    13961395    loadConstantOrVariablePayload(t0, Int32Tag, t2, .opPutByValSlow)
    1397     loadp JSCell::m_structure[t1], t3
    1398     loadp 16[PC], t0
    1399     if VALUE_PROFILER
    1400         storep t3, ArrayProfile::m_lastSeenStructure[t0]
    1401     end
    1402     btpz Structure::m_indexingType[t3], HasArrayStorage, .opPutByValSlow
    14031396    loadp JSObject::m_butterfly[t1], t0
    14041397    biaeq t2, -sizeof IndexingHeader + IndexingHeader::m_vectorLength[t0], .opPutByValSlow

  • trunk/Source/JavaScriptCore/llint/LowLevelInterpreter64.asm

    r128534 r128790  
    10241024    loadConstantOrVariableCell(t0, t3, .opGetArrayLengthSlow)
    10251025    loadp JSCell::m_structure[t3], t2
    1026     if VALUE_PROFILER
    1027         storep t2, ArrayProfile::m_lastSeenStructure[t1]
    1028     end
    1029     loadb Structure::m_indexingType[t2], t1
    1030     btiz t1, IsArray, .opGetArrayLengthSlow
    1031     btiz t1, HasArrayStorage, .opGetArrayLengthSlow
     1026    arrayProfile(t2, t1, t0)
     1027    btiz t2, IsArray, .opGetArrayLengthSlow
     1028    btiz t2, HasArrayStorage, .opGetArrayLengthSlow
    10321029    loadis 8[PB, PC, 8], t1
    10331030    loadp 64[PB, PC, 8], t2
    … …  
    11531150    traceExecution()
    11541151    loadis 16[PB, PC, 8], t2
     1152    loadConstantOrVariableCell(t2, t0, .opGetByValSlow)
     1153    loadp JSCell::m_structure[t0], t2
     1154    loadp 32[PB, PC, 8], t3
     1155    arrayProfile(t2, t3, t1)
    11551156    loadis 24[PB, PC, 8], t3
    1156     loadConstantOrVariableCell(t2, t0, .opGetByValSlow)
     1157    btiz t2, HasArrayStorage, .opGetByValSlow
    11571158    loadConstantOrVariableInt32(t3, t1, .opGetByValSlow)
    11581159    sxi2p t1, t1
    1159     loadp JSCell::m_structure[t0], t3
    1160     loadp 32[PB, PC, 8], t2
    1161     if VALUE_PROFILER
    1162         storep t3, ArrayProfile::m_lastSeenStructure[t2]
    1163     end
    1164     btbz Structure::m_indexingType[t3], HasArrayStorage, .opGetByValSlow
    11651160    loadp JSObject::m_butterfly[t0], t3
    11661161    biaeq t1, -sizeof IndexingHeader + IndexingHeader::m_vectorLength[t3], .opGetByValSlow
    … …  
    12361231    loadis 8[PB, PC, 8], t0
    12371232    loadConstantOrVariableCell(t0, t1, .opPutByValSlow)
     1233    loadp JSCell::m_structure[t1], t2
     1234    loadp 32[PB, PC, 8], t0
     1235    arrayProfile(t2, t0, t3)
     1236    btiz t2, HasArrayStorage, .opPutByValSlow
    12381237    loadis 16[PB, PC, 8], t0
    12391238    loadConstantOrVariableInt32(t0, t2, .opPutByValSlow)
    12401239    sxi2p t2, t2
    1241     loadp JSCell::m_structure[t1], t3
    1242     loadp 32[PB, PC, 8], t0
    1243     if VALUE_PROFILER
    1244         storep t3, ArrayProfile::m_lastSeenStructure[t0]
    1245     end
    1246     btbz Structure::m_indexingType[t3], HasArrayStorage, .opPutByValSlow
    12471240    loadp JSObject::m_butterfly[t1], t0
    12481241    biaeq t2, -sizeof IndexingHeader + IndexingHeader::m_vectorLength[t0], .opPutByValSlow

  • trunk/Source/WTF/ChangeLog

    r128762 r128790  
     12012-09-17  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Array profiling has convergence issues
     4        https://bugs.webkit.org/show_bug.cgi?id=96891
     5
     6        Reviewed by Gavin Barraclough.
     7
     8        Added functions for testing if something is a power of 2.
     9
     10        * wtf/MathExtras.h:
     11        (hasZeroOrOneBitsSet):
     12        (hasTwoOrMoreBitsSet):
     13
    1142012-09-17  Ilya Tikhonovsky  <loislo@chromium.org>
    215

  • trunk/Source/WTF/wtf/MathExtras.h

    r127114 r128790  
    295295}
    296296
     297template<typename T> inline bool hasZeroOrOneBitsSet(T value)
     298{
     299    return !((value - 1) & value);
     300}
     301
     302template<typename T> inline bool hasTwoOrMoreBitsSet(T value)
     303{
     304    return !hasZeroOrOneBitsSet(value);
     305}
     306
    297307#if !COMPILER(MSVC) && !COMPILER(RVCT) && !OS(SOLARIS)
    298308using std::isfinite;
Note: See TracChangeset for help on using the changeset viewer.