Changeset 93466 in webkit for trunk/Source/JavaScriptCore/wtf/StdLibExtras.h

Timestamp:

Aug 19, 2011, 7:17:49 PM (14 years ago)

Author:

[email protected]

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.

• JavaScriptCore.xcodeproj/project.pbxproj:
• bytecode/CodeBlock.cpp:

(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):

File:

• trunk/Source/JavaScriptCore/wtf/StdLibExtras.h (modified) (2 diffs)

trunk/Source/JavaScriptCore/wtf/StdLibExtras.h

@@ -131 +131 @@
 // Binary search algorithm, calls extractKey on pre-sorted elements in array,
 // compares result with key (KeyTypes should be comparable with '--', '<', '>').
-template<typename ArrayType, typename KeyType, KeyType(*extractKey)(ArrayType*)>
-inline ArrayType* binarySearch(ArrayType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
+template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*)>
+inline ArrayElementType* binarySearch(ArrayElementType* array, size_t size, KeyType key, BinarySearchMode mode = KeyMustBePresentInArray)
 {
     // The array must contain at least one element (pre-condition, array does contain key).
@@ -169 +169 @@
 }
 
+// Modified binarySearch() algorithm designed for array-like classes that support
+// operator[] but not operator+=. One example of a class that qualifies is
+// SegmentedVector.
+template<typename ArrayElementType, typename KeyType, KeyType(*extractKey)(ArrayElementType*), typename ArrayType>
+inline ArrayElementType* genericBinarySearch(ArrayType& array, size_t size, KeyType key)
+{
+    // The array must contain at least one element (pre-condition, array does conatin key).
+    // If the array only contains one element, no need to do the comparison.
+    size_t offset = 0;
+    while (size > 1) {
+        // Pick an element to check, half way through the array, and read the value.
+        int pos = (size - 1) >> 1;
+        KeyType val = extractKey(&array[offset + pos]);
+        
+        // If the key matches, success!
+        if (val == key)
+            return &array[offset + pos];
+        // The item we are looking for is smaller than the item being check; reduce the value of 'size',
+        // chopping off the right hand half of the array.
+        if (key < val)
+            size = pos;
+        // Discard all values in the left hand half of the array, up to and including the item at pos.
+        else {
+            size -= (pos + 1);
+            offset += (pos + 1);
+        }
+
+        // 'size' should never reach zero.
+        ASSERT(size);
+    }
+    
+    // If we reach this point we've chopped down to one element, no need to check it matches
+    ASSERT(size == 1);
+    ASSERT(key == extractKey(&array[offset]));
+    return &array[offset];
+}
+
 } // namespace WTF