| OLD | NEW |
|---|
| (Empty) |
| 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/bit-vector.h" | |
| 8 #include "src/compiler.h" | |
| 9 #include "src/compiler/graph-visualizer.h" | |
| 10 #include "src/compiler/node.h" | |
| 11 #include "src/compiler/node-properties.h" | |
| 12 #include "src/compiler/operator-properties.h" | |
| 13 | |
| 14 namespace v8 { | |
| 15 namespace internal { | |
| 16 namespace compiler { | |
| 17 | |
| 18 | |
| 19 StructuredGraphBuilder::StructuredGraphBuilder(Isolate* isolate, | |
| 20 Zone* local_zone, Graph* graph, | |
| 21 CommonOperatorBuilder* common) | |
| 22 : GraphBuilder(isolate, graph), | |
| 23 common_(common), | |
| 24 environment_(NULL), | |
| 25 local_zone_(local_zone), | |
| 26 input_buffer_size_(0), | |
| 27 input_buffer_(NULL), | |
| 28 current_context_(NULL), | |
| 29 exit_control_(NULL) { | |
| 30 EnsureInputBufferSize(kInputBufferSizeIncrement); | |
| 31 } | |
| 32 | |
| 33 | |
| 34 Node** StructuredGraphBuilder::EnsureInputBufferSize(int size) { | |
| 35 if (size > input_buffer_size_) { | |
| 36 size += kInputBufferSizeIncrement; | |
| 37 input_buffer_ = local_zone()->NewArray<Node*>(size); | |
| 38 } | |
| 39 return input_buffer_; | |
| 40 } | |
| 41 | |
| 42 | |
| 43 Node* StructuredGraphBuilder::MakeNode(const Operator* op, | |
| 44 int value_input_count, | |
| 45 Node** value_inputs, bool incomplete) { | |
| 46 DCHECK(op->ValueInputCount() == value_input_count); | |
| 47 | |
| 48 bool has_context = OperatorProperties::HasContextInput(op); | |
| 49 bool has_framestate = OperatorProperties::HasFrameStateInput(op); | |
| 50 bool has_control = op->ControlInputCount() == 1; | |
| 51 bool has_effect = op->EffectInputCount() == 1; | |
| 52 | |
| 53 DCHECK(op->ControlInputCount() < 2); | |
| 54 DCHECK(op->EffectInputCount() < 2); | |
| 55 | |
| 56 Node* result = NULL; | |
| 57 if (!has_context && !has_framestate && !has_control && !has_effect) { | |
| 58 result = graph()->NewNode(op, value_input_count, value_inputs, incomplete); | |
| 59 } else { | |
| 60 int input_count_with_deps = value_input_count; | |
| 61 if (has_context) ++input_count_with_deps; | |
| 62 if (has_framestate) ++input_count_with_deps; | |
| 63 if (has_control) ++input_count_with_deps; | |
| 64 if (has_effect) ++input_count_with_deps; | |
| 65 Node** buffer = EnsureInputBufferSize(input_count_with_deps); | |
| 66 memcpy(buffer, value_inputs, kPointerSize * value_input_count); | |
| 67 Node** current_input = buffer + value_input_count; | |
| 68 if (has_context) { | |
| 69 *current_input++ = current_context(); | |
| 70 } | |
| 71 if (has_framestate) { | |
| 72 // The frame state will be inserted later. Here we misuse | |
| 73 // the dead_control node as a sentinel to be later overwritten | |
| 74 // with the real frame state. | |
| 75 *current_input++ = dead_control(); | |
| 76 } | |
| 77 if (has_effect) { | |
| 78 *current_input++ = environment_->GetEffectDependency(); | |
| 79 } | |
| 80 if (has_control) { | |
| 81 *current_input++ = environment_->GetControlDependency(); | |
| 82 } | |
| 83 result = graph()->NewNode(op, input_count_with_deps, buffer, incomplete); | |
| 84 if (has_effect) { | |
| 85 environment_->UpdateEffectDependency(result); | |
| 86 } | |
| 87 if (result->op()->ControlOutputCount() > 0 && | |
| 88 !environment()->IsMarkedAsUnreachable()) { | |
| 89 environment_->UpdateControlDependency(result); | |
| 90 } | |
| 91 } | |
| 92 | |
| 93 return result; | |
| 94 } | |
| 95 | |
| 96 | |
| 97 void StructuredGraphBuilder::UpdateControlDependencyToLeaveFunction( | |
| 98 Node* exit) { | |
| 99 if (environment()->IsMarkedAsUnreachable()) return; | |
| 100 if (exit_control() != NULL) { | |
| 101 exit = MergeControl(exit_control(), exit); | |
| 102 } | |
| 103 environment()->MarkAsUnreachable(); | |
| 104 set_exit_control(exit); | |
| 105 } | |
| 106 | |
| 107 | |
| 108 StructuredGraphBuilder::Environment* StructuredGraphBuilder::CopyEnvironment( | |
| 109 Environment* env) { | |
| 110 return new (local_zone()) Environment(*env); | |
| 111 } | |
| 112 | |
| 113 | |
| 114 StructuredGraphBuilder::Environment::Environment( | |
| 115 StructuredGraphBuilder* builder, Node* control_dependency) | |
| 116 : builder_(builder), | |
| 117 control_dependency_(control_dependency), | |
| 118 effect_dependency_(control_dependency), | |
| 119 values_(zone()) {} | |
| 120 | |
| 121 | |
| 122 StructuredGraphBuilder::Environment::Environment(const Environment& copy) | |
| 123 : builder_(copy.builder()), | |
| 124 control_dependency_(copy.control_dependency_), | |
| 125 effect_dependency_(copy.effect_dependency_), | |
| 126 values_(copy.zone()) { | |
| 127 const size_t kStackEstimate = 7; // optimum from experimentation! | |
| 128 values_.reserve(copy.values_.size() + kStackEstimate); | |
| 129 values_.insert(values_.begin(), copy.values_.begin(), copy.values_.end()); | |
| 130 } | |
| 131 | |
| 132 | |
| 133 void StructuredGraphBuilder::Environment::Merge(Environment* other) { | |
| 134 DCHECK(values_.size() == other->values_.size()); | |
| 135 | |
| 136 // Nothing to do if the other environment is dead. | |
| 137 if (other->IsMarkedAsUnreachable()) return; | |
| 138 | |
| 139 // Resurrect a dead environment by copying the contents of the other one and | |
| 140 // placing a singleton merge as the new control dependency. | |
| 141 if (this->IsMarkedAsUnreachable()) { | |
| 142 Node* other_control = other->control_dependency_; | |
| 143 Node* inputs[] = {other_control}; | |
| 144 control_dependency_ = | |
| 145 graph()->NewNode(common()->Merge(1), arraysize(inputs), inputs, true); | |
| 146 effect_dependency_ = other->effect_dependency_; | |
| 147 values_ = other->values_; | |
| 148 return; | |
| 149 } | |
| 150 | |
| 151 // Create a merge of the control dependencies of both environments and update | |
| 152 // the current environment's control dependency accordingly. | |
| 153 Node* control = builder_->MergeControl(this->GetControlDependency(), | |
| 154 other->GetControlDependency()); | |
| 155 UpdateControlDependency(control); | |
| 156 | |
| 157 // Create a merge of the effect dependencies of both environments and update | |
| 158 // the current environment's effect dependency accordingly. | |
| 159 Node* effect = builder_->MergeEffect(this->GetEffectDependency(), | |
| 160 other->GetEffectDependency(), control); | |
| 161 UpdateEffectDependency(effect); | |
| 162 | |
| 163 // Introduce Phi nodes for values that have differing input at merge points, | |
| 164 // potentially extending an existing Phi node if possible. | |
| 165 for (int i = 0; i < static_cast<int>(values_.size()); ++i) { | |
| 166 values_[i] = builder_->MergeValue(values_[i], other->values_[i], control); | |
| 167 } | |
| 168 } | |
| 169 | |
| 170 | |
| 171 void StructuredGraphBuilder::Environment::PrepareForLoop(BitVector* assigned, | |
| 172 bool is_osr) { | |
| 173 int size = static_cast<int>(values()->size()); | |
| 174 | |
| 175 Node* control = builder_->NewLoop(); | |
| 176 if (assigned == nullptr) { | |
| 177 // Assume that everything is updated in the loop. | |
| 178 for (int i = 0; i < size; ++i) { | |
| 179 Node* phi = builder_->NewPhi(1, values()->at(i), control); | |
| 180 values()->at(i) = phi; | |
| 181 } | |
| 182 } else { | |
| 183 // Only build phis for those locals assigned in this loop. | |
| 184 for (int i = 0; i < size; ++i) { | |
| 185 if (i < assigned->length() && !assigned->Contains(i)) continue; | |
| 186 Node* phi = builder_->NewPhi(1, values()->at(i), control); | |
| 187 values()->at(i) = phi; | |
| 188 } | |
| 189 } | |
| 190 Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control); | |
| 191 UpdateEffectDependency(effect); | |
| 192 | |
| 193 if (is_osr) { | |
| 194 // Merge OSR values as inputs to the phis of the loop. | |
| 195 Graph* graph = builder_->graph(); | |
| 196 Node* osr_loop_entry = builder_->graph()->NewNode( | |
| 197 builder_->common()->OsrLoopEntry(), graph->start(), graph->start()); | |
| 198 | |
| 199 builder_->MergeControl(control, osr_loop_entry); | |
| 200 builder_->MergeEffect(effect, osr_loop_entry, control); | |
| 201 | |
| 202 for (int i = 0; i < size; ++i) { | |
| 203 Node* val = values()->at(i); | |
| 204 if (!IrOpcode::IsConstantOpcode(val->opcode())) { | |
| 205 Node* osr_value = | |
| 206 graph->NewNode(builder_->common()->OsrValue(i), osr_loop_entry); | |
| 207 values()->at(i) = builder_->MergeValue(val, osr_value, control); | |
| 208 } | |
| 209 } | |
| 210 } | |
| 211 } | |
| 212 | |
| 213 | |
| 214 Node* StructuredGraphBuilder::NewPhi(int count, Node* input, Node* control) { | |
| 215 const Operator* phi_op = common()->Phi(kMachAnyTagged, count); | |
| 216 Node** buffer = EnsureInputBufferSize(count + 1); | |
| 217 MemsetPointer(buffer, input, count); | |
| 218 buffer[count] = control; | |
| 219 return graph()->NewNode(phi_op, count + 1, buffer, true); | |
| 220 } | |
| 221 | |
| 222 | |
| 223 // TODO(mstarzinger): Revisit this once we have proper effect states. | |
| 224 Node* StructuredGraphBuilder::NewEffectPhi(int count, Node* input, | |
| 225 Node* control) { | |
| 226 const Operator* phi_op = common()->EffectPhi(count); | |
| 227 Node** buffer = EnsureInputBufferSize(count + 1); | |
| 228 MemsetPointer(buffer, input, count); | |
| 229 buffer[count] = control; | |
| 230 return graph()->NewNode(phi_op, count + 1, buffer, true); | |
| 231 } | |
| 232 | |
| 233 | |
| 234 Node* StructuredGraphBuilder::MergeControl(Node* control, Node* other) { | |
| 235 int inputs = control->op()->ControlInputCount() + 1; | |
| 236 if (control->opcode() == IrOpcode::kLoop) { | |
| 237 // Control node for loop exists, add input. | |
| 238 const Operator* op = common()->Loop(inputs); | |
| 239 control->AppendInput(graph_zone(), other); | |
| 240 control->set_op(op); | |
| 241 } else if (control->opcode() == IrOpcode::kMerge) { | |
| 242 // Control node for merge exists, add input. | |
| 243 const Operator* op = common()->Merge(inputs); | |
| 244 control->AppendInput(graph_zone(), other); | |
| 245 control->set_op(op); | |
| 246 } else { | |
| 247 // Control node is a singleton, introduce a merge. | |
| 248 const Operator* op = common()->Merge(inputs); | |
| 249 Node* inputs[] = {control, other}; | |
| 250 control = graph()->NewNode(op, arraysize(inputs), inputs, true); | |
| 251 } | |
| 252 return control; | |
| 253 } | |
| 254 | |
| 255 | |
| 256 Node* StructuredGraphBuilder::MergeEffect(Node* value, Node* other, | |
| 257 Node* control) { | |
| 258 int inputs = control->op()->ControlInputCount(); | |
| 259 if (value->opcode() == IrOpcode::kEffectPhi && | |
| 260 NodeProperties::GetControlInput(value) == control) { | |
| 261 // Phi already exists, add input. | |
| 262 value->set_op(common()->EffectPhi(inputs)); | |
| 263 value->InsertInput(graph_zone(), inputs - 1, other); | |
| 264 } else if (value != other) { | |
| 265 // Phi does not exist yet, introduce one. | |
| 266 value = NewEffectPhi(inputs, value, control); | |
| 267 value->ReplaceInput(inputs - 1, other); | |
| 268 } | |
| 269 return value; | |
| 270 } | |
| 271 | |
| 272 | |
| 273 Node* StructuredGraphBuilder::MergeValue(Node* value, Node* other, | |
| 274 Node* control) { | |
| 275 int inputs = control->op()->ControlInputCount(); | |
| 276 if (value->opcode() == IrOpcode::kPhi && | |
| 277 NodeProperties::GetControlInput(value) == control) { | |
| 278 // Phi already exists, add input. | |
| 279 value->set_op(common()->Phi(kMachAnyTagged, inputs)); | |
| 280 value->InsertInput(graph_zone(), inputs - 1, other); | |
| 281 } else if (value != other) { | |
| 282 // Phi does not exist yet, introduce one. | |
| 283 value = NewPhi(inputs, value, control); | |
| 284 value->ReplaceInput(inputs - 1, other); | |
| 285 } | |
| 286 return value; | |
| 287 } | |
| 288 | |
| 289 | |
| 290 Node* StructuredGraphBuilder::dead_control() { | |
| 291 if (!dead_control_.is_set()) { | |
| 292 Node* dead_node = graph()->NewNode(common_->Dead()); | |
| 293 dead_control_.set(dead_node); | |
| 294 return dead_node; | |
| 295 } | |
| 296 return dead_control_.get(); | |
| 297 } | |
| 298 } | |
| 299 } | |
| 300 } // namespace v8::internal::compiler | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 894073002:
[turbofan] Put StructuredGraphBuilder out of its misery and merge its remnants back into the AstGra… (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master