From 57e2aa1b261389fbaadaab83c75b3f0156973452 Mon Sep 17 00:00:00 2001
From: "ager@chromium.org"
 <ager@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Thu, 18 Sep 2008 11:18:27 +0000
Subject: [PATCH] Use null instead of undefined for deleted elements in code
 caches. Update the lookup and update code for code caches to deal with
 deleted elements.

Do not clear the code cache for the builtins object.  If there was a
matching element in the code cache, we would have hit the monomorphic
prototype failure case and removed it.
Review URL: http://codereview.chromium.org/3140

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@340 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/ic.cc         |  6 ++----
 src/objects-inl.h |  7 +++++++
 src/objects.cc    | 27 ++++++++++++++++++++++-----
 src/objects.h     |  1 +
 4 files changed, 32 insertions(+), 9 deletions(-)

diff --git a/src/ic.cc b/src/ic.cc
index 59794ea..fa150c1 100644
--- a/src/ic.cc
+++ b/src/ic.cc
@@ -164,11 +164,9 @@ IC::State IC::StateFrom(Code* target, Object* receiver) {
   // builtins are loaded lazily.  It is important to keep inline
   // caches for the builtins object monomorphic.  Therefore, if we get
   // an inline cache miss for the builtins object after lazily loading
-  // JavaScript builtins, we clear the code cache and return
-  // uninitialized as the state to force the inline cache back to
-  // monomorphic state.
+  // JavaScript builtins, we return uninitialized as the state to
+  // force the inline cache back to monomorphic state.
   if (receiver->IsJSBuiltinsObject()) {
-    map->ClearCodeCache();
     return UNINITIALIZED;
   }
 
diff --git a/src/objects-inl.h b/src/objects-inl.h
index 5bcf0a7..271dd7e 100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -977,6 +977,13 @@ void FixedArray::set_undefined(int index) {
 }
 
 
+void FixedArray::set_null(int index) {
+  ASSERT(index >= 0 && index < this->length());
+  ASSERT(!Heap::InNewSpace(Heap::null_value()));
+  WRITE_FIELD(this, kHeaderSize + index * kPointerSize, Heap::null_value());
+}
+
+
 void FixedArray::set_the_hole(int index) {
   ASSERT(index >= 0 && index < this->length());
   ASSERT(!Heap::InNewSpace(Heap::the_hole_value()));
diff --git a/src/objects.cc b/src/objects.cc
index 7240d90..fb202c2 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -2379,9 +2379,15 @@ Object* Map::UpdateCodeCache(String* name, Code* code) {
   // First check whether we can update existing code cache without
   // extending it.
   int length = cache->length();
+  int deleted_index = -1;
   for (int i = 0; i < length; i += 2) {
     Object* key = cache->get(i);
+    if (key->IsNull()) {
+      if (deleted_index < 0) deleted_index = i;
+      continue;
+    }
     if (key->IsUndefined()) {
+      if (deleted_index >= 0) i = deleted_index;
       cache->set(i + 0, name);
       cache->set(i + 1, code);
       return this;
@@ -2395,6 +2401,14 @@ Object* Map::UpdateCodeCache(String* name, Code* code) {
     }
   }
 
+  // Reached the end of the code cache.  If there were deleted
+  // elements, reuse the space for the first of them.
+  if (deleted_index >= 0) {
+    cache->set(deleted_index + 0, name);
+    cache->set(deleted_index + 1, code);
+    return this;
+  }
+
   // Extend the code cache with some new entries (at least one).
   int new_length = length + ((length >> 1) & ~1) + 2;
   ASSERT((new_length & 1) == 0);  // must be a multiple of two
@@ -2415,9 +2429,9 @@ Object* Map::FindInCodeCache(String* name, Code::Flags flags) {
   int length = cache->length();
   for (int i = 0; i < length; i += 2) {
     Object* key = cache->get(i);
-    if (key->IsUndefined()) {
-      return key;
-    }
+    // Skip deleted elements.
+    if (key->IsNull()) continue;
+    if (key->IsUndefined()) return key;
     if (name->Equals(String::cast(key))) {
       Code* code = Code::cast(cache->get(i + 1));
       if (code->flags() == flags) return code;
@@ -2440,8 +2454,11 @@ int Map::IndexInCodeCache(Code* code) {
 void Map::RemoveFromCodeCache(int index) {
   FixedArray* array = code_cache();
   ASSERT(array->length() >= index && array->get(index)->IsCode());
-  array->set_undefined(index - 1);  // key
-  array->set_undefined(index);  // code
+  // Use null instead of undefined for deleted elements to distinguish
+  // deleted elements from unused elements.  This distinction is used
+  // when looking up in the cache and when updating the cache.
+  array->set_null(index - 1);  // key
+  array->set_null(index);  // code
 }
 
 
diff --git a/src/objects.h b/src/objects.h
index 0957a9f..60b4cfe 100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -1443,6 +1443,7 @@ class FixedArray: public Array {
 
   // Setters for frequently used oddballs located in old space.
   inline void set_undefined(int index);
+  inline void set_null(int index);
   inline void set_the_hole(int index);
 
   // Setter that skips the write barrier if mode is SKIP_WRITE_BARRIER.
-- 
2.7.4