Changeset 131868 in webkit


Ignore:
Timestamp:
Oct 19, 2012 12:24:32 AM (12 years ago)
Author:
fpizlo@apple.com
Message:

Baseline array profiling should be less accurate, and DFG OSR exit should update array profiles on CheckArray and CheckStructure failure
​https://bugs.webkit.org/show_bug.cgi?id=99261

Reviewed by Oliver Hunt.

This makes array profiling stochastic, like value profiling. The point is to avoid
noticing one-off indexing types that we'll never see again, but instead to:

Notice the big ones: We want the DFG to compile based on the things that happen with
high probability. So, this change makes array profiling do like value profiling and
only notice a random subsampling of indexing types that flowed through an array
access. Prior to this patch array profiles noticed all indexing types and weighted
them identically.

Bias the recent: Often an array access will see awkward indexing types during the
first handful of executions because of artifacts of program startup. So, we want to
bias towards the indexing types that we saw most recently. With this change, array
profiling does like value profiling and usually tells use a random sampling that
is biased to what happened recently.

Have a backup plan: The above two things don't work by themselves because our
randomness is not that random (nor do we care enough to make it more random), and
because some procedures will have a <1/10 probability event that we must handle
without bailing because it dominates a hot loop. So, like value profiling, this
patch makes array profiling use OSR exits to tell us why we are bailing out, so
that we don't make the same mistake again in the future.

This change also makes the way that the 32-bit OSR exit compiler snatches scratch
registers more uniform. We don't need a scratch buffer when we can push and pop.

  • bytecode/DFGExitProfile.h:
  • dfg/DFGOSRExitCompiler32_64.cpp:

(JSC::DFG::OSRExitCompiler::compileExit):

  • dfg/DFGOSRExitCompiler64.cpp:

(JSC::DFG::OSRExitCompiler::compileExit):

  • dfg/DFGSpeculativeJIT.cpp:

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

  • dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

  • jit/JITInlineMethods.h:

(JSC::JIT::emitArrayProfilingSite):

  • llint/LowLevelInterpreter.asm:
Location:
trunk/Source/JavaScriptCore
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r131860 r131868  
     12012-10-18  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Baseline array profiling should be less accurate, and DFG OSR exit should update array profiles on CheckArray and CheckStructure failure
     4        https://bugs.webkit.org/show_bug.cgi?id=99261
     5
     6        Reviewed by Oliver Hunt.
     7
     8        This makes array profiling stochastic, like value profiling. The point is to avoid
     9        noticing one-off indexing types that we'll never see again, but instead to:
     10       
     11        Notice the big ones: We want the DFG to compile based on the things that happen with
     12        high probability. So, this change makes array profiling do like value profiling and
     13        only notice a random subsampling of indexing types that flowed through an array
     14        access. Prior to this patch array profiles noticed all indexing types and weighted
     15        them identically.
     16       
     17        Bias the recent: Often an array access will see awkward indexing types during the
     18        first handful of executions because of artifacts of program startup. So, we want to
     19        bias towards the indexing types that we saw most recently. With this change, array
     20        profiling does like value profiling and usually tells use a random sampling that
     21        is biased to what happened recently.
     22       
     23        Have a backup plan: The above two things don't work by themselves because our
     24        randomness is not that random (nor do we care enough to make it more random), and
     25        because some procedures will have a <1/10 probability event that we must handle
     26        without bailing because it dominates a hot loop. So, like value profiling, this
     27        patch makes array profiling use OSR exits to tell us why we are bailing out, so
     28        that we don't make the same mistake again in the future.
     29       
     30        This change also makes the way that the 32-bit OSR exit compiler snatches scratch
     31        registers more uniform. We don't need a scratch buffer when we can push and pop.
     32
     33        * bytecode/DFGExitProfile.h:
     34        * dfg/DFGOSRExitCompiler32_64.cpp:
     35        (JSC::DFG::OSRExitCompiler::compileExit):
     36        * dfg/DFGOSRExitCompiler64.cpp:
     37        (JSC::DFG::OSRExitCompiler::compileExit):
     38        * dfg/DFGSpeculativeJIT.cpp:
     39        (JSC::DFG::SpeculativeJIT::checkArray):
     40        (JSC::DFG::SpeculativeJIT::arrayify):
     41        * dfg/DFGSpeculativeJIT32_64.cpp:
     42        (JSC::DFG::SpeculativeJIT::compile):
     43        * dfg/DFGSpeculativeJIT64.cpp:
     44        (JSC::DFG::SpeculativeJIT::compile):
     45        * jit/JITInlineMethods.h:
     46        (JSC::JIT::emitArrayProfilingSite):
     47        * llint/LowLevelInterpreter.asm:
     48
    1492012-10-18  Yuqiang Xian  <yuqiang.xian@intel.com>
    250

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

    r127536 r131868  
    3737    BadType, // We exited because a type prediction was wrong.
    3838    BadCache, // We exited because an inline cache was wrong.
     39    BadIndexingType, // We exited because an indexing type was wrong.
    3940    Overflow, // We exited because of overflow.
    4041    NegativeZero, // We exited because we encountered negative zero.

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

    r131822 r131868  
    8484    // 3) Refine some value profile, if appropriate.
    8585   
    86     if (!!exit.m_jsValueSource && !!exit.m_valueProfile) {
    87         EncodedJSValue* bucket = exit.m_valueProfile.getSpecFailBucket(0);
    88        
    89         if (exit.m_jsValueSource.isAddress()) {
    90             // Save a register so we can use it.
    91             GPRReg scratch = GPRInfo::regT0;
    92             if (scratch == exit.m_jsValueSource.base())
    93                 scratch = GPRInfo::regT1;
    94             ScratchBuffer* scratchBuffer = m_jit.globalData()->scratchBufferForSize(sizeof(uint32_t));
    95             EncodedJSValue* scratchDataBuffer = static_cast<EncodedJSValue*>(scratchBuffer->dataBuffer());
    96             m_jit.store32(scratch, scratchDataBuffer);
    97             m_jit.load32(exit.m_jsValueSource.asAddress(OBJECT_OFFSETOF(EncodedValueDescriptor, asBits.tag)), scratch);
    98             m_jit.store32(scratch, &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.tag);
    99             m_jit.load32(exit.m_jsValueSource.asAddress(OBJECT_OFFSETOF(EncodedValueDescriptor, asBits.payload)), scratch);
    100             m_jit.store32(scratch, &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.payload);
    101             m_jit.load32(scratchDataBuffer, scratch);
    102         } else if (exit.m_jsValueSource.hasKnownTag()) {
    103             m_jit.store32(AssemblyHelpers::TrustedImm32(exit.m_jsValueSource.tag()), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.tag);
    104             m_jit.store32(exit.m_jsValueSource.payloadGPR(), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.payload);
    105         } else {
    106             m_jit.store32(exit.m_jsValueSource.tagGPR(), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.tag);
    107             m_jit.store32(exit.m_jsValueSource.payloadGPR(), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.payload);
     86    if (!!exit.m_jsValueSource) {
     87        if (exit.m_kind == BadCache || exit.m_kind == BadIndexingType) {
     88            // If the instruction that this originated from has an array profile, then
     89            // refine it. If it doesn't, then do nothing. The latter could happen for
     90            // hoisted checks, or checks emitted for operations that didn't have array
     91            // profiling - either ops that aren't array accesses at all, or weren't
     92            // known to be array acceses in the bytecode. The latter case is a FIXME
     93            // while the former case is an outcome of a CheckStructure not knowing why
     94            // it was emitted (could be either due to an inline cache of a property
     95            // property access, or due to an array profile).
     96           
     97            // Note: We are free to assume that the jsValueSource is already known to
     98            // be a cell since both BadCache and BadIndexingType exits occur after
     99            // the cell check would have already happened.
     100           
     101            CodeOrigin codeOrigin = exit.m_codeOriginForExitProfile;
     102            if (ArrayProfile* arrayProfile = m_jit.baselineCodeBlockFor(codeOrigin)->getArrayProfile(codeOrigin.bytecodeIndex)) {
     103                GPRReg usedRegister1;
     104                GPRReg usedRegister2;
     105                if (exit.m_jsValueSource.isAddress()) {
     106                    usedRegister1 = exit.m_jsValueSource.base();
     107                    usedRegister2 = InvalidGPRReg;
     108                } else {
     109                    usedRegister1 = exit.m_jsValueSource.payloadGPR();
     110                    if (exit.m_jsValueSource.hasKnownTag())
     111                        usedRegister2 = InvalidGPRReg;
     112                    else
     113                        usedRegister2 = exit.m_jsValueSource.tagGPR();
     114                }
     115               
     116                GPRReg scratch1;
     117                GPRReg scratch2;
     118                scratch1 = AssemblyHelpers::selectScratchGPR(usedRegister1, usedRegister2);
     119                scratch2 = AssemblyHelpers::selectScratchGPR(usedRegister1, usedRegister2, scratch1);
     120               
     121                m_jit.push(scratch1);
     122                m_jit.push(scratch2);
     123               
     124                GPRReg value;
     125                if (exit.m_jsValueSource.isAddress()) {
     126                    value = scratch1;
     127                    m_jit.loadPtr(AssemblyHelpers::Address(exit.m_jsValueSource.asAddress()), value);
     128                } else
     129                    value = exit.m_jsValueSource.payloadGPR();
     130               
     131                m_jit.loadPtr(AssemblyHelpers::Address(value, JSCell::structureOffset()), scratch1);
     132                m_jit.storePtr(scratch1, arrayProfile->addressOfLastSeenStructure());
     133                m_jit.load8(AssemblyHelpers::Address(scratch1, Structure::indexingTypeOffset()), scratch1);
     134                m_jit.move(AssemblyHelpers::TrustedImm32(1), scratch2);
     135                m_jit.lshift32(scratch1, scratch2);
     136                m_jit.or32(scratch2, AssemblyHelpers::AbsoluteAddress(arrayProfile->addressOfArrayModes()));
     137               
     138                m_jit.pop(scratch2);
     139                m_jit.pop(scratch1);
     140            }
     141        }
     142       
     143        if (!!exit.m_valueProfile) {
     144            EncodedJSValue* bucket = exit.m_valueProfile.getSpecFailBucket(0);
     145       
     146            if (exit.m_jsValueSource.isAddress()) {
     147                // Save a register so we can use it.
     148                GPRReg scratch = AssemblyHelpers::selectScratchGPR(exit.m_jsValueSource.base());
     149               
     150                m_jit.push(scratch);
     151
     152                m_jit.load32(exit.m_jsValueSource.asAddress(OBJECT_OFFSETOF(EncodedValueDescriptor, asBits.tag)), scratch);
     153                m_jit.store32(scratch, &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.tag);
     154                m_jit.load32(exit.m_jsValueSource.asAddress(OBJECT_OFFSETOF(EncodedValueDescriptor, asBits.payload)), scratch);
     155                m_jit.store32(scratch, &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.payload);
     156               
     157                m_jit.pop(scratch);
     158            } else if (exit.m_jsValueSource.hasKnownTag()) {
     159                m_jit.store32(AssemblyHelpers::TrustedImm32(exit.m_jsValueSource.tag()), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.tag);
     160                m_jit.store32(exit.m_jsValueSource.payloadGPR(), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.payload);
     161            } else {
     162                m_jit.store32(exit.m_jsValueSource.tagGPR(), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.tag);
     163                m_jit.store32(exit.m_jsValueSource.payloadGPR(), &bitwise_cast<EncodedValueDescriptor*>(bucket)->asBits.payload);
     164            }
    108165        }
    109166    }

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

    r131858 r131868  
    8787    }
    8888
    89     // 3) Refine some value profile, if appropriate.
    90    
    91     if (!!exit.m_jsValueSource && !!exit.m_valueProfile) {
    92         EncodedJSValue* bucket = exit.m_valueProfile.getSpecFailBucket(0);
    93        
     89    // 3) Refine some array and/or value profile, if appropriate.
     90   
     91    if (!!exit.m_jsValueSource) {
     92        if (exit.m_kind == BadCache || exit.m_kind == BadIndexingType) {
     93            // If the instruction that this originated from has an array profile, then
     94            // refine it. If it doesn't, then do nothing. The latter could happen for
     95            // hoisted checks, or checks emitted for operations that didn't have array
     96            // profiling - either ops that aren't array accesses at all, or weren't
     97            // known to be array acceses in the bytecode. The latter case is a FIXME
     98            // while the former case is an outcome of a CheckStructure not knowing why
     99            // it was emitted (could be either due to an inline cache of a property
     100            // property access, or due to an array profile).
     101           
     102            CodeOrigin codeOrigin = exit.m_codeOriginForExitProfile;
     103            if (ArrayProfile* arrayProfile = m_jit.baselineCodeBlockFor(codeOrigin)->getArrayProfile(codeOrigin.bytecodeIndex)) {
     104                GPRReg usedRegister;
     105                if (exit.m_jsValueSource.isAddress())
     106                    usedRegister = exit.m_jsValueSource.base();
     107                else
     108                    usedRegister = exit.m_jsValueSource.gpr();
     109               
     110                GPRReg scratch1;
     111                GPRReg scratch2;
     112                scratch1 = AssemblyHelpers::selectScratchGPR(usedRegister);
     113                scratch2 = AssemblyHelpers::selectScratchGPR(usedRegister, scratch1);
     114               
     115                m_jit.push(scratch1);
     116                m_jit.push(scratch2);
     117               
     118                GPRReg value;
     119                if (exit.m_jsValueSource.isAddress()) {
     120                    value = scratch1;
     121                    m_jit.loadPtr(AssemblyHelpers::Address(exit.m_jsValueSource.asAddress()), value);
     122                } else
     123                    value = exit.m_jsValueSource.gpr();
     124               
     125                m_jit.loadPtr(AssemblyHelpers::Address(value, JSCell::structureOffset()), scratch1);
     126                m_jit.storePtr(scratch1, arrayProfile->addressOfLastSeenStructure());
     127                m_jit.load8(AssemblyHelpers::Address(scratch1, Structure::indexingTypeOffset()), scratch1);
     128                m_jit.move(AssemblyHelpers::TrustedImm32(1), scratch2);
     129                m_jit.lshift32(scratch1, scratch2);
     130                m_jit.or32(scratch2, AssemblyHelpers::AbsoluteAddress(arrayProfile->addressOfArrayModes()));
     131               
     132                m_jit.pop(scratch2);
     133                m_jit.pop(scratch1);
     134            }
     135        }
     136       
     137        if (!!exit.m_valueProfile) {
     138            EncodedJSValue* bucket = exit.m_valueProfile.getSpecFailBucket(0);
     139           
    94140#if DFG_ENABLE(VERBOSE_SPECULATION_FAILURE)
    95         dataLog("  (have exit profile, bucket %p)  ", bucket);
     141            dataLog("  (have exit profile, bucket %p)  ", bucket);
    96142#endif
    97143           
    98         if (exit.m_jsValueSource.isAddress()) {
    99             // We can't be sure that we have a spare register. So use the tagTypeNumberRegister,
    100             // since we know how to restore it.
    101             m_jit.load64(AssemblyHelpers::Address(exit.m_jsValueSource.asAddress()), GPRInfo::tagTypeNumberRegister);
    102             m_jit.store64(GPRInfo::tagTypeNumberRegister, bucket);
    103             m_jit.move(AssemblyHelpers::TrustedImm64(bitwise_cast<int64_t>(TagTypeNumber)), GPRInfo::tagTypeNumberRegister);
    104         } else
    105             m_jit.store64(exit.m_jsValueSource.gpr(), bucket);
     144            if (exit.m_jsValueSource.isAddress()) {
     145                // We can't be sure that we have a spare register. So use the tagTypeNumberRegister,
     146                // since we know how to restore it.
     147                m_jit.load64(AssemblyHelpers::Address(exit.m_jsValueSource.asAddress()), GPRInfo::tagTypeNumberRegister);
     148                m_jit.store64(GPRInfo::tagTypeNumberRegister, bucket);
     149                m_jit.move(AssemblyHelpers::TrustedImmPtr(bitwise_cast<void*>(TagTypeNumber)), GPRInfo::tagTypeNumberRegister);
     150            } else
     151                m_jit.store64(exit.m_jsValueSource.gpr(), bucket);
     152        }
    106153    }
    107154

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

    r131858 r131868  
    438438        m_jit.load8(MacroAssembler::Address(tempGPR, Structure::indexingTypeOffset()), tempGPR);
    439439        speculationCheck(
    440             Uncountable, JSValueRegs(), NoNode,
     440            BadIndexingType, JSValueSource::unboxedCell(baseReg), NoNode,
    441441            jumpSlowForUnwantedArrayMode(tempGPR, node.arrayMode()));
    442442       
    … …  
    536536    // then this mode won't work.
    537537    speculationCheck(
    538         Uncountable, JSValueRegs(), NoNode,
     538        BadIndexingType, JSValueSource::unboxedCell(baseReg), NoNode,
    539539        m_jit.branchTest8(
    540540            MacroAssembler::NonZero,
    … …  
    570570        MacroAssembler::Address(structureGPR, Structure::indexingTypeOffset()), structureGPR);
    571571    speculationCheck(
    572         Uncountable, JSValueRegs(), NoNode,
     572        BadIndexingType, JSValueSource::unboxedCell(baseReg), NoNode,
    573573        jumpSlowForUnwantedArrayMode(structureGPR, desiredArrayMode));
    574574   

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

    r131822 r131868  
    38803880        if (node.structureSet().size() == 1) {
    38813881            speculationCheckWithConditionalDirection(
    3882                 BadCache, JSValueRegs(), NoNode,
     3882                BadCache, JSValueSource::unboxedCell(base.gpr()), NoNode,
    38833883                m_jit.branchWeakPtr(
    38843884                    JITCompiler::NotEqual,
    … …  
    38973897           
    38983898            speculationCheckWithConditionalDirection(
    3899                 BadCache, JSValueRegs(), NoNode,
     3899                BadCache, JSValueSource::unboxedCell(base.gpr()), NoNode,
    39003900                m_jit.branchWeakPtr(
    39013901                    JITCompiler::NotEqual, structure.gpr(), node.structureSet().last()),
    … …  
    39113911    case StructureTransitionWatchpoint:
    39123912    case ForwardStructureTransitionWatchpoint: {
     3913        // There is a fascinating question here of what to do about array profiling.
     3914        // We *could* try to tell the OSR exit about where the base of the access is.
     3915        // The DFG will have kept it alive, though it may not be in a register, and
     3916        // we shouldn't really load it since that could be a waste. For now though,
     3917        // we'll just rely on the fact that when a watchpoint fires then that's
     3918        // quite a hint already.
     3919       
    39133920        m_jit.addWeakReference(node.structure());
    39143921        node.structure()->addTransitionWatchpoint(

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

    r131858 r131868  
    38763876        if (node.structureSet().size() == 1) {
    38773877            speculationCheckWithConditionalDirection(
    3878                 BadCache, JSValueRegs(), NoNode,
     3878                BadCache, JSValueRegs(base.gpr()), NoNode,
    38793879                m_jit.branchWeakPtr(
    38803880                    JITCompiler::NotEqual,
    … …  
    38933893           
    38943894            speculationCheckWithConditionalDirection(
    3895                 BadCache, JSValueRegs(), NoNode,
     3895                BadCache, JSValueRegs(base.gpr()), NoNode,
    38963896                m_jit.branchWeakPtr(
    38973897                    JITCompiler::NotEqual, structure.gpr(), node.structureSet().last()),
    … …  
    39073907    case StructureTransitionWatchpoint:
    39083908    case ForwardStructureTransitionWatchpoint: {
     3909        // There is a fascinating question here of what to do about array profiling.
     3910        // We *could* try to tell the OSR exit about where the base of the access is.
     3911        // The DFG will have kept it alive, though it may not be in a register, and
     3912        // we shouldn't really load it since that could be a waste. For now though,
     3913        // we'll just rely on the fact that when a watchpoint fires then that's
     3914        // quite a hint already.
     3915       
    39093916        m_jit.addWeakReference(node.structure());
    39103917        node.structure()->addTransitionWatchpoint(

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

    r131858 r131868  
    549549inline void JIT::emitArrayProfilingSite(RegisterID structureAndIndexingType, RegisterID scratch, ArrayProfile* arrayProfile)
    550550{
     551    UNUSED_PARAM(scratch); // We had found this scratch register useful here before, so I will keep it for now.
     552   
    551553    RegisterID structure = structureAndIndexingType;
    552554    RegisterID indexingType = structureAndIndexingType;
    553555   
    554     if (canBeOptimized()) {
     556    if (canBeOptimized())
    555557        storePtr(structure, arrayProfile->addressOfLastSeenStructure());
    556         load8(Address(structure, Structure::indexingTypeOffset()), indexingType);
    557         move(TrustedImm32(1), scratch);
    558         lshift32(indexingType, scratch);
    559         or32(scratch, AbsoluteAddress(arrayProfile->addressOfArrayModes()));
    560     } else
    561         load8(Address(structure, Structure::indexingTypeOffset()), indexingType);
     558
     559    load8(Address(structure, Structure::indexingTypeOffset()), indexingType);
    562560}
    563561

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

    r131822 r131868  
    240240    if VALUE_PROFILER
    241241        storep structure, ArrayProfile::m_lastSeenStructure[profile]
    242         loadb Structure::m_indexingType[structure], indexingType
    243         move 1, scratch
    244         lshifti indexingType, scratch
    245         ori scratch, ArrayProfile::m_observedArrayModes[profile]
    246     else
    247         loadb Structure::m_indexingType[structure], indexingType
    248     end
     242    end
     243    loadb Structure::m_indexingType[structure], indexingType
    249244end
    250245
Note: See TracChangeset for help on using the changeset viewer.