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
StructuredGraphBuilder(Graph * graph,CommonOperatorBuilder * common)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
MakeNode(const Operator * op,int value_input_count,Node ** value_inputs)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
UpdateControlDependencyToLeaveFunction(Node * exit)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
CopyEnvironment(Environment * env)96 StructuredGraphBuilder::Environment* StructuredGraphBuilder::CopyEnvironment(
97 Environment* env) {
98 return new (zone()) Environment(*env);
99 }
100
101
Environment(StructuredGraphBuilder * builder,Node * control_dependency)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
Environment(const Environment & copy)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
Merge(Environment * other)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
PrepareForLoop()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
NewPhi(int count,Node * input,Node * control)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.
NewEffectPhi(int count,Node * input,Node * control)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
MergeControl(Node * control,Node * other)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
MergeEffect(Node * value,Node * other,Node * control)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
MergeValue(Node * value,Node * other,Node * control)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
dead_control()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
250