text: // Copyright 2011 the V8 project authors. All rights reserved.
  // Redistribution and use in source and binary forms, with or without
  // modification, are permitted provided that the following conditions are
  // met:
  //
  //     * Redistributions of source code must retain the above copyright
  //       notice, this list of conditions and the following disclaimer.
  //     * Redistributions in binary form must reproduce the above
  //       copyright notice, this list of conditions and the following
  //       disclaimer in the documentation and/or other materials provided
  //       with the distribution.
  //     * Neither the name of Google Inc. nor the names of its
  //       contributors may be used to endorse or promote products derived
  //       from this software without specific prior written permission.
  //
  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  
  #include "v8.h"
  
  #include "assembler.h"
  #include "compilation-cache.h"
  #include "serialize.h"
  
  namespace v8 {
  namespace internal {
  
  
  // The number of generations for each sub cache.
  // The number of ScriptGenerations is carefully chosen based on histograms.
  // See issue 458: http://code.google.com/p/v8/issues/detail?id=458
  static const int kScriptGenerations = 5;
  static const int kEvalGlobalGenerations = 2;
  static const int kEvalContextualGenerations = 2;
  static const int kRegExpGenerations = 2;
  
  // Initial size of each compilation cache table allocated.
  static const int kInitialCacheSize = 64;
  
  
  CompilationCache::CompilationCache(Isolate* isolate)
      : isolate_(isolate),
        script_(isolate, kScriptGenerations),
        eval_global_(isolate, kEvalGlobalGenerations),
        eval_contextual_(isolate, kEvalContextualGenerations),
        reg_exp_(isolate, kRegExpGenerations),
        enabled_(true) {
    CompilationSubCache* subcaches[kSubCacheCount] =
      {&script_, &eval_global_, &eval_contextual_, &reg_exp_};
    for (int i = 0; i < kSubCacheCount; ++i) {
      subcaches_[i] = subcaches[i];
    }
  }
  
  
  CompilationCache::~CompilationCache() {}
  
  
  static Handle<CompilationCacheTable> AllocateTable(Isolate* isolate, int size) {
    CALL_HEAP_FUNCTION(isolate,
                       CompilationCacheTable::Allocate(size),
                       CompilationCacheTable);
  }
  
  
  Handle<CompilationCacheTable> CompilationSubCache::GetTable(int generation) {
    ASSERT(generation < generations_);
    Handle<CompilationCacheTable> result;
    if (tables_[generation]->IsUndefined()) {
      result = AllocateTable(isolate(), kInitialCacheSize);
      tables_[generation] = *result;
    } else {
      CompilationCacheTable* table =
          CompilationCacheTable::cast(tables_[generation]);
      result = Handle<CompilationCacheTable>(table, isolate());
    }
    return result;
  }
  
  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] = isolate()->heap()->undefined_value();
  }
  
  
  void CompilationSubCache::IterateFunctions(ObjectVisitor* v) {
    Object* undefined = isolate()->heap()->raw_unchecked_undefined_value();
    for (int i = 0; i < generations_; i++) {
      if (tables_[i] != undefined) {
        reinterpret_cast<CompilationCacheTable*>(tables_[i])->IterateElements(v);
      }
    }
  }
  
  
  void CompilationSubCache::Iterate(ObjectVisitor* v) {
    v->VisitPointers(&tables_[0], &tables_[generations_]);
  }
  
  
  void CompilationSubCache::Clear() {
    MemsetPointer(tables_, isolate()->heap()->undefined_value(), generations_);
  }
  
  
  void CompilationSubCache::Remove(Handle<SharedFunctionInfo> function_info) {
    // Probe the script generation tables. Make sure not to leak handles
    // into the caller's handle scope.
    { HandleScope scope(isolate());
      for (int generation = 0; generation < generations(); generation++) {
        Handle<CompilationCacheTable> table = GetTable(generation);
        table->Remove(*function_info);
      }
    }
  }
  
  
  CompilationCacheScript::CompilationCacheScript(Isolate* isolate,
                                                 int generations)
      : CompilationSubCache(isolate, generations),
        script_histogram_(NULL),
        script_histogram_initialized_(false) { }
  
  
  // 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.
  bool CompilationCacheScript::HasOrigin(
      Handle<SharedFunctionInfo> function_info,
      Handle<Object> name,
      int line_offset,
      int column_offset) {
    Handle<Script> script =
        Handle<Script>(Script::cast(function_info->script()), isolate());
    // If the script name isn't set, the boilerplate script should have
    // an undefined name to have the same origin.
    if (name.is_null()) {
      return script->name()->IsUndefined();
    }
    // Do the fast bailout checks first.
    if (line_offset != script->line_offset()->value()) return false;
    if (column_offset != script->column_offset()->value()) return false;
    // Check that both names are strings. If not, no match.
    if (!name->IsString() || !script->name()->IsString()) return false;
    // Compare the two name strings for equality.
    return String::cast(*name)->Equals(String::cast(script->name()));
  }
  
  
  // TODO(245): Need to allow identical code from different contexts to
  // be cached in the same script generation. Currently the first use
  // will be cached, but subsequent code from different source / line
  // won't.
  Handle<SharedFunctionInfo> CompilationCacheScript::Lookup(Handle<String> source,
                                                            Handle<Object> name,
                                                            int line_offset,
                                                            int column_offset) {
    Object* result = NULL;
    int generation;
  
    // Probe the script generation tables. Make sure not to leak handles
    // into the caller's handle scope.
    { HandleScope scope(isolate());
      for (generation = 0; generation < generations(); generation++) {
        Handle<CompilationCacheTable> table = GetTable(generation);
        Handle<Object> probe(table->Lookup(*source), isolate());
        if (probe->IsSharedFunctionInfo()) {
          Handle<SharedFunctionInfo> function_info =
              Handle<SharedFunctionInfo>::cast(probe);
          // Break when we've found a suitable shared function info that
          // matches the origin.
          if (HasOrigin(function_info, name, line_offset, column_offset)) {
            result = *function_info;
            break;
          }
        }
      }
    }
  
    if (!script_histogram_initialized_) {
      script_histogram_ = isolate()->stats_table()->CreateHistogram(
          "V8.ScriptCache",
          0,
          kScriptGenerations,
          kScriptGenerations + 1);
      script_histogram_initialized_ = true;
    }
  
    if (script_histogram_ != NULL) {
      // The level NUMBER_OF_SCRIPT_GENERATIONS is equivalent to a cache miss.
      isolate()->stats_table()->AddHistogramSample(script_histogram_, generation);
    }
  
    // Once outside the manacles of the handle scope, we need to recheck
    // to see if we actually found a cached script. If so, we return a
    // handle created in the caller's handle scope.
    if (result != NULL) {
      Handle<SharedFunctionInfo> shared(SharedFunctionInfo::cast(result),
                                        isolate());
      ASSERT(HasOrigin(shared, 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 != 0) Put(source, shared);
      isolate()->counters()->compilation_cache_hits()->Increment();
      return shared;
    } else {
      isolate()->counters()->compilation_cache_misses()->Increment();
      return Handle<SharedFunctionInfo>::null();
    }
  }
  
  
  MaybeObject* CompilationCacheScript::TryTablePut(
      Handle<String> source,
      Handle<SharedFunctionInfo> function_info) {
    Handle<CompilationCacheTable> table = GetFirstTable();
    return table->Put(*source, *function_info);
  }
  
  
  Handle<CompilationCacheTable> CompilationCacheScript::TablePut(
      Handle<String> source,
      Handle<SharedFunctionInfo> function_info) {
    CALL_HEAP_FUNCTION(isolate(),
                       TryTablePut(source, function_info),
                       CompilationCacheTable);
  }
  
  
  void CompilationCacheScript::Put(Handle<String> source,
                                   Handle<SharedFunctionInfo> function_info) {
    HandleScope scope(isolate());
    SetFirstTable(TablePut(source, function_info));
  }
  
  
  Handle<SharedFunctionInfo> CompilationCacheEval::Lookup(
      Handle<String> source,
      Handle<Context> context,
      LanguageMode language_mode,
      int scope_position) {
    // 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(isolate());
      for (generation = 0; generation < generations(); generation++) {
        Handle<CompilationCacheTable> table = GetTable(generation);
        result = table->LookupEval(
            *source, *context, language_mode, scope_position);
        if (result->IsSharedFunctionInfo()) {
          break;
        }
      }
    }
    if (result->IsSharedFunctionInfo()) {
      Handle<SharedFunctionInfo>
          function_info(SharedFunctionInfo::cast(result), isolate());
      if (generation != 0) {
        Put(source, context, function_info, scope_position);
      }
      isolate()->counters()->compilation_cache_hits()->Increment();
      return function_info;
    } else {
      isolate()->counters()->compilation_cache_misses()->Increment();
      return Handle<SharedFunctionInfo>::null();
    }
  }
  
  
  MaybeObject* CompilationCacheEval::TryTablePut(
      Handle<String> source,
      Handle<Context> context,
      Handle<SharedFunctionInfo> function_info,
      int scope_position) {
    Handle<CompilationCacheTable> table = GetFirstTable();
    return table->PutEval(*source, *context, *function_info, scope_position);
  }
  
  
  Handle<CompilationCacheTable> CompilationCacheEval::TablePut(
      Handle<String> source,
      Handle<Context> context,
      Handle<SharedFunctionInfo> function_info,
      int scope_position) {
    CALL_HEAP_FUNCTION(isolate(),
                       TryTablePut(
                           source, context, function_info, scope_position),
                       CompilationCacheTable);
  }
  
  
  void CompilationCacheEval::Put(Handle<String> source,
                                 Handle<Context> context,
                                 Handle<SharedFunctionInfo> function_info,
                                 int scope_position) {
    HandleScope scope(isolate());
    SetFirstTable(TablePut(source, context, function_info, scope_position));
  }
  
  
  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(isolate());
      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), isolate());
      if (generation != 0) {
        Put(source, flags, data);
      }
      isolate()->counters()->compilation_cache_hits()->Increment();
      return data;
    } else {
      isolate()->counters()->compilation_cache_misses()->Increment();
      return Handle<FixedArray>::null();
    }
  }
  
  
  MaybeObject* CompilationCacheRegExp::TryTablePut(
      Handle<String> source,
      JSRegExp::Flags flags,
      Handle<FixedArray> data) {
    Handle<CompilationCacheTable> table = GetFirstTable();
    return table->PutRegExp(*source, flags, *data);
  }
  
  
  Handle<CompilationCacheTable> CompilationCacheRegExp::TablePut(
      Handle<String> source,
      JSRegExp::Flags flags,
      Handle<FixedArray> data) {
    CALL_HEAP_FUNCTION(isolate(),
                       TryTablePut(source, flags, data),
                       CompilationCacheTable);
  }
  
  
  void CompilationCacheRegExp::Put(Handle<String> source,
                                   JSRegExp::Flags flags,
                                   Handle<FixedArray> data) {
    HandleScope scope(isolate());
    SetFirstTable(TablePut(source, flags, data));
  }
  
  
  void CompilationCache::Remove(Handle<SharedFunctionInfo> function_info) {
    if (!IsEnabled()) return;
  
    eval_global_.Remove(function_info);
    eval_contextual_.Remove(function_info);
    script_.Remove(function_info);
  }
  
  
  Handle<SharedFunctionInfo> CompilationCache::LookupScript(Handle<String> source,
                                                            Handle<Object> name,
                                                            int line_offset,
                                                            int column_offset) {
    if (!IsEnabled()) {
      return Handle<SharedFunctionInfo>::null();
    }
  
    return script_.Lookup(source, name, line_offset, column_offset);
  }
  
  
  Handle<SharedFunctionInfo> CompilationCache::LookupEval(
      Handle<String> source,
      Handle<Context> context,
      bool is_global,
      LanguageMode language_mode,
      int scope_position) {
    if (!IsEnabled()) {
      return Handle<SharedFunctionInfo>::null();
    }
  
    Handle<SharedFunctionInfo> result;
    if (is_global) {
      result = eval_global_.Lookup(
          source, context, language_mode, scope_position);
    } else {
      ASSERT(scope_position != RelocInfo::kNoPosition);
      result = eval_contextual_.Lookup(
          source, context, language_mode, scope_position);
    }
    return result;
  }
  
  
  Handle<FixedArray> CompilationCache::LookupRegExp(Handle<String> source,
                                                    JSRegExp::Flags flags) {
    if (!IsEnabled()) {
      return Handle<FixedArray>::null();
    }
  
    return reg_exp_.Lookup(source, flags);
  }
  
  
  void CompilationCache::PutScript(Handle<String> source,
                                   Handle<SharedFunctionInfo> function_info) {
    if (!IsEnabled()) {
      return;
    }
  
    script_.Put(source, function_info);
  }
  
  
  void CompilationCache::PutEval(Handle<String> source,
                                 Handle<Context> context,
                                 bool is_global,
                                 Handle<SharedFunctionInfo> function_info,
                                 int scope_position) {
    if (!IsEnabled()) {
      return;
    }
  
    HandleScope scope(isolate());
    if (is_global) {
      eval_global_.Put(source, context, function_info, scope_position);
    } else {
      ASSERT(scope_position != RelocInfo::kNoPosition);
      eval_contextual_.Put(source, context, function_info, scope_position);
    }
  }
  
  
  
  void CompilationCache::PutRegExp(Handle<String> source,
                                   JSRegExp::Flags flags,
                                   Handle<FixedArray> data) {
    if (!IsEnabled()) {
      return;
    }
  
    reg_exp_.Put(source, flags, data);
  }
  
  
  void CompilationCache::Clear() {
    for (int i = 0; i < kSubCacheCount; i++) {
      subcaches_[i]->Clear();
    }
  }
  
  
  void CompilationCache::Iterate(ObjectVisitor* v) {
    for (int i = 0; i < kSubCacheCount; i++) {
      subcaches_[i]->Iterate(v);
    }
  }
  
  
  void CompilationCache::IterateFunctions(ObjectVisitor* v) {
    for (int i = 0; i < kSubCacheCount; i++) {
      subcaches_[i]->IterateFunctions(v);
    }
  }
  
  
  void CompilationCache::MarkCompactPrologue() {
    for (int i = 0; i < kSubCacheCount; i++) {
      subcaches_[i]->Age();
    }
  }
  
  
  void CompilationCache::Enable() {
    enabled_ = true;
  }
  
  
  void CompilationCache::Disable() {
    enabled_ = false;
    Clear();
  }
  
  
  } }  // namespace v8::internal
  