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
17namespace v8 {
18namespace internal {
19namespace compiler {
20
21
22StructuredGraphBuilder::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
31Node* 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
85void 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
96StructuredGraphBuilder::Environment* StructuredGraphBuilder::CopyEnvironment(
97    Environment* env) {
98  return new (zone()) Environment(*env);
99}
100
101
102StructuredGraphBuilder::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
110StructuredGraphBuilder::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
117void 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
153void 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
164Node* 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.
174Node* 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
184Node* 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
205Node* 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
222Node* 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
239Node* 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
250