[Interpreter] Local flow control in the 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
index 5f963770075659cb1939025cf35861bd8235407c..bf9eb1df7addf121ab4204094850f3b6ecfcb1d6 100644
--- a/src/compiler/bytecode-graph-builder.cc
+++ b/src/compiler/bytecode-graph-builder.cc
@@ -4,6 +4,7 @@
 
 #include "src/compiler/bytecode-graph-builder.h"
 
+#include "src/compiler/bytecode-basic-block-analysis.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/operator-properties.h"
 #include "src/interpreter/bytecode-array-iterator.h"
@@ -55,6 +56,21 @@ BytecodeGraphBuilder::Environment::Environment(BytecodeGraphBuilder* builder,
 }
 
 
+BytecodeGraphBuilder::Environment::Environment(
+    const BytecodeGraphBuilder::Environment* other)
+    : builder_(other->builder_),
+      register_count_(other->register_count_),
+      parameter_count_(other->parameter_count_),
+      accumulator_(other->accumulator_),
+      context_(other->context_),
+      control_dependency_(other->control_dependency_),
+      effect_dependency_(other->effect_dependency_),
+      values_(other->zone()),
+      register_base_(other->register_base_) {
+  values_ = other->values_;
+}
+
+
 int BytecodeGraphBuilder::Environment::RegisterToValuesIndex(
     interpreter::Register the_register) const {
   if (the_register.is_parameter()) {
@@ -107,12 +123,74 @@ void BytecodeGraphBuilder::Environment::MarkAsUnreachable() {
 }
 
 
+BytecodeGraphBuilder::Environment*
+BytecodeGraphBuilder::Environment::CopyForLoop() {
+  PrepareForLoop();
+  return new (zone()) Environment(this);
+}
+
+
+BytecodeGraphBuilder::Environment*
+BytecodeGraphBuilder::Environment::CopyForConditional() const {
+  return new (zone()) Environment(this);
+}
+
+
+void BytecodeGraphBuilder::Environment::Merge(
+    BytecodeGraphBuilder::Environment* other) {
+  // Nothing to do if the other environment is dead.
+  if (other->IsMarkedAsUnreachable()) {
+    return;
+  }
+
+  // Create a merge of the control dependencies of both environments and update
+  // the current environment's control dependency accordingly.
+  Node* control = builder()->MergeControl(GetControlDependency(),
+                                          other->GetControlDependency());
+  UpdateControlDependency(control);
+
+  // Create a merge of the effect dependencies of both environments and update
+  // the current environment's effect dependency accordingly.
+  Node* effect = builder()->MergeEffect(GetEffectDependency(),
+                                        other->GetEffectDependency(), control);
+  UpdateEffectDependency(effect);
+
+  // Introduce Phi nodes for values that have differing input at merge points,
+  // potentially extending an existing Phi node if possible.
+  accumulator_ =
+      builder()->MergeValue(accumulator_, other->accumulator_, control);
+  context_ = builder()->MergeValue(context_, other->context_, control);
+  for (int i = 0; i < static_cast<int>(values_.size()); i++) {
+    values_[i] = builder()->MergeValue(values_[i], other->values_[i], control);
+  }
+}
+
+
+void BytecodeGraphBuilder::Environment::PrepareForLoop() {
+  Node* control = builder()->NewLoop();
+  accumulator_ = builder()->NewPhi(1, accumulator_, control);
+  context_ = builder()->NewPhi(1, context_, control);
+
+  int size = static_cast<int>(values()->size());
+  for (int i = 0; i < size; i++) {
+    values()->at(i) = builder()->NewPhi(1, values()->at(i), control);
+  }
+  Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control);
+  UpdateEffectDependency(effect);
+
+  Node* terminate = builder()->graph()->NewNode(
+      builder()->common()->Terminate(), effect, control);
+  builder()->exit_controls_.push_back(terminate);
+}
+
+
 BytecodeGraphBuilder::BytecodeGraphBuilder(Zone* local_zone,
                                            CompilationInfo* compilation_info,
                                            JSGraph* jsgraph)
     : local_zone_(local_zone),
       info_(compilation_info),
       jsgraph_(jsgraph),
+      block_environment_infos_(local_zone),
       input_buffer_size_(0),
       input_buffer_(nullptr),
       exit_controls_(local_zone) {
@@ -241,13 +319,30 @@ bool BytecodeGraphBuilder::CreateGraph(bool stack_check) {
 void BytecodeGraphBuilder::CreateGraphBody(bool stack_check) {
   // TODO(oth): Review ast-graph-builder equivalent, i.e. arguments
   // object setup, this function variable if used, tracing hooks.
-  VisitBytecodes();
+  VisitBasicBlocks();
 }
 
 
-void BytecodeGraphBuilder::VisitBytecodes() {
+void BytecodeGraphBuilder::VisitBasicBlocks() {
+  BytecodeBasicBlockAnalysis analyzer(local_zone(), bytecode_array());
+  const ZoneVector<BytecodeBasicBlock*>* blocks = analyzer.Analyze();
+
+  block_environment_infos_.resize(blocks->size());
+  for (auto block_iter = blocks->begin(); block_iter != blocks->end();
+       block_iter++) {
+    VisitBytecodesInBasicBlock(*block_iter);
+  }
+}
+
+void BytecodeGraphBuilder::VisitBytecodesInBasicBlock(
+    BytecodeBasicBlock* block) {
+  set_basic_block(block);
+  PrepareForNewBasicBlockVisit();
+
   interpreter::BytecodeArrayIterator iterator(bytecode_array());
-  while (!iterator.done()) {
+  iterator.AdvanceToOffset(basic_block()->start());
+  while (!iterator.done() &&
+         iterator.current_offset() != basic_block()->end()) {
     switch (iterator.current_bytecode()) {
 #define BYTECODE_CASE(name, ...)       \
   case interpreter::Bytecode::k##name: \
@@ -258,6 +353,7 @@ void BytecodeGraphBuilder::VisitBytecodes() {
     }
     iterator.Advance();
   }
+  CompleteNewBasicBlockVisit();
 }
 
 
@@ -1118,85 +1214,141 @@ void BytecodeGraphBuilder::VisitToObject(
 
 void BytecodeGraphBuilder::VisitJump(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  BuildJump();
 }
 
 
 void BytecodeGraphBuilder::VisitJumpConstant(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  BuildJump();
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfTrue(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->TrueConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfTrueConstant(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->TrueConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);

[rmcilroy, 2015/12/08 13:25:07]

Please factor out the common code here into a BuildJumpIfValueEquals(Node*
comperand) helper function, and call it from
VisitJumpIfTrue/Constant/False/Null/Undefined, etc.

[oth, 2015/12/09 11:26:45]

I'd like to keep the control flow aspects and condition building separate so
these methods now look like:

Node* condition = BuildConditionForJump...
BuildConditionalJump(condition)

 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfFalse(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->FalseConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfFalseConstant(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->FalseConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfToBooleanTrue(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* to_boolean =
+      NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator);
+  Node* comperand = jsgraph()->TrueConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), to_boolean, comperand);
+  BuildConditionalJump(comparison);

[rmcilroy, 2015/12/08 13:25:07]

ditto, with a BuildJumpIfToBooleanValueEquals(...)

[oth, 2015/12/09 11:26:45]

Done.

 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfToBooleanTrueConstant(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* to_boolean =
+      NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator);
+  Node* comperand = jsgraph()->TrueConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), to_boolean, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfToBooleanFalse(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* to_boolean =
+      NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator);
+  Node* comperand = jsgraph()->FalseConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), to_boolean, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfToBooleanFalseConstant(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* to_boolean =
+      NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator);
+  Node* comperand = jsgraph()->FalseConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), to_boolean, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfNull(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->NullConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfNullConstant(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->NullConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfUndefined(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->UndefinedConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
 void BytecodeGraphBuilder::VisitJumpIfUndefinedConstant(
     const interpreter::BytecodeArrayIterator& iterator) {
-  UNIMPLEMENTED();
+  Node* accumulator = environment()->LookupAccumulator();
+  Node* comperand = jsgraph()->UndefinedConstant();
+  Node* comparison =
+      NewNode(javascript()->StrictEqual(), accumulator, comperand);
+  BuildConditionalJump(comparison);
 }
 
 
@@ -1205,6 +1357,7 @@ void BytecodeGraphBuilder::VisitReturn(
   Node* control =
       NewNode(common()->Return(), environment()->LookupAccumulator());
   UpdateControlDependencyToLeaveFunction(control);
+  BuildReturn();
 }
 
 
@@ -1226,6 +1379,119 @@ void BytecodeGraphBuilder::VisitForInDone(
 }
 
 
+void BytecodeGraphBuilder::PrepareForNewBasicBlockVisit() {

[rmcilroy, 2015/12/08 13:25:07]

nit - I would drop the "new" here, but don't really mind if you want to keep it.

[oth, 2015/12/09 11:26:45]

Done.

+  int block_id = basic_block()->rpo_id();
+
+  DCHECK_NULL(block_environment_infos_[block_id]);
+  block_environment_infos_[block_id] =
+      new (local_zone()) BlockEnvironmentInfo();
+
+  // Count number of forward and back links to this block
+  int back_edges = 0;
+
+  // Merge forward links and check for backwards edges
+  bool default_done = false;
+  for (size_t i = 0; i < basic_block()->incoming_count(); i++) {
+    const BytecodeBasicBlock* incoming = basic_block()->incoming(i);
+    if (incoming->is_dominated_by(basic_block())) {
+      back_edges++;
+    } else {
+      Environment* preceding_environment;
+      if (incoming->if_true() == basic_block()) {
+        preceding_environment =
+            block_environment_infos_[incoming->rpo_id()]->if_true_environment();
+      } else {
+        DCHECK_EQ(incoming->if_false(), basic_block());
+        preceding_environment = block_environment_infos_[incoming->rpo_id()]
+                                    ->if_false_environment();
+      }
+
+      DCHECK_NOT_NULL(preceding_environment);
+      if (default_done) {

[rmcilroy, 2015/12/08 13:25:07]

Could you get rid of the default_done boolean by adding a
DCHECK_NULL(environment()) at the top of this function, and then doing: 
  if (environment()) {
    environment()->Merge(preceding_environment);
  } else {
    set_environment(preceding_environment);
  }

If this doesn't work, could you rename "default_done" to something else (the
"default" is a bit confusing to me since it makes me think this incoming path
has some kind of special control flow or something).

[oth, 2015/12/09 11:26:45]

Done.

+        environment()->Merge(preceding_environment);
+      } else {
+        set_environment(preceding_environment);
+        default_done = true;
+      }
+    }
+  }
+
+  if (back_edges) {

[rmcilroy, 2015/12/08 13:25:07]

nit - back_edges != 0

[oth, 2015/12/09 11:26:45]

Done.

+    Environment* loop_env = environment()->CopyForLoop();
+    block_environment_infos_[block_id]->set_loop_header_environment(loop_env);
+  }
+}
+
+
+void BytecodeGraphBuilder::CompleteNewBasicBlockVisit() {

[rmcilroy, 2015/12/08 13:25:07]

ditto

[oth, 2015/12/09 11:26:45]

Done.

+  if (!basic_block()->is_exit()) {
+    int last_offset = basic_block()->last_bytecode_offset();
+    interpreter::Bytecode last_bytecode =
+        interpreter::Bytecodes::FromByte(bytecode_array()->get(last_offset));
+    if (!interpreter::Bytecodes::IsLocalControlFlow(last_bytecode)) {

[rmcilroy, 2015/12/08 13:25:08]

Could you do the IsLocalControlFlow check in the bytecode analyzer and add a
flag for it on the basic_block?

[oth, 2015/12/09 11:26:45]

Done.

+      DCHECK_NOT_NULL(basic_block()->if_true());
+      DCHECK_NULL(basic_block()->if_false());
+      DCHECK(basic_block()->if_true() != nullptr);
+      DCHECK_NOT_NULL(environment());

[rmcilroy, 2015/12/08 13:25:08]

Should environment not always be non-null at this point? Could we move this
DCHECK out of the conditinoals to the start of the function?

[oth, 2015/12/09 11:26:45]

Change to make the invariant true.

+      int block_id = basic_block()->rpo_id();
+      block_environment_infos_[block_id]->set_if_true_environment(
+          environment());
+      BuildBackEdgeIfRequired(basic_block()->if_true());

[rmcilroy, 2015/12/08 13:25:07]

Would be good to have a comment here one why what appears to be a fallthrough
basic block might actually be a back edge from the point of view of the TF graph
due to loop headers 

[oth, 2015/12/09 11:26:45]

Done.

+    }
+  }
+  set_environment(nullptr);
+}
+
+
+void BytecodeGraphBuilder::BuildReturn() {
+  DCHECK_NOT_NULL(basic_block()->if_true());
+  DCHECK_NULL(basic_block()->if_false());
+  int block_id = basic_block()->rpo_id();
+  block_environment_infos_[block_id]->set_if_true_environment(environment());
+  set_environment(nullptr);
+}
+
+
+void BytecodeGraphBuilder::BuildBackEdgeIfRequired(BytecodeBasicBlock* target) {

[rmcilroy, 2015/12/08 13:25:07]

nit - move above BuildReturn (group BuildReturn / Jump / etc.)

[oth, 2015/12/09 11:26:45]

Done.

+  if (basic_block()->is_dominated_by(target)) {
+    BytecodeBasicBlock* loop_header = target;
+    BlockEnvironmentInfo* info =
+        block_environment_infos_[loop_header->rpo_id()];
+    info->loop_header_environment()->Merge(environment());
+  }
+}
+
+
+void BytecodeGraphBuilder::BuildJump() {
+  DCHECK_NOT_NULL(basic_block()->if_true());
+  DCHECK_NULL(basic_block()->if_false());
+  int block_id = basic_block()->rpo_id();
+  block_environment_infos_[block_id]->set_if_true_environment(environment());
+  BuildBackEdgeIfRequired(basic_block()->if_true());
+  set_environment(nullptr);
+}
+
+
+void BytecodeGraphBuilder::BuildConditionalJump(Node* condition) {
+  DCHECK_NOT_NULL(basic_block()->if_true());
+  DCHECK_NOT_NULL(basic_block()->if_false());
+  int block_id = basic_block()->rpo_id();
+  NewBranch(condition);
+  // Save environment for false branch.
+  Environment* saved_env = environment()->CopyForConditional();
+  // Process true branch.
+  NewIfTrue();
+  block_environment_infos_[block_id]->set_if_true_environment(environment());
+  BuildBackEdgeIfRequired(basic_block()->if_true());
+  // Restore environment and process false branch.
+  set_environment(saved_env);
+  NewIfFalse();
+  block_environment_infos_[block_id]->set_if_false_environment(environment());
+  BuildBackEdgeIfRequired(basic_block()->if_false());
+  set_environment(nullptr);
+}
+
+
 Node** BytecodeGraphBuilder::EnsureInputBufferSize(int size) {
   if (size > input_buffer_size_) {
     size = size + kInputBufferSizeIncrement + input_buffer_size_;
@@ -1298,6 +1564,26 @@ Node* BytecodeGraphBuilder::MakeNode(const Operator* op, int value_input_count,
 }
 
 
+Node* BytecodeGraphBuilder::NewPhi(int count, Node* input, Node* control) {
+  const Operator* phi_op = common()->Phi(kMachAnyTagged, count);
+  Node** buffer = EnsureInputBufferSize(count + 1);
+  MemsetPointer(buffer, input, count);
+  buffer[count] = control;
+  return graph()->NewNode(phi_op, count + 1, buffer, true);
+}
+
+
+// TODO(mstarzinger): Revisit this once we have proper effect states.
+Node* BytecodeGraphBuilder::NewEffectPhi(int count, Node* input,
+                                         Node* control) {
+  const Operator* phi_op = common()->EffectPhi(count);
+  Node** buffer = EnsureInputBufferSize(count + 1);
+  MemsetPointer(buffer, input, count);
+  buffer[count] = control;
+  return graph()->NewNode(phi_op, count + 1, buffer, true);
+}
+
+
 Node* BytecodeGraphBuilder::MergeControl(Node* control, Node* other) {
   int inputs = control->op()->ControlInputCount() + 1;
   if (control->opcode() == IrOpcode::kLoop) {
@@ -1320,6 +1606,40 @@ Node* BytecodeGraphBuilder::MergeControl(Node* control, Node* other) {
 }
 
 
+Node* BytecodeGraphBuilder::MergeEffect(Node* value, Node* other,
+                                        Node* control) {
+  int inputs = control->op()->ControlInputCount();
+  if (value->opcode() == IrOpcode::kEffectPhi &&
+      NodeProperties::GetControlInput(value) == control) {
+    // Phi already exists, add input.
+    value->InsertInput(graph_zone(), inputs - 1, other);
+    NodeProperties::ChangeOp(value, common()->EffectPhi(inputs));
+  } else if (value != other) {
+    // Phi does not exist yet, introduce one.
+    value = NewEffectPhi(inputs, value, control);
+    value->ReplaceInput(inputs - 1, other);
+  }
+  return value;
+}
+
+
+Node* BytecodeGraphBuilder::MergeValue(Node* value, Node* other,
+                                       Node* control) {
+  int inputs = control->op()->ControlInputCount();
+  if (value->opcode() == IrOpcode::kPhi &&
+      NodeProperties::GetControlInput(value) == control) {
+    // Phi already exists, add input.
+    value->InsertInput(graph_zone(), inputs - 1, other);
+    NodeProperties::ChangeOp(value, common()->Phi(kMachAnyTagged, inputs));
+  } else if (value != other) {
+    // Phi does not exist yet, introduce one.
+    value = NewPhi(inputs, value, control);
+    value->ReplaceInput(inputs - 1, other);
+  }
+  return value;
+}
+
+
 void BytecodeGraphBuilder::UpdateControlDependencyToLeaveFunction(Node* exit) {
   if (environment()->IsMarkedAsUnreachable()) return;
   environment()->MarkAsUnreachable();