src/v8/src/compiler/graph-builder.cc

   1 // Copyright 2013 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/graph-builder.h"
   6
   7 #include "src/compiler.h"
   8 #include "src/compiler/generic-graph.h"
   9 #include "src/compiler/generic-node.h"
  10 #include "src/compiler/generic-node-inl.h"
  11 #include "src/compiler/graph-visualizer.h"
  12 #include "src/compiler/node-properties.h"
  13 #include "src/compiler/node-properties-inl.h"
  14 #include "src/compiler/operator-properties.h"
  15 #include "src/compiler/operator-properties-inl.h"
  16
  17 namespace v8 {
  18 namespace internal {
  19 namespace compiler {
  20
  21
  22 StructuredGraphBuilder::StructuredGraphBuilder(Graph* graph,
  23                                                CommonOperatorBuilder* common)
  24     : GraphBuilder(graph),
  25       common_(common),
  26       environment_(NULL),
  27       current_context_(NULL),
  28       exit_control_(NULL) {}
  29
  30
  31 Node* StructuredGraphBuilder::MakeNode(const Operator* op,
  32                                        int value_input_count,
  33                                        Node** value_inputs) {
  34   DCHECK(op->InputCount() == value_input_count);
  35
  36   bool has_context = OperatorProperties::HasContextInput(op);
  37   bool has_framestate = OperatorProperties::HasFrameStateInput(op);
  38   bool has_control = OperatorProperties::GetControlInputCount(op) == 1;
  39   bool has_effect = OperatorProperties::GetEffectInputCount(op) == 1;
  40
  41   DCHECK(OperatorProperties::GetControlInputCount(op) < 2);
  42   DCHECK(OperatorProperties::GetEffectInputCount(op) < 2);
  43
  44   Node* result = NULL;
  45   if (!has_context && !has_framestate && !has_control && !has_effect) {
  46     result = graph()->NewNode(op, value_input_count, value_inputs);
  47   } else {
  48     int input_count_with_deps = value_input_count;
  49     if (has_context) ++input_count_with_deps;
  50     if (has_framestate) ++input_count_with_deps;
  51     if (has_control) ++input_count_with_deps;
  52     if (has_effect) ++input_count_with_deps;
  53     Node** buffer = zone()->NewArray<Node*>(input_count_with_deps);
  54     memcpy(buffer, value_inputs, kPointerSize * value_input_count);
  55     Node** current_input = buffer + value_input_count;
  56     if (has_context) {
  57       *current_input++ = current_context();
  58     }
  59     if (has_framestate) {
  60       // The frame state will be inserted later. Here we misuse
  61       // the dead_control node as a sentinel to be later overwritten
  62       // with the real frame state.
  63       *current_input++ = dead_control();
  64     }
  65     if (has_effect) {
  66       *current_input++ = environment_->GetEffectDependency();
  67     }
  68     if (has_control) {
  69       *current_input++ = environment_->GetControlDependency();
  70     }
  71     result = graph()->NewNode(op, input_count_with_deps, buffer);
  72     if (has_effect) {
  73       environment_->UpdateEffectDependency(result);
  74     }
  75     if (OperatorProperties::HasControlOutput(result->op()) &&
  76         !environment()->IsMarkedAsUnreachable()) {
  77       environment_->UpdateControlDependency(result);
  78     }
  79   }
  80
  81   return result;
  82 }
  83
  84
  85 void StructuredGraphBuilder::UpdateControlDependencyToLeaveFunction(
  86     Node* exit) {
  87   if (environment()->IsMarkedAsUnreachable()) return;
  88   if (exit_control() != NULL) {
  89     exit = MergeControl(exit_control(), exit);
  90   }
  91   environment()->MarkAsUnreachable();
  92   set_exit_control(exit);
  93 }
  94
  95
  96 StructuredGraphBuilder::Environment* StructuredGraphBuilder::CopyEnvironment(
  97     Environment* env) {
  98   return new (zone()) Environment(*env);
  99 }
 100
 101
 102 StructuredGraphBuilder::Environment::Environment(
 103     StructuredGraphBuilder* builder, Node* control_dependency)
 104     : builder_(builder),
 105       control_dependency_(control_dependency),
 106       effect_dependency_(control_dependency),
 107       values_(zone()) {}
 108
 109
 110 StructuredGraphBuilder::Environment::Environment(const Environment& copy)
 111     : builder_(copy.builder()),
 112       control_dependency_(copy.control_dependency_),
 113       effect_dependency_(copy.effect_dependency_),
 114       values_(copy.values_) {}
 115
 116
 117 void StructuredGraphBuilder::Environment::Merge(Environment* other) {
 118   DCHECK(values_.size() == other->values_.size());
 119
 120   // Nothing to do if the other environment is dead.
 121   if (other->IsMarkedAsUnreachable()) return;
 122
 123   // Resurrect a dead environment by copying the contents of the other one and
 124   // placing a singleton merge as the new control dependency.
 125   if (this->IsMarkedAsUnreachable()) {
 126     Node* other_control = other->control_dependency_;
 127     control_dependency_ = graph()->NewNode(common()->Merge(1), other_control);
 128     effect_dependency_ = other->effect_dependency_;
 129     values_ = other->values_;
 130     return;
 131   }
 132
 133   // Create a merge of the control dependencies of both environments and update
 134   // the current environment's control dependency accordingly.
 135   Node* control = builder_->MergeControl(this->GetControlDependency(),
 136                                          other->GetControlDependency());
 137   UpdateControlDependency(control);
 138
 139   // Create a merge of the effect dependencies of both environments and update
 140   // the current environment's effect dependency accordingly.
 141   Node* effect = builder_->MergeEffect(this->GetEffectDependency(),
 142                                        other->GetEffectDependency(), control);
 143   UpdateEffectDependency(effect);
 144
 145   // Introduce Phi nodes for values that have differing input at merge points,
 146   // potentially extending an existing Phi node if possible.
 147   for (int i = 0; i < static_cast<int>(values_.size()); ++i) {
 148     values_[i] = builder_->MergeValue(values_[i], other->values_[i], control);
 149   }
 150 }
 151
 152
 153 void StructuredGraphBuilder::Environment::PrepareForLoop() {
 154   Node* control = GetControlDependency();
 155   for (int i = 0; i < static_cast<int>(values()->size()); ++i) {
 156     Node* phi = builder_->NewPhi(1, values()->at(i), control);
 157     values()->at(i) = phi;
 158   }
 159   Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control);
 160   UpdateEffectDependency(effect);
 161 }
 162
 163
 164 Node* StructuredGraphBuilder::NewPhi(int count, Node* input, Node* control) {
 165   const Operator* phi_op = common()->Phi(kMachAnyTagged, count);
 166   Node** buffer = zone()->NewArray<Node*>(count + 1);
 167   MemsetPointer(buffer, input, count);
 168   buffer[count] = control;
 169   return graph()->NewNode(phi_op, count + 1, buffer);
 170 }
 171
 172
 173 // TODO(mstarzinger): Revisit this once we have proper effect states.
 174 Node* StructuredGraphBuilder::NewEffectPhi(int count, Node* input,
 175                                            Node* control) {
 176   const Operator* phi_op = common()->EffectPhi(count);
 177   Node** buffer = zone()->NewArray<Node*>(count + 1);
 178   MemsetPointer(buffer, input, count);
 179   buffer[count] = control;
 180   return graph()->NewNode(phi_op, count + 1, buffer);
 181 }
 182
 183
 184 Node* StructuredGraphBuilder::MergeControl(Node* control, Node* other) {
 185   int inputs = OperatorProperties::GetControlInputCount(control->op()) + 1;
 186   if (control->opcode() == IrOpcode::kLoop) {
 187     // Control node for loop exists, add input.
 188     const Operator* op = common()->Loop(inputs);
 189     control->AppendInput(zone(), other);
 190     control->set_op(op);
 191   } else if (control->opcode() == IrOpcode::kMerge) {
 192     // Control node for merge exists, add input.
 193     const Operator* op = common()->Merge(inputs);
 194     control->AppendInput(zone(), other);
 195     control->set_op(op);
 196   } else {
 197     // Control node is a singleton, introduce a merge.
 198     const Operator* op = common()->Merge(inputs);
 199     control = graph()->NewNode(op, control, other);
 200   }
 201   return control;
 202 }
 203
 204
 205 Node* StructuredGraphBuilder::MergeEffect(Node* value, Node* other,
 206                                           Node* control) {
 207   int inputs = OperatorProperties::GetControlInputCount(control->op());
 208   if (value->opcode() == IrOpcode::kEffectPhi &&
 209       NodeProperties::GetControlInput(value) == control) {
 210     // Phi already exists, add input.
 211     value->set_op(common()->EffectPhi(inputs));
 212     value->InsertInput(zone(), inputs - 1, other);
 213   } else if (value != other) {
 214     // Phi does not exist yet, introduce one.
 215     value = NewEffectPhi(inputs, value, control);
 216     value->ReplaceInput(inputs - 1, other);
 217   }
 218   return value;
 219 }
 220
 221
 222 Node* StructuredGraphBuilder::MergeValue(Node* value, Node* other,
 223                                          Node* control) {
 224   int inputs = OperatorProperties::GetControlInputCount(control->op());
 225   if (value->opcode() == IrOpcode::kPhi &&
 226       NodeProperties::GetControlInput(value) == control) {
 227     // Phi already exists, add input.
 228     value->set_op(common()->Phi(kMachAnyTagged, inputs));
 229     value->InsertInput(zone(), inputs - 1, other);
 230   } else if (value != other) {
 231     // Phi does not exist yet, introduce one.
 232     value = NewPhi(inputs, value, control);
 233     value->ReplaceInput(inputs - 1, other);
 234   }
 235   return value;
 236 }
 237
 238
 239 Node* StructuredGraphBuilder::dead_control() {
 240   if (!dead_control_.is_set()) {
 241     Node* dead_node = graph()->NewNode(common_->Dead());
 242     dead_control_.set(dead_node);
 243     return dead_node;
 244   }
 245   return dead_control_.get();
 246 }
 247 }
 248 }
 249 }  // namespace v8::internal::compiler