[interpreter] Implement OSR graph construction from bytecode.

src/compiler/bytecode-graph-builder.cc

 // Copyright 2015 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/compiler/bytecode-graph-builder.h"
 
 #include "src/compiler/bytecode-branch-analysis.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/operator-properties.h"
 #include "src/interpreter/bytecodes.h"
@@ skipping 42 matching lines @@
   void UpdateControlDependency(Node* dependency) {
     control_dependency_ = dependency;
   }
 
   Node* Context() const { return context_; }
   void SetContext(Node* new_context) { context_ = new_context; }
 
   Environment* CopyForConditional() const;
   Environment* CopyForLoop();
   void Merge(Environment* other);
+  void PrepareForOsr();
 
  private:
   explicit Environment(const Environment* copy);
   void PrepareForLoop();
   bool StateValuesAreUpToDate(Node** state_values, int offset, int count,
                               int output_poke_start, int output_poke_end);
   bool StateValuesRequireUpdate(Node** state_values, int offset, int count);
   void UpdateStateValues(Node** state_values, int offset, int count);
 
   int RegisterToValuesIndex(interpreter::Register the_register) const;
@@ skipping 278 matching lines @@
   for (int i = 0; i < size; i++) {
     values()->at(i) = builder()->NewPhi(1, values()->at(i), control);
   }
 
   // Connect to the loop end.
   Node* terminate = builder()->graph()->NewNode(
       builder()->common()->Terminate(), effect, control);
   builder()->exit_controls_.push_back(terminate);
 }
 
+void BytecodeGraphBuilder::Environment::PrepareForOsr() {
+  DCHECK_EQ(IrOpcode::kLoop, GetControlDependency()->opcode());
+  DCHECK_EQ(1, GetControlDependency()->InputCount());
+  Node* start = graph()->start();
+
+  // Create a control node for the OSR entry point and merge it into the loop
+  // header. Update the current environment's control dependency accordingly.
+  Node* entry = graph()->NewNode(common()->OsrLoopEntry(), start, start);
+  Node* control = builder()->MergeControl(GetControlDependency(), entry);
+  UpdateControlDependency(control);
+
+  // Create a merge of the effect from the OSR entry and the existing effect
+  // dependency. Update the current environment's effect dependency accordingly.
+  Node* effect = builder()->MergeEffect(GetEffectDependency(), entry, control);
+  UpdateEffectDependency(effect);
+
+  // Rename all values in the environment which will extend or introduce Phi
+  // nodes to contain the OSR values available at the entry point.
+  Node* osr_context = graph()->NewNode(
+      common()->OsrValue(Linkage::kOsrContextSpillSlotIndex), entry);
+  context_ = builder()->MergeValue(context_, osr_context, control);
+  int size = static_cast<int>(values()->size());
+  for (int i = 0; i < size; i++) {
+    int idx = i;  // Indexing scheme follows {StandardFrame}, adapt accordingly.
+    if (i >= register_base()) idx += InterpreterFrameConstants::kExtraSlotCount;
+    if (i >= accumulator_base()) idx = Linkage::kOsrAccumulatorRegisterIndex;
+    Node* osr_value = graph()->NewNode(common()->OsrValue(idx), entry);
+    values_[i] = builder()->MergeValue(values_[i], osr_value, control);
+  }
+}
 
 bool BytecodeGraphBuilder::Environment::StateValuesRequireUpdate(
     Node** state_values, int offset, int count) {
   if (*state_values == nullptr) {
     return true;
   }
   DCHECK_EQ((*state_values)->InputCount(), count);
   DCHECK_LE(static_cast<size_t>(offset + count), values()->size());
   Node** env_values = (count == 0) ? nullptr : &values()->at(offset);
   for (int i = 0; i < count; i++) {
@@ skipping 69 matching lines @@
     : local_zone_(local_zone),
       jsgraph_(jsgraph),
       bytecode_array_(handle(info->shared_info()->bytecode_array())),
       exception_handler_table_(
           handle(HandlerTable::cast(bytecode_array()->handler_table()))),
       feedback_vector_(handle(info->closure()->feedback_vector())),
       frame_state_function_info_(common()->CreateFrameStateFunctionInfo(
           FrameStateType::kInterpretedFunction,
           bytecode_array()->parameter_count(),
           bytecode_array()->register_count(), info->shared_info())),
+      osr_ast_id_(info->osr_ast_id()),
       merge_environments_(local_zone),
       exception_handlers_(local_zone),
       current_exception_handler_(0),
       input_buffer_size_(0),
       input_buffer_(nullptr),
       exit_controls_(local_zone) {}
 
 Node* BytecodeGraphBuilder::GetNewTarget() {
   if (!new_target_.is_set()) {
     int params = bytecode_array()->parameter_count();
@@ skipping 54 matching lines @@
   // parameters (including the receiver) plus new target, number of arguments,
   // context and closure.
   int actual_parameter_count = bytecode_array()->parameter_count() + 4;
   graph()->SetStart(graph()->NewNode(common()->Start(actual_parameter_count)));
 
   Environment env(this, bytecode_array()->register_count(),
                   bytecode_array()->parameter_count(), graph()->start(),
                   GetFunctionContext());
   set_environment(&env);
 
+  // For OSR add an {OsrNormalEntry} as the start of the top-level environment.
+  // It will be replaced with {Dead} after typing and optimizations.
+  if (!osr_ast_id_.IsNone()) NewNode(common()->OsrNormalEntry());
+
   VisitBytecodes();
 
   // Finish the basic structure of the graph.
   DCHECK_NE(0u, exit_controls_.size());
   int const input_count = static_cast<int>(exit_controls_.size());
   Node** const inputs = &exit_controls_.front();
   Node* end = graph()->NewNode(common()->End(input_count), input_count, inputs);
   graph()->SetEnd(end);
 
   return true;
@@ skipping 852 matching lines @@
   BuildJumpIfEqual(jsgraph()->UndefinedConstant());
 }
 
 void BytecodeGraphBuilder::VisitStackCheck() {
   FrameStateBeforeAndAfter states(this);
   Node* node = NewNode(javascript()->StackCheck());
   environment()->RecordAfterState(node, &states);
 }
 
 void BytecodeGraphBuilder::VisitOsrPoll() {
-  // TODO(4764): Implement OSR graph construction. Not marked UNIMPLEMENTED to
-  // ensure the --ignition-osr flag can already be fuzzed without crashing.
+  // TODO(4764): This should be moved into the {VisitBytecodes} once we merge
+  // the polling with existing bytecode. This will also guarantee that we are
+  // not missing the OSR entry point, which we wouldn't catch right now.
+  if (osr_ast_id_.ToInt() == bytecode_iterator().current_offset()) {
+    environment()->PrepareForOsr();
+  }
 }
 
 void BytecodeGraphBuilder::VisitReturn() {
   Node* control =
       NewNode(common()->Return(), environment()->LookupAccumulator());
   MergeControlToLeaveFunction(control);
 }
 
 void BytecodeGraphBuilder::VisitDebugger() {
   FrameStateBeforeAndAfter states(this);
@@ skipping 384 matching lines @@
     // Phi does not exist yet, introduce one.
     value = NewPhi(inputs, value, control);
     value->ReplaceInput(inputs - 1, other);
   }
   return value;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8