CSE2410 Fall 2014 Bounce

// Copyright 2013 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 "accessors.h"

#include "codegen.h"

#include "deoptimizer.h"

#include "disasm.h"

#include "full-codegen.h"

#include "global-handles.h"

#include "macro-assembler.h"

#include "prettyprinter.h"

namespace v8 {

namespace internal {

static MemoryChunk* AllocateCodeChunk(MemoryAllocator* allocator) {

  return allocator->AllocateChunk(Deoptimizer::GetMaxDeoptTableSize(),

                                  OS::CommitPageSize(),

#if defined(__native_client__)

  // The Native Client port of V8 uses an interpreter,

  // so code pages don't need PROT_EXEC.

                                  NOT_EXECUTABLE,

#else

                                  EXECUTABLE,

#endif

                                  NULL);

}

DeoptimizerData::DeoptimizerData(MemoryAllocator* allocator)

    : allocator_(allocator),

#ifdef ENABLE_DEBUGGER_SUPPORT

      deoptimized_frame_info_(NULL),

#endif

      current_(NULL) {

  for (int i = 0; i < Deoptimizer::kBailoutTypesWithCodeEntry; ++i) {

    deopt_entry_code_entries_[i] = -1;

    deopt_entry_code_[i] = AllocateCodeChunk(allocator);

  }

}

DeoptimizerData::~DeoptimizerData() {

  for (int i = 0; i < Deoptimizer::kBailoutTypesWithCodeEntry; ++i) {

    allocator_->Free(deopt_entry_code_[i]);

    deopt_entry_code_[i] = NULL;

  }

}

#ifdef ENABLE_DEBUGGER_SUPPORT

void DeoptimizerData::Iterate(ObjectVisitor* v) {

  if (deoptimized_frame_info_ != NULL) {

    deoptimized_frame_info_->Iterate(v);

  }

}

#endif

Code* Deoptimizer::FindDeoptimizingCode(Address addr) {

  if (function_->IsHeapObject()) {

    // Search all deoptimizing code in the native context of the function.

    Context* native_context = function_->context()->native_context();

    Object* element = native_context->DeoptimizedCodeListHead();

    while (!element->IsUndefined()) {

      Code* code = Code::cast(element);

      ASSERT(code->kind() == Code::OPTIMIZED_FUNCTION);

      if (code->contains(addr)) return code;

      element = code->next_code_link();

    }

  }

  return NULL;

}

// We rely on this function not causing a GC.  It is called from generated code

// without having a real stack frame in place.

Deoptimizer* Deoptimizer::New(JSFunction* function,

                              BailoutType type,

                              unsigned bailout_id,

                              Address from,

                              int fp_to_sp_delta,

                              Isolate* isolate) {

  Deoptimizer* deoptimizer = new Deoptimizer(isolate,

                                             function,

                                             type,

                                             bailout_id,

                                             from,

                                             fp_to_sp_delta,

                                             NULL);

  ASSERT(isolate->deoptimizer_data()->current_ == NULL);

  isolate->deoptimizer_data()->current_ = deoptimizer;

  return deoptimizer;

}

// No larger than 2K on all platforms

static const int kDeoptTableMaxEpilogueCodeSize = 2 * KB;

size_t Deoptimizer::GetMaxDeoptTableSize() {

  int entries_size =

      Deoptimizer::kMaxNumberOfEntries * Deoptimizer::table_entry_size_;

  int commit_page_size = static_cast<int>(OS::CommitPageSize());

  int page_count = ((kDeoptTableMaxEpilogueCodeSize + entries_size - 1) /

                    commit_page_size) + 1;

  return static_cast<size_t>(commit_page_size * page_count);

}

Deoptimizer* Deoptimizer::Grab(Isolate* isolate) {

  Deoptimizer* result = isolate->deoptimizer_data()->current_;

  ASSERT(result != NULL);

  result->DeleteFrameDescriptions();

  isolate->deoptimizer_data()->current_ = NULL;

  return result;

}

int Deoptimizer::ConvertJSFrameIndexToFrameIndex(int jsframe_index) {

  if (jsframe_index == 0) return 0;

  int frame_index = 0;

  while (jsframe_index >= 0) {

    FrameDescription* frame = output_[frame_index];

    if (frame->GetFrameType() == StackFrame::JAVA_SCRIPT) {

      jsframe_index--;

    }

    frame_index++;

  }

  return frame_index - 1;

}

#ifdef ENABLE_DEBUGGER_SUPPORT

DeoptimizedFrameInfo* Deoptimizer::DebuggerInspectableFrame(

    JavaScriptFrame* frame,

    int jsframe_index,

    Isolate* isolate) {

  ASSERT(frame->is_optimized());

  ASSERT(isolate->deoptimizer_data()->deoptimized_frame_info_ == NULL);

  // Get the function and code from the frame.

  JSFunction* function = frame->function();

  Code* code = frame->LookupCode();

  // Locate the deoptimization point in the code. As we are at a call the

  // return address must be at a place in the code with deoptimization support.

  SafepointEntry safepoint_entry = code->GetSafepointEntry(frame->pc());

  int deoptimization_index = safepoint_entry.deoptimization_index();

  ASSERT(deoptimization_index != Safepoint::kNoDeoptimizationIndex);

  // Always use the actual stack slots when calculating the fp to sp

  // delta adding two for the function and context.

  unsigned stack_slots = code->stack_slots();

  unsigned fp_to_sp_delta = ((stack_slots + 2) * kPointerSize);

  Deoptimizer* deoptimizer = new Deoptimizer(isolate,

                                             function,

                                             Deoptimizer::DEBUGGER,

                                             deoptimization_index,

                                             frame->pc(),

                                             fp_to_sp_delta,

                                             code);

  Address tos = frame->fp() - fp_to_sp_delta;

  deoptimizer->FillInputFrame(tos, frame);

  // Calculate the output frames.

  Deoptimizer::ComputeOutputFrames(deoptimizer);

  // Create the GC safe output frame information and register it for GC

  // handling.

  ASSERT_LT(jsframe_index, deoptimizer->jsframe_count());

  // Convert JS frame index into frame index.

  int frame_index = deoptimizer->ConvertJSFrameIndexToFrameIndex(jsframe_index);

  bool has_arguments_adaptor =

      frame_index > 0 &&

      deoptimizer->output_[frame_index - 1]->GetFrameType() ==

      StackFrame::ARGUMENTS_ADAPTOR;

  int construct_offset = has_arguments_adaptor ? 2 : 1;

  bool has_construct_stub =

      frame_index >= construct_offset &&

      deoptimizer->output_[frame_index - construct_offset]->GetFrameType() ==

      StackFrame::CONSTRUCT;

  DeoptimizedFrameInfo* info = new DeoptimizedFrameInfo(deoptimizer,

                                                        frame_index,

                                                        has_arguments_adaptor,

                                                        has_construct_stub);

  isolate->deoptimizer_data()->deoptimized_frame_info_ = info;

  // Get the "simulated" top and size for the requested frame.

  FrameDescription* parameters_frame =

      deoptimizer->output_[

          has_arguments_adaptor ? (frame_index - 1) : frame_index];

  uint32_t parameters_size = (info->parameters_count() + 1) * kPointerSize;

  Address parameters_top = reinterpret_cast<Address>(

      parameters_frame->GetTop() + (parameters_frame->GetFrameSize() -

                                    parameters_size));

  uint32_t expressions_size = info->expression_count() * kPointerSize;

  Address expressions_top = reinterpret_cast<Address>(

      deoptimizer->output_[frame_index]->GetTop());

  // Done with the GC-unsafe frame descriptions. This re-enables allocation.

  deoptimizer->DeleteFrameDescriptions();

  // Allocate a heap number for the doubles belonging to this frame.

  deoptimizer->MaterializeHeapNumbersForDebuggerInspectableFrame(

      parameters_top, parameters_size, expressions_top, expressions_size, info);

  // Finished using the deoptimizer instance.

  delete deoptimizer;

  return info;

}

void Deoptimizer::DeleteDebuggerInspectableFrame(DeoptimizedFrameInfo* info,

                                                 Isolate* isolate) {

  ASSERT(isolate->deoptimizer_data()->deoptimized_frame_info_ == info);

  delete info;

  isolate->deoptimizer_data()->deoptimized_frame_info_ = NULL;

}

#endif

void Deoptimizer::GenerateDeoptimizationEntries(MacroAssembler* masm,

                                                int count,

                                                BailoutType type) {

  TableEntryGenerator generator(masm, type, count);

  generator.Generate();

}

void Deoptimizer::VisitAllOptimizedFunctionsForContext(

    Context* context, OptimizedFunctionVisitor* visitor) {

  DisallowHeapAllocation no_allocation;

  ASSERT(context->IsNativeContext());

  visitor->EnterContext(context);

  // Visit the list of optimized functions, removing elements that

  // no longer refer to optimized code.

  JSFunction* prev = NULL;

  Object* element = context->OptimizedFunctionsListHead();

  while (!element->IsUndefined()) {

    JSFunction* function = JSFunction::cast(element);

    Object* next = function->next_function_link();

    if (function->code()->kind() != Code::OPTIMIZED_FUNCTION ||

        (visitor->VisitFunction(function),

         function->code()->kind() != Code::OPTIMIZED_FUNCTION)) {

      // The function no longer refers to optimized code, or the visitor

      // changed the code to which it refers to no longer be optimized code.

      // Remove the function from this list.

      if (prev != NULL) {

        prev->set_next_function_link(next);

      } else {

        context->SetOptimizedFunctionsListHead(next);

      }

      // The visitor should not alter the link directly.

      ASSERT(function->next_function_link() == next);

      // Set the next function link to undefined to indicate it is no longer

      // in the optimized functions list.

      function->set_next_function_link(context->GetHeap()->undefined_value());

    } else {

      // The visitor should not alter the link directly.

      ASSERT(function->next_function_link() == next);

      // preserve this element.

      prev = function;

    }

    element = next;

  }

  visitor->LeaveContext(context);

}

void Deoptimizer::VisitAllOptimizedFunctions(

    Isolate* isolate,

    OptimizedFunctionVisitor* visitor) {

  DisallowHeapAllocation no_allocation;

  // Run through the list of all native contexts.

  Object* context = isolate->heap()->native_contexts_list();

  while (!context->IsUndefined()) {

    VisitAllOptimizedFunctionsForContext(Context::cast(context), visitor);

    context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);

  }

}

// Unlink functions referring to code marked for deoptimization, then move

// marked code from the optimized code list to the deoptimized code list,

// and patch code for lazy deopt.

void Deoptimizer::DeoptimizeMarkedCodeForContext(Context* context) {

  DisallowHeapAllocation no_allocation;

  // A "closure" that unlinks optimized code that is going to be

  // deoptimized from the functions that refer to it.

  class SelectedCodeUnlinker: public OptimizedFunctionVisitor {

   public:

    virtual void EnterContext(Context* context) { }  // Don't care.

    virtual void LeaveContext(Context* context)  { }  // Don't care.

    virtual void VisitFunction(JSFunction* function) {

      Code* code = function->code();

      if (!code->marked_for_deoptimization()) return;

      // Unlink this function and evict from optimized code map.

      SharedFunctionInfo* shared = function->shared();

      function->set_code(shared->code());

      shared->EvictFromOptimizedCodeMap(code, "deoptimized function");

      if (FLAG_trace_deopt) {

        PrintF("[deoptimizer unlinked: ");

        function->PrintName();

        PrintF(" / %" V8PRIxPTR "]\n", reinterpret_cast<intptr_t>(function));

      }

    }

  };

  // Unlink all functions that refer to marked code.

  SelectedCodeUnlinker unlinker;

  VisitAllOptimizedFunctionsForContext(context, &unlinker);

  // Move marked code from the optimized code list to the deoptimized

  // code list, collecting them into a ZoneList.

  Isolate* isolate = context->GetHeap()->isolate();

  Zone zone(isolate);

  ZoneList<Code*> codes(10, &zone);

  // Walk over all optimized code objects in this native context.

  Code* prev = NULL;

  Object* element = context->OptimizedCodeListHead();

  while (!element->IsUndefined()) {

    Code* code = Code::cast(element);

    ASSERT(code->kind() == Code::OPTIMIZED_FUNCTION);

    Object* next = code->next_code_link();

    if (code->marked_for_deoptimization()) {

      // Put the code into the list for later patching.

      codes.Add(code, &zone);

      if (prev != NULL) {

        // Skip this code in the optimized code list.

        prev->set_next_code_link(next);

      } else {

        // There was no previous node, the next node is the new head.

        context->SetOptimizedCodeListHead(next);

      }

      // Move the code to the _deoptimized_ code list.

      code->set_next_code_link(context->DeoptimizedCodeListHead());

      context->SetDeoptimizedCodeListHead(code);

    } else {

      // Not marked; preserve this element.

      prev = code;

    }

    element = next;

  }

  // TODO(titzer): we need a handle scope only because of the macro assembler,

  // which is only used in EnsureCodeForDeoptimizationEntry.

  HandleScope scope(isolate);

  // Now patch all the codes for deoptimization.

  for (int i = 0; i < codes.length(); i++) {

    // It is finally time to die, code object.

    // Do platform-specific patching to force any activations to lazy deopt.

    PatchCodeForDeoptimization(isolate, codes[i]);

    // We might be in the middle of incremental marking with compaction.

    // Tell collector to treat this code object in a special way and

    // ignore all slots that might have been recorded on it.

    isolate->heap()->mark_compact_collector()->InvalidateCode(codes[i]);

  }

}

void Deoptimizer::DeoptimizeAll(Isolate* isolate) {

  if (FLAG_trace_deopt) {

    PrintF("[deoptimize all code in all contexts]\n");

  }

  DisallowHeapAllocation no_allocation;

  // For all contexts, mark all code, then deoptimize.

  Object* context = isolate->heap()->native_contexts_list();

  while (!context->IsUndefined()) {

    Context* native_context = Context::cast(context);

    MarkAllCodeForContext(native_context);

    DeoptimizeMarkedCodeForContext(native_context);

    context = native_context->get(Context::NEXT_CONTEXT_LINK);

  }

}

void Deoptimizer::DeoptimizeMarkedCode(Isolate* isolate) {

  if (FLAG_trace_deopt) {

    PrintF("[deoptimize marked code in all contexts]\n");

  }

  DisallowHeapAllocation no_allocation;

  // For all contexts, deoptimize code already marked.

  Object* context = isolate->heap()->native_contexts_list();

  while (!context->IsUndefined()) {

    Context* native_context = Context::cast(context);

    DeoptimizeMarkedCodeForContext(native_context);

    context = native_context->get(Context::NEXT_CONTEXT_LINK);

  }

}

void Deoptimizer::DeoptimizeGlobalObject(JSObject* object) {

  if (FLAG_trace_deopt) {

    PrintF("[deoptimize global object @ 0x%08" V8PRIxPTR "]\n",

        reinterpret_cast<intptr_t>(object));

  }

  if (object->IsJSGlobalProxy()) {

    Object* proto = object->GetPrototype();

    ASSERT(proto->IsJSGlobalObject());

    Context* native_context = GlobalObject::cast(proto)->native_context();

    MarkAllCodeForContext(native_context);

    DeoptimizeMarkedCodeForContext(native_context);

  } else if (object->IsGlobalObject()) {

    Context* native_context = GlobalObject::cast(object)->native_context();

    MarkAllCodeForContext(native_context);

    DeoptimizeMarkedCodeForContext(native_context);

  }

}

void Deoptimizer::MarkAllCodeForContext(Context* context) {

  Object* element = context->OptimizedCodeListHead();

  while (!element->IsUndefined()) {

    Code* code = Code::cast(element);

    ASSERT(code->kind() == Code::OPTIMIZED_FUNCTION);

    code->set_marked_for_deoptimization(true);

    element = code->next_code_link();

  }

}

void Deoptimizer::DeoptimizeFunction(JSFunction* function) {

  Code* code = function->code();

  if (code->kind() == Code::OPTIMIZED_FUNCTION) {

    // Mark the code for deoptimization and unlink any functions that also

    // refer to that code. The code cannot be shared across native contexts,

    // so we only need to search one.

    code->set_marked_for_deoptimization(true);

    DeoptimizeMarkedCodeForContext(function->context()->native_context());

  }

}

void Deoptimizer::ComputeOutputFrames(Deoptimizer* deoptimizer) {

  deoptimizer->DoComputeOutputFrames();

}

bool Deoptimizer::TraceEnabledFor(BailoutType deopt_type,

                                  StackFrame::Type frame_type) {

  switch (deopt_type) {

    case EAGER:

    case SOFT:

    case LAZY:

    case DEBUGGER:

      return (frame_type == StackFrame::STUB)

          ? FLAG_trace_stub_failures

          : FLAG_trace_deopt;

  }

  UNREACHABLE();

  return false;

}

const char* Deoptimizer::MessageFor(BailoutType type) {

  switch (type) {

    case EAGER: return "eager";

    case SOFT: return "soft";

    case LAZY: return "lazy";

    case DEBUGGER: return "debugger";

  }

  UNREACHABLE();

  return NULL;

}

Deoptimizer::Deoptimizer(Isolate* isolate,

                         JSFunction* function,

                         BailoutType type,

                         unsigned bailout_id,

                         Address from,

                         int fp_to_sp_delta,

                         Code* optimized_code)

    : isolate_(isolate),

      function_(function),

      bailout_id_(bailout_id),

      bailout_type_(type),

      from_(from),

      fp_to_sp_delta_(fp_to_sp_delta),

      has_alignment_padding_(0),

      input_(NULL),

      output_count_(0),

      jsframe_count_(0),

      output_(NULL),

      deferred_objects_tagged_values_(0),

      deferred_objects_double_values_(0),

      deferred_objects_(0),

      deferred_heap_numbers_(0),

      jsframe_functions_(0),

      jsframe_has_adapted_arguments_(0),

      materialized_values_(NULL),

      materialized_objects_(NULL),

      materialization_value_index_(0),

      materialization_object_index_(0),

      trace_(false) {

  // For COMPILED_STUBs called from builtins, the function pointer is a SMI

  // indicating an internal frame.

  if (function->IsSmi()) {

    function = NULL;

  }

  ASSERT(from != NULL);

  if (function != NULL && function->IsOptimized()) {

    function->shared()->increment_deopt_count();

    if (bailout_type_ == Deoptimizer::SOFT) {

      isolate->counters()->soft_deopts_executed()->Increment();

      // Soft deopts shouldn't count against the overall re-optimization count

      // that can eventually lead to disabling optimization for a function.

      int opt_count = function->shared()->opt_count();

      if (opt_count > 0) opt_count--;

      function->shared()->set_opt_count(opt_count);

    }

  }

  compiled_code_ = FindOptimizedCode(function, optimized_code);

#if DEBUG

  ASSERT(compiled_code_ != NULL);

  if (type == EAGER || type == SOFT || type == LAZY) {

    ASSERT(compiled_code_->kind() != Code::FUNCTION);

  }

#endif

  StackFrame::Type frame_type = function == NULL

      ? StackFrame::STUB

      : StackFrame::JAVA_SCRIPT;

  trace_ = TraceEnabledFor(type, frame_type);

#ifdef DEBUG

  CHECK(AllowHeapAllocation::IsAllowed());

  disallow_heap_allocation_ = new DisallowHeapAllocation();

#endif  // DEBUG

  unsigned size = ComputeInputFrameSize();

  input_ = new(size) FrameDescription(size, function);

  input_->SetFrameType(frame_type);

}

Code* Deoptimizer::FindOptimizedCode(JSFunction* function,

                                     Code* optimized_code) {

  switch (bailout_type_) {

    case Deoptimizer::SOFT:

    case Deoptimizer::EAGER:

    case Deoptimizer::LAZY: {

      Code* compiled_code = FindDeoptimizingCode(from_);

      return (compiled_code == NULL)

          ? static_cast<Code*>(isolate_->FindCodeObject(from_))

          : compiled_code;

    }

    case Deoptimizer::DEBUGGER:

      ASSERT(optimized_code->contains(from_));

      return optimized_code;

  }

  UNREACHABLE();

  return NULL;

}

void Deoptimizer::PrintFunctionName() {

  if (function_->IsJSFunction()) {

    function_->PrintName();

  } else {

    PrintF("%s", Code::Kind2String(compiled_code_->kind()));

  }

}

Deoptimizer::~Deoptimizer() {

  ASSERT(input_ == NULL && output_ == NULL);

  ASSERT(disallow_heap_allocation_ == NULL);

}

void Deoptimizer::DeleteFrameDescriptions() {

  delete input_;

  for (int i = 0; i < output_count_; ++i) {

    if (output_[i] != input_) delete output_[i];

  }

  delete[] output_;

  input_ = NULL;

  output_ = NULL;

#ifdef DEBUG

  CHECK(!AllowHeapAllocation::IsAllowed());

  CHECK(disallow_heap_allocation_ != NULL);

  delete disallow_heap_allocation_;

  disallow_heap_allocation_ = NULL;

#endif  // DEBUG

}

Address Deoptimizer::GetDeoptimizationEntry(Isolate* isolate,

                                            int id,

                                            BailoutType type,

                                            GetEntryMode mode) {

  ASSERT(id >= 0);

  if (id >= kMaxNumberOfEntries) return NULL;

  if (mode == ENSURE_ENTRY_CODE) {

    EnsureCodeForDeoptimizationEntry(isolate, type, id);

  } else {

    ASSERT(mode == CALCULATE_ENTRY_ADDRESS);

  }

  DeoptimizerData* data = isolate->deoptimizer_data();

  ASSERT(type < kBailoutTypesWithCodeEntry);

  MemoryChunk* base = data->deopt_entry_code_[type];

  return base->area_start() + (id * table_entry_size_);

}

int Deoptimizer::GetDeoptimizationId(Isolate* isolate,

                                     Address addr,

                                     BailoutType type) {

  DeoptimizerData* data = isolate->deoptimizer_data();

  MemoryChunk* base = data->deopt_entry_code_[type];

  Address start = base->area_start();

  if (base == NULL ||

      addr < start ||

      addr >= start + (kMaxNumberOfEntries * table_entry_size_)) {

    return kNotDeoptimizationEntry;

  }

  ASSERT_EQ(0,

            static_cast<int>(addr - start) % table_entry_size_);

  return static_cast<int>(addr - start) / table_entry_size_;

}

int Deoptimizer::GetOutputInfo(DeoptimizationOutputData* data,

                               BailoutId id,

                               SharedFunctionInfo* shared) {

  // TODO(kasperl): For now, we do a simple linear search for the PC

  // offset associated with the given node id. This should probably be

  // changed to a binary search.

  int length = data->DeoptPoints();

  for (int i = 0; i < length; i++) {

    if (data->AstId(i) == id) {

      return data->PcAndState(i)->value();

    }

  }

  PrintF("[couldn't find pc offset for node=%d]\n", id.ToInt());

  PrintF("[method: %s]\n", *shared->DebugName()->ToCString());

  // Print the source code if available.

  HeapStringAllocator string_allocator;

  StringStream stream(&string_allocator);

  shared->SourceCodePrint(&stream, -1);

  PrintF("[source:\n%s\n]", *stream.ToCString());

  FATAL("unable to find pc offset during deoptimization");

  return -1;

}

int Deoptimizer::GetDeoptimizedCodeCount(Isolate* isolate) {

  int length = 0;

  // Count all entries in the deoptimizing code list of every context.

  Object* context = isolate->heap()->native_contexts_list();

  while (!context->IsUndefined()) {

    Context* native_context = Context::cast(context);

    Object* element = native_context->DeoptimizedCodeListHead();

    while (!element->IsUndefined()) {

      Code* code = Code::cast(element);

      ASSERT(code->kind() == Code::OPTIMIZED_FUNCTION);

      length++;

      element = code->next_code_link();

    }

    context = Context::cast(context)->get(Context::NEXT_CONTEXT_LINK);

  }

  return length;

}

// We rely on this function not causing a GC.  It is called from generated code

// without having a real stack frame in place.

void Deoptimizer::DoComputeOutputFrames() {

  // Print some helpful diagnostic information.

  if (FLAG_log_timer_events &&

      compiled_code_->kind() == Code::OPTIMIZED_FUNCTION) {

    LOG(isolate(), CodeDeoptEvent(compiled_code_));

  }

  ElapsedTimer timer;

  if (trace_) {

    timer.Start();

    PrintF("[deoptimizing (DEOPT %s): begin 0x%08" V8PRIxPTR " ",

           MessageFor(bailout_type_),

           reinterpret_cast<intptr_t>(function_));

    PrintFunctionName();

    PrintF(" @%d, FP to SP delta: %d]\n", bailout_id_, fp_to_sp_delta_);

    if (bailout_type_ == EAGER || bailout_type_ == SOFT) {

      compiled_code_->PrintDeoptLocation(bailout_id_);

    }

  }

  // Determine basic deoptimization information.  The optimized frame is

  // described by the input data.

  DeoptimizationInputData* input_data =

      DeoptimizationInputData::cast(compiled_code_->deoptimization_data());

  BailoutId node_id = input_data->AstId(bailout_id_);

  ByteArray* translations = input_data->TranslationByteArray();

  unsigned translation_index =

      input_data->TranslationIndex(bailout_id_)->value();

  // Do the input frame to output frame(s) translation.

  TranslationIterator iterator(translations, translation_index);

  Translation::Opcode opcode =

      static_cast<Translation::Opcode>(iterator.Next());

  ASSERT(Translation::BEGIN == opcode);

  USE(opcode);

  // Read the number of output frames and allocate an array for their

  // descriptions.

  int count = iterator.Next();

  iterator.Next();  // Drop JS frames count.

  ASSERT(output_ == NULL);

  output_ = new FrameDescription*[count];

  for (int i = 0; i < count; ++i) {

    output_[i] = NULL;

  }

  output_count_ = count;

  // Translate each output frame.

  for (int i = 0; i < count; ++i) {

    // Read the ast node id, function, and frame height for this output frame.

    Translation::Opcode opcode =

        static_cast<Translation::Opcode>(iterator.Next());

    switch (opcode) {

      case Translation::JS_FRAME:

        DoComputeJSFrame(&iterator, i);

        jsframe_count_++;

        break;

      case Translation::ARGUMENTS_ADAPTOR_FRAME:

        DoComputeArgumentsAdaptorFrame(&iterator, i);

        break;

      case Translation::CONSTRUCT_STUB_FRAME:

        DoComputeConstructStubFrame(&iterator, i);

        break;

      case Translation::GETTER_STUB_FRAME:

        DoComputeAccessorStubFrame(&iterator, i, false);

        break;

      case Translation::SETTER_STUB_FRAME:

        DoComputeAccessorStubFrame(&iterator, i, true);

        break;

      case Translation::COMPILED_STUB_FRAME:

        DoComputeCompiledStubFrame(&iterator, i);

        break;

      case Translation::BEGIN:

      case Translation::REGISTER:

      case Translation::INT32_REGISTER:

      case Translation::UINT32_REGISTER:

      case Translation::DOUBLE_REGISTER:

      case Translation::STACK_SLOT:

      case Translation::INT32_STACK_SLOT:

      case Translation::UINT32_STACK_SLOT:

      case Translation::DOUBLE_STACK_SLOT:

      case Translation::LITERAL:

      case Translation::ARGUMENTS_OBJECT:

      default:

        UNREACHABLE();

        break;

    }

  }

  // Print some helpful diagnostic information.

  if (trace_) {

    double ms = timer.Elapsed().InMillisecondsF();

    int index = output_count_ - 1;  // Index of the topmost frame.

    JSFunction* function = output_[index]->GetFunction();

    PrintF("[deoptimizing (%s): end 0x%08" V8PRIxPTR " ",

           MessageFor(bailout_type_),

           reinterpret_cast<intptr_t>(function));

    PrintFunctionName();

    PrintF(" @%d => node=%d, pc=0x%08" V8PRIxPTR ", state=%s, alignment=%s,"

           " took %0.3f ms]\n",

           bailout_id_,

           node_id.ToInt(),

           output_[index]->GetPc(),

           FullCodeGenerator::State2String(

               static_cast<FullCodeGenerator::State>(

                   output_[index]->GetState()->value())),

           has_alignment_padding_ ? "with padding" : "no padding",

           ms);

  }

}

void Deoptimizer::DoComputeJSFrame(TranslationIterator* iterator,

                                   int frame_index) {

  BailoutId node_id = BailoutId(iterator->Next());

  JSFunction* function;

  if (frame_index != 0) {

    function = JSFunction::cast(ComputeLiteral(iterator->Next()));

  } else {

    int closure_id = iterator->Next();

    USE(closure_id);

    ASSERT_EQ(Translation::kSelfLiteralId, closure_id);

    function = function_;

  }

  unsigned height = iterator->Next();

  unsigned height_in_bytes = height * kPointerSize;

  if (trace_) {

    PrintF("  translating ");

    function->PrintName();

    PrintF(" => node=%d, height=%d\n", node_id.ToInt(), height_in_bytes);

  }

  // The 'fixed' part of the frame consists of the incoming parameters and

  // the part described by JavaScriptFrameConstants.

  unsigned fixed_frame_size = ComputeFixedSize(function);

  unsigned input_frame_size = input_->GetFrameSize();

  unsigned output_frame_size = height_in_bytes + fixed_frame_size;

  // Allocate and store the output frame description.

  FrameDescription* output_frame =

      new(output_frame_size) FrameDescription(output_frame_size, function);

  output_frame->SetFrameType(StackFrame::JAVA_SCRIPT);

  bool is_bottommost = (0 == frame_index);

  bool is_topmost = (output_count_ - 1 == frame_index);

  ASSERT(frame_index >= 0 && frame_index < output_count_);

  ASSERT(output_[frame_index] == NULL);

  output_[frame_index] = output_frame;

  // The top address for the bottommost output frame can be computed from

  // the input frame pointer and the output frame's height.  For all

  // subsequent output frames, it can be computed from the previous one's

  // top address and the current frame's size.

  Register fp_reg = JavaScriptFrame::fp_register();

  intptr_t top_address;

  if (is_bottommost) {

    // Determine whether the input frame contains alignment padding.

    has_alignment_padding_ = HasAlignmentPadding(function) ? 1 : 0;

    // 2 = context and function in the frame.

    // If the optimized frame had alignment padding, adjust the frame pointer

    // to point to the new position of the old frame pointer after padding

    // is removed. Subtract 2 * kPointerSize for the context and function slots.

    top_address = input_->GetRegister(fp_reg.code()) - (2 * kPointerSize) -

        height_in_bytes + has_alignment_padding_ * kPointerSize;

  } else {

    top_address = output_[frame_index - 1]->GetTop() - output_frame_size;

  }

  output_frame->SetTop(top_address);

  // Compute the incoming parameter translation.

  int parameter_count = function->shared()->formal_parameter_count() + 1;

  unsigned output_offset = output_frame_size;

  unsigned input_offset = input_frame_size;

  for (int i = 0; i < parameter_count; ++i) {

    output_offset -= kPointerSize;

    DoTranslateCommand(iterator, frame_index, output_offset);

  }

  input_offset -= (parameter_count * kPointerSize);

  // There are no translation commands for the caller's pc and fp, the

  // context, and the function.  Synthesize their values and set them up

  // explicitly.

  //

  // The caller's pc for the bottommost output frame is the same as in the

  // input frame.  For all subsequent output frames, it can be read from the

  // previous one.  This frame's pc can be computed from the non-optimized

  // function code and AST id of the bailout.

  output_offset -= kPCOnStackSize;

  input_offset -= kPCOnStackSize;

  intptr_t value;

  if (is_bottommost) {

    value = input_->GetFrameSlot(input_offset);

  } else {

    value = output_[frame_index - 1]->GetPc();

  }

  output_frame->SetCallerPc(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR  " ; caller's pc\n",

           top_address + output_offset, output_offset, value);

  }

  // The caller's frame pointer for the bottommost output frame is the same

  // as in the input frame.  For all subsequent output frames, it can be

  // read from the previous one.  Also compute and set this frame's frame

  // pointer.

  output_offset -= kFPOnStackSize;

  input_offset -= kFPOnStackSize;

  if (is_bottommost) {

    value = input_->GetFrameSlot(input_offset);

  } else {

    value = output_[frame_index - 1]->GetFp();

  }

  output_frame->SetCallerFp(output_offset, value);

  intptr_t fp_value = top_address + output_offset;

  ASSERT(!is_bottommost || (input_->GetRegister(fp_reg.code()) +

      has_alignment_padding_ * kPointerSize) == fp_value);

  output_frame->SetFp(fp_value);

  if (is_topmost) output_frame->SetRegister(fp_reg.code(), fp_value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; caller's fp\n",

           fp_value, output_offset, value);

  }

  ASSERT(!is_bottommost || !has_alignment_padding_ ||

         (fp_value & kPointerSize) != 0);

  // For the bottommost output frame the context can be gotten from the input

  // frame. For all subsequent output frames it can be gotten from the function

  // so long as we don't inline functions that need local contexts.

  Register context_reg = JavaScriptFrame::context_register();

  output_offset -= kPointerSize;

  input_offset -= kPointerSize;

  if (is_bottommost) {

    value = input_->GetFrameSlot(input_offset);

  } else {

    value = reinterpret_cast<intptr_t>(function->context());

  }

  output_frame->SetFrameSlot(output_offset, value);

  output_frame->SetContext(value);

  if (is_topmost) output_frame->SetRegister(context_reg.code(), value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR "; context\n",

           top_address + output_offset, output_offset, value);

  }

  // The function was mentioned explicitly in the BEGIN_FRAME.

  output_offset -= kPointerSize;

  input_offset -= kPointerSize;

  value = reinterpret_cast<intptr_t>(function);

  // The function for the bottommost output frame should also agree with the

  // input frame.

  ASSERT(!is_bottommost || input_->GetFrameSlot(input_offset) == value);

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR "; function\n",

           top_address + output_offset, output_offset, value);

  }

  // Translate the rest of the frame.

  for (unsigned i = 0; i < height; ++i) {

    output_offset -= kPointerSize;

    DoTranslateCommand(iterator, frame_index, output_offset);

  }

  ASSERT(0 == output_offset);

  // Compute this frame's PC, state, and continuation.

  Code* non_optimized_code = function->shared()->code();

  FixedArray* raw_data = non_optimized_code->deoptimization_data();

  DeoptimizationOutputData* data = DeoptimizationOutputData::cast(raw_data);

  Address start = non_optimized_code->instruction_start();

  unsigned pc_and_state = GetOutputInfo(data, node_id, function->shared());

  unsigned pc_offset = FullCodeGenerator::PcField::decode(pc_and_state);

  intptr_t pc_value = reinterpret_cast<intptr_t>(start + pc_offset);

  output_frame->SetPc(pc_value);

  FullCodeGenerator::State state =

      FullCodeGenerator::StateField::decode(pc_and_state);

  output_frame->SetState(Smi::FromInt(state));

  // Set the continuation for the topmost frame.

  if (is_topmost && bailout_type_ != DEBUGGER) {

    Builtins* builtins = isolate_->builtins();

    Code* continuation = builtins->builtin(Builtins::kNotifyDeoptimized);

    if (bailout_type_ == LAZY) {

      continuation = builtins->builtin(Builtins::kNotifyLazyDeoptimized);

    } else if (bailout_type_ == SOFT) {

      continuation = builtins->builtin(Builtins::kNotifySoftDeoptimized);

    } else {

      ASSERT(bailout_type_ == EAGER);

    }

    output_frame->SetContinuation(

        reinterpret_cast<intptr_t>(continuation->entry()));

  }

}

void Deoptimizer::DoComputeArgumentsAdaptorFrame(TranslationIterator* iterator,

                                                 int frame_index) {

  JSFunction* function = JSFunction::cast(ComputeLiteral(iterator->Next()));

  unsigned height = iterator->Next();

  unsigned height_in_bytes = height * kPointerSize;

  if (trace_) {

    PrintF("  translating arguments adaptor => height=%d\n", height_in_bytes);

  }

  unsigned fixed_frame_size = ArgumentsAdaptorFrameConstants::kFrameSize;

  unsigned output_frame_size = height_in_bytes + fixed_frame_size;

  // Allocate and store the output frame description.

  FrameDescription* output_frame =

      new(output_frame_size) FrameDescription(output_frame_size, function);

  output_frame->SetFrameType(StackFrame::ARGUMENTS_ADAPTOR);

  // Arguments adaptor can not be topmost or bottommost.

  ASSERT(frame_index > 0 && frame_index < output_count_ - 1);

  ASSERT(output_[frame_index] == NULL);

  output_[frame_index] = output_frame;

  // The top address of the frame is computed from the previous

  // frame's top and this frame's size.

  intptr_t top_address;

  top_address = output_[frame_index - 1]->GetTop() - output_frame_size;

  output_frame->SetTop(top_address);

  // Compute the incoming parameter translation.

  int parameter_count = height;

  unsigned output_offset = output_frame_size;

  for (int i = 0; i < parameter_count; ++i) {

    output_offset -= kPointerSize;

    DoTranslateCommand(iterator, frame_index, output_offset);

  }

  // Read caller's PC from the previous frame.

  output_offset -= kPCOnStackSize;

  intptr_t callers_pc = output_[frame_index - 1]->GetPc();

  output_frame->SetCallerPc(output_offset, callers_pc);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; caller's pc\n",

           top_address + output_offset, output_offset, callers_pc);

  }

  // Read caller's FP from the previous frame, and set this frame's FP.

  output_offset -= kFPOnStackSize;

  intptr_t value = output_[frame_index - 1]->GetFp();

  output_frame->SetCallerFp(output_offset, value);

  intptr_t fp_value = top_address + output_offset;

  output_frame->SetFp(fp_value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; caller's fp\n",

           fp_value, output_offset, value);

  }

  // A marker value is used in place of the context.

  output_offset -= kPointerSize;

  intptr_t context = reinterpret_cast<intptr_t>(

      Smi::FromInt(StackFrame::ARGUMENTS_ADAPTOR));

  output_frame->SetFrameSlot(output_offset, context);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; context (adaptor sentinel)\n",

           top_address + output_offset, output_offset, context);

  }

  // The function was mentioned explicitly in the ARGUMENTS_ADAPTOR_FRAME.

  output_offset -= kPointerSize;

  value = reinterpret_cast<intptr_t>(function);

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; function\n",

           top_address + output_offset, output_offset, value);

  }

  // Number of incoming arguments.

  output_offset -= kPointerSize;

  value = reinterpret_cast<intptr_t>(Smi::FromInt(height - 1));

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; argc (%d)\n",

           top_address + output_offset, output_offset, value, height - 1);

  }

  ASSERT(0 == output_offset);

  Builtins* builtins = isolate_->builtins();

  Code* adaptor_trampoline =

      builtins->builtin(Builtins::kArgumentsAdaptorTrampoline);

  intptr_t pc_value = reinterpret_cast<intptr_t>(

      adaptor_trampoline->instruction_start() +

      isolate_->heap()->arguments_adaptor_deopt_pc_offset()->value());

  output_frame->SetPc(pc_value);

}

void Deoptimizer::DoComputeConstructStubFrame(TranslationIterator* iterator,

                                              int frame_index) {

  Builtins* builtins = isolate_->builtins();

  Code* construct_stub = builtins->builtin(Builtins::kJSConstructStubGeneric);

  JSFunction* function = JSFunction::cast(ComputeLiteral(iterator->Next()));

  unsigned height = iterator->Next();

  unsigned height_in_bytes = height * kPointerSize;

  if (trace_) {

    PrintF("  translating construct stub => height=%d\n", height_in_bytes);

  }

  unsigned fixed_frame_size = ConstructFrameConstants::kFrameSize;

  unsigned output_frame_size = height_in_bytes + fixed_frame_size;

  // Allocate and store the output frame description.

  FrameDescription* output_frame =

      new(output_frame_size) FrameDescription(output_frame_size, function);

  output_frame->SetFrameType(StackFrame::CONSTRUCT);

  // Construct stub can not be topmost or bottommost.

  ASSERT(frame_index > 0 && frame_index < output_count_ - 1);

  ASSERT(output_[frame_index] == NULL);

  output_[frame_index] = output_frame;

  // The top address of the frame is computed from the previous

  // frame's top and this frame's size.

  intptr_t top_address;

  top_address = output_[frame_index - 1]->GetTop() - output_frame_size;

  output_frame->SetTop(top_address);

  // Compute the incoming parameter translation.

  int parameter_count = height;

  unsigned output_offset = output_frame_size;

  for (int i = 0; i < parameter_count; ++i) {

    output_offset -= kPointerSize;

    int deferred_object_index = deferred_objects_.length();

    DoTranslateCommand(iterator, frame_index, output_offset);

    // The allocated receiver of a construct stub frame is passed as the

    // receiver parameter through the translation. It might be encoding

    // a captured object, patch the slot address for a captured object.

    if (i == 0 && deferred_objects_.length() > deferred_object_index) {

      ASSERT(!deferred_objects_[deferred_object_index].is_arguments());

      deferred_objects_[deferred_object_index].patch_slot_address(top_address);

    }

  }

  // Read caller's PC from the previous frame.

  output_offset -= kPCOnStackSize;

  intptr_t callers_pc = output_[frame_index - 1]->GetPc();

  output_frame->SetCallerPc(output_offset, callers_pc);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; caller's pc\n",

           top_address + output_offset, output_offset, callers_pc);

  }

  // Read caller's FP from the previous frame, and set this frame's FP.

  output_offset -= kFPOnStackSize;

  intptr_t value = output_[frame_index - 1]->GetFp();

  output_frame->SetCallerFp(output_offset, value);

  intptr_t fp_value = top_address + output_offset;

  output_frame->SetFp(fp_value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; caller's fp\n",

           fp_value, output_offset, value);

  }

  // The context can be gotten from the previous frame.

  output_offset -= kPointerSize;

  value = output_[frame_index - 1]->GetContext();

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; context\n",

           top_address + output_offset, output_offset, value);

  }

  // A marker value is used in place of the function.

  output_offset -= kPointerSize;

  value = reinterpret_cast<intptr_t>(Smi::FromInt(StackFrame::CONSTRUCT));

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; function (construct sentinel)\n",

           top_address + output_offset, output_offset, value);

  }

  // The output frame reflects a JSConstructStubGeneric frame.

  output_offset -= kPointerSize;

  value = reinterpret_cast<intptr_t>(construct_stub);

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; code object\n",

           top_address + output_offset, output_offset, value);

  }

  // Number of incoming arguments.

  output_offset -= kPointerSize;

  value = reinterpret_cast<intptr_t>(Smi::FromInt(height - 1));

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; argc (%d)\n",

           top_address + output_offset, output_offset, value, height - 1);

  }

  // Constructor function being invoked by the stub (only present on some

  // architectures, indicated by kConstructorOffset).

  if (ConstructFrameConstants::kConstructorOffset != kMinInt) {

    output_offset -= kPointerSize;

    value = reinterpret_cast<intptr_t>(function);

    output_frame->SetFrameSlot(output_offset, value);

    if (trace_) {

      PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

             V8PRIxPTR " ; constructor function\n",

             top_address + output_offset, output_offset, value);

    }

  }

  // The newly allocated object was passed as receiver in the artificial

  // constructor stub environment created by HEnvironment::CopyForInlining().

  output_offset -= kPointerSize;

  value = output_frame->GetFrameSlot(output_frame_size - kPointerSize);

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %d] <- 0x%08"

           V8PRIxPTR " ; allocated receiver\n",

           top_address + output_offset, output_offset, value);

  }

  ASSERT(0 == output_offset);

  intptr_t pc = reinterpret_cast<intptr_t>(

      construct_stub->instruction_start() +

      isolate_->heap()->construct_stub_deopt_pc_offset()->value());

  output_frame->SetPc(pc);

}

void Deoptimizer::DoComputeAccessorStubFrame(TranslationIterator* iterator,

                                             int frame_index,

                                             bool is_setter_stub_frame) {

  JSFunction* accessor = JSFunction::cast(ComputeLiteral(iterator->Next()));

  // The receiver (and the implicit return value, if any) are expected in

  // registers by the LoadIC/StoreIC, so they don't belong to the output stack

  // frame. This means that we have to use a height of 0.

  unsigned height = 0;

  unsigned height_in_bytes = height * kPointerSize;

  const char* kind = is_setter_stub_frame ? "setter" : "getter";

  if (trace_) {

    PrintF("  translating %s stub => height=%u\n", kind, height_in_bytes);

  }

  // We need 1 stack entry for the return address + 4 stack entries from

  // StackFrame::INTERNAL (FP, context, frame type, code object, see

  // MacroAssembler::EnterFrame). For a setter stub frame we need one additional

  // entry for the implicit return value, see

  // StoreStubCompiler::CompileStoreViaSetter.

  unsigned fixed_frame_entries = (kPCOnStackSize / kPointerSize) +

                                 (kFPOnStackSize / kPointerSize) + 3 +

                                 (is_setter_stub_frame ? 1 : 0);

  unsigned fixed_frame_size = fixed_frame_entries * kPointerSize;

  unsigned output_frame_size = height_in_bytes + fixed_frame_size;

  // Allocate and store the output frame description.

  FrameDescription* output_frame =

      new(output_frame_size) FrameDescription(output_frame_size, accessor);

  output_frame->SetFrameType(StackFrame::INTERNAL);

  // A frame for an accessor stub can not be the topmost or bottommost one.

  ASSERT(frame_index > 0 && frame_index < output_count_ - 1);

  ASSERT(output_[frame_index] == NULL);

  output_[frame_index] = output_frame;

  // The top address of the frame is computed from the previous frame's top and

  // this frame's size.

  intptr_t top_address = output_[frame_index - 1]->GetTop() - output_frame_size;

  output_frame->SetTop(top_address);

  unsigned output_offset = output_frame_size;

  // Read caller's PC from the previous frame.

  output_offset -= kPCOnStackSize;

  intptr_t callers_pc = output_[frame_index - 1]->GetPc();

  output_frame->SetCallerPc(output_offset, callers_pc);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %u] <- 0x%08" V8PRIxPTR

           " ; caller's pc\n",

           top_address + output_offset, output_offset, callers_pc);

  }

  // Read caller's FP from the previous frame, and set this frame's FP.

  output_offset -= kFPOnStackSize;

  intptr_t value = output_[frame_index - 1]->GetFp();

  output_frame->SetCallerFp(output_offset, value);

  intptr_t fp_value = top_address + output_offset;

  output_frame->SetFp(fp_value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %u] <- 0x%08" V8PRIxPTR

           " ; caller's fp\n",

           fp_value, output_offset, value);

  }

  // The context can be gotten from the previous frame.

  output_offset -= kPointerSize;

  value = output_[frame_index - 1]->GetContext();

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %u] <- 0x%08" V8PRIxPTR

           " ; context\n",

           top_address + output_offset, output_offset, value);

  }

  // A marker value is used in place of the function.

  output_offset -= kPointerSize;

  value = reinterpret_cast<intptr_t>(Smi::FromInt(StackFrame::INTERNAL));

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %u] <- 0x%08" V8PRIxPTR

           " ; function (%s sentinel)\n",

           top_address + output_offset, output_offset, value, kind);

  }

  // Get Code object from accessor stub.

  output_offset -= kPointerSize;

  Builtins::Name name = is_setter_stub_frame ?

      Builtins::kStoreIC_Setter_ForDeopt :

      Builtins::kLoadIC_Getter_ForDeopt;

  Code* accessor_stub = isolate_->builtins()->builtin(name);

  value = reinterpret_cast<intptr_t>(accessor_stub);

  output_frame->SetFrameSlot(output_offset, value);

  if (trace_) {

    PrintF("    0x%08" V8PRIxPTR ": [top + %u] <- 0x%08" V8PRIxPTR

           " ; code object\n",

           top_address + output_offset, output_offset, value);

  }

  // Skip receiver.

  Translation::Opcode opcode =