Revision: 4616
Author: [email protected]
Date: Fri May 7 05:48:18 2010
Log: Moving more code to lookup an item from the native cache into code
generator.
To bypass expensive invocation of JS functions from C++ and omit runtime
call overhead for searching the cache, more elaborate deferred code is
generated.
Review URL: http://codereview.chromium.org/1695007
http://code.google.com/p/v8/source/detail?r=4616
Modified:
/branches/bleeding_edge/src/heap.h
/branches/bleeding_edge/src/ia32/codegen-ia32.cc
/branches/bleeding_edge/src/objects.h
/branches/bleeding_edge/src/x64/codegen-x64.cc
/branches/bleeding_edge/test/cctest/test-api.cc
=======================================
--- /branches/bleeding_edge/src/heap.h Thu May 6 02:35:18 2010
+++ /branches/bleeding_edge/src/heap.h Fri May 7 05:48:18 2010
@@ -978,6 +978,8 @@
static inline bool ShouldBePromoted(Address old_address, int
object_size);
static int MaxObjectSizeInNewSpace() { return kMaxObjectSizeInNewSpace; }
+
+ static void ClearJSFunctionResultCaches();
private:
static int reserved_semispace_size_;
@@ -1193,8 +1195,6 @@
HeapObject* target,
int size);
- static void ClearJSFunctionResultCaches();
-
#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
// Record the copy of an object in the NewSpace's statistics.
static void RecordCopiedObject(HeapObject* obj);
=======================================
--- /branches/bleeding_edge/src/ia32/codegen-ia32.cc Fri May 7 04:55:24
2010
+++ /branches/bleeding_edge/src/ia32/codegen-ia32.cc Fri May 7 05:48:18
2010
@@ -6627,14 +6627,120 @@
virtual void Generate();
private:
- Register dst_, cache_, key_;
+ Register dst_; // on invocation Smi index of finger, on exit
+ // holds value being looked up.
+ Register cache_; // instance of JSFunctionResultCache.
+ Register key_; // key being looked up.
};
+
+
+// Return a position of the element at |index_as_smi| + |additional_offset|
+// in FixedArray pointer to which is held in |array|. |index_as_smi| is
Smi.
+static Operand ArrayElement(Register array,
+ Register index_as_smi,
+ int additional_offset = 0) {
+ int offset = FixedArray::kHeaderSize + additional_offset * kPointerSize;
+ return FieldOperand(array, index_as_smi, times_half_pointer_size,
offset);
+}
void DeferredSearchCache::Generate() {
- __ push(cache_);
+ Label first_loop, search_further, second_loop, cache_miss;
+
+ // Smi-tagging is equivalent to multiplying by 2.
+ STATIC_ASSERT(kSmiTag == 0);
+ STATIC_ASSERT(kSmiTagSize == 1);
+
+ Smi* kEntrySizeSmi = Smi::FromInt(JSFunctionResultCache::kEntrySize);
+ Smi* kEntriesIndexSmi =
Smi::FromInt(JSFunctionResultCache::kEntriesIndex);
+
+ // Check the cache from finger to start of the cache.
+ __ bind(&first_loop);
+ __ sub(Operand(dst_), Immediate(kEntrySizeSmi));
+ __ cmp(Operand(dst_), Immediate(kEntriesIndexSmi));
+ __ j(less, &search_further);
+
+ __ cmp(key_, ArrayElement(cache_, dst_));
+ __ j(not_equal, &first_loop);
+
+ __ mov(FieldOperand(cache_, JSFunctionResultCache::kFingerOffset), dst_);
+ __ mov(dst_, ArrayElement(cache_, dst_, 1));
+ __ jmp(exit_label());
+
+ __ bind(&search_further);
+
+ // Check the cache from end of cache up to finger.
+ __ mov(dst_, FieldOperand(cache_,
JSFunctionResultCache::kCacheSizeOffset));
+
+ __ bind(&second_loop);
+ __ sub(Operand(dst_), Immediate(kEntrySizeSmi));
+ // Consider prefetching into some reg.
+ __ cmp(dst_, FieldOperand(cache_, JSFunctionResultCache::kFingerOffset));
+ __ j(less_equal, &cache_miss);
+
+ __ cmp(key_, ArrayElement(cache_, dst_));
+ __ j(not_equal, &second_loop);
+
+ __ mov(FieldOperand(cache_, JSFunctionResultCache::kFingerOffset), dst_);
+ __ mov(dst_, ArrayElement(cache_, dst_, 1));
+ __ jmp(exit_label());
+
+ __ bind(&cache_miss);
+ __ push(cache_); // store a reference to cache
+ __ push(key_); // store a key
+ Handle<Object> receiver(Top::global_context()->global());
+ __ push(Immediate(receiver));
__ push(key_);
- __ CallRuntime(Runtime::kGetFromCache, 2);
+ // On ia32 function must be in edi.
+ __ mov(edi, FieldOperand(cache_, JSFunctionResultCache::kFactoryOffset));
+ ParameterCount expected(1);
+ __ InvokeFunction(edi, expected, CALL_FUNCTION);
+
+ // Find a place to put new cached value into.
+ Label add_new_entry, update_cache;
+ __ mov(ecx, Operand(esp, kPointerSize)); // restore the cache
+ // Possible optimization: cache size is constant for the given cache
+ // so technically we could use a constant here. However, if we have
+ // cache miss this optimization would hardly matter much.
+
+ // Check if we could add new entry to cache.
+ __ mov(ebx, FieldOperand(ecx, FixedArray::kLengthOffset));
+ __ SmiTag(ebx);
+ __ cmp(ebx, FieldOperand(ecx, JSFunctionResultCache::kCacheSizeOffset));
+ __ j(greater, &add_new_entry);
+
+ // Check if we could evict entry after finger.
+ __ mov(edx, FieldOperand(ecx, JSFunctionResultCache::kFingerOffset));
+ __ add(Operand(edx), Immediate(kEntrySizeSmi));
+ __ cmp(ebx, Operand(edx));
+ __ j(greater, &update_cache);
+
+ // Need to wrap over the cache.
+ __ mov(edx, Immediate(kEntriesIndexSmi));
+ __ jmp(&update_cache);
+
+ __ bind(&add_new_entry);
+ __ mov(edx, FieldOperand(ecx, JSFunctionResultCache::kCacheSizeOffset));
+ __ lea(ebx, Operand(edx, JSFunctionResultCache::kEntrySize << 1));
+ __ mov(FieldOperand(ecx, JSFunctionResultCache::kCacheSizeOffset), ebx);
+
+ // Update the cache itself.
+ // edx holds the index.
+ __ bind(&update_cache);
+ __ pop(ebx); // restore the key
+ __ mov(FieldOperand(ecx, JSFunctionResultCache::kFingerOffset), edx);
+ // Store key.
+ __ mov(ArrayElement(ecx, edx), ebx);
+ __ RecordWrite(ecx, 0, ebx, edx);
+
+ // Store value.
+ __ pop(ecx); // restore the cache.
+ __ mov(edx, FieldOperand(ecx, JSFunctionResultCache::kFingerOffset));
+ __ add(Operand(edx), Immediate(Smi::FromInt(1)));
+ __ mov(ebx, eax);
+ __ mov(ArrayElement(ecx, edx), ebx);
+ __ RecordWrite(ecx, 0, ebx, edx);
+
if (!dst_.is(eax)) {
__ mov(dst_, eax);
}
@@ -6676,21 +6782,14 @@
cache.reg(),
key.reg());
- const int kFingerOffset =
- FixedArray::OffsetOfElementAt(JSFunctionResultCache::kFingerIndex);
// tmp.reg() now holds finger offset as a smi.
ASSERT(kSmiTag == 0 && kSmiTagSize == 1);
- __ mov(tmp.reg(), FieldOperand(cache.reg(), kFingerOffset));
- __ cmp(key.reg(), FieldOperand(cache.reg(),
- tmp.reg(), // as smi
- times_half_pointer_size,
- FixedArray::kHeaderSize));
+ __ mov(tmp.reg(), FieldOperand(cache.reg(),
+ JSFunctionResultCache::kFingerOffset));
+ __ cmp(key.reg(), ArrayElement(cache.reg(), tmp.reg()));
deferred->Branch(not_equal);
- __ mov(tmp.reg(), FieldOperand(cache.reg(),
- tmp.reg(), // as smi
- times_half_pointer_size,
- kPointerSize + FixedArray::kHeaderSize));
+ __ mov(tmp.reg(), ArrayElement(cache.reg(), tmp.reg(), 1));
deferred->BindExit();
frame_->Push(&tmp);
=======================================
--- /branches/bleeding_edge/src/objects.h Thu May 6 06:21:53 2010
+++ /branches/bleeding_edge/src/objects.h Fri May 7 05:48:18 2010
@@ -2328,6 +2328,10 @@
static const int kEntrySize = 2; // key + value
+ static const int kFactoryOffset = kHeaderSize;
+ static const int kFingerOffset = kFactoryOffset + kPointerSize;
+ static const int kCacheSizeOffset = kFingerOffset + kPointerSize;
+
inline void MakeZeroSize();
inline void Clear();
=======================================
--- /branches/bleeding_edge/src/x64/codegen-x64.cc Fri May 7 04:25:29 2010
+++ /branches/bleeding_edge/src/x64/codegen-x64.cc Fri May 7 05:48:18 2010
@@ -4476,22 +4476,142 @@
class DeferredSearchCache: public DeferredCode {
public:
- DeferredSearchCache(Register dst, Register cache, Register key)
- : dst_(dst), cache_(cache), key_(key) {
+ DeferredSearchCache(Register dst,
+ Register cache,
+ Register key,
+ Register scratch)
+ : dst_(dst), cache_(cache), key_(key), scratch_(scratch) {
set_comment("[ DeferredSearchCache");
}
virtual void Generate();
private:
- Register dst_, cache_, key_;
+ Register dst_; // on invocation index of finger (as Smi), on exit
+ // holds value being looked up.
+ Register cache_; // instance of JSFunctionResultCache.
+ Register key_; // key being looked up.
+ Register scratch_;
};
+
+
+// Return a position of the element at |index| + |additional_offset|
+// in FixedArray pointer to which is held in |array|. |index| is int32.
+static Operand ArrayElement(Register array,
+ Register index,
+ int additional_offset = 0) {
+ int offset = FixedArray::kHeaderSize + additional_offset * kPointerSize;
+ return FieldOperand(array, index, times_pointer_size, offset);
+}
void DeferredSearchCache::Generate() {
- __ push(cache_);
+ Label first_loop, search_further, second_loop, cache_miss;
+
+ Immediate kEntriesIndexImm =
Immediate(JSFunctionResultCache::kEntriesIndex);
+ Immediate kEntrySizeImm = Immediate(JSFunctionResultCache::kEntrySize);
+
+ __ SmiToInteger32(dst_, dst_);
+ // Check the cache from finger to start of the cache.
+ __ bind(&first_loop);
+ __ subq(dst_, kEntrySizeImm);
+ __ cmpq(dst_, kEntriesIndexImm);
+ __ j(less, &search_further);
+
+ __ cmpq(ArrayElement(cache_, dst_), key_);
+ __ j(not_equal, &first_loop);
+
+ __ Integer32ToSmi(scratch_, dst_);
+ __ movq(FieldOperand(cache_, JSFunctionResultCache::kFingerOffset),
scratch_);
+ __ movq(dst_, ArrayElement(cache_, dst_, 1));
+ __ jmp(exit_label());
+
+ __ bind(&search_further);
+
+ // Check the cache from end of cache up to finger.
+ __ movq(dst_, FieldOperand(cache_,
JSFunctionResultCache::kCacheSizeOffset));
+ __ movq(scratch_, FieldOperand(cache_,
JSFunctionResultCache::kFingerOffset));
+ __ SmiToInteger32(dst_, dst_);
+ __ SmiToInteger32(scratch_, scratch_);
+
+ __ bind(&second_loop);
+ __ subq(dst_, kEntrySizeImm);
+ __ cmpq(dst_, scratch_);
+ __ j(less_equal, &cache_miss);
+
+ __ cmpq(ArrayElement(cache_, dst_), key_);
+ __ j(not_equal, &second_loop);
+
+ __ Integer32ToSmi(scratch_, dst_);
+ __ movq(FieldOperand(cache_, JSFunctionResultCache::kFingerOffset),
scratch_);
+ __ movq(dst_, ArrayElement(cache_, dst_, 1));
+ __ jmp(exit_label());
+
+ __ bind(&cache_miss);
+ __ push(cache_); // store a reference to cache
+ __ push(key_); // store a key
+ Handle<Object> receiver(Top::global_context()->global());
+ __ Push(receiver);
__ push(key_);
- __ CallRuntime(Runtime::kGetFromCache, 2);
+ // On x64 function must be in rdi.
+ __ movq(rdi, FieldOperand(cache_,
JSFunctionResultCache::kFactoryOffset));
+ ParameterCount expected(1);
+ __ InvokeFunction(rdi, expected, CALL_FUNCTION);
+
+ // Find a place to put new cached value into.
+ Label add_new_entry, update_cache;
+ __ movq(rcx, Operand(rsp, kPointerSize)); // restore the cache
+ // Possible optimization: cache size is constant for the given cache
+ // so technically we could use a constant here. However, if we have
+ // cache miss this optimization would hardly matter much.
+
+ // Check if we could add new entry to cache.
+ __ movl(rbx, FieldOperand(rcx, FixedArray::kLengthOffset));
+ __ movq(r9, FieldOperand(rcx, JSFunctionResultCache::kCacheSizeOffset));
+ __ SmiToInteger32(r9, r9);
+ __ cmpq(rbx, r9);
+ __ j(greater, &add_new_entry);
+
+ // Check if we could evict entry after finger.
+ __ movq(rdx, FieldOperand(rcx, JSFunctionResultCache::kFingerOffset));
+ __ SmiToInteger32(rdx, rdx);
+ __ addq(rdx, kEntrySizeImm);
+ Label forward;
+ __ cmpq(rbx, rdx);
+ __ j(greater, &forward);
+ // Need to wrap over the cache.
+ __ movq(rdx, kEntriesIndexImm);
+ __ bind(&forward);
+ __ Integer32ToSmi(r9, rdx);
+ __ jmp(&update_cache);
+
+ __ bind(&add_new_entry);
+ // r9 holds cache size as int.
+ __ movq(rdx, r9);
+ __ Integer32ToSmi(r9, r9);
+ __ SmiAddConstant(rbx, r9,
Smi::FromInt(JSFunctionResultCache::kEntrySize));
+ __ movq(FieldOperand(rcx, JSFunctionResultCache::kCacheSizeOffset), rbx);
+
+ // Update the cache itself.
+ // rdx holds the index as int.
+ // r9 holds the index as smi.
+ __ bind(&update_cache);
+ __ pop(rbx); // restore the key
+ __ movq(FieldOperand(rcx, JSFunctionResultCache::kFingerOffset), r9);
+ // Store key.
+ __ movq(ArrayElement(rcx, rdx), rbx);
+ __ RecordWrite(rcx, 0, rbx, r9);
+
+ // Store value.
+ __ pop(rcx); // restore the cache.
+ __ movq(rdx, FieldOperand(rcx, JSFunctionResultCache::kFingerOffset));
+ __ SmiAddConstant(rdx, rdx, Smi::FromInt(1));
+ __ movq(r9, rdx);
+ __ SmiToInteger32(rdx, rdx);
+ __ movq(rbx, rax);
+ __ movq(ArrayElement(rcx, rdx), rbx);
+ __ RecordWrite(rcx, 0, rbx, r9);
+
if (!dst_.is(rax)) {
__ movq(dst_, rax);
}
@@ -4529,27 +4649,28 @@
Result tmp = allocator()->Allocate();
ASSERT(tmp.is_valid());
+ Result scratch = allocator()->Allocate();
+ ASSERT(scratch.is_valid());
+
DeferredSearchCache* deferred = new DeferredSearchCache(tmp.reg(),
cache.reg(),
- key.reg());
+ key.reg(),
+ scratch.reg());
const int kFingerOffset =
FixedArray::OffsetOfElementAt(JSFunctionResultCache::kFingerIndex);
// tmp.reg() now holds finger offset as a smi.
- ASSERT(kSmiTag == 0 && kSmiTagSize == 1);
__ movq(tmp.reg(), FieldOperand(cache.reg(), kFingerOffset));
SmiIndex index =
masm()->SmiToIndex(kScratchRegister, tmp.reg(), kPointerSizeLog2);
__ cmpq(key.reg(), FieldOperand(cache.reg(),
- index.reg,
- index.scale,
+ index.reg, index.scale,
FixedArray::kHeaderSize));
+ // Do NOT alter index.reg or tmp.reg() before cmpq below.
deferred->Branch(not_equal);
-
__ movq(tmp.reg(), FieldOperand(cache.reg(),
- index.reg,
- index.scale,
- kPointerSize + FixedArray::kHeaderSize));
+ index.reg, index.scale,
+ FixedArray::kHeaderSize + kPointerSize));
deferred->BindExit();
frame_->Push(&tmp);
=======================================
--- /branches/bleeding_edge/test/cctest/test-api.cc Thu May 6 04:05:50 2010
+++ /branches/bleeding_edge/test/cctest/test-api.cc Fri May 7 05:48:18 2010
@@ -10264,3 +10264,120 @@
CHECK_EQ(2, prologue_call_count_second);
CHECK_EQ(2, epilogue_call_count_second);
}
+
+
+THREADED_TEST(AddToJSFunctionResultCache) {
+ i::FLAG_allow_natives_syntax = true;
+ v8::HandleScope scope;
+
+ LocalContext context;
+
+ const char* code =
+ "(function() {"
+ " var key0 = 'a';"
+ " var key1 = 'b';"
+ " var r0 = %_GetFromCache(0, key0);"
+ " var r1 = %_GetFromCache(0, key1);"
+ " var r0_ = %_GetFromCache(0, key0);"
+ " if (r0 !== r0_)"
+ " return 'Different results for ' + key0 + ': ' + r0 + ' vs. ' +
r0_;"
+ " var r1_ = %_GetFromCache(0, key1);"
+ " if (r1 !== r1_)"
+ " return 'Different results for ' + key1 + ': ' + r1 + ' vs. ' +
r1_;"
+ " return 'PASSED';"
+ "})()";
+ v8::internal::Heap::ClearJSFunctionResultCaches();
+ ExpectString(code, "PASSED");
+}
+
+
+static const int k0CacheSize = 16;
+
+THREADED_TEST(FillJSFunctionResultCache) {
+ i::FLAG_allow_natives_syntax = true;
+ v8::HandleScope scope;
+
+ LocalContext context;
+
+ const char* code =
+ "(function() {"
+ " var k = 'a';"
+ " var r = %_GetFromCache(0, k);"
+ " for (var i = 0; i < 16; i++) {"
+ " %_GetFromCache(0, 'a' + i);"
+ " };"
+ " if (r === %_GetFromCache(0, k))"
+ " return 'FAILED: k0CacheSize is too small';"
+ " return 'PASSED';"
+ "})()";
+ v8::internal::Heap::ClearJSFunctionResultCaches();
+ ExpectString(code, "PASSED");
+}
+
+
+THREADED_TEST(RoundRobinGetFromCache) {
+ i::FLAG_allow_natives_syntax = true;
+ v8::HandleScope scope;
+
+ LocalContext context;
+
+ const char* code =
+ "(function() {"
+ " var keys = [];"
+ " for (var i = 0; i < 16; i++) keys.push(i);"
+ " var values = [];"
+ " for (var i = 0; i < 16; i++) values[i] = %_GetFromCache(0,
keys[i]);"
+ " for (var i = 0; i < 16; i++) {"
+ " var v = %_GetFromCache(0, keys[i]);"
+ " if (v !== values[i])"
+ " return 'Wrong value for ' + "
+ " keys[i] + ': ' + v + ' vs. ' + values[i];"
+ " };"
+ " return 'PASSED';"
+ "})()";
+ v8::internal::Heap::ClearJSFunctionResultCaches();
+ ExpectString(code, "PASSED");
+}
+
+
+THREADED_TEST(ReverseGetFromCache) {
+ i::FLAG_allow_natives_syntax = true;
+ v8::HandleScope scope;
+
+ LocalContext context;
+
+ const char* code =
+ "(function() {"
+ " var keys = [];"
+ " for (var i = 0; i < 16; i++) keys.push(i);"
+ " var values = [];"
+ " for (var i = 0; i < 16; i++) values[i] = %_GetFromCache(0,
keys[i]);"
+ " for (var i = 15; i >= 16; i--) {"
+ " var v = %_GetFromCache(0, keys[i]);"
+ " if (v !== values[i])"
+ " return 'Wrong value for ' + "
+ " keys[i] + ': ' + v + ' vs. ' + values[i];"
+ " };"
+ " return 'PASSED';"
+ "})()";
+ v8::internal::Heap::ClearJSFunctionResultCaches();
+ ExpectString(code, "PASSED");
+}
+
+
+THREADED_TEST(TestEviction) {
+ i::FLAG_allow_natives_syntax = true;
+ v8::HandleScope scope;
+
+ LocalContext context;
+
+ const char* code =
+ "(function() {"
+ " for (var i = 0; i < 2*16; i++) {"
+ " %_GetFromCache(0, 'a' + i);"
+ " };"
+ " return 'PASSED';"
+ "})()";
+ v8::internal::Heap::ClearJSFunctionResultCaches();
+ ExpectString(code, "PASSED");
+}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
