From 3ce873c351a54d2d699df9e2ed4692732184adca Mon Sep 17 00:00:00 2001
From: "sgjesse@chromium.org"
 <sgjesse@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Mon, 22 Jun 2009 11:12:51 +0000
Subject: [PATCH] Refactor the handling of generations in the compilation
 cache.

Add generations to the compilation cache for eval and regexp. The number of generations for these are set to two.

BUG=none
TEST=none
Review URL: http://codereview.chromium.org/140056

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@2233 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/compilation-cache.cc | 360 ++++++++++++++++++++++++++++-----------
 src/compilation-cache.h  |  17 +-
 src/compiler.cc          |   7 +-
 3 files changed, 266 insertions(+), 118 deletions(-)

diff --git a/src/compilation-cache.cc b/src/compilation-cache.cc
index 421b6766f..fd706af88 100644
--- a/src/compilation-cache.cc
+++ b/src/compilation-cache.cc
@@ -32,28 +32,123 @@
 namespace v8 {
 namespace internal {
 
-enum {
-  // The number of script generations tell how many GCs a script can
-  // survive in the compilation cache, before it will be flushed if it
-  // hasn't been used.
-  NUMBER_OF_SCRIPT_GENERATIONS = 5,
-
-  // The compilation cache consists of tables - one for each entry
-  // kind plus extras for the script generations.
-  NUMBER_OF_TABLE_ENTRIES =
-      CompilationCache::LAST_ENTRY + NUMBER_OF_SCRIPT_GENERATIONS
+
+// The number of sub caches covering the different types to cache.
+static const int kSubCacheCount = 4;
+
+// The number of generations for each sub cache.
+static const int kScriptGenerations = 5;
+static const int kEvalGlobalGenerations = 2;
+static const int kEvalContextualGenerations = 2;
+static const int kRegExpGenerations = 2;
+
+// Initial of each compilation cache table allocated.
+static const int kInitialCacheSize = 64;
+
+// The compilation cache consists of several generational sub-caches which uses
+// this class as a base class. A sub-cache contains a compilation cache tables
+// for each generation of the sub-cache. As the same source code string has
+// different compiled code for scripts and evals. Internally, we use separate
+// sub-caches to avoid getting the wrong kind of result when looking up.
+class CompilationSubCache {
+ public:
+  explicit CompilationSubCache(int generations): generations_(generations) {
+    tables_ = NewArray<Object*>(generations);
+  }
+
+  // Get the compilation cache tables for a specific generation.
+  Handle<CompilationCacheTable> GetTable(int generation);
+
+  // Age the sub-cache by evicting the oldest generation and creating a new
+  // young generation.
+  void Age();
+
+  // GC support.
+  void Iterate(ObjectVisitor* v);
+
+  // Clear this sub-cache evicting all its content.
+  void Clear();
+
+  // Number of generations in this sub-cache.
+  inline int generations() { return generations_; }
+
+ private:
+  int generations_;  // Number of generations.
+  Object** tables_;  // Compilation cache tables - one for each generation.
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(CompilationSubCache);
 };
 
 
+// Sub-cache for scripts.
+class CompilationCacheScript : public CompilationSubCache {
+ public:
+  explicit CompilationCacheScript(int generations)
+      : CompilationSubCache(generations) { }
+
+  Handle<JSFunction> Lookup(Handle<String> source,
+                            Handle<Object> name,
+                            int line_offset,
+                            int column_offset);
+  void Put(Handle<String> source, Handle<JSFunction> boilerplate);
+
+ private:
+  bool HasOrigin(Handle<JSFunction> boilerplate,
+                 Handle<Object> name,
+                 int line_offset,
+                 int column_offset);
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(CompilationCacheScript);
+};
+
+
+// Sub-cache for eval scripts.
+class CompilationCacheEval: public CompilationSubCache {
+ public:
+  explicit CompilationCacheEval(int generations)
+      : CompilationSubCache(generations) { }
+
+  Handle<JSFunction> Lookup(Handle<String> source, Handle<Context> context);
+
+  void Put(Handle<String> source,
+           Handle<Context> context,
+           Handle<JSFunction> boilerplate);
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(CompilationCacheEval);
+};
+
+
+// Sub-cache for regular expressions.
+class CompilationCacheRegExp: public CompilationSubCache {
+ public:
+  explicit CompilationCacheRegExp(int generations)
+      : CompilationSubCache(generations) { }
+
+  Handle<FixedArray> Lookup(Handle<String> source, JSRegExp::Flags flags);
+
+  void Put(Handle<String> source,
+           JSRegExp::Flags flags,
+           Handle<FixedArray> data);
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(CompilationCacheRegExp);
+};
+
+
+// Statically allocate all the sub-caches.
+static CompilationCacheScript script(kScriptGenerations);
+static CompilationCacheEval eval_global(kEvalGlobalGenerations);
+static CompilationCacheEval eval_contextual(kEvalContextualGenerations);
+static CompilationCacheRegExp reg_exp(kRegExpGenerations);
+static CompilationSubCache* subcaches[kSubCacheCount] =
+    {&script, &eval_global, &eval_contextual, &reg_exp};
+
+
 // Current enable state of the compilation cache.
 static bool enabled = true;
 static inline bool IsEnabled() {
   return FLAG_compilation_cache && enabled;
 }
 
-// Keep separate tables for the different entry kinds.
-static Object* tables[NUMBER_OF_TABLE_ENTRIES] = { 0, };
-
 
 static Handle<CompilationCacheTable> AllocateTable(int size) {
   CALL_HEAP_FUNCTION(CompilationCacheTable::Allocate(size),
@@ -61,54 +156,40 @@ static Handle<CompilationCacheTable> AllocateTable(int size) {
 }
 
 
-static Handle<CompilationCacheTable> GetTable(int index) {
-  ASSERT(index >= 0 && index < NUMBER_OF_TABLE_ENTRIES);
+Handle<CompilationCacheTable> CompilationSubCache::GetTable(int generation) {
+  ASSERT(generation < generations_);
   Handle<CompilationCacheTable> result;
-  if (tables[index]->IsUndefined()) {
-    static const int kInitialCacheSize = 64;
+  if (tables_[generation]->IsUndefined()) {
     result = AllocateTable(kInitialCacheSize);
-    tables[index] = *result;
+    tables_[generation] = *result;
   } else {
-    CompilationCacheTable* table = CompilationCacheTable::cast(tables[index]);
+    CompilationCacheTable* table =
+        CompilationCacheTable::cast(tables_[generation]);
     result = Handle<CompilationCacheTable>(table);
   }
   return result;
 }
 
 
-static Handle<JSFunction> Lookup(Handle<String> source,
-                                 Handle<Context> context,
-                                 CompilationCache::Entry entry) {
-  // Make sure not to leak the table into the surrounding handle
-  // scope. Otherwise, we risk keeping old tables around even after
-  // having cleared the cache.
-  Object* result;
-  { HandleScope scope;
-    Handle<CompilationCacheTable> table = GetTable(entry);
-    result = table->LookupEval(*source, *context);
-  }
-  if (result->IsJSFunction()) {
-    return Handle<JSFunction>(JSFunction::cast(result));
-  } else {
-    return Handle<JSFunction>::null();
+void CompilationSubCache::Age() {
+  // Age the generations implicitly killing off the oldest.
+  for (int i = generations_ - 1; i > 0; i--) {
+    tables_[i] = tables_[i - 1];
   }
+
+  // Set the first generation as unborn.
+  tables_[0] = Heap::undefined_value();
 }
 
 
-static Handle<FixedArray> Lookup(Handle<String> source,
-                                 JSRegExp::Flags flags) {
-  // Make sure not to leak the table into the surrounding handle
-  // scope. Otherwise, we risk keeping old tables around even after
-  // having cleared the cache.
-  Object* result;
-  { HandleScope scope;
-    Handle<CompilationCacheTable> table = GetTable(CompilationCache::REGEXP);
-    result = table->LookupRegExp(*source, flags);
-  }
-  if (result->IsFixedArray()) {
-    return Handle<FixedArray>(FixedArray::cast(result));
-  } else {
-    return Handle<FixedArray>::null();
+void CompilationSubCache::Iterate(ObjectVisitor* v) {
+  v->VisitPointers(&tables_[0], &tables_[generations_]);
+}
+
+
+void CompilationSubCache::Clear() {
+  for (int i = 0; i < generations_; i++) {
+    tables_[i] = Heap::undefined_value();
   }
 }
 
@@ -116,10 +197,10 @@ static Handle<FixedArray> Lookup(Handle<String> source,
 // We only re-use a cached function for some script source code if the
 // script originates from the same place. This is to avoid issues
 // when reporting errors, etc.
-static bool HasOrigin(Handle<JSFunction> boilerplate,
-                      Handle<Object> name,
-                      int line_offset,
-                      int column_offset) {
+bool CompilationCacheScript::HasOrigin(Handle<JSFunction> boilerplate,
+                                       Handle<Object> name,
+                                       int line_offset,
+                                       int column_offset) {
   Handle<Script> script =
       Handle<Script>(Script::cast(boilerplate->shared()->script()));
   // If the script name isn't set, the boilerplate script should have
@@ -141,24 +222,17 @@ static bool HasOrigin(Handle<JSFunction> boilerplate,
 // be cached in the same script generation. Currently the first use
 // will be cached, but subsequent code from different source / line
 // won't.
-Handle<JSFunction> CompilationCache::LookupScript(Handle<String> source,
+Handle<JSFunction> CompilationCacheScript::Lookup(Handle<String> source,
                                                   Handle<Object> name,
                                                   int line_offset,
                                                   int column_offset) {
-  if (!IsEnabled()) {
-    return Handle<JSFunction>::null();
-  }
-
-  // Use an int for the generation index, so value range propagation
-  // in gcc 4.3+ won't assume it can only go up to LAST_ENTRY when in
-  // fact it can go up to SCRIPT + NUMBER_OF_SCRIPT_GENERATIONS.
-  int generation = SCRIPT;
   Object* result = NULL;
+  int generation;
 
   // Probe the script generation tables. Make sure not to leak handles
   // into the caller's handle scope.
   { HandleScope scope;
-    while (generation < SCRIPT + NUMBER_OF_SCRIPT_GENERATIONS) {
+    for (generation = 0; generation < generations(); generation++) {
       Handle<CompilationCacheTable> table = GetTable(generation);
       Handle<Object> probe(table->Lookup(*source));
       if (probe->IsJSFunction()) {
@@ -170,20 +244,18 @@ Handle<JSFunction> CompilationCache::LookupScript(Handle<String> source,
           break;
         }
       }
-      // Go to the next generation.
-      generation++;
     }
   }
 
   static void* script_histogram = StatsTable::CreateHistogram(
       "V8.ScriptCache",
       0,
-      NUMBER_OF_SCRIPT_GENERATIONS,
-      NUMBER_OF_SCRIPT_GENERATIONS + 1);
+      kScriptGenerations,
+      kScriptGenerations + 1);
 
   if (script_histogram != NULL) {
     // The level NUMBER_OF_SCRIPT_GENERATIONS is equivalent to a cache miss.
-    StatsTable::AddHistogramSample(script_histogram, generation - SCRIPT);
+    StatsTable::AddHistogramSample(script_histogram, generation);
   }
 
   // Once outside the manacles of the handle scope, we need to recheck
@@ -194,7 +266,7 @@ Handle<JSFunction> CompilationCache::LookupScript(Handle<String> source,
     ASSERT(HasOrigin(boilerplate, name, line_offset, column_offset));
     // If the script was found in a later generation, we promote it to
     // the first generation to let it survive longer in the cache.
-    if (generation != SCRIPT) PutScript(source, boilerplate);
+    if (generation != 0) Put(source, boilerplate);
     Counters::compilation_cache_hits.Increment();
     return boilerplate;
   } else {
@@ -204,19 +276,118 @@ Handle<JSFunction> CompilationCache::LookupScript(Handle<String> source,
 }
 
 
+void CompilationCacheScript::Put(Handle<String> source,
+                                 Handle<JSFunction> boilerplate) {
+  HandleScope scope;
+  ASSERT(boilerplate->IsBoilerplate());
+  Handle<CompilationCacheTable> table = GetTable(0);
+  CALL_HEAP_FUNCTION_VOID(table->Put(*source, *boilerplate));
+}
+
+
+Handle<JSFunction> CompilationCacheEval::Lookup(Handle<String> source,
+                                                Handle<Context> context) {
+  // Make sure not to leak the table into the surrounding handle
+  // scope. Otherwise, we risk keeping old tables around even after
+  // having cleared the cache.
+  Object* result = NULL;
+  int generation;
+  { HandleScope scope;
+    for (generation = 0; generation < generations(); generation++) {
+      Handle<CompilationCacheTable> table = GetTable(generation);
+      result = table->LookupEval(*source, *context);
+      if (result->IsJSFunction()) {
+        break;
+      }
+    }
+  }
+  if (result->IsJSFunction()) {
+    Handle<JSFunction> boilerplate(JSFunction::cast(result));
+    if (generation != 0) {
+      Put(source, context, boilerplate);
+    }
+    Counters::compilation_cache_hits.Increment();
+    return boilerplate;
+  } else {
+    Counters::compilation_cache_misses.Increment();
+    return Handle<JSFunction>::null();
+  }
+}
+
+
+void CompilationCacheEval::Put(Handle<String> source,
+                               Handle<Context> context,
+                               Handle<JSFunction> boilerplate) {
+  HandleScope scope;
+  ASSERT(boilerplate->IsBoilerplate());
+  Handle<CompilationCacheTable> table = GetTable(0);
+  CALL_HEAP_FUNCTION_VOID(table->PutEval(*source, *context, *boilerplate));
+}
+
+
+Handle<FixedArray> CompilationCacheRegExp::Lookup(Handle<String> source,
+                                                  JSRegExp::Flags flags) {
+  // Make sure not to leak the table into the surrounding handle
+  // scope. Otherwise, we risk keeping old tables around even after
+  // having cleared the cache.
+  Object* result = NULL;
+  int generation;
+  { HandleScope scope;
+    for (generation = 0; generation < generations(); generation++) {
+      Handle<CompilationCacheTable> table = GetTable(generation);
+      result = table->LookupRegExp(*source, flags);
+      if (result->IsFixedArray()) {
+        break;
+      }
+    }
+  }
+  if (result->IsFixedArray()) {
+    Handle<FixedArray> data(FixedArray::cast(result));
+    if (generation != 0) {
+      Put(source, flags, data);
+    }
+    Counters::compilation_cache_hits.Increment();
+    return data;
+  } else {
+    Counters::compilation_cache_misses.Increment();
+    return Handle<FixedArray>::null();
+  }
+}
+
+
+void CompilationCacheRegExp::Put(Handle<String> source,
+                                 JSRegExp::Flags flags,
+                                 Handle<FixedArray> data) {
+  HandleScope scope;
+  Handle<CompilationCacheTable> table = GetTable(0);
+  CALL_HEAP_FUNCTION_VOID(table->PutRegExp(*source, flags, *data));
+}
+
+
+Handle<JSFunction> CompilationCache::LookupScript(Handle<String> source,
+                                                  Handle<Object> name,
+                                                  int line_offset,
+                                                  int column_offset) {
+  if (!IsEnabled()) {
+    return Handle<JSFunction>::null();
+  }
+
+  return script.Lookup(source, name, line_offset, column_offset);
+}
+
+
 Handle<JSFunction> CompilationCache::LookupEval(Handle<String> source,
                                                 Handle<Context> context,
-                                                Entry entry) {
+                                                bool is_global) {
   if (!IsEnabled()) {
     return Handle<JSFunction>::null();
   }
 
-  ASSERT(entry == EVAL_GLOBAL || entry == EVAL_CONTEXTUAL);
-  Handle<JSFunction> result = Lookup(source, context, entry);
-  if (result.is_null()) {
-    Counters::compilation_cache_misses.Increment();
+  Handle<JSFunction> result;
+  if (is_global) {
+    result = eval_global.Lookup(source, context);
   } else {
-    Counters::compilation_cache_hits.Increment();
+    result = eval_contextual.Lookup(source, context);
   }
   return result;
 }
@@ -228,13 +399,7 @@ Handle<FixedArray> CompilationCache::LookupRegExp(Handle<String> source,
     return Handle<FixedArray>::null();
   }
 
-  Handle<FixedArray> result = Lookup(source, flags);
-  if (result.is_null()) {
-    Counters::compilation_cache_misses.Increment();
-  } else {
-    Counters::compilation_cache_hits.Increment();
-  }
-  return result;
+  return reg_exp.Lookup(source, flags);
 }
 
 
@@ -244,16 +409,14 @@ void CompilationCache::PutScript(Handle<String> source,
     return;
   }
 
-  HandleScope scope;
   ASSERT(boilerplate->IsBoilerplate());
-  Handle<CompilationCacheTable> table = GetTable(SCRIPT);
-  CALL_HEAP_FUNCTION_VOID(table->Put(*source, *boilerplate));
+  script.Put(source, boilerplate);
 }
 
 
 void CompilationCache::PutEval(Handle<String> source,
                                Handle<Context> context,
-                               Entry entry,
+                               bool is_global,
                                Handle<JSFunction> boilerplate) {
   if (!IsEnabled()) {
     return;
@@ -261,8 +424,11 @@ void CompilationCache::PutEval(Handle<String> source,
 
   HandleScope scope;
   ASSERT(boilerplate->IsBoilerplate());
-  Handle<CompilationCacheTable> table = GetTable(entry);
-  CALL_HEAP_FUNCTION_VOID(table->PutEval(*source, *context, *boilerplate));
+  if (is_global) {
+    eval_global.Put(source, context, boilerplate);
+  } else {
+    eval_contextual.Put(source, context, boilerplate);
+  }
 }
 
 
@@ -274,31 +440,27 @@ void CompilationCache::PutRegExp(Handle<String> source,
     return;
   }
 
-  HandleScope scope;
-  Handle<CompilationCacheTable> table = GetTable(REGEXP);
-  CALL_HEAP_FUNCTION_VOID(table->PutRegExp(*source, flags, *data));
+  reg_exp.Put(source, flags, data);
 }
 
 
 void CompilationCache::Clear() {
-  for (int i = 0; i < NUMBER_OF_TABLE_ENTRIES; i++) {
-    tables[i] = Heap::undefined_value();
+  for (int i = 0; i < kSubCacheCount; i++) {
+    subcaches[i]->Clear();
   }
 }
 
 
 void CompilationCache::Iterate(ObjectVisitor* v) {
-  v->VisitPointers(&tables[0], &tables[NUMBER_OF_TABLE_ENTRIES]);
+  for (int i = 0; i < kSubCacheCount; i++) {
+    subcaches[i]->Iterate(v);
+  }
 }
 
 
 void CompilationCache::MarkCompactPrologue() {
-  ASSERT(LAST_ENTRY == SCRIPT);
-  for (int i = NUMBER_OF_TABLE_ENTRIES - 1; i > SCRIPT; i--) {
-    tables[i] = tables[i - 1];
-  }
-  for (int j = 0; j <= LAST_ENTRY; j++) {
-    tables[j] = Heap::undefined_value();
+  for (int i = 0; i < kSubCacheCount; i++) {
+    subcaches[i]->Age();
   }
 }
 
diff --git a/src/compilation-cache.h b/src/compilation-cache.h
index 4545defc5..3487c08a1 100644
--- a/src/compilation-cache.h
+++ b/src/compilation-cache.h
@@ -34,20 +34,9 @@ namespace internal {
 
 // The compilation cache keeps function boilerplates for compiled
 // scripts and evals. The boilerplates are looked up using the source
-// string as the key.
+// string as the key. For regular expressions the compilation data is cached.
 class CompilationCache {
  public:
-  // The same source code string has different compiled code for
-  // scripts and evals. Internally, we use separate caches to avoid
-  // getting the wrong kind of entry when looking up.
-  enum Entry {
-    EVAL_GLOBAL,
-    EVAL_CONTEXTUAL,
-    REGEXP,
-    SCRIPT,
-    LAST_ENTRY = SCRIPT
-  };
-
   // Finds the script function boilerplate for a source
   // string. Returns an empty handle if the cache doesn't contain a
   // script for the given source string with the right origin.
@@ -61,7 +50,7 @@ class CompilationCache {
   // contain a script for the given source string.
   static Handle<JSFunction> LookupEval(Handle<String> source,
                                        Handle<Context> context,
-                                       Entry entry);
+                                       bool is_global);
 
   // Returns the regexp data associated with the given regexp if it
   // is in cache, otherwise an empty handle.
@@ -77,7 +66,7 @@ class CompilationCache {
   // with the boilerplate. This may overwrite an existing mapping.
   static void PutEval(Handle<String> source,
                       Handle<Context> context,
-                      Entry entry,
+                      bool is_global,
                       Handle<JSFunction> boilerplate);
 
   // Associate the (source, flags) pair to the given regexp data.
diff --git a/src/compiler.cc b/src/compiler.cc
index 8ab126acc..acd5e75bc 100644
--- a/src/compiler.cc
+++ b/src/compiler.cc
@@ -295,14 +295,11 @@ Handle<JSFunction> Compiler::CompileEval(Handle<String> source,
 
   // The VM is in the COMPILER state until exiting this function.
   VMState state(COMPILER);
-  CompilationCache::Entry entry = is_global
-      ? CompilationCache::EVAL_GLOBAL
-      : CompilationCache::EVAL_CONTEXTUAL;
 
   // Do a lookup in the compilation cache; if the entry is not there,
   // invoke the compiler and add the result to the cache.
   Handle<JSFunction> result =
-      CompilationCache::LookupEval(source, context, entry);
+      CompilationCache::LookupEval(source, context, is_global);
   if (result.is_null()) {
     // Create a script object describing the script to be compiled.
     Handle<Script> script = Factory::NewScript(source);
@@ -314,7 +311,7 @@ Handle<JSFunction> Compiler::CompileEval(Handle<String> source,
                           NULL,
                           NULL);
     if (!result.is_null()) {
-      CompilationCache::PutEval(source, context, entry, result);
+      CompilationCache::PutEval(source, context, is_global, result);
     }
   }
 
-- 
2.34.1