// Copyright 2013 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "src/deoptimizer.h" #include #include "src/accessors.h" #include "src/assembler-inl.h" #include "src/ast/prettyprinter.h" #include "src/callable.h" #include "src/disasm.h" #include "src/frames-inl.h" #include "src/global-handles.h" #include "src/interpreter/interpreter.h" #include "src/macro-assembler.h" #include "src/objects/debug-objects-inl.h" #include "src/tracing/trace-event.h" #include "src/v8.h" // Has to be the last include (doesn't have include guards) #include "src/objects/object-macros.h" namespace v8 { namespace internal { // {FrameWriter} offers a stack writer abstraction for writing // FrameDescriptions. The main service the class provides is managing // {top_offset_}, i.e. the offset of the next slot to write to. class FrameWriter { public: static const int NO_INPUT_INDEX = -1; FrameWriter(Deoptimizer* deoptimizer, FrameDescription* frame, CodeTracer::Scope* trace_scope) : deoptimizer_(deoptimizer), frame_(frame), trace_scope_(trace_scope), top_offset_(frame->GetFrameSize()) {} void PushRawValue(intptr_t value, const char* debug_hint) { PushValue(value); if (trace_scope_ != nullptr) { DebugPrintOutputValue(value, debug_hint); } } void PushRawObject(Object* obj, const char* debug_hint) { intptr_t value = reinterpret_cast(obj); PushValue(value); if (trace_scope_ != nullptr) { DebugPrintOutputObject(obj, top_offset_, debug_hint); } } void PushCallerPc(intptr_t pc) { top_offset_ -= kPCOnStackSize; frame_->SetCallerPc(top_offset_, pc); DebugPrintOutputValue(pc, "caller's pc\n"); } void PushCallerFp(intptr_t fp) { top_offset_ -= kFPOnStackSize; frame_->SetCallerFp(top_offset_, fp); DebugPrintOutputValue(fp, "caller's fp\n"); } void PushCallerConstantPool(intptr_t cp) { top_offset_ -= kPointerSize; frame_->SetCallerConstantPool(top_offset_, cp); DebugPrintOutputValue(cp, "caller's constant_pool\n"); } void PushTranslatedValue(const TranslatedFrame::iterator& iterator, const char* debug_hint = "") { Object* obj = iterator->GetRawValue(); PushRawObject(obj, debug_hint); if (trace_scope_) { PrintF(trace_scope_->file(), " (input #%d)\n", iterator.input_index()); } deoptimizer_->QueueValueForMaterialization(output_address(top_offset_), obj, iterator); } unsigned top_offset() const { return top_offset_; } private: void PushValue(intptr_t value) { CHECK_GE(top_offset_, 0); top_offset_ -= kPointerSize; frame_->SetFrameSlot(top_offset_, value); } Address output_address(unsigned output_offset) { Address output_address = static_cast

(frame_->GetTop()) + output_offset; return output_address; } void DebugPrintOutputValue(intptr_t value, const char* debug_hint = "") { if (trace_scope_ != nullptr) { PrintF(trace_scope_->file(), " " V8PRIxPTR_FMT ": [top + %3d] <- " V8PRIxPTR_FMT " ; %s", output_address(top_offset_), top_offset_, value, debug_hint); } } void DebugPrintOutputObject(Object* obj, unsigned output_offset, const char* debug_hint = "") { if (trace_scope_ != nullptr) { PrintF(trace_scope_->file(), " " V8PRIxPTR_FMT ": [top + %3d] <- ", output_address(output_offset), output_offset); if (obj->IsSmi()) { PrintF(V8PRIxPTR_FMT " ", reinterpret_cast

(obj), Smi::cast(obj)->value()); } else { obj->ShortPrint(trace_scope_->file()); } PrintF(trace_scope_->file(), " ; %s", debug_hint); } } Deoptimizer* deoptimizer_; FrameDescription* frame_; CodeTracer::Scope* trace_scope_; unsigned top_offset_; }; DeoptimizerData::DeoptimizerData(Heap* heap) : heap_(heap), current_(nullptr) { for (int i = 0; i <= DeoptimizerData::kLastDeoptimizeKind; ++i) { deopt_entry_code_[i] = nullptr; } Code** start = &deopt_entry_code_[0]; Code** end = &deopt_entry_code_[DeoptimizerData::kLastDeoptimizeKind + 1]; heap_->RegisterStrongRoots(reinterpret_cast(start), reinterpret_cast(end)); } DeoptimizerData::~DeoptimizerData() { for (int i = 0; i <= DeoptimizerData::kLastDeoptimizeKind; ++i) { deopt_entry_code_[i] = nullptr; } Code** start = &deopt_entry_code_[0]; heap_->UnregisterStrongRoots(reinterpret_cast(start)); } Code* DeoptimizerData::deopt_entry_code(DeoptimizeKind kind) { return deopt_entry_code_[static_cast(kind)]; } void DeoptimizerData::set_deopt_entry_code(DeoptimizeKind kind, Code* code) { deopt_entry_code_[static_cast(kind)] = code; } Code* Deoptimizer::FindDeoptimizingCode(Address addr) { if (function_->IsHeapObject()) { // Search all deoptimizing code in the native context of the function. Isolate* isolate = isolate_; Context* native_context = function_->context()->native_context(); Object* element = native_context->DeoptimizedCodeListHead(); while (!element->IsUndefined(isolate)) { Code* code = Code::cast(element); CHECK(code->kind() == Code::OPTIMIZED_FUNCTION); if (code->contains(addr)) return code; element = code->next_code_link(); } } return nullptr; } // 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, DeoptimizeKind kind, unsigned bailout_id, Address from, int fp_to_sp_delta, Isolate* isolate) { Deoptimizer* deoptimizer = new Deoptimizer(isolate, function, kind, bailout_id, from, fp_to_sp_delta); CHECK_NULL(isolate->deoptimizer_data()->current_); isolate->deoptimizer_data()->current_ = deoptimizer; return deoptimizer; } Deoptimizer* Deoptimizer::Grab(Isolate* isolate) { Deoptimizer* result = isolate->deoptimizer_data()->current_; CHECK_NOT_NULL(result); result->DeleteFrameDescriptions(); isolate->deoptimizer_data()->current_ = nullptr; return result; } DeoptimizedFrameInfo* Deoptimizer::DebuggerInspectableFrame( JavaScriptFrame* frame, int jsframe_index, Isolate* isolate) { CHECK(frame->is_optimized()); TranslatedState translated_values(frame); translated_values.Prepare(frame->fp()); TranslatedState::iterator frame_it = translated_values.end(); int counter = jsframe_index; for (auto it = translated_values.begin(); it != translated_values.end(); it++) { if (it->kind() == TranslatedFrame::kInterpretedFunction || it->kind() == TranslatedFrame::kJavaScriptBuiltinContinuation || it->kind() == TranslatedFrame::kJavaScriptBuiltinContinuationWithCatch) { if (counter == 0) { frame_it = it; break; } counter--; } } CHECK(frame_it != translated_values.end()); // We only include kJavaScriptBuiltinContinuation frames above to get the // counting right. CHECK_EQ(frame_it->kind(), TranslatedFrame::kInterpretedFunction); DeoptimizedFrameInfo* info = new DeoptimizedFrameInfo(&translated_values, frame_it, isolate); return info; } void Deoptimizer::GenerateDeoptimizationEntries(MacroAssembler* masm, int count, DeoptimizeKind kind) { NoRootArrayScope no_root_array(masm); TableEntryGenerator generator(masm, kind, count); generator.Generate(); } namespace { class ActivationsFinder : public ThreadVisitor { public: explicit ActivationsFinder(std::set* codes, Code* topmost_optimized_code, bool safe_to_deopt_topmost_optimized_code) : codes_(codes) { #ifdef DEBUG topmost_ = topmost_optimized_code; safe_to_deopt_ = safe_to_deopt_topmost_optimized_code; #endif } // Find the frames with activations of codes marked for deoptimization, search // for the trampoline to the deoptimizer call respective to each code, and use // it to replace the current pc on the stack. void VisitThread(Isolate* isolate, ThreadLocalTop* top) override { for (StackFrameIterator it(isolate, top); !it.done(); it.Advance()) { if (it.frame()->type() == StackFrame::OPTIMIZED) { Code* code = it.frame()->LookupCode(); if (code->kind() == Code::OPTIMIZED_FUNCTION && code->marked_for_deoptimization()) { codes_->erase(code); // Obtain the trampoline to the deoptimizer call. SafepointEntry safepoint = code->GetSafepointEntry(it.frame()->pc()); int trampoline_pc = safepoint.trampoline_pc(); DCHECK_IMPLIES(code == topmost_, safe_to_deopt_); // Replace the current pc on the stack with the trampoline. it.frame()->set_pc(code->raw_instruction_start() + trampoline_pc); } } } } private: std::set* codes_; #ifdef DEBUG Code* topmost_; bool safe_to_deopt_; #endif }; } // namespace // Move marked code from the optimized code list to the deoptimized code list, // and replace pc on the stack for codes marked for deoptimization. void Deoptimizer::DeoptimizeMarkedCodeForContext(Context* context) { DisallowHeapAllocation no_allocation; Isolate* isolate = context->GetHeap()->isolate(); Code* topmost_optimized_code = nullptr; bool safe_to_deopt_topmost_optimized_code = false; #ifdef DEBUG // Make sure all activations of optimized code can deopt at their current PC. // The topmost optimized code has special handling because it cannot be // deoptimized due to weak object dependency. for (StackFrameIterator it(isolate, isolate->thread_local_top()); !it.done(); it.Advance()) { StackFrame::Type type = it.frame()->type(); if (type == StackFrame::OPTIMIZED) { Code* code = it.frame()->LookupCode(); JSFunction* function = static_cast(it.frame())->function(); if (FLAG_trace_deopt) { CodeTracer::Scope scope(isolate->GetCodeTracer()); PrintF(scope.file(), "[deoptimizer found activation of function: "); function->PrintName(scope.file()); PrintF(scope.file(), " / %" V8PRIxPTR "]\n", reinterpret_cast(function)); } SafepointEntry safepoint = code->GetSafepointEntry(it.frame()->pc()); int deopt_index = safepoint.deoptimization_index(); // Turbofan deopt is checked when we are patching addresses on stack. bool safe_if_deopt_triggered = deopt_index != Safepoint::kNoDeoptimizationIndex; bool is_builtin_code = code->kind() == Code::BUILTIN; DCHECK(topmost_optimized_code == nullptr || safe_if_deopt_triggered || is_builtin_code); if (topmost_optimized_code == nullptr) { topmost_optimized_code = code; safe_to_deopt_topmost_optimized_code = safe_if_deopt_triggered; } } } #endif // We will use this set to mark those Code objects that are marked for // deoptimization and have not been found in stack frames. std::set codes; // Move marked code from the optimized code list to the deoptimized code list. // Walk over all optimized code objects in this native context. Code* prev = nullptr; Object* element = context->OptimizedCodeListHead(); while (!element->IsUndefined(isolate)) { Code* code = Code::cast(element); CHECK_EQ(code->kind(), Code::OPTIMIZED_FUNCTION); Object* next = code->next_code_link(); if (code->marked_for_deoptimization()) { // Make sure that this object does not point to any garbage. isolate->heap()->InvalidateCodeEmbeddedObjects(code); codes.insert(code); if (prev != nullptr) { // 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; } ActivationsFinder visitor(&codes, topmost_optimized_code, safe_to_deopt_topmost_optimized_code); // Iterate over the stack of this thread. visitor.VisitThread(isolate, isolate->thread_local_top()); // In addition to iterate over the stack of this thread, we also // need to consider all the other threads as they may also use // the code currently beings deoptimized. isolate->thread_manager()->IterateArchivedThreads(&visitor); // If there's no activation of a code in any stack then we can remove its // deoptimization data. We do this to ensure that code objects that are // unlinked don't transitively keep objects alive unnecessarily. for (Code* code : codes) { isolate->heap()->InvalidateCodeDeoptimizationData(code); } } void Deoptimizer::DeoptimizeAll(Isolate* isolate) { RuntimeCallTimerScope runtimeTimer(isolate, RuntimeCallCounterId::kDeoptimizeCode); TimerEventScope timer(isolate); TRACE_EVENT0("v8", "V8.DeoptimizeCode"); if (FLAG_trace_deopt) { CodeTracer::Scope scope(isolate->GetCodeTracer()); PrintF(scope.file(), "[deoptimize all code in all contexts]\n"); } isolate->AbortConcurrentOptimization(BlockingBehavior::kBlock); DisallowHeapAllocation no_allocation; // For all contexts, mark all code, then deoptimize. Object* context = isolate->heap()->native_contexts_list(); while (!context->IsUndefined(isolate)) { Context* native_context = Context::cast(context); MarkAllCodeForContext(native_context); DeoptimizeMarkedCodeForContext(native_context); context = native_context->next_context_link(); } } void Deoptimizer::DeoptimizeMarkedCode(Isolate* isolate) { RuntimeCallTimerScope runtimeTimer(isolate, RuntimeCallCounterId::kDeoptimizeCode); TimerEventScope timer(isolate); TRACE_EVENT0("v8", "V8.DeoptimizeCode"); if (FLAG_trace_deopt) { CodeTracer::Scope scope(isolate->GetCodeTracer()); PrintF(scope.file(), "[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(isolate)) { Context* native_context = Context::cast(context); DeoptimizeMarkedCodeForContext(native_context); context = native_context->next_context_link(); } } void Deoptimizer::MarkAllCodeForContext(Context* context) { Object* element = context->OptimizedCodeListHead(); Isolate* isolate = context->GetIsolate(); while (!element->IsUndefined(isolate)) { Code* code = Code::cast(element); CHECK_EQ(code->kind(), Code::OPTIMIZED_FUNCTION); code->set_marked_for_deoptimization(true); element = code->next_code_link(); } } void Deoptimizer::DeoptimizeFunction(JSFunction* function, Code* code) { Isolate* isolate = function->GetIsolate(); RuntimeCallTimerScope runtimeTimer(isolate, RuntimeCallCounterId::kDeoptimizeCode); TimerEventScope timer(isolate); TRACE_EVENT0("v8", "V8.DeoptimizeCode"); if (code == nullptr) 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); // The code in the function's optimized code feedback vector slot might // be different from the code on the function - evict it if necessary. function->feedback_vector()->EvictOptimizedCodeMarkedForDeoptimization( function->shared(), "unlinking code marked for deopt"); if (!code->deopt_already_counted()) { function->feedback_vector()->increment_deopt_count(); code->set_deopt_already_counted(true); } DeoptimizeMarkedCodeForContext(function->context()->native_context()); } } void Deoptimizer::ComputeOutputFrames(Deoptimizer* deoptimizer) { deoptimizer->DoComputeOutputFrames(); } const char* Deoptimizer::MessageFor(DeoptimizeKind kind) { switch (kind) { case DeoptimizeKind::kEager: return "eager"; case DeoptimizeKind::kSoft: return "soft"; case DeoptimizeKind::kLazy: return "lazy"; } FATAL("Unsupported deopt kind"); return nullptr; } Deoptimizer::Deoptimizer(Isolate* isolate, JSFunction* function, DeoptimizeKind kind, unsigned bailout_id, Address from, int fp_to_sp_delta) : isolate_(isolate), function_(function), bailout_id_(bailout_id), deopt_kind_(kind), from_(from), fp_to_sp_delta_(fp_to_sp_delta), deoptimizing_throw_(false), catch_handler_data_(-1), catch_handler_pc_offset_(-1), input_(nullptr), output_count_(0), jsframe_count_(0), output_(nullptr), caller_frame_top_(0), caller_fp_(0), caller_pc_(0), caller_constant_pool_(0), input_frame_context_(0), stack_fp_(0), trace_scope_(nullptr) { if (isolate->deoptimizer_lazy_throw()) { isolate->set_deoptimizer_lazy_throw(false); deoptimizing_throw_ = true; } DCHECK_NE(from, kNullAddress); compiled_code_ = FindOptimizedCode(); DCHECK_NOT_NULL(compiled_code_); DCHECK(function->IsJSFunction()); trace_scope_ = FLAG_trace_deopt ? new CodeTracer::Scope(isolate->GetCodeTracer()) : nullptr; #ifdef DEBUG DCHECK(AllowHeapAllocation::IsAllowed()); disallow_heap_allocation_ = new DisallowHeapAllocation(); #endif // DEBUG if (compiled_code_->kind() != Code::OPTIMIZED_FUNCTION || !compiled_code_->deopt_already_counted()) { // If the function is optimized, and we haven't counted that deopt yet, then // increment the function's deopt count so that we can avoid optimising // functions that deopt too often. if (deopt_kind_ == DeoptimizeKind::kSoft) { // Soft deopts shouldn't count against the overall deoptimization count // that can eventually lead to disabling optimization for a function. isolate->counters()->soft_deopts_executed()->Increment(); } else if (function != nullptr) { function->feedback_vector()->increment_deopt_count(); } } if (compiled_code_->kind() == Code::OPTIMIZED_FUNCTION) { compiled_code_->set_deopt_already_counted(true); PROFILE(isolate_, CodeDeoptEvent(compiled_code_, kind, from_, fp_to_sp_delta_)); } unsigned size = ComputeInputFrameSize(); int parameter_count = function->shared()->internal_formal_parameter_count() + 1; input_ = new (size) FrameDescription(size, parameter_count); } Code* Deoptimizer::FindOptimizedCode() { Code* compiled_code = FindDeoptimizingCode(from_); return (compiled_code == nullptr) ? static_cast(isolate_->FindCodeObject(from_)) : compiled_code; } void Deoptimizer::PrintFunctionName() { if (function_->IsHeapObject() && function_->IsJSFunction()) { function_->ShortPrint(trace_scope_->file()); } else { PrintF(trace_scope_->file(), "%s", Code::Kind2String(compiled_code_->kind())); } } Handle Deoptimizer::function() const { return Handle(function_, isolate()); } Handle

 Deoptimizer::compiled_code() const {
  return Handle(compiled_code_, isolate());
}

Deoptimizer::~Deoptimizer() {
  DCHECK(input_ == nullptr && output_ == nullptr);
  DCHECK_NULL(disallow_heap_allocation_);
  delete trace_scope_;
}


void Deoptimizer::DeleteFrameDescriptions() {
  delete input_;
  for (int i = 0; i < output_count_; ++i) {
    if (output_[i] != input_) delete output_[i];
  }
  delete[] output_;
  input_ = nullptr;
  output_ = nullptr;
#ifdef DEBUG
  DCHECK(!AllowHeapAllocation::IsAllowed());
  DCHECK_NOT_NULL(disallow_heap_allocation_);
  delete disallow_heap_allocation_;
  disallow_heap_allocation_ = nullptr;
#endif  // DEBUG
}

Address Deoptimizer::GetDeoptimizationEntry(Isolate* isolate, int id,
                                            DeoptimizeKind kind) {
  CHECK_GE(id, 0);
  if (id >= kMaxNumberOfEntries) return kNullAddress;
  DeoptimizerData* data = isolate->deoptimizer_data();
  CHECK_LE(kind, DeoptimizerData::kLastDeoptimizeKind);
  CHECK_NOT_NULL(data->deopt_entry_code(kind));
  Code* code = data->deopt_entry_code(kind);
  return code->raw_instruction_start() + (id * table_entry_size_);
}

int Deoptimizer::GetDeoptimizationId(Isolate* isolate, Address addr,
                                     DeoptimizeKind kind) {
  DeoptimizerData* data = isolate->deoptimizer_data();
  CHECK_LE(kind, DeoptimizerData::kLastDeoptimizeKind);
  DCHECK(IsInDeoptimizationTable(isolate, addr, kind));
  Code* code = data->deopt_entry_code(kind);
  Address start = code->raw_instruction_start();
  DCHECK_EQ(0,
            static_cast(addr - start) % table_entry_size_);
  return static_cast(addr - start) / table_entry_size_;
}

bool Deoptimizer::IsInDeoptimizationTable(Isolate* isolate, Address addr,
                                          DeoptimizeKind type) {
  DeoptimizerData* data = isolate->deoptimizer_data();
  CHECK_LE(type, DeoptimizerData::kLastDeoptimizeKind);
  Code* code = data->deopt_entry_code(type);
  if (code == nullptr) return false;
  Address start = code->raw_instruction_start();
  return ((table_entry_size_ == 0 && addr == start) ||
          (addr >= start &&
           addr < start + (kMaxNumberOfEntries * table_entry_size_)));
}

bool Deoptimizer::IsDeoptimizationEntry(Isolate* isolate, Address addr,
                                        DeoptimizeKind* type) {
  if (IsInDeoptimizationTable(isolate, addr, DeoptimizeKind::kEager)) {
    *type = DeoptimizeKind::kEager;
    return true;
  }
  if (IsInDeoptimizationTable(isolate, addr, DeoptimizeKind::kSoft)) {
    *type = DeoptimizeKind::kSoft;
    return true;
  }
  if (IsInDeoptimizationTable(isolate, addr, DeoptimizeKind::kLazy)) {
    *type = DeoptimizeKind::kLazy;
    return true;
  }
  return false;
}

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(isolate)) {
    Context* native_context = Context::cast(context);
    Object* element = native_context->DeoptimizedCodeListHead();
    while (!element->IsUndefined(isolate)) {
      Code* code = Code::cast(element);
      DCHECK(code->kind() == Code::OPTIMIZED_FUNCTION);
      if (!code->marked_for_deoptimization()) {
        length++;
      }
      element = code->next_code_link();
    }
    context = Context::cast(context)->next_context_link();
  }
  return length;
}

namespace {

int LookupCatchHandler(TranslatedFrame* translated_frame, int* data_out) {
  switch (translated_frame->kind()) {
    case TranslatedFrame::kInterpretedFunction: {
      int bytecode_offset = translated_frame->node_id().ToInt();
      HandlerTable table(
          translated_frame->raw_shared_info()->GetBytecodeArray());
      return table.LookupRange(bytecode_offset, data_out, nullptr);
    }
    case TranslatedFrame::kJavaScriptBuiltinContinuationWithCatch: {
      return 0;
    }
    default:
      break;
  }
  return -1;
}

bool ShouldPadArguments(int arg_count) {
  return kPadArguments && (arg_count % 2 != 0);
}

}  // namespace

// 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() {
  base::ElapsedTimer timer;

  // Determine basic deoptimization information.  The optimized frame is
  // described by the input data.
  DeoptimizationData* input_data =
      DeoptimizationData::cast(compiled_code_->deoptimization_data());

  {
    // Read caller's PC, caller's FP and caller's constant pool values
    // from input frame. Compute caller's frame top address.

    Register fp_reg = JavaScriptFrame::fp_register();
    stack_fp_ = input_->GetRegister(fp_reg.code());

    caller_frame_top_ = stack_fp_ + ComputeInputFrameAboveFpFixedSize();

    Address fp_address = input_->GetFramePointerAddress();
    caller_fp_ = Memory(fp_address);
    caller_pc_ =
        Memory(fp_address + CommonFrameConstants::kCallerPCOffset);
    input_frame_context_ = Memory(
        fp_address + CommonFrameConstants::kContextOrFrameTypeOffset);

    if (FLAG_enable_embedded_constant_pool) {
      caller_constant_pool_ = Memory(
          fp_address + CommonFrameConstants::kConstantPoolOffset);
    }
  }

  if (trace_scope_ != nullptr) {
    timer.Start();
    PrintF(trace_scope_->file(), "[deoptimizing (DEOPT %s): begin ",
           MessageFor(deopt_kind_));
    PrintFunctionName();
    PrintF(trace_scope_->file(),
           " (opt #%d) @%d, FP to SP delta: %d, caller sp: " V8PRIxPTR_FMT
           "]\n",
           input_data->OptimizationId()->value(), bailout_id_, fp_to_sp_delta_,
           caller_frame_top_);
    if (deopt_kind_ == DeoptimizeKind::kEager ||
        deopt_kind_ == DeoptimizeKind::kSoft) {
      compiled_code_->PrintDeoptLocation(
          trace_scope_->file(), "            ;;; deoptimize at ", from_);
    }
  }

  BailoutId node_id = input_data->BytecodeOffset(bailout_id_);
  ByteArray* translations = input_data->TranslationByteArray();
  unsigned translation_index =
      input_data->TranslationIndex(bailout_id_)->value();

  TranslationIterator state_iterator(translations, translation_index);
  translated_state_.Init(
      isolate_, input_->GetFramePointerAddress(), &state_iterator,
      input_data->LiteralArray(), input_->GetRegisterValues(),
      trace_scope_ == nullptr ? nullptr : trace_scope_->file(),
      function_->IsHeapObject()
          ? function_->shared()->internal_formal_parameter_count()
          : 0);

  // Do the input frame to output frame(s) translation.
  size_t count = translated_state_.frames().size();
  // If we are supposed to go to the catch handler, find the catching frame
  // for the catch and make sure we only deoptimize upto that frame.
  if (deoptimizing_throw_) {
    size_t catch_handler_frame_index = count;
    for (size_t i = count; i-- > 0;) {
      catch_handler_pc_offset_ = LookupCatchHandler(
          &(translated_state_.frames()[i]), &catch_handler_data_);
      if (catch_handler_pc_offset_ >= 0) {
        catch_handler_frame_index = i;
        break;
      }
    }
    CHECK_LT(catch_handler_frame_index, count);
    count = catch_handler_frame_index + 1;
  }

  DCHECK_NULL(output_);
  output_ = new FrameDescription*[count];
  for (size_t i = 0; i < count; ++i) {
    output_[i] = nullptr;
  }
  output_count_ = static_cast(count);

  // Translate each output frame.
  int frame_index = 0;  // output_frame_index
  for (size_t i = 0; i < count; ++i, ++frame_index) {
    // Read the ast node id, function, and frame height for this output frame.
    TranslatedFrame* translated_frame = &(translated_state_.frames()[i]);
    bool handle_exception = deoptimizing_throw_ && i == count - 1;
    switch (translated_frame->kind()) {
      case TranslatedFrame::kInterpretedFunction:
        DoComputeInterpretedFrame(translated_frame, frame_index,
                                  handle_exception);
        jsframe_count_++;
        break;
      case TranslatedFrame::kArgumentsAdaptor:
        DoComputeArgumentsAdaptorFrame(translated_frame, frame_index);
        break;
      case TranslatedFrame::kConstructStub:
        DoComputeConstructStubFrame(translated_frame, frame_index);
        break;
      case TranslatedFrame::kBuiltinContinuation:
        DoComputeBuiltinContinuation(translated_frame, frame_index,
                                     BuiltinContinuationMode::STUB);
        break;
      case TranslatedFrame::kJavaScriptBuiltinContinuation:
        DoComputeBuiltinContinuation(translated_frame, frame_index,
                                     BuiltinContinuationMode::JAVASCRIPT);
        break;
      case TranslatedFrame::kJavaScriptBuiltinContinuationWithCatch:
        DoComputeBuiltinContinuation(
            translated_frame, frame_index,
            handle_exception
                ? BuiltinContinuationMode::JAVASCRIPT_HANDLE_EXCEPTION
                : BuiltinContinuationMode::JAVASCRIPT_WITH_CATCH);
        break;
      case TranslatedFrame::kInvalid:
        FATAL("invalid frame");
        break;
    }
  }

  // Print some helpful diagnostic information.
  if (trace_scope_ != nullptr) {
    double ms = timer.Elapsed().InMillisecondsF();
    int index = output_count_ - 1;  // Index of the topmost frame.
    PrintF(trace_scope_->file(), "[deoptimizing (%s): end ",
           MessageFor(deopt_kind_));
    PrintFunctionName();
    PrintF(trace_scope_->file(),
           " @%d => node=%d, pc=" V8PRIxPTR_FMT ", caller sp=" V8PRIxPTR_FMT
           ", took %0.3f ms]\n",
           bailout_id_, node_id.ToInt(), output_[index]->GetPc(),
           caller_frame_top_, ms);
  }
}

void Deoptimizer::DoComputeInterpretedFrame(TranslatedFrame* translated_frame,
                                            int frame_index,
                                            bool goto_catch_handler) {
  SharedFunctionInfo* shared = translated_frame->raw_shared_info();

  TranslatedFrame::iterator value_iterator = translated_frame->begin();
  bool is_bottommost = (0 == frame_index);
  bool is_topmost = (output_count_ - 1 == frame_index);

  int bytecode_offset = translated_frame->node_id().ToInt();
  int height = translated_frame->height();
  int register_count = height - 1;  // Exclude accumulator.
  int register_stack_slot_count =
      InterpreterFrameConstants::RegisterStackSlotCount(register_count);
  int height_in_bytes = register_stack_slot_count * kPointerSize;

  // The topmost frame will contain the accumulator.
  if (is_topmost) {
    height_in_bytes += kPointerSize;
    if (PadTopOfStackRegister()) height_in_bytes += kPointerSize;
  }

  TranslatedFrame::iterator function_iterator = value_iterator++;
  if (trace_scope_ != nullptr) {
    PrintF(trace_scope_->file(), "  translating interpreted frame ");
    std::unique_ptr name = shared->DebugName()->ToCString();
    PrintF(trace_scope_->file(), "%s", name.get());
    PrintF(trace_scope_->file(), " => bytecode_offset=%d, height=%d%s\n",
           bytecode_offset, height_in_bytes,
           goto_catch_handler ? " (throw)" : "");
  }
  if (goto_catch_handler) {
    bytecode_offset = catch_handler_pc_offset_;
  }

  // The 'fixed' part of the frame consists of the incoming parameters and
  // the part described by InterpreterFrameConstants. This will include
  // argument padding, when needed.
  unsigned fixed_frame_size = ComputeInterpretedFixedSize(shared);
  unsigned output_frame_size = height_in_bytes + fixed_frame_size;

  // Allocate and store the output frame description.
  int parameter_count = shared->internal_formal_parameter_count() + 1;
  FrameDescription* output_frame = new (output_frame_size)
      FrameDescription(output_frame_size, parameter_count);
  FrameWriter frame_writer(this, output_frame, trace_scope_);

  CHECK(frame_index >= 0 && frame_index < output_count_);
  CHECK_NULL(output_[frame_index]);
  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;
  if (is_bottommost) {
    top_address = caller_frame_top_ - output_frame_size;
  } else {
    top_address = output_[frame_index - 1]->GetTop() - output_frame_size;
  }
  output_frame->SetTop(top_address);

  // Compute the incoming parameter translation.

  ReadOnlyRoots roots(isolate());
  if (ShouldPadArguments(parameter_count)) {
    frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
  }

  for (int i = 0; i < parameter_count; ++i, ++value_iterator) {
    frame_writer.PushTranslatedValue(value_iterator, "stack parameter");
  }

  DCHECK_EQ(output_frame->GetLastArgumentSlotOffset(),
            frame_writer.top_offset());
  if (trace_scope_ != nullptr) {
    PrintF(trace_scope_->file(), "    -------------------------\n");
  }

  // There are no translation commands for the caller's pc and fp, the
  // context, the function and the bytecode offset.  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.
  const intptr_t caller_pc =
      is_bottommost ? caller_pc_ : output_[frame_index - 1]->GetPc();
  frame_writer.PushCallerPc(caller_pc);

  // 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.
  const intptr_t caller_fp =
      is_bottommost ? caller_fp_ : output_[frame_index - 1]->GetFp();
  frame_writer.PushCallerFp(caller_fp);

  intptr_t fp_value = top_address + frame_writer.top_offset();
  output_frame->SetFp(fp_value);
  if (is_topmost) {
    Register fp_reg = InterpretedFrame::fp_register();
    output_frame->SetRegister(fp_reg.code(), fp_value);
  }

  if (FLAG_enable_embedded_constant_pool) {
    // For the bottommost output frame the constant pool pointer can be gotten
    // from the input frame. For subsequent output frames, it can be read from
    // the previous frame.
    const intptr_t caller_cp =
        is_bottommost ? caller_constant_pool_
                      : output_[frame_index - 1]->GetConstantPool();
    frame_writer.PushCallerConstantPool(caller_cp);
  }

  // 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.

  // When deoptimizing into a catch block, we need to take the context
  // from a register that was specified in the handler table.
  TranslatedFrame::iterator context_pos = value_iterator++;
  if (goto_catch_handler) {
    // Skip to the translated value of the register specified
    // in the handler table.
    for (int i = 0; i < catch_handler_data_ + 1; ++i) {
      context_pos++;
    }
  }
  // Read the context from the translations.
  Object* context = context_pos->GetRawValue();
  output_frame->SetContext(reinterpret_cast(context));
  frame_writer.PushTranslatedValue(context_pos, "context\n");

  // The function was mentioned explicitly in the BEGIN_FRAME.
  frame_writer.PushTranslatedValue(function_iterator, "function\n");

  // Set the bytecode array pointer.
  Object* bytecode_array = shared->HasBreakInfo()
                               ? shared->GetDebugInfo()->DebugBytecodeArray()
                               : shared->GetBytecodeArray();
  frame_writer.PushRawObject(bytecode_array, "bytecode array\n");

  // The bytecode offset was mentioned explicitly in the BEGIN_FRAME.
  int raw_bytecode_offset =
      BytecodeArray::kHeaderSize - kHeapObjectTag + bytecode_offset;
  Smi* smi_bytecode_offset = Smi::FromInt(raw_bytecode_offset);
  frame_writer.PushRawObject(smi_bytecode_offset, "bytecode offset\n");

  if (trace_scope_ != nullptr) {
    PrintF(trace_scope_->file(), "    -------------------------\n");
  }

  // Translate the rest of the interpreter registers in the frame.
  for (int i = 0; i < register_count; ++i, ++value_iterator) {
    frame_writer.PushTranslatedValue(value_iterator, "stack parameter");
  }

  int register_slots_written = register_count;
  DCHECK_LE(register_slots_written, register_stack_slot_count);
  // Some architectures must pad the stack frame with extra stack slots
  // to ensure the stack frame is aligned. Do this now.
  while (register_slots_written < register_stack_slot_count) {
    register_slots_written++;
    frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
  }

  // Translate the accumulator register (depending on frame position).
  if (is_topmost) {
    if (PadTopOfStackRegister()) {
      frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
    }
    // For topmost frame, put the accumulator on the stack. The
    // {NotifyDeoptimized} builtin pops it off the topmost frame (possibly
    // after materialization).
    if (goto_catch_handler) {
      // If we are lazy deopting to a catch handler, we set the accumulator to
      // the exception (which lives in the result register).
      intptr_t accumulator_value =
          input_->GetRegister(kInterpreterAccumulatorRegister.code());
      frame_writer.PushRawObject(reinterpret_cast(accumulator_value),
                                 "accumulator\n");
      ++value_iterator;  // Skip the accumulator.
    } else {
      frame_writer.PushTranslatedValue(value_iterator++, "accumulator");
    }
  } else {
    // For non-topmost frames, skip the accumulator translation. For those
    // frames, the return value from the callee will become the accumulator.
    ++value_iterator;
  }
  CHECK_EQ(translated_frame->end(), value_iterator);
  CHECK_EQ(0u, frame_writer.top_offset());

  // Compute this frame's PC and state. The PC will be a special builtin that
  // continues the bytecode dispatch. Note that non-topmost and lazy-style
  // bailout handlers also advance the bytecode offset before dispatch, hence
  // simulating what normal handlers do upon completion of the operation.
  Builtins* builtins = isolate_->builtins();
  Code* dispatch_builtin =
      (!is_topmost || (deopt_kind_ == DeoptimizeKind::kLazy)) &&
              !goto_catch_handler
          ? builtins->builtin(Builtins::kInterpreterEnterBytecodeAdvance)
          : builtins->builtin(Builtins::kInterpreterEnterBytecodeDispatch);
  output_frame->SetPc(
      static_cast(dispatch_builtin->InstructionStart()));

  // Update constant pool.
  if (FLAG_enable_embedded_constant_pool) {
    intptr_t constant_pool_value =
        static_cast(dispatch_builtin->constant_pool());
    output_frame->SetConstantPool(constant_pool_value);
    if (is_topmost) {
      Register constant_pool_reg =
          InterpretedFrame::constant_pool_pointer_register();
      output_frame->SetRegister(constant_pool_reg.code(), constant_pool_value);
    }
  }

  // Clear the context register. The context might be a de-materialized object
  // and will be materialized by {Runtime_NotifyDeoptimized}. For additional
  // safety we use Smi(0) instead of the potential {arguments_marker} here.
  if (is_topmost) {
    intptr_t context_value = reinterpret_cast(Smi::kZero);
    Register context_reg = JavaScriptFrame::context_register();
    output_frame->SetRegister(context_reg.code(), context_value);
    // Set the continuation for the topmost frame.
    Code* continuation = builtins->builtin(Builtins::kNotifyDeoptimized);
    output_frame->SetContinuation(
        static_cast(continuation->InstructionStart()));
  }
}

void Deoptimizer::DoComputeArgumentsAdaptorFrame(
    TranslatedFrame* translated_frame, int frame_index) {
  TranslatedFrame::iterator value_iterator = translated_frame->begin();
  bool is_bottommost = (0 == frame_index);

  unsigned height = translated_frame->height();
  unsigned height_in_bytes = height * kPointerSize;
  int parameter_count = height;
  if (ShouldPadArguments(parameter_count)) height_in_bytes += kPointerSize;

  TranslatedFrame::iterator function_iterator = value_iterator++;
  if (trace_scope_ != nullptr) {
    PrintF(trace_scope_->file(),
           "  translating arguments adaptor => height=%d\n", height_in_bytes);
  }

  unsigned fixed_frame_size = ArgumentsAdaptorFrameConstants::kFixedFrameSize;
  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, parameter_count);
  FrameWriter frame_writer(this, output_frame, trace_scope_);

  // Arguments adaptor can not be topmost.
  CHECK(frame_index < output_count_ - 1);
  CHECK_NULL(output_[frame_index]);
  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;
  if (is_bottommost) {
    top_address = caller_frame_top_ - output_frame_size;
  } else {
    top_address = output_[frame_index - 1]->GetTop() - output_frame_size;
  }
  output_frame->SetTop(top_address);

  ReadOnlyRoots roots(isolate());
  if (ShouldPadArguments(parameter_count)) {
    frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
  }

  // Compute the incoming parameter translation.
  for (int i = 0; i < parameter_count; ++i, ++value_iterator) {
    frame_writer.PushTranslatedValue(value_iterator, "stack parameter");
  }

  DCHECK_EQ(output_frame->GetLastArgumentSlotOffset(),
            frame_writer.top_offset());

  // Read caller's PC from the previous frame.
  const intptr_t caller_pc =
      is_bottommost ? caller_pc_ : output_[frame_index - 1]->GetPc();
  frame_writer.PushCallerPc(caller_pc);

  // Read caller's FP from the previous frame, and set this frame's FP.
  const intptr_t caller_fp =
      is_bottommost ? caller_fp_ : output_[frame_index - 1]->GetFp();
  frame_writer.PushCallerFp(caller_fp);

  intptr_t fp_value = top_address + frame_writer.top_offset();
  output_frame->SetFp(fp_value);

  if (FLAG_enable_embedded_constant_pool) {
    // Read the caller's constant pool from the previous frame.
    const intptr_t caller_cp =
        is_bottommost ? caller_constant_pool_
                      : output_[frame_index - 1]->GetConstantPool();
    frame_writer.PushCallerConstantPool(caller_cp);
  }

  // A marker value is used in place of the context.
  intptr_t marker = StackFrame::TypeToMarker(StackFrame::ARGUMENTS_ADAPTOR);
  frame_writer.PushRawValue(marker, "context (adaptor sentinel)\n");

  // The function was mentioned explicitly in the ARGUMENTS_ADAPTOR_FRAME.
  frame_writer.PushTranslatedValue(function_iterator, "function\n");

  // Number of incoming arguments.
  frame_writer.PushRawObject(Smi::FromInt(height - 1), "argc\n");

  frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");

  CHECK_EQ(translated_frame->end(), value_iterator);
  DCHECK_EQ(0, frame_writer.top_offset());

  Builtins* builtins = isolate_->builtins();
  Code* adaptor_trampoline =
      builtins->builtin(Builtins::kArgumentsAdaptorTrampoline);
  intptr_t pc_value = static_cast(
      adaptor_trampoline->InstructionStart() +
      isolate_->heap()->arguments_adaptor_deopt_pc_offset()->value());
  output_frame->SetPc(pc_value);
  if (FLAG_enable_embedded_constant_pool) {
    intptr_t constant_pool_value =
        static_cast(adaptor_trampoline->constant_pool());
    output_frame->SetConstantPool(constant_pool_value);
  }
}

void Deoptimizer::DoComputeConstructStubFrame(TranslatedFrame* translated_frame,
                                              int frame_index) {
  TranslatedFrame::iterator value_iterator = translated_frame->begin();
  bool is_topmost = (output_count_ - 1 == frame_index);
  // The construct frame could become topmost only if we inlined a constructor
  // call which does a tail call (otherwise the tail callee's frame would be
  // the topmost one). So it could only be the DeoptimizeKind::kLazy case.
  CHECK(!is_topmost || deopt_kind_ == DeoptimizeKind::kLazy);

  Builtins* builtins = isolate_->builtins();
  Code* construct_stub = builtins->builtin(Builtins::kJSConstructStubGeneric);
  BailoutId bailout_id = translated_frame->node_id();
  unsigned height = translated_frame->height();
  unsigned parameter_count = height - 1;  // Exclude the context.
  unsigned height_in_bytes = parameter_count * kPointerSize;

  // If the construct frame appears to be topmost we should ensure that the
  // value of result register is preserved during continuation execution.
  // We do this here by "pushing" the result of the constructor function to the
  // top of the reconstructed stack and popping it in
  // {Builtins::kNotifyDeoptimized}.
  if (is_topmost) {
    height_in_bytes += kPointerSize;
    if (PadTopOfStackRegister()) height_in_bytes += kPointerSize;
  }

  if (ShouldPadArguments(parameter_count)) height_in_bytes += kPointerSize;

  TranslatedFrame::iterator function_iterator = value_iterator++;
  if (trace_scope_ != nullptr) {
    PrintF(trace_scope_->file(),
           "  translating construct stub => bailout_id=%d (%s), height=%d\n",
           bailout_id.ToInt(),
           bailout_id == BailoutId::ConstructStubCreate() ? "create" : "invoke",
           height_in_bytes);
  }

  unsigned fixed_frame_size = ConstructFrameConstants::kFixedFrameSize;
  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, parameter_count);
  FrameWriter frame_writer(this, output_frame, trace_scope_);

  // Construct stub can not be topmost.
  DCHECK(frame_index > 0 && frame_index < output_count_);
  DCHECK_NULL(output_[frame_index]);
  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);

  ReadOnlyRoots roots(isolate());
  if (ShouldPadArguments(parameter_count)) {
    frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
  }

  // The allocated receiver of a construct stub frame is passed as the
  // receiver parameter through the translation. It might be encoding
  // a captured object, so we need save it for later.
  TranslatedFrame::iterator receiver_iterator = value_iterator;

  // Compute the incoming parameter translation.
  for (unsigned i = 0; i < parameter_count; ++i, ++value_iterator) {
    frame_writer.PushTranslatedValue(value_iterator, "stack parameter");
  }

  DCHECK_EQ(output_frame->GetLastArgumentSlotOffset(),
            frame_writer.top_offset());

  // Read caller's PC from the previous frame.
  const intptr_t caller_pc = output_[frame_index - 1]->GetPc();
  frame_writer.PushCallerPc(caller_pc);

  // Read caller's FP from the previous frame, and set this frame's FP.
  const intptr_t caller_fp = output_[frame_index - 1]->GetFp();
  frame_writer.PushCallerFp(caller_fp);

  intptr_t fp_value = top_address + frame_writer.top_offset();
  output_frame->SetFp(fp_value);
  if (is_topmost) {
    Register fp_reg = JavaScriptFrame::fp_register();
    output_frame->SetRegister(fp_reg.code(), fp_value);
  }

  if (FLAG_enable_embedded_constant_pool) {
    // Read the caller's constant pool from the previous frame.
    const intptr_t caller_cp = output_[frame_index - 1]->GetConstantPool();
    frame_writer.PushCallerConstantPool(caller_cp);
  }

  // A marker value is used to mark the frame.
  intptr_t marker = StackFrame::TypeToMarker(StackFrame::CONSTRUCT);
  frame_writer.PushRawValue(marker, "context (construct stub sentinel)\n");

  frame_writer.PushTranslatedValue(value_iterator++, "context\n");

  // Number of incoming arguments.
  frame_writer.PushRawObject(Smi::FromInt(parameter_count - 1), "argc\n");

  // The constructor function was mentioned explicitly in the
  // CONSTRUCT_STUB_FRAME.
  frame_writer.PushTranslatedValue(function_iterator, "constuctor function\n");

  // The deopt info contains the implicit receiver or the new target at the
  // position of the receiver. Copy it to the top of stack, with the hole value
  // as padding to maintain alignment.

  frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");

  CHECK(bailout_id == BailoutId::ConstructStubCreate() ||
        bailout_id == BailoutId::ConstructStubInvoke());
  const char* debug_hint = bailout_id == BailoutId::ConstructStubCreate()
                               ? "new target\n"
                               : "allocated receiver\n";
  frame_writer.PushTranslatedValue(receiver_iterator, debug_hint);

  if (is_topmost) {
    if (PadTopOfStackRegister()) {
      frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
    }
    // Ensure the result is restored back when we return to the stub.
    Register result_reg = kReturnRegister0;
    intptr_t result = input_->GetRegister(result_reg.code());
    frame_writer.PushRawValue(result, "subcall result\n");
  }

  CHECK_EQ(translated_frame->end(), value_iterator);
  CHECK_EQ(0u, frame_writer.top_offset());

  // Compute this frame's PC.
  DCHECK(bailout_id.IsValidForConstructStub());
  Address start = construct_stub->InstructionStart();
  int pc_offset =
      bailout_id == BailoutId::ConstructStubCreate()
          ? isolate_->heap()->construct_stub_create_deopt_pc_offset()->value()
          : isolate_->heap()->construct_stub_invoke_deopt_pc_offset()->value();
  intptr_t pc_value = static_cast(start + pc_offset);
  output_frame->SetPc(pc_value);

  // Update constant pool.
  if (FLAG_enable_embedded_constant_pool) {
    intptr_t constant_pool_value =
        static_cast(construct_stub->constant_pool());
    output_frame->SetConstantPool(constant_pool_value);
    if (is_topmost) {
      Register constant_pool_reg =
          JavaScriptFrame::constant_pool_pointer_register();
      output_frame->SetRegister(constant_pool_reg.code(), constant_pool_value);
    }
  }

  // Clear the context register. The context might be a de-materialized object
  // and will be materialized by {Runtime_NotifyDeoptimized}. For additional
  // safety we use Smi(0) instead of the potential {arguments_marker} here.
  if (is_topmost) {
    intptr_t context_value = reinterpret_cast(Smi::kZero);
    Register context_reg = JavaScriptFrame::context_register();
    output_frame->SetRegister(context_reg.code(), context_value);
  }

  // Set the continuation for the topmost frame.
  if (is_topmost) {
    Builtins* builtins = isolate_->builtins();
    DCHECK_EQ(DeoptimizeKind::kLazy, deopt_kind_);
    Code* continuation = builtins->builtin(Builtins::kNotifyDeoptimized);
    output_frame->SetContinuation(
        static_cast(continuation->InstructionStart()));
  }
}

bool Deoptimizer::BuiltinContinuationModeIsJavaScript(
    BuiltinContinuationMode mode) {
  switch (mode) {
    case BuiltinContinuationMode::STUB:
      return false;
    case BuiltinContinuationMode::JAVASCRIPT:
    case BuiltinContinuationMode::JAVASCRIPT_WITH_CATCH:
    case BuiltinContinuationMode::JAVASCRIPT_HANDLE_EXCEPTION:
      return true;
  }
  UNREACHABLE();
}

bool Deoptimizer::BuiltinContinuationModeIsWithCatch(
    BuiltinContinuationMode mode) {
  switch (mode) {
    case BuiltinContinuationMode::STUB:
    case BuiltinContinuationMode::JAVASCRIPT:
      return false;
    case BuiltinContinuationMode::JAVASCRIPT_WITH_CATCH:
    case BuiltinContinuationMode::JAVASCRIPT_HANDLE_EXCEPTION:
      return true;
  }
  UNREACHABLE();
}

StackFrame::Type Deoptimizer::BuiltinContinuationModeToFrameType(
    BuiltinContinuationMode mode) {
  switch (mode) {
    case BuiltinContinuationMode::STUB:
      return StackFrame::BUILTIN_CONTINUATION;
    case BuiltinContinuationMode::JAVASCRIPT:
      return StackFrame::JAVA_SCRIPT_BUILTIN_CONTINUATION;
    case BuiltinContinuationMode::JAVASCRIPT_WITH_CATCH:
      return StackFrame::JAVA_SCRIPT_BUILTIN_CONTINUATION_WITH_CATCH;
    case BuiltinContinuationMode::JAVASCRIPT_HANDLE_EXCEPTION:
      return StackFrame::JAVA_SCRIPT_BUILTIN_CONTINUATION_WITH_CATCH;
  }
  UNREACHABLE();
}

Builtins::Name Deoptimizer::TrampolineForBuiltinContinuation(
    BuiltinContinuationMode mode, bool must_handle_result) {
  switch (mode) {
    case BuiltinContinuationMode::STUB:
      return must_handle_result ? Builtins::kContinueToCodeStubBuiltinWithResult
                                : Builtins::kContinueToCodeStubBuiltin;
    case BuiltinContinuationMode::JAVASCRIPT:
    case BuiltinContinuationMode::JAVASCRIPT_WITH_CATCH:
    case BuiltinContinuationMode::JAVASCRIPT_HANDLE_EXCEPTION:
      return must_handle_result
                 ? Builtins::kContinueToJavaScriptBuiltinWithResult
                 : Builtins::kContinueToJavaScriptBuiltin;
  }
  UNREACHABLE();
}

// BuiltinContinuationFrames capture the machine state that is expected as input
// to a builtin, including both input register values and stack parameters. When
// the frame is reactivated (i.e. the frame below it returns), a
// ContinueToBuiltin stub restores the register state from the frame and tail
// calls to the actual target builtin, making it appear that the stub had been
// directly called by the frame above it. The input values to populate the frame
// are taken from the deopt's FrameState.
//
// Frame translation happens in two modes, EAGER and LAZY. In EAGER mode, all of
// the parameters to the Builtin are explicitly specified in the TurboFan
// FrameState node. In LAZY mode, there is always one fewer parameters specified
// in the FrameState than expected by the Builtin. In that case, construction of
// BuiltinContinuationFrame adds the final missing parameter during
// deoptimization, and that parameter is always on the stack and contains the
// value returned from the callee of the call site triggering the LAZY deopt
// (e.g. rax on x64). This requires that continuation Builtins for LAZY deopts
// must have at least one stack parameter.
//
//                TO
//    |          ....           |
//    +-------------------------+
//    | arg padding (arch dept) |<- at most 1*kPointerSize
//    +-------------------------+
//    |     builtin param 0     |<- FrameState input value n becomes
//    +-------------------------+
//    |           ...           |
//    +-------------------------+
//    |     builtin param m     |<- FrameState input value n+m-1, or in
//    +-----needs-alignment-----+   the LAZY case, return LAZY result value
//    | ContinueToBuiltin entry |
//    +-------------------------+
// |  |    saved frame (FP)     |
// |  +=====needs=alignment=====+<- fpreg
// |  |constant pool (if ool_cp)|
// v  +-------------------------+
//    |BUILTIN_CONTINUATION mark|
//    +-------------------------+
//    |  JSFunction (or zero)   |<- only if JavaScript builtin
//    +-------------------------+
//    |  frame height above FP  |
//    +-------------------------+
//    |         context         |<- this non-standard context slot contains
//    +-------------------------+   the context, even for non-JS builtins.
//    |     builtin address     |
//    +-------------------------+
//    | builtin input GPR reg0  |<- populated from deopt FrameState using
//    +-------------------------+   the builtin's CallInterfaceDescriptor
//    |          ...            |   to map a FrameState's 0..n-1 inputs to
//    +-------------------------+   the builtin's n input register params.
//    | builtin input GPR regn  |
//    +-------------------------+
//    | reg padding (arch dept) |
//    +-----needs--alignment----+
//    | res padding (arch dept) |<- only if {is_topmost}; result is pop'd by
//    +-------------------------+<- kNotifyDeopt ASM stub and moved to acc
//    |      result  value      |<- reg, as ContinueToBuiltin stub expects.
//    +-----needs-alignment-----+<- spreg
//
void Deoptimizer::DoComputeBuiltinContinuation(
    TranslatedFrame* translated_frame, int frame_index,
    BuiltinContinuationMode mode) {
  TranslatedFrame::iterator value_iterator = translated_frame->begin();

  // The output frame must have room for all of the parameters that need to be
  // passed to the builtin continuation.
  const int height_in_words = translated_frame->height();

  BailoutId bailout_id = translated_frame->node_id();
  Builtins::Name builtin_name = Builtins::GetBuiltinFromBailoutId(bailout_id);
  CHECK(!Builtins::IsLazy(builtin_name));
  Code* builtin = isolate()->builtins()->builtin(builtin_name);
  Callable continuation_callable =
      Builtins::CallableFor(isolate(), builtin_name);
  CallInterfaceDescriptor continuation_descriptor =
      continuation_callable.descriptor();

  const bool is_bottommost = (0 == frame_index);
  const bool is_topmost = (output_count_ - 1 == frame_index);
  const bool must_handle_result =
      !is_topmost || deopt_kind_ == DeoptimizeKind::kLazy;

#if defined(V8_TARGET_ARCH_IA32) && defined(V8_EMBEDDED_BUILTINS)
  // TODO(v8:6666): Fold into Default config once root is fully supported.
  const RegisterConfiguration* config(
      RegisterConfiguration::PreserveRootIA32());
#else
  const RegisterConfiguration* config(RegisterConfiguration::Default());
#endif
  const int allocatable_register_count =
      config->num_allocatable_general_registers();
  const int padding_slot_count =
      BuiltinContinuationFrameConstants::PaddingSlotCount(
          allocatable_register_count);

  const int register_parameter_count =
      continuation_descriptor.GetRegisterParameterCount();
  // Make sure to account for the context by removing it from the register
  // parameter count.
  const int translated_stack_parameters =
      height_in_words - register_parameter_count - 1;
  const int stack_param_count =
      translated_stack_parameters + (must_handle_result ? 1 : 0) +
      (BuiltinContinuationModeIsWithCatch(mode) ? 1 : 0);
  const int stack_param_pad_count =
      ShouldPadArguments(stack_param_count) ? 1 : 0;

  // If the builtins frame appears to be topmost we should ensure that the
  // value of result register is preserved during continuation execution.
  // We do this here by "pushing" the result of callback function to the
  // top of the reconstructed stack and popping it in
  // {Builtins::kNotifyDeoptimized}.
  const int push_result_count =
      is_topmost ? (PadTopOfStackRegister() ? 2 : 1) : 0;

  const unsigned output_frame_size =
      kPointerSize * (stack_param_count + stack_param_pad_count +
                      allocatable_register_count + padding_slot_count +
                      push_result_count) +
      BuiltinContinuationFrameConstants::kFixedFrameSize;

  const unsigned output_frame_size_above_fp =
      kPointerSize * (allocatable_register_count + padding_slot_count +
                      push_result_count) +
      (BuiltinContinuationFrameConstants::kFixedFrameSize -
       BuiltinContinuationFrameConstants::kFixedFrameSizeAboveFp);

  // Validate types of parameters. They must all be tagged except for argc for
  // JS builtins.
  bool has_argc = false;
  for (int i = 0; i < register_parameter_count; ++i) {
    MachineType type = continuation_descriptor.GetParameterType(i);
    int code = continuation_descriptor.GetRegisterParameter(i).code();
    // Only tagged and int32 arguments are supported, and int32 only for the
    // arguments count on JavaScript builtins.
    if (type == MachineType::Int32()) {
      CHECK_EQ(code, kJavaScriptCallArgCountRegister.code());
      has_argc = true;
    } else {
      // Any other argument must be a tagged value.
      CHECK(IsAnyTagged(type.representation()));
    }
  }
  CHECK_EQ(BuiltinContinuationModeIsJavaScript(mode), has_argc);

  if (trace_scope_ != nullptr) {
    PrintF(trace_scope_->file(),
           "  translating BuiltinContinuation to %s,"
           " register param count %d,"
           " stack param count %d\n",
           Builtins::name(builtin_name), register_parameter_count,
           stack_param_count);
  }

  FrameDescription* output_frame = new (output_frame_size)
      FrameDescription(output_frame_size, stack_param_count);
  output_[frame_index] = output_frame;
  FrameWriter frame_writer(this, output_frame, trace_scope_);

  // The top address of the frame is computed from the previous frame's top and
  // this frame's size.
  intptr_t top_address;
  if (is_bottommost) {
    top_address = caller_frame_top_ - output_frame_size;
  } else {
    top_address = output_[frame_index - 1]->GetTop() - output_frame_size;
  }
  output_frame->SetTop(top_address);

  // Get the possible JSFunction for the case that this is a
  // JavaScriptBuiltinContinuationFrame, which needs the JSFunction pointer
  // like a normal JavaScriptFrame.
  const intptr_t maybe_function =
      reinterpret_cast(value_iterator->GetRawValue());
  ++value_iterator;

  ReadOnlyRoots roots(isolate());
  if (ShouldPadArguments(stack_param_count)) {
    frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
  }

  for (int i = 0; i < translated_stack_parameters; ++i, ++value_iterator) {
    frame_writer.PushTranslatedValue(value_iterator, "stack parameter");
  }

  switch (mode) {
    case BuiltinContinuationMode::STUB:
      break;
    case BuiltinContinuationMode::JAVASCRIPT:
      break;
    case BuiltinContinuationMode::JAVASCRIPT_WITH_CATCH: {
      frame_writer.PushRawObject(roots.the_hole_value(),
                                 "placeholder for exception on lazy deopt\n");
    } break;
    case BuiltinContinuationMode::JAVASCRIPT_HANDLE_EXCEPTION: {
      intptr_t accumulator_value =
          input_->GetRegister(kInterpreterAccumulatorRegister.code());
      frame_writer.PushRawObject(reinterpret_cast(accumulator_value),
                                 "exception (from accumulator)\n");
    } break;
  }

  if (must_handle_result) {
    frame_writer.PushRawObject(roots.the_hole_value(),
                               "placeholder for return result on lazy deopt\n");
  }

  DCHECK_EQ(output_frame->GetLastArgumentSlotOffset(),
            frame_writer.top_offset());

  std::vector register_values;
  int total_registers = config->num_general_registers();
  register_values.resize(total_registers, {value_iterator});

  for (int i = 0; i < register_parameter_count; ++i, ++value_iterator) {
    int code = continuation_descriptor.GetRegisterParameter(i).code();
    register_values[code] = value_iterator;
  }

  // The context register is always implicit in the CallInterfaceDescriptor but
  // its register must be explicitly set when continuing to the builtin. Make
  // sure that it's harvested from the translation and copied into the register
  // set (it was automatically added at the end of the FrameState by the
  // instruction selector).
  Object* context = value_iterator->GetRawValue();
  const intptr_t value = reinterpret_cast(context);
  TranslatedFrame::iterator context_register_value = value_iterator++;
  register_values[kContextRegister.code()] = context_register_value;
  output_frame->SetContext(value);
  output_frame->SetRegister(kContextRegister.code(), value);

  // Set caller's PC (JSFunction continuation).
  const intptr_t caller_pc =
      is_bottommost ? caller_pc_ : output_[frame_index - 1]->GetPc();
  frame_writer.PushCallerPc(caller_pc);

  // Read caller's FP from the previous frame, and set this frame's FP.
  const intptr_t caller_fp =
      is_bottommost ? caller_fp_ : output_[frame_index - 1]->GetFp();
  frame_writer.PushCallerFp(caller_fp);

  const intptr_t fp_value = top_address + frame_writer.top_offset();
  output_frame->SetFp(fp_value);

  DCHECK_EQ(output_frame_size_above_fp, frame_writer.top_offset());

  if (FLAG_enable_embedded_constant_pool) {
    // Read the caller's constant pool from the previous frame.
    const intptr_t caller_cp =
        is_bottommost ? caller_constant_pool_
                      : output_[frame_index - 1]->GetConstantPool();
    frame_writer.PushCallerConstantPool(caller_cp);
  }

  // A marker value is used in place of the context.
  const intptr_t marker =
      StackFrame::TypeToMarker(BuiltinContinuationModeToFrameType(mode));
  frame_writer.PushRawValue(marker,
                            "context (builtin continuation sentinel)\n");

  if (BuiltinContinuationModeIsJavaScript(mode)) {
    frame_writer.PushRawValue(maybe_function, "JSFunction\n");
  } else {
    frame_writer.PushRawValue(0, "unused\n");
  }

  // The delta from the SP to the FP; used to reconstruct SP in
  // Isolate::UnwindAndFindHandler.
  frame_writer.PushRawObject(Smi::FromInt(output_frame_size_above_fp),
                             "frame height at deoptimization\n");

  // The context even if this is a stub contininuation frame. We can't use the
  // usual context slot, because we must store the frame marker there.
  frame_writer.PushTranslatedValue(context_register_value,
                                   "builtin JavaScript context\n");

  // The builtin to continue to.
  frame_writer.PushRawObject(builtin, "builtin address\n");

  for (int i = 0; i < allocatable_register_count; ++i) {
    int code = config->GetAllocatableGeneralCode(i);
    ScopedVector str(128);
    if (trace_scope_ != nullptr) {
      if (BuiltinContinuationModeIsJavaScript(mode) &&
          code == kJavaScriptCallArgCountRegister.code()) {
        SNPrintF(
            str,
            "tagged argument count %s (will be untagged by continuation)\n",
            config->GetGeneralRegisterName(code));
      } else {
        SNPrintF(str, "builtin register argument %s\n",
                 config->GetGeneralRegisterName(code));
      }
    }
    frame_writer.PushTranslatedValue(
        register_values[code], trace_scope_ != nullptr ? str.start() : "");
  }

  // Some architectures must pad the stack frame with extra stack slots
  // to ensure the stack frame is aligned.
  for (int i = 0; i < padding_slot_count; ++i) {
    frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
  }

  if (is_topmost) {
    if (PadTopOfStackRegister()) {
      frame_writer.PushRawObject(roots.the_hole_value(), "padding\n");
    }
    // Ensure the result is restored back when we return to the stub.

    if (must_handle_result) {
      Register result_reg = kReturnRegister0;
      frame_writer.PushRawValue(input_->GetRegister(result_reg.code()),
                                "callback result\n");
    } else {
      frame_writer.PushRawObject(roots.undefined_value(), "callback result\n");
    }
  }

  CHECK_EQ(translated_frame->end(), value_iterator);
  CHECK_EQ(0u, frame_writer.top_offset());

  // Clear the context register. The context might be a de-materialized object
  // and will be materialized by {Runtime_NotifyDeoptimized}. For additional
  // safety we use Smi(0) instead of the potential {arguments_marker} here.
  if (is_topmost) {
    intptr_t context_value = reinterpret_cast(Smi::kZero);
    Register context_reg = JavaScriptFrame::context_register();
    output_frame->SetRegister(context_reg.code(), context_value);
  }

  // Ensure the frame pointer register points to the callee's frame. The builtin
  // will build its own frame once we continue to it.
  Register fp_reg = JavaScriptFrame::fp_register();
  output_frame->SetRegister(fp_reg.code(), fp_value);

  Code* continue_to_builtin = isolate()->builtins()->builtin(
      TrampolineForBuiltinContinuation(mode, must_handle_result));
  output_frame->SetPc(
      static_cast(continue_to_builtin->InstructionStart()));

  Code* continuation =
      isolate()->builtins()->builtin(Builtins::kNotifyDeoptimized);
  output_frame->SetContinuation(
      static_cast(continuation->InstructionStart()));
}

void Deoptimizer::MaterializeHeapObjects() {
  translated_state_.Prepare(static_cast(stack_fp_));
  if (FLAG_deopt_every_n_times > 0) {
    // Doing a GC here will find problems with the deoptimized frames.
    isolate_->heap()->CollectAllGarbage(Heap::kNoGCFlags,
                                        GarbageCollectionReason::kTesting);
  }

  for (auto& materialization : values_to_materialize_) {
    Handle