[turbofan] Put StructuredGraphBuilder out of its misery and merge its remnants back into the AstGra…

src/compiler/ast-graph-builder.cc

 // Copyright 2014 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/ast-graph-builder.h"
 
 #include "src/compiler.h"
 #include "src/compiler/ast-loop-assignment-analyzer.h"
 #include "src/compiler/control-builders.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/machine-operator.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/operator-properties.h"
 #include "src/full-codegen.h"
 #include "src/parser.h"
 #include "src/scopes.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
+
 AstGraphBuilder::AstGraphBuilder(Zone* local_zone, CompilationInfo* info,
                                  JSGraph* jsgraph, LoopAssignmentAnalysis* loop)
-    : StructuredGraphBuilder(jsgraph->isolate(), local_zone, jsgraph->graph(),
-                             jsgraph->common()),
+    : local_zone_(local_zone),
       info_(info),
       jsgraph_(jsgraph),
+      environment_(nullptr),
+      ast_context_(nullptr),
       globals_(0, local_zone),
-      breakable_(NULL),
-      execution_context_(NULL),
+      breakable_(nullptr),
+      execution_context_(nullptr),
+      input_buffer_size_(0),
+      input_buffer_(nullptr),
+      current_context_(nullptr),
+      exit_control_(nullptr),
       loop_assignment_analysis_(loop) {
   InitializeAstVisitor(info->isolate(), local_zone);
 }
 
 
 Node* AstGraphBuilder::GetFunctionClosure() {
   if (!function_closure_.is_set()) {
     const Operator* op =
         common()->Parameter(Linkage::kJSFunctionCallClosureParamIndex);
     Node* node = NewNode(op, graph()->start());
@@ skipping 102 matching lines @@
   Property* property = expr->AsProperty();
   DCHECK(expr->IsValidReferenceExpression());
   LhsKind lhs_kind =
       (property == NULL) ? VARIABLE : (property->key()->IsPropertyName())
                                           ? NAMED_PROPERTY
                                           : KEYED_PROPERTY;
   return lhs_kind;
 }
 
 
-StructuredGraphBuilder::Environment* AstGraphBuilder::CopyEnvironment(
-    StructuredGraphBuilder::Environment* env) {
-  return new (zone()) Environment(*reinterpret_cast<Environment*>(env));
-}
-
-
 AstGraphBuilder::Environment::Environment(AstGraphBuilder* builder,
                                           Scope* scope,
                                           Node* control_dependency)
-    : StructuredGraphBuilder::Environment(builder, control_dependency),
+    : builder_(builder),
       parameters_count_(scope->num_parameters() + 1),
       locals_count_(scope->num_stack_slots()),
-      parameters_node_(NULL),
-      locals_node_(NULL),
-      stack_node_(NULL) {
+      values_(builder_->local_zone()),
+      control_dependency_(control_dependency),
+      effect_dependency_(control_dependency),
+      parameters_node_(nullptr),
+      locals_node_(nullptr),
+      stack_node_(nullptr) {
   DCHECK_EQ(scope->num_parameters() + 1, parameters_count());
 
   // Bind the receiver variable.
   Node* receiver = builder->graph()->NewNode(common()->Parameter(0),
                                              builder->graph()->start());
   values()->push_back(receiver);
 
   // Bind all parameter variables. The parameter indices are shifted by 1
   // (receiver is parameter index -1 but environment index 0).
   for (int i = 0; i < scope->num_parameters(); ++i) {
     Node* parameter = builder->graph()->NewNode(common()->Parameter(i + 1),
                                                 builder->graph()->start());
     values()->push_back(parameter);
   }
 
   // Bind all local variables to undefined.
   Node* undefined_constant = builder->jsgraph()->UndefinedConstant();
   values()->insert(values()->end(), locals_count(), undefined_constant);
 }
 
 
-AstGraphBuilder::Environment::Environment(const Environment& copy)
-    : StructuredGraphBuilder::Environment(
-          static_cast<StructuredGraphBuilder::Environment>(copy)),
-      parameters_count_(copy.parameters_count_),
-      locals_count_(copy.locals_count_),
-      parameters_node_(copy.parameters_node_),
-      locals_node_(copy.locals_node_),
-      stack_node_(copy.stack_node_) {}
+AstGraphBuilder::Environment::Environment(
+    const AstGraphBuilder::Environment* copy)
+    : builder_(copy->builder_),
+      parameters_count_(copy->parameters_count_),
+      locals_count_(copy->locals_count_),
+      values_(copy->zone()),
+      control_dependency_(copy->control_dependency_),
+      effect_dependency_(copy->effect_dependency_),
+      parameters_node_(copy->parameters_node_),
+      locals_node_(copy->locals_node_),
+      stack_node_(copy->stack_node_) {
+  const size_t kStackEstimate = 7;  // optimum from experimentation!
+  values_.reserve(copy->values_.size() + kStackEstimate);
+  values_.insert(values_.begin(), copy->values_.begin(), copy->values_.end());
+}
 
 
 void AstGraphBuilder::Environment::UpdateStateValues(Node** state_values,
                                                      int offset, int count) {
   bool should_update = false;
   Node** env_values = (count == 0) ? NULL : &values()->at(offset);
   if (*state_values == NULL || (*state_values)->InputCount() != count) {
     should_update = true;
   } else {
     DCHECK(static_cast<size_t>(offset + count) <= values()->size());
@@ skipping 14 matching lines @@
 Node* AstGraphBuilder::Environment::Checkpoint(
     BailoutId ast_id, OutputFrameStateCombine combine) {
   UpdateStateValues(&parameters_node_, 0, parameters_count());
   UpdateStateValues(&locals_node_, parameters_count(), locals_count());
   UpdateStateValues(&stack_node_, parameters_count() + locals_count(),
                     stack_height());
 
   const Operator* op = common()->FrameState(JS_FRAME, ast_id, combine);
 
   return graph()->NewNode(op, parameters_node_, locals_node_, stack_node_,
-                          GetContext(),
+                          builder()->current_context(),
                           builder()->jsgraph()->UndefinedConstant());
 }
 
 
 AstGraphBuilder::AstContext::AstContext(AstGraphBuilder* own,
                                         Expression::Context kind)
     : kind_(kind), owner_(own), outer_(own->ast_context()) {
   owner()->set_ast_context(this);  // Push.
 #ifdef DEBUG
   original_height_ = environment()->stack_height();
@@ skipping 268 matching lines @@
   compare_if.If(condition);
   compare_if.Then();
   Visit(stmt->then_statement());
   compare_if.Else();
   Visit(stmt->else_statement());
   compare_if.End();
 }
 
 
 void AstGraphBuilder::VisitContinueStatement(ContinueStatement* stmt) {
-  StructuredGraphBuilder::Environment* env = environment()->CopyAsUnreachable();
+  Environment* env = environment()->CopyAsUnreachable();
   breakable()->ContinueTarget(stmt->target());
   set_environment(env);
 }
 
 
 void AstGraphBuilder::VisitBreakStatement(BreakStatement* stmt) {
-  StructuredGraphBuilder::Environment* env = environment()->CopyAsUnreachable();
+  Environment* env = environment()->CopyAsUnreachable();
   breakable()->BreakTarget(stmt->target());
   set_environment(env);
 }
 
 
 void AstGraphBuilder::VisitReturnStatement(ReturnStatement* stmt) {
   VisitForValue(stmt->expression());
   Node* result = environment()->Pop();
   Node* control = NewNode(common()->Return(), result);
   UpdateControlDependencyToLeaveFunction(control);
@@ skipping 1399 matching lines @@
   }
   Node* value = NewNode(op, arity, all);
   return value;
 }
 
 
 Node* AstGraphBuilder::BuildPatchReceiverToGlobalProxy(Node* receiver) {
   // Sloppy mode functions and builtins need to replace the receiver with the
   // global proxy when called as functions (without an explicit receiver
   // object). Otherwise there is nothing left to do here.
-  if (info()->strict_mode() != SLOPPY || info()->is_native()) return receiver;
+  if (strict_mode() != SLOPPY || info()->is_native()) return receiver;
 
   // There is no need to perform patching if the receiver is never used. Note
   // that scope predicates are purely syntactical, a call to eval might still
   // inspect the receiver value.
   if (!info()->scope()->uses_this() && !info()->scope()->inner_uses_this() &&
       !info()->scope()->calls_sloppy_eval()) {
     return receiver;
   }
 
   IfBuilder receiver_check(this);
@@ skipping 473 matching lines @@
   }
 }
 
 
 BitVector* AstGraphBuilder::GetVariablesAssignedInLoop(
     IterationStatement* stmt) {
   if (loop_assignment_analysis_ == NULL) return NULL;
   return loop_assignment_analysis_->GetVariablesAssignedInLoop(stmt);
 }
 
+
+Node** AstGraphBuilder::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* AstGraphBuilder::MakeNode(const Operator* op, int value_input_count,
+                                Node** value_inputs, bool incomplete) {
+  DCHECK(op->ValueInputCount() == value_input_count);
+
+  bool has_context = OperatorProperties::HasContextInput(op);
+  bool has_framestate = OperatorProperties::HasFrameStateInput(op);
+  bool has_control = op->ControlInputCount() == 1;
+  bool has_effect = op->EffectInputCount() == 1;
+
+  DCHECK(op->ControlInputCount() < 2);
+  DCHECK(op->EffectInputCount() < 2);
+
+  Node* result = NULL;
+  if (!has_context && !has_framestate && !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;
+    if (has_framestate) ++input_count_with_deps;
+    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++ = current_context();
+    }
+    if (has_framestate) {
+      // The frame state will be inserted later. Here we misuse
+      // the dead_control node as a sentinel to be later overwritten
+      // with the real frame state.
+      *current_input++ = dead_control();
+    }
+    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 (has_effect) {
+      environment_->UpdateEffectDependency(result);
+    }
+    if (result->op()->ControlOutputCount() > 0 &&
+        !environment()->IsMarkedAsUnreachable()) {
+      environment_->UpdateControlDependency(result);
+    }
+  }
+
+  return result;
+}
+
+
+void AstGraphBuilder::UpdateControlDependencyToLeaveFunction(Node* exit) {
+  if (environment()->IsMarkedAsUnreachable()) return;
+  if (exit_control() != NULL) {
+    exit = MergeControl(exit_control(), exit);
+  }
+  environment()->MarkAsUnreachable();
+  set_exit_control(exit);
+}
+
+
+void AstGraphBuilder::Environment::Merge(Environment* other) {
+  DCHECK(values_.size() == other->values_.size());
+
+  // Nothing to do if the other environment is dead.
+  if (other->IsMarkedAsUnreachable()) return;
+
+  // Resurrect a dead environment by copying the contents of the other one and
+  // placing a singleton merge as the new control dependency.
+  if (this->IsMarkedAsUnreachable()) {
+    Node* other_control = other->control_dependency_;
+    Node* inputs[] = {other_control};
+    control_dependency_ =
+        graph()->NewNode(common()->Merge(1), arraysize(inputs), inputs, true);
+    effect_dependency_ = other->effect_dependency_;
+    values_ = other->values_;
+    return;
+  }
+
+  // Create a merge of the control dependencies of both environments and update
+  // the current environment's control dependency accordingly.
+  Node* control = builder_->MergeControl(this->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(this->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.
+  for (int i = 0; i < static_cast<int>(values_.size()); ++i) {
+    values_[i] = builder_->MergeValue(values_[i], other->values_[i], control);
+  }
+}
+
+
+void AstGraphBuilder::Environment::PrepareForLoop(BitVector* assigned,
+                                                  bool is_osr) {
+  int size = static_cast<int>(values()->size());
+
+  Node* control = builder_->NewLoop();
+  if (assigned == nullptr) {
+    // Assume that everything is updated in the loop.
+    for (int i = 0; i < size; ++i) {
+      Node* phi = builder_->NewPhi(1, values()->at(i), control);
+      values()->at(i) = phi;
+    }
+  } else {
+    // Only build phis for those locals assigned in this loop.
+    for (int i = 0; i < size; ++i) {
+      if (i < assigned->length() && !assigned->Contains(i)) continue;
+      Node* phi = builder_->NewPhi(1, values()->at(i), control);
+      values()->at(i) = phi;
+    }
+  }
+  Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control);
+  UpdateEffectDependency(effect);
+
+  if (is_osr) {
+    // Merge OSR values as inputs to the phis of the loop.
+    Graph* graph = builder_->graph();
+    Node* osr_loop_entry = builder_->graph()->NewNode(
+        builder_->common()->OsrLoopEntry(), graph->start(), graph->start());
+
+    builder_->MergeControl(control, osr_loop_entry);
+    builder_->MergeEffect(effect, osr_loop_entry, control);
+
+    for (int i = 0; i < size; ++i) {
+      Node* val = values()->at(i);
+      if (!IrOpcode::IsConstantOpcode(val->opcode())) {
+        Node* osr_value =
+            graph->NewNode(builder_->common()->OsrValue(i), osr_loop_entry);
+        values()->at(i) = builder_->MergeValue(val, osr_value, control);
+      }
+    }
+  }
+}
+
+
+Node* AstGraphBuilder::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* AstGraphBuilder::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* AstGraphBuilder::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;
+}
+
+
+Node* AstGraphBuilder::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->set_op(common()->EffectPhi(inputs));
+    value->InsertInput(graph_zone(), inputs - 1, other);
+  } else if (value != other) {
+    // Phi does not exist yet, introduce one.
+    value = NewEffectPhi(inputs, value, control);
+    value->ReplaceInput(inputs - 1, other);
+  }
+  return value;
+}
+
+
+Node* AstGraphBuilder::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->set_op(common()->Phi(kMachAnyTagged, inputs));
+    value->InsertInput(graph_zone(), inputs - 1, other);
+  } else if (value != other) {
+    // Phi does not exist yet, introduce one.
+    value = NewPhi(inputs, value, control);
+    value->ReplaceInput(inputs - 1, other);
+  }
+  return value;
+}
+
+
+Node* AstGraphBuilder::dead_control() {
+  if (!dead_control_.is_set()) {
+    Node* dead_node = graph()->NewNode(common()->Dead());
+    dead_control_.set(dead_node);
+    return dead_node;
+  }
+  return dead_control_.get();
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8