[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());
+  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);

[Jarin, 2016/07/26 14:46:36]

Could we possibly DCHECK that the control dependency has one input at this point
to make sure that the shape is what turbofan osr deconstruction expects?
(Possibly also that the existing input is OsrNormalEntry.)

[Michael Starzinger, 2016/07/26 14:58:51]

Done. The first invariant yes, I added a check of the input count. The second
suggestion however will most likely not hold. The "normal entry" is right after
start. There will be other control between the start and the loop. All we can
guarantee is that the "normal entry" should control-dominate the first loop
entry, but that is hard to verify in a check.

+  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);
+  for (size_t i = 0; i < values_.size(); i++) {
+    int index =
+        static_cast<int>(i) + InterpreterFrameConstants::kExtraSlotCount;
+    Node* osr_value = graph()->NewNode(common()->OsrValue(index), 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