Changeset 93466 in webkit


Ignore:
Timestamp:
Aug 19, 2011 7:17:49 PM (13 years ago)
Author:
fpizlo@apple.com
Message:

The JSC JIT currently has no facility to profile and report
the types of values
​https://bugs.webkit.org/show_bug.cgi?id=65901

Reviewed by Gavin Barraclough.

Added the ability to profile the values seen at function calls (both
arguments and results) and heap loads. This is done with emphasis
on performance. A value profiling site consists of: add, and,
move, and store; no branching is necessary. Each value profiling
site (called a ValueProfile) has a ring buffer of 8 recently-seen
values. ValueProfiles are stored in the CodeBlock; there will be
one for each argument (excluding this) and each heap load or callsite.
Each time a value profiling site executes, it stores the value into
a pseudo-random element in the ValueProfile buffer. The point is
that for frequently executed code, we will have 8 somewhat recent
values in the buffer and will be able to not only figure out what
type it is, but also to be able to reason about the actual values
if we wish to do so.

This feature is currently disabled by default. When enabled, it
results in a 3.7% slow-down on SunSpider.

(JSC::CodeBlock::~CodeBlock):

  • bytecode/CodeBlock.h:

(JSC::CodeBlock::addValueProfile):
(JSC::CodeBlock::numberOfValueProfiles):
(JSC::CodeBlock::valueProfile):
(JSC::CodeBlock::valueProfileForBytecodeOffset):

  • bytecode/ValueProfile.h: Added.

(JSC::ValueProfile::ValueProfile):
(JSC::ValueProfile::numberOfSamples):
(JSC::ValueProfile::computeProbability):
(JSC::ValueProfile::numberOfInt32s):
(JSC::ValueProfile::numberOfDoubles):
(JSC::ValueProfile::numberOfCells):
(JSC::ValueProfile::probabilityOfInt32):
(JSC::ValueProfile::probabilityOfDouble):
(JSC::ValueProfile::probabilityOfCell):
(JSC::getValueProfileBytecodeOffset):

  • jit/JIT.cpp:

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

  • jit/JIT.h:

(JSC::JIT::emitValueProfilingSite):

  • jit/JITCall.cpp:

(JSC::JIT::emit_op_call_put_result):

  • jit/JITInlineMethods.h:

(JSC::JIT::emitValueProfilingSite):

  • jit/JITPropertyAccess.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC::JIT::emitSlow_op_get_by_val):
(JSC::JIT::emit_op_method_check):
(JSC::JIT::emit_op_get_by_id):
(JSC::JIT::emitSlow_op_get_by_id):

  • jit/JSInterfaceJIT.h:
  • wtf/Platform.h:
  • wtf/StdLibExtras.h:

(WTF::binarySearch):
(WTF::genericBinarySearch):

Location:
trunk/Source/JavaScriptCore
Files:
1 added
12 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r93465 r93466  
     12011-08-19  Filip Pizlo  <fpizlo@apple.com>
     2
     3        The JSC JIT currently has no facility to profile and report
     4        the types of values
     5        https://bugs.webkit.org/show_bug.cgi?id=65901
     6
     7        Reviewed by Gavin Barraclough.
     8       
     9        Added the ability to profile the values seen at function calls (both
     10        arguments and results) and heap loads.  This is done with emphasis
     11        on performance.  A value profiling site consists of: add, and,
     12        move, and store; no branching is necessary.  Each value profiling
     13        site (called a ValueProfile) has a ring buffer of 8 recently-seen
     14        values.  ValueProfiles are stored in the CodeBlock; there will be
     15        one for each argument (excluding this) and each heap load or callsite.
     16        Each time a value profiling site executes, it stores the value into
     17        a pseudo-random element in the ValueProfile buffer.  The point is
     18        that for frequently executed code, we will have 8 somewhat recent
     19        values in the buffer and will be able to not only figure out what
     20        type it is, but also to be able to reason about the actual values
     21        if we wish to do so.
     22       
     23        This feature is currently disabled by default.  When enabled, it
     24        results in a 3.7% slow-down on SunSpider.
     25
     26        * JavaScriptCore.xcodeproj/project.pbxproj:
     27        * bytecode/CodeBlock.cpp:
     28        (JSC::CodeBlock::~CodeBlock):
     29        * bytecode/CodeBlock.h:
     30        (JSC::CodeBlock::addValueProfile):
     31        (JSC::CodeBlock::numberOfValueProfiles):
     32        (JSC::CodeBlock::valueProfile):
     33        (JSC::CodeBlock::valueProfileForBytecodeOffset):
     34        * bytecode/ValueProfile.h: Added.
     35        (JSC::ValueProfile::ValueProfile):
     36        (JSC::ValueProfile::numberOfSamples):
     37        (JSC::ValueProfile::computeProbability):
     38        (JSC::ValueProfile::numberOfInt32s):
     39        (JSC::ValueProfile::numberOfDoubles):
     40        (JSC::ValueProfile::numberOfCells):
     41        (JSC::ValueProfile::probabilityOfInt32):
     42        (JSC::ValueProfile::probabilityOfDouble):
     43        (JSC::ValueProfile::probabilityOfCell):
     44        (JSC::getValueProfileBytecodeOffset):
     45        * jit/JIT.cpp:
     46        (JSC::JIT::privateCompileSlowCases):
     47        (JSC::JIT::privateCompile):
     48        * jit/JIT.h:
     49        (JSC::JIT::emitValueProfilingSite):
     50        * jit/JITCall.cpp:
     51        (JSC::JIT::emit_op_call_put_result):
     52        * jit/JITInlineMethods.h:
     53        (JSC::JIT::emitValueProfilingSite):
     54        * jit/JITPropertyAccess.cpp:
     55        (JSC::JIT::emit_op_get_by_val):
     56        (JSC::JIT::emitSlow_op_get_by_val):
     57        (JSC::JIT::emit_op_method_check):
     58        (JSC::JIT::emit_op_get_by_id):
     59        (JSC::JIT::emitSlow_op_get_by_id):
     60        * jit/JSInterfaceJIT.h:
     61        * wtf/Platform.h:
     62        * wtf/StdLibExtras.h:
     63        (WTF::binarySearch):
     64        (WTF::genericBinarySearch):
     65
    1662011-08-19  Daniel Bates  <dbates@webkit.org>
    267

  • trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r92974 r93466  
    5050                0BF28A2911A33DC300638F84 /* SizeLimits.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0BF28A2811A33DC300638F84 /* SizeLimits.cpp */; };
    5151                0F29479C126E698C00B3ABF5 /* DecimalNumber.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F29479B126E698C00B3ABF5 /* DecimalNumber.cpp */; };
     52                0F963B3813FC6FE90002D9B2 /* ValueProfile.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F963B3613FC6FDE0002D9B2 /* ValueProfile.h */; settings = {ATTRIBUTES = (Private, ); }; };
    5253                1400067712A6F7830064D123 /* OSAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 1400067612A6F7830064D123 /* OSAllocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
    5354                1400069312A6F9E10064D123 /* OSAllocatorPosix.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1400069212A6F9E10064D123 /* OSAllocatorPosix.cpp */; };
    … …  
    730731                0BF28A2811A33DC300638F84 /* SizeLimits.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SizeLimits.cpp; sourceTree = "<group>"; };
    731732                0F29479B126E698C00B3ABF5 /* DecimalNumber.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = DecimalNumber.cpp; sourceTree = "<group>"; };
     733                0F963B3613FC6FDE0002D9B2 /* ValueProfile.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ValueProfile.h; sourceTree = "<group>"; };
    732734                1400067612A6F7830064D123 /* OSAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = OSAllocator.h; sourceTree = "<group>"; };
    733735                1400069212A6F9E10064D123 /* OSAllocatorPosix.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = OSAllocatorPosix.cpp; sourceTree = "<group>"; };
    … …  
    21642166                        isa = PBXGroup;
    21652167                        children = (
     2168                                0F963B3613FC6FDE0002D9B2 /* ValueProfile.h */,
    21662169                                969A07900ED1D3AE00F1F681 /* CodeBlock.cpp */,
    21672170                                969A07910ED1D3AE00F1F681 /* CodeBlock.h */,
    … …  
    22312234                                86ADD1450FDDEA980006EEC2 /* ARMv7Assembler.h in Headers */,
    22322235                                BC18C3E60E16F5CD00B34460 /* ArrayConstructor.h in Headers */,
     2236                                0F963B3813FC6FE90002D9B2 /* ValueProfile.h in Headers */,
    22332237                                BC18C3E70E16F5CD00B34460 /* ArrayPrototype.h in Headers */,
    22342238                                BC18C5240E16FC8A00B34460 /* ArrayPrototype.lut.h in Headers */,

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

    r93238 r93466  
    14331433CodeBlock::~CodeBlock()
    14341434{
     1435#if ENABLE(VERBOSE_VALUE_PROFILE)
     1436    printf("ValueProfile for %p:\n", this);
     1437    for (unsigned i = 0; i < numberOfValueProfiles(); ++i) {
     1438        ValueProfile* profile = valueProfile(i);
     1439        if (profile->bytecodeOffset < 0) {
     1440            ASSERT(profile->bytecodeOffset == -1);
     1441            printf("   arg = %u: ", i + 1);
     1442        } else
     1443            printf("   bc = %d: ", profile->bytecodeOffset);
     1444        printf("samples = %u, int32 = %u, double = %u, cell = %u\n",
     1445               profile->numberOfSamples(),
     1446               profile->probabilityOfInt32(),
     1447               profile->probabilityOfDouble(),
     1448               profile->probabilityOfCell());
     1449    }
     1450#endif
     1451
    14351452#if ENABLE(JIT)
    14361453    for (size_t size = m_structureStubInfos.size(), i = 0; i < size; ++i)

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

    r93238 r93466  
    4040#include "RegExpObject.h"
    4141#include "UString.h"
     42#include "ValueProfile.h"
    4243#include <wtf/FastAllocBase.h>
    4344#include <wtf/PassOwnPtr.h>
    4445#include <wtf/RefPtr.h>
     46#include <wtf/SegmentedVector.h>
    4547#include <wtf/Vector.h>
    4648
    … …  
    382384        MethodCallLinkInfo& methodCallLinkInfo(int index) { return m_methodCallLinkInfos[index]; }
    383385#endif
     386       
     387#if ENABLE(VALUE_PROFILER)
     388        ValueProfile* addValueProfile(int bytecodeOffset)
     389        {
     390            m_valueProfiles.append(ValueProfile(bytecodeOffset));
     391            return &m_valueProfiles.last();
     392        }
     393        unsigned numberOfValueProfiles() { return m_valueProfiles.size(); }
     394        ValueProfile* valueProfile(int index) { return &m_valueProfiles[index]; }
     395        ValueProfile* valueProfileForBytecodeOffset(int bytecodeOffset)
     396        {
     397            return WTF::genericBinarySearch<ValueProfile, int, getValueProfileBytecodeOffset>(m_valueProfiles, m_valueProfiles.size(), bytecodeOffset);
     398        }
     399#endif
     400
    384401        unsigned globalResolveInfoCount() const
    385402        {
    … …  
    576593        Vector<CallLinkInfo> m_callLinkInfos;
    577594        Vector<MethodCallLinkInfo> m_methodCallLinkInfos;
     595#endif
     596#if ENABLE(VALUE_PROFILER)
     597        SegmentedVector<ValueProfile, 8> m_valueProfiles;
    578598#endif
    579599

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

    r92498 r93466  
    373373    m_globalResolveInfoIndex = 0;
    374374    m_callLinkInfoIndex = 0;
     375   
     376#if !ASSERT_DISABLED && ENABLE(VALUE_PROFILER)
     377    // Use this to assert that slow-path code associates new profiling sites with existing
     378    // ValueProfiles rather than creating new ones. This ensures that for a given instruction
     379    // (say, get_by_id) we get combined statistics for both the fast-path executions of that
     380    // instructions and the slow-path executions. Furthermore, if the slow-path code created
     381    // new ValueProfiles then the ValueProfiles would no longer be sorted by bytecode offset,
     382    // which would break the invariant necessary to use CodeBlock::valueProfileForBytecodeOffset().
     383    unsigned numberOfValueProfiles = m_codeBlock->numberOfValueProfiles();
     384#endif
    375385
    376386    for (Vector<SlowCaseEntry>::iterator iter = m_slowCases.begin(); iter != m_slowCases.end();) {
    … …  
    462472    ASSERT(m_propertyAccessInstructionIndex == m_propertyAccessCompilationInfo.size());
    463473    ASSERT(m_callLinkInfoIndex == m_callStructureStubCompilationInfo.size());
     474#if ENABLE(VALUE_PROFILER)
     475    ASSERT(numberOfValueProfiles == m_codeBlock->numberOfValueProfiles());
     476#endif
    464477
    465478#ifndef NDEBUG
    … …  
    491504        static SamplingCounter counter("orignalJIT");
    492505        emitCount(counter);
     506#endif
     507
     508#if ENABLE(VALUE_PROFILER)
     509        ASSERT(m_bytecodeOffset == (unsigned)-1);
     510        for (int argumentRegister = -RegisterFile::CallFrameHeaderSize - m_codeBlock->m_numParameters + 1; argumentRegister < -RegisterFile::CallFrameHeaderSize; ++argumentRegister) {
     511            loadPtr(Address(callFrameRegister, argumentRegister * sizeof(Register)), regT0);
     512            emitValueProfilingSite(FirstProfilingSite);
     513        }
    493514#endif
    494515

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

    r93277 r93466  
    305305        template<typename T> void emitAllocateJSFinalObject(T structure, RegisterID result, RegisterID storagePtr);
    306306        void emitAllocateJSFunction(FunctionExecutable*, RegisterID scopeChain, RegisterID result, RegisterID storagePtr);
     307       
     308        enum ValueProfilingSiteKind { FirstProfilingSite, SubsequentProfilingSite };
     309#if ENABLE(VALUE_PROFILER)
     310        // This assumes that the value to profile is in regT0 and that regT3 is available for
     311        // scratch.
     312        void emitValueProfilingSite(ValueProfilingSiteKind);
     313#else
     314        void emitValueProfilingSite(ValueProfilingSiteKind) { }
     315#endif
    307316
    308317#if USE(JSVALUE32_64)

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

    r90423 r93466  
    5959{
    6060    int dst = instruction[1].u.operand;
     61    emitValueProfilingSite(FirstProfilingSite);
    6162    emitPutVirtualRegister(dst);
    6263}

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

    r92498 r93466  
    431431}
    432432
     433#if ENABLE(VALUE_PROFILER)
     434inline void JIT::emitValueProfilingSite(ValueProfilingSiteKind siteKind)
     435{
     436    const RegisterID value = regT0;
     437    const RegisterID scratch = regT3;
     438   
     439    ValueProfile* valueProfile;
     440    if (siteKind == FirstProfilingSite)
     441        valueProfile = m_codeBlock->addValueProfile(m_bytecodeOffset);
     442    else {
     443        ASSERT(siteKind == SubsequentProfilingSite);
     444        valueProfile = m_codeBlock->valueProfileForBytecodeOffset(m_bytecodeOffset);
     445    }
     446   
     447    ASSERT(valueProfile);
     448   
     449    if (m_randomGenerator.getUint32() & 1)
     450        add32(Imm32(1), bucketCounterRegister);
     451    else
     452        add32(Imm32(3), bucketCounterRegister);
     453    and32(Imm32(ValueProfile::bucketIndexMask), bucketCounterRegister);
     454    move(ImmPtr(valueProfile->buckets), scratch);
     455    storePtr(value, BaseIndex(scratch, bucketCounterRegister, TimesEight));
     456}
     457#endif
     458
    433459#if USE(JSVALUE32_64)
    434460

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

    r90875 r93466  
    108108    addSlowCase(branchTestPtr(Zero, regT0));
    109109
     110    emitValueProfilingSite(FirstProfilingSite);
    110111    emitPutVirtualRegister(dst);
    111112}
    … …  
    137138    stubCall.addArgument(property, regT2);
    138139    stubCall.call(dst);
     140
     141    emitValueProfilingSite(SubsequentProfilingSite);
    139142}
    140143
    … …  
    319322
    320323    match.link(this);
     324    emitValueProfilingSite(FirstProfilingSite);
    321325    emitPutVirtualRegister(resultVReg);
    322326
    … …  
    346350    emitGetVirtualRegister(baseVReg, regT0);
    347351    compileGetByIdHotPath(baseVReg, ident);
     352    emitValueProfilingSite(FirstProfilingSite);
    348353    emitPutVirtualRegister(resultVReg);
    349354}
    … …  
    388393
    389394    compileGetByIdSlowCase(resultVReg, baseVReg, ident, iter, false);
     395    emitValueProfilingSite(SubsequentProfilingSite);
    390396}
    391397

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

    r90237 r93466  
    5656        static const RegisterID firstArgumentRegister = X86Registers::edi;
    5757       
     58#if ENABLE(VALUE_PROFILER)
     59        static const RegisterID bucketCounterRegister = X86Registers::r10;
     60#endif
     61       
    5862        static const RegisterID timeoutCheckRegister = X86Registers::r12;
    5963        static const RegisterID callFrameRegister = X86Registers::r13;

  • trunk/Source/JavaScriptCore/wtf/Platform.h

    r93445 r93466  
    969969#endif
    970970
     971/* Currently only implemented for JSVALUE64, only tested on PLATFORM(MAC) */
     972#if !defined(ENABLE_VALUE_PROFILER) && ENABLE(JIT) && USE(JSVALUE64) && PLATFORM(MAC)
     973#define ENABLE_VALUE_PROFILER 0
     974#endif
     975
     976#if !defined(ENABLE_VERBOSE_VALUE_PROFILE) && ENABLE(VALUE_PROFILER)
     977#define ENABLE_VERBOSE_VALUE_PROFILE 0
     978#endif
     979
    971980/* Ensure that either the JIT or the interpreter has been enabled. */
    972981#if !defined(ENABLE_INTERPRETER) && !ENABLE(JIT)

  • trunk/Source/JavaScriptCore/wtf/StdLibExtras.h

    r93039 r93466  
    131131// Binary search algorithm, calls extractKey on pre-sorted elements in array,
    132132// compares result with key (KeyTypes should be comparable with '--', '<', '>').
    133 template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)>
    134 inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
     133template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*)>
     134inline ArrayElementType* binarySearch(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
    135135{
    136136    // The array must contain at least one element (pre-condition, array does contain key).
    … …  
    169169}
    170170
     171// Modified binarySearch() algorithm designed for array-like classes that support
     172// operator[] but not operator+=. One example of a class that qualifies is
     173// SegmentedVector.
     174template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*), typename ArrayType>
     175inline ArrayElementType* genericBinarySearch(ArrayType& array, size_t size, KeyType key)
     176{
     177    // The array must contain at least one element (pre-condition, array does conatin key).
     178    // If the array only contains one element, no need to do the comparison.
     179    size_t offset = 0;
     180    while (size > 1) {
     181        // Pick an element to check, half way through the array, and read the value.
     182        int pos = (size - 1) >> 1;
     183        KeyType val = extractKey(&array[offset + pos]);
     184       
     185        // If the key matches, success!
     186        if (val == key)
     187            return &array[offset + pos];
     188        // The item we are looking for is smaller than the item being check; reduce the value of 'size',
     189        // chopping off the right hand half of the array.
     190        if (key < val)
     191            size = pos;
     192        // Discard all values in the left hand half of the array, up to and including the item at pos.
     193        else {
     194            size -= (pos + 1);
     195            offset += (pos + 1);
     196        }
     197
     198        // 'size' should never reach zero.
     199        ASSERT(size);
     200    }
     201   
     202    // If we reach this point we've chopped down to one element, no need to check it matches
     203    ASSERT(size == 1);
     204    ASSERT(key == extractKey(&array[offset]));
     205    return &array[offset];
     206}
     207
    171208} // namespace WTF
    172209
Note: See TracChangeset for help on using the changeset viewer.