[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..957a98c3d22ec382846c29a9ee08004d937b0649
--- /dev/null
+++ b/src/compiler/bytecode-graph-builder.cc
@@ -0,0 +1,444 @@
+// 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()
+BytecodeGraphBuilder::Environment::Environment(BytecodeGraphBuilder* builder,
+                                               int locals_count,
+                                               int parameters_count,
+                                               Node* control_dependency,
+                                               Node* context)
+    : builder_(builder),
+      locals_count_(locals_count),

[Michael Starzinger, 2015/09/03 12:19:40]

nit: Wouldn't it better fit the semantics if this were called "register_count"
instead?

[oth, 2015/09/04 11:06:36]

Done.

+      parameters_count_(parameters_count),
+      context_(context),
+      control_dependency_(control_dependency),
+      effect_dependency_(control_dependency),
+      values_(builder->local_zone()) {
+  //
+  // values_ layout
+  //
+  // [parameters] [receiver] [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.

[rmcilroy, 2015/09/03 12:41:57]

nit - update comment (values are no longer pushed to the back of the array)

[oth, 2015/09/04 11:06:36]

Done.

+  //
+
+  // parameters
+  for (int i = 0; i < parameters_count; i++) {
+    const Operator* op = common()->Parameter(i, nullptr);
+    Node* parameter = builder->graph()->NewNode(op, builder->graph()->start());
+    values()->push_back(parameter);
+  }
+
+  // TODO(oth): receiver

[rmcilroy, 2015/09/03 12:41:57]

I think the receiver is just Parameter(-1), so you could probably push that as: 

 const Operator* op = common()->Parameter(-1, nullptr);
 Node* parameter = builder->graph()->NewNode(op, builder->graph()->start());
 values()->push_back(parameter);

if you want it here.

[Michael Starzinger, 2015/09/03 12:52:07]

Please use Linkage::kJSFunctionCallClosureParamIndex in that case!

[Michael Starzinger, 2015/09/03 12:55:19]

Ah, sorry, this is about reveiver, not callee ... hmm ... can we in that case
add kInterpreterReceiverParamIndex to Linkage? Magic -1 is scarry. :/

[oth, 2015/09/04 11:06:36]

Done.

+
+  // registers
+  register_base_ = static_cast<int>(values()->size());
+  Node* undefined_constant = builder->jsgraph()->UndefinedConstant();
+  values()->insert(values()->end(), locals_count, undefined_constant);
+
+  // accumulator
+  accumulator_ = undefined_constant;
+}
+
+
+int BytecodeGraphBuilder::Environment::RegisterToValuesIndex(
+    interpreter::Register the_register) const {
+  if (the_register.is_parameter()) {
+    return the_register.ToParameterIndex(parameters_count());

[rmcilroy, 2015/09/03 12:41:57]

Does this work - I think the receiver will come back as ParameterIndex '0' and
arg0 will come back as ParameterIndex '1' (so I think you need to push the
receiver into values first before the other parameters).

[oth, 2015/09/04 11:06:36]

Done.

+  } else {
+    return the_register.index() + register_base();
+  }
+}
+
+
+void BytecodeGraphBuilder::Environment::BindRegister(
+    interpreter::Register the_register, Node* node) {
+  int values_index = RegisterToValuesIndex(the_register);
+  values()->at(values_index) = node;
+}
+
+
+Node* BytecodeGraphBuilder::Environment::LookupRegister(
+    interpreter::Register the_register) const {
+  int values_index = RegisterToValuesIndex(the_register);
+  return values()->at(values_index);
+}
+
+
+void BytecodeGraphBuilder::Environment::BindAccumulator(Node* node) {
+  accumulator_ = node;
+}
+
+
+Node* BytecodeGraphBuilder::Environment::LookupAccumulator() const {
+  return accumulator_;
+}
+
+
+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),
+      input_buffer_size_(0),
+      input_buffer_(nullptr),
+      exit_controls_(local_zone) {
+  bytecode_array_ = handle(info()->shared_info()->bytecode_array());
+}
+
+
+Node* BytecodeGraphBuilder::GetFunctionContext() {
+  if (!function_context_.is_set()) {
+    // Parameter (arity + 1) is special for the outer context of the function
+    const Operator* op = common()->Parameter(
+        info()->num_parameters_including_this(), "%context");
+    Node* node = NewNode(op, graph()->start());
+    function_context_.set(node);
+  }
+  return function_context_.get();
+}
+
+
+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.
+
+  // The additional count items are for the context and closure. as

[Michael Starzinger, 2015/09/03 12:19:40]

nit: Drop trailing "as".

[oth, 2015/09/04 11:06:36]

Done.

+  int actual_parameter_count = bytecode_array()->parameter_count() + 2;
+  graph()->SetStart(graph()->NewNode(common()->Start(actual_parameter_count)));
+
+  // Locals count are the explicitly named interpreter registers.
+  int locals_count = bytecode_array()->local_count();

[Michael Starzinger, 2015/09/03 12:19:40]

nit: Likewise "register_count" here.

[oth, 2015/09/04 11:06:36]

Done.

+  Environment env(this, locals_count, actual_parameter_count, graph()->start(),
+                  GetFunctionContext());
+  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;
+}
+
+
+void BytecodeGraphBuilder::CreateGraphBody(bool stack_check) {
+  // TODO(oth): review ast-graph-builder equivalent, ie arguments

[rmcilroy, 2015/09/03 12:41:57]

nit - /s/ie/i.e.,

[oth, 2015/09/04 11:06:36]

Done.

+  // object setup, this function variable if used, tracing hooks.
+  VisitBytecodes();
+}
+
+
+void BytecodeGraphBuilder::VisitBytecodes() {
+  int last_bytecode_length = 0;
+  for (int i = 0; i < bytecode_array()->length(); i += last_bytecode_length) {

[Michael Starzinger, 2015/09/03 12:19:40]

Would it be more readable to write the loop with less local variable? I was
thinking along the lines of the following. Just a suggestion, pick whichever you
think is more readable ...

int offset = 0
while (offset < bytecode_array()->length()) {
  interpreter::Bytecode bytecode = bytecode_at(offset);
  switch (...) { ... VisitFoo(offset + 1) ... }
  offset += 1 + interpreter::Bytecodes::Size(bytecode);
}

[oth, 2015/09/04 11:06:36]

Yes, good point. Have gone with the suggestion for the BytecodeArrayIterator as
that's potentially useful elsewhere (disassembler).

+    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()->Constant(smi8_at(operand_offset));
+  environment()->BindAccumulator(node);
+}
+
+
+void BytecodeGraphBuilder::VisitLdaConstant(int operand_offset) {
+  Node* node = jsgraph()->Constant(constant_at(operand_offset));
+  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) {
+  // TODO(oth): Real frame state and environment check pointing.
+  int frame_state_count =
+      OperatorProperties::GetFrameStateInputCount(node->op());
+  for (int i = 0; i < frame_state_count; i++) {
+    NodeProperties::ReplaceFrameStateInput(node, i,
+                                           jsgraph()->EmptyFrameState());
+  }
+  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);
+}
+
+
+void BytecodeGraphBuilder::VisitLoadIC(int operand_offset) { UNIMPLEMENTED(); }
+
+
+void BytecodeGraphBuilder::VisitKeyedLoadIC(int operand_offsfet) {
+  UNIMPLEMENTED();
+}
+
+
+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) {
+      *current_input++ = environment()->Context();
+    }
+    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));
+}
+
+
+Handle<Object> BytecodeGraphBuilder::constant_at(int offset) const {
+  Handle<FixedArray> constants = handle(bytecode_array()->constant_pool());
+  int constant_index = static_cast<int8_t>(bytecode_array()->get(offset));
+  return FixedArray::get(constants, constant_index);
+}
+
+
+int8_t BytecodeGraphBuilder::smi8_at(int offset) const {
+  return static_cast<int8_t>(bytecode_array()->get(offset));
+}
+
+
+interpreter::Register BytecodeGraphBuilder::register_at(int offset) const {
+  return interpreter::Register::FromOperand(bytecode_array()->get(offset));
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8