[Interpreter] Bytecode graph builder

src/compiler/bytecode-graph-builder.cc

Index: src/compiler/bytecode-graph-builder.cc
diff --git a/src/compiler/bytecode-graph-builder.cc b/src/compiler/bytecode-graph-builder.cc
new file mode 100644
index 0000000000000000000000000000000000000000..192173e8fc1edf5e4a7b4b5e33b01705929110c7
--- /dev/null
+++ b/src/compiler/bytecode-graph-builder.cc
@@ -0,0 +1,434 @@
+// 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/operator-properties.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// Issues:
+// - Need to deal with FrameState / FrameStateBeforeAndAfter / StateValue.
+// - Scopes - intimately tied to AST. Need to eval what is needed.
+// - Need story for context parameter, closure parameter, this.
+//   * GetFunctionClosureForContext()
+//   * GetFunctionClosure()
+//   * GetFunctionContext()
+//
+// NB Nodes talk slides: http://shortn/_fmVf0TjCC4

[rmcilroy, 2015/09/01 14:00:06]

nit - probably remove the internal talk link

[oth, 2015/09/01 15:25:57]

Done.

+
+BytecodeGraphBuilder::Environment::Environment(BytecodeGraphBuilder* builder,
+                                               int locals_count,
+                                               Node* control_dependency)
+    : builder_(builder),
+      locals_count_(locals_count),
+      control_dependency_(control_dependency),
+      effect_dependency_(control_dependency),
+      values_(builder->local_zone()) {
+  //
+  // values_ layout
+  //
+  // [parameters] [receiver] [registers] [accumulator] [old registers]
+  //
+  // The accumulator is treated as a bytecode register. As values are
+  // overwritten, the old values are pushed to the back of the values
+  // array.
+  //
+  // TODO(oth): add support for parameters
+  //
+  register_base_ = values()->size();
+  Node* undefined_constant = builder->jsgraph()->UndefinedConstant();
+
+  values()->insert(values()->end(), locals_count, undefined_constant);
+  values()->push_back(undefined_constant);

[rmcilroy, 2015/09/01 14:00:06]

nit - comment that this is the accumulator

[oth, 2015/09/01 15:25:57]

Moved accumulator out of values per later review comment.

+}
+
+
+void BytecodeGraphBuilder::Environment::BindRegister(size_t register_index,
+                                                     Node* node) {
+  size_t values_index = register_index + register_base();
+  values()->push_back(values()->at(values_index));

[rmcilroy, 2015/09/01 14:00:06]

Do we need to keep the old register values around (e.g., here where we are
pushing back the existing Node* for the register to the end of the vector before
replacing it with the new node)? Seems like we should be OK just dropping them
on the floor since we won't need them after this point.

[oth, 2015/09/01 15:25:57]

Done.

+  values()->at(values_index) = node;
+}
+
+
+Node* BytecodeGraphBuilder::Environment::LookupRegister(
+    size_t register_index) const {
+  size_t values_index = register_index + register_base();
+  return values()->at(values_index);
+}
+
+
+void BytecodeGraphBuilder::Environment::BindAccumulator(Node* node) {
+  BindRegister(accumulator_pseudo_register(), node);

[rmcilroy, 2015/09/01 14:00:06]

nit - could we just have a separate Node* accumulator_ in the Environment rather
than a accumulator_pseudo_register which points to a location in values to make
things a bit clearer?

[oth, 2015/09/01 15:25:57]

Done.

+}
+
+
+Node* BytecodeGraphBuilder::Environment::LookupAccumulator() const {
+  return LookupRegister(accumulator_pseudo_register());
+}
+
+
+bool BytecodeGraphBuilder::Environment::IsMarkedAsUnreachable() const {
+  return GetControlDependency()->opcode() == IrOpcode::kDead;
+}
+
+
+void BytecodeGraphBuilder::Environment::MarkAsUnreachable() {
+  UpdateControlDependency(builder()->jsgraph()->Dead());
+}
+
+
+BytecodeGraphBuilder::BytecodeGraphBuilder(Zone* local_zone,
+                                           CompilationInfo* compilation_info,
+                                           JSGraph* jsgraph)
+    : local_zone_(local_zone),
+      info_(compilation_info),
+      jsgraph_(jsgraph),
+      exit_controls_(local_zone) {
+  bytecode_array_ = handle(info()->shared_info()->bytecode_array());
+}
+
+
+BytecodeGraphBuilder::BytecodeGraphBuilder(Zone* local_zone,
+                                           Handle<BytecodeArray> bytecode_array,
+                                           JSGraph* jsgraph)
+    : local_zone_(local_zone),
+      info_(nullptr),
+      jsgraph_(jsgraph),
+      bytecode_array_(bytecode_array),
+      input_buffer_size_(0),
+      input_buffer_(nullptr),
+      exit_controls_(local_zone) {}
+
+
+bool BytecodeGraphBuilder::CreateGraph(bool stack_check) {
+  // Set up the basic structure of the graph. Outputs for {Start} are
+  // the formal parameters (including the receiver) plus context and
+  // closure.
+
+  int actual_parameter_count = info()->num_parameters_including_this() + 2;
+  graph()->SetStart(graph()->NewNode(common()->Start(actual_parameter_count)));
+
+  // Locals count are the explicitly named interpreter registers.
+  int locals_count = bytecode_array()->frame_size() / kPointerSize;

[rmcilroy, 2015/09/01 14:00:06]

optional nit - you could add a locals_count() helper on BytecodeArray object for
this if you like. 

[oth, 2015/09/01 15:25:57]

Done.

+  Environment env(this, locals_count, graph()->start());
+  set_environment(&env);
+
+  // Build function context only if there are context allocated variables.
+  if (info()->num_heap_slots() > 0) {
+    UNIMPLEMENTED();  // write ast-graph-builder equivalent.
+  } else {
+    // Simply use the outer function context in building the graph.
+    CreateGraphBody(stack_check);
+  }
+
+  // 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;
+}
+
+
+bool BytecodeGraphBuilder::CreateGraphForTest(bool stack_check) {
+  // Set up the basic structure of the graph. Outputs for {Start} are
+  // the formal parameters (including the receiver) plus context and
+  // closure.
+  int actual_parameter_count =
+      /* info()->num_parameters_including_this() */ 0 + 2;
+  graph()->SetStart(graph()->NewNode(common()->Start(actual_parameter_count)));
+
+  // Locals count are the explicitly named interpreter registers.
+  int locals_count = bytecode_array()->frame_size() / kPointerSize;
+  Environment env(this, locals_count, graph()->start());
+  set_environment(&env);
+
+  // Build function context only if there are context allocated variables.
+  // - Assume no context allocated variables.
+  // Simply use the outer function context in building the graph.
+  CreateGraphBody(stack_check);
+
+  // 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;
+}
+
+
+void BytecodeGraphBuilder::CreateGraphBody(bool stack_check) {
+  // TODO(oth): write ast-graph-builder equivalent.

[rmcilroy, 2015/09/01 14:00:06]

not sure what this TODO means, could you add more detail or remove the TODO if
it's no longer applicable

[oth, 2015/09/01 15:25:57]

Done.

+  VisitBytecodes();
+}
+
+
+void BytecodeGraphBuilder::VisitBytecodes() {
+  int last_bytecode_length = 0;
+  for (int i = 0; i < bytecode_array()->length(); i += last_bytecode_length) {
+    interpreter::Bytecode bytecode = bytecode_at(i);
+    int operand_offset = i + 1;
+    switch (bytecode) {
+#define BYTECODE_CASE(name, ...)       \
+  case interpreter::Bytecode::k##name: \
+    Visit##name(operand_offset);       \
+    break;
+      BYTECODE_LIST(BYTECODE_CASE)
+#undef BYTECODE_CODE
+    }
+    last_bytecode_length = interpreter::Bytecodes::Size(bytecode);
+  }
+}
+
+
+void BytecodeGraphBuilder::VisitLdaZero(int operand_offset) {
+  Node* node = jsgraph()->ZeroConstant();
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaSmi8(int operand_offset) {
+  Node* node = jsgraph()->Int32Constant(smi8_at(operand_offset));
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaConstant(int operand_offset) {
+  Handle<FixedArray> constants = handle(bytecode_array()->constant_pool());
+  Handle<Object> constant = FixedArray::get(constants, operand_offset);

[rmcilroy, 2015/09/01 14:00:06]

nit - create a helper for getting a given constant?

[oth, 2015/09/01 15:25:57]

Done. Noticed this code is broken anyway - it needs to get the operand at
operand_offset and use that as the index into the constants. Will write test.

+  Node* node = jsgraph()->Constant(constant);
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaUndefined(int operand_offset) {
+  Node* node = jsgraph()->UndefinedConstant();
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaNull(int operand_offset) {
+  Node* node = jsgraph()->NullConstant();
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaTheHole(int operand_offset) {
+  Node* node = jsgraph()->TheHoleConstant();
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaTrue(int operand_offset) {
+  Node* node = jsgraph()->TrueConstant();
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaFalse(int operand_offset) {
+  Node* node = jsgraph()->FalseConstant();
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdar(int operand_offset) {
+  Node* value = environment()->LookupRegister(register_at(operand_offset));
+  environment()->BindAccumulator(value);
+}
+
+
+void BytecodeGraphBuilder::VisitStar(int operand_offset) {
+  Node* value = environment()->LookupAccumulator();
+  environment()->BindRegister(register_at(operand_offset), value);
+}
+
+
+void BytecodeGraphBuilder::FinishBinaryOperation(Node* node) {
+  // What is the minimal work here?
+  // In the initial absence of:
+  // - FrameStateBeforeAndAfter / BailOutId
+  // - Environment check pointing
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitAdd(int operand_offset) {
+  const Operator* js_op = javascript()->Add(language_mode());
+  Node* left = environment()->LookupRegister(register_at(operand_offset));
+  Node* right = environment()->LookupAccumulator();
+  Node* node = NewNode(js_op, left, right);
+  FinishBinaryOperation(node);
+}
+
+
+void BytecodeGraphBuilder::VisitSub(int operand_offset) {
+  const Operator* js_op = javascript()->Subtract(language_mode());
+  Node* left = environment()->LookupRegister(register_at(operand_offset));
+  Node* right = environment()->LookupAccumulator();
+  Node* node = NewNode(js_op, left, right);
+  FinishBinaryOperation(node);
+}
+
+
+void BytecodeGraphBuilder::VisitMul(int operand_offset) {
+  const Operator* js_op = javascript()->Multiply(language_mode());
+  Node* left = environment()->LookupRegister(register_at(operand_offset));
+  Node* right = environment()->LookupAccumulator();
+  Node* node = NewNode(js_op, left, right);
+  FinishBinaryOperation(node);
+}
+
+
+void BytecodeGraphBuilder::VisitDiv(int operand_offset) {
+  const Operator* js_op = javascript()->Divide(language_mode());
+  Node* left = environment()->LookupRegister(register_at(operand_offset));
+  Node* right = environment()->LookupAccumulator();
+  Node* node = NewNode(js_op, left, right);
+  FinishBinaryOperation(node);
+}
+
+
+void BytecodeGraphBuilder::VisitMod(int operand_offset) {
+  const Operator* js_op = javascript()->Modulus(language_mode());
+  Node* left = environment()->LookupRegister(register_at(operand_offset));
+  Node* right = environment()->LookupAccumulator();
+  Node* node = NewNode(js_op, left, right);
+  FinishBinaryOperation(node);
+}
+
+
+void BytecodeGraphBuilder::VisitReturn(int operand_offset) {
+  Node* control =
+      NewNode(common()->Return(), environment()->LookupAccumulator());
+  UpdateControlDependencyToLeaveFunction(control);
+}
+
+
+Node** BytecodeGraphBuilder::EnsureInputBufferSize(int size) {
+  if (size > input_buffer_size_) {
+    size = size + kInputBufferSizeIncrement + input_buffer_size_;
+    input_buffer_ = local_zone()->NewArray<Node*>(size);
+    input_buffer_size_ = size;
+  }
+  return input_buffer_;
+}
+
+
+Node* BytecodeGraphBuilder::MakeNode(const Operator* op, int value_input_count,
+                                     Node** value_inputs, bool incomplete) {
+  DCHECK_EQ(op->ValueInputCount(), value_input_count);
+
+  bool has_context = OperatorProperties::HasContextInput(op);
+  int frame_state_count = OperatorProperties::GetFrameStateInputCount(op);
+  bool has_control = op->ControlInputCount() == 1;
+  bool has_effect = op->EffectInputCount() == 1;
+
+  DCHECK_LT(op->ControlInputCount(), 2);
+  DCHECK_LT(op->EffectInputCount(), 2);
+
+  Node* result = NULL;
+  if (!has_context && frame_state_count == 0 && !has_control && !has_effect) {
+    result = graph()->NewNode(op, value_input_count, value_inputs, incomplete);
+  } else {
+    int input_count_with_deps = value_input_count;
+    if (has_context) ++input_count_with_deps;
+    input_count_with_deps += frame_state_count;
+    if (has_control) ++input_count_with_deps;
+    if (has_effect) ++input_count_with_deps;
+    Node** buffer = EnsureInputBufferSize(input_count_with_deps);
+    memcpy(buffer, value_inputs, kPointerSize * value_input_count);
+    Node** current_input = buffer + value_input_count;
+    if (has_context) {
+      // TODO(oth): need context.
+      *current_input++ = jsgraph()->Dead();
+    }
+    for (int i = 0; i < frame_state_count; i++) {
+      // The frame state will be inserted later. Here we misuse
+      // the {Dead} node as a sentinel to be later overwritten
+      // with the real frame state.
+      *current_input++ = jsgraph()->Dead();
+    }
+    if (has_effect) {
+      *current_input++ = environment()->GetEffectDependency();
+    }
+    if (has_control) {
+      *current_input++ = environment()->GetControlDependency();
+    }
+    result = graph()->NewNode(op, input_count_with_deps, buffer, incomplete);
+    if (!environment()->IsMarkedAsUnreachable()) {
+      // Update the current control dependency for control-producing nodes.
+      if (NodeProperties::IsControl(result)) {
+        environment()->UpdateControlDependency(result);
+      }
+      // Update the current effect dependency for effect-producing nodes.
+      if (result->op()->EffectOutputCount() > 0) {
+        environment()->UpdateEffectDependency(result);
+      }
+      // Add implicit success continuation for throwing nodes.
+      if (!result->op()->HasProperty(Operator::kNoThrow)) {
+        const Operator* op = common()->IfSuccess();
+        Node* on_success = graph()->NewNode(op, result);
+        environment_->UpdateControlDependency(on_success);
+      }
+    }
+  }
+
+  return result;
+}
+
+
+Node* BytecodeGraphBuilder::MergeControl(Node* control, Node* other) {
+  int inputs = control->op()->ControlInputCount() + 1;
+  if (control->opcode() == IrOpcode::kLoop) {
+    // Control node for loop exists, add input.
+    const Operator* op = common()->Loop(inputs);
+    control->AppendInput(graph_zone(), other);
+    control->set_op(op);
+  } else if (control->opcode() == IrOpcode::kMerge) {
+    // Control node for merge exists, add input.
+    const Operator* op = common()->Merge(inputs);
+    control->AppendInput(graph_zone(), other);
+    control->set_op(op);
+  } else {
+    // Control node is a singleton, introduce a merge.
+    const Operator* op = common()->Merge(inputs);
+    Node* inputs[] = {control, other};
+    control = graph()->NewNode(op, arraysize(inputs), inputs, true);
+  }
+  return control;
+}
+
+
+void BytecodeGraphBuilder::UpdateControlDependencyToLeaveFunction(Node* exit) {
+  if (environment()->IsMarkedAsUnreachable()) return;
+  environment()->MarkAsUnreachable();
+  exit_controls_.push_back(exit);
+}
+
+
+interpreter::Bytecode BytecodeGraphBuilder::bytecode_at(int offset) const {
+  return interpreter::Bytecodes::FromByte(bytecode_array()->get(offset));
+}
+
+
+int8_t BytecodeGraphBuilder::smi8_at(int offset) const {
+  return static_cast<int8_t>(bytecode_array()->get(offset));
+}
+
+
+int8_t BytecodeGraphBuilder::register_at(int offset) const {
+  return static_cast<int8_t>(-bytecode_array()->get(offset));
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8