Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 7 | #include "src/bit-vector.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 8 | #include "src/compiler.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 9 | #include "src/compiler/graph-visualizer.h" |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 10 | #include "src/compiler/node.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 11 | #include "src/compiler/node-properties.h" |
| 12 | #include "src/compiler/node-properties-inl.h" |
| 13 | #include "src/compiler/operator-properties.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 14 | |
| 15 | namespace v8 { |
| 16 | namespace internal { |
| 17 | namespace compiler { |
| 18 | |
| 19 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 20 | StructuredGraphBuilder::StructuredGraphBuilder(Zone* local_zone, Graph* graph, |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 21 | CommonOperatorBuilder* common) |
| 22 | : GraphBuilder(graph), |
| 23 | common_(common), |
| 24 | environment_(NULL), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 25 | local_zone_(local_zone), |
| 26 | input_buffer_size_(0), |
| 27 | input_buffer_(NULL), |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 28 | current_context_(NULL), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 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 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 41 | |
| 42 | |
| 43 | Node* StructuredGraphBuilder::MakeNode(const Operator* op, |
| 44 | int value_input_count, |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 45 | Node** value_inputs, bool incomplete) { |
| 46 | DCHECK(op->ValueInputCount() == value_input_count); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 47 | |
| 48 | bool has_context = OperatorProperties::HasContextInput(op); |
| 49 | bool has_framestate = OperatorProperties::HasFrameStateInput(op); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 50 | bool has_control = op->ControlInputCount() == 1; |
| 51 | bool has_effect = op->EffectInputCount() == 1; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 52 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 53 | DCHECK(op->ControlInputCount() < 2); |
| 54 | DCHECK(op->EffectInputCount() < 2); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 55 | |
| 56 | Node* result = NULL; |
| 57 | if (!has_context && !has_framestate && !has_control && !has_effect) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 58 | result = graph()->NewNode(op, value_input_count, value_inputs, incomplete); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 65 | Node** buffer = EnsureInputBufferSize(input_count_with_deps); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 83 | result = graph()->NewNode(op, input_count_with_deps, buffer, incomplete); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 84 | if (has_effect) { |
| 85 | environment_->UpdateEffectDependency(result); |
| 86 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 87 | if (result->op()->ControlOutputCount() > 0 && |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 110 | return new (local_zone()) Environment(*env); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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_), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 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 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 143 | Node* inputs[] = {other_control}; |
| 144 | control_dependency_ = |
| 145 | graph()->NewNode(common()->Merge(1), arraysize(inputs), inputs, true); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 171 | void StructuredGraphBuilder::Environment::PrepareForLoop(BitVector* assigned) { |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 172 | Node* control = GetControlDependency(); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 173 | int size = static_cast<int>(values()->size()); |
| 174 | if (assigned == NULL) { |
| 175 | // Assume that everything is updated in the loop. |
| 176 | for (int i = 0; i < size; ++i) { |
| 177 | Node* phi = builder_->NewPhi(1, values()->at(i), control); |
| 178 | values()->at(i) = phi; |
| 179 | } |
| 180 | } else { |
| 181 | // Only build phis for those locals assigned in this loop. |
| 182 | for (int i = 0; i < size; ++i) { |
| 183 | if (i < assigned->length() && !assigned->Contains(i)) continue; |
| 184 | Node* phi = builder_->NewPhi(1, values()->at(i), control); |
| 185 | values()->at(i) = phi; |
| 186 | } |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 187 | } |
| 188 | Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control); |
| 189 | UpdateEffectDependency(effect); |
| 190 | } |
| 191 | |
| 192 | |
| 193 | Node* StructuredGraphBuilder::NewPhi(int count, Node* input, Node* control) { |
| 194 | const Operator* phi_op = common()->Phi(kMachAnyTagged, count); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 195 | Node** buffer = EnsureInputBufferSize(count + 1); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 196 | MemsetPointer(buffer, input, count); |
| 197 | buffer[count] = control; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 198 | return graph()->NewNode(phi_op, count + 1, buffer, true); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 199 | } |
| 200 | |
| 201 | |
| 202 | // TODO(mstarzinger): Revisit this once we have proper effect states. |
| 203 | Node* StructuredGraphBuilder::NewEffectPhi(int count, Node* input, |
| 204 | Node* control) { |
| 205 | const Operator* phi_op = common()->EffectPhi(count); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 206 | Node** buffer = EnsureInputBufferSize(count + 1); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 207 | MemsetPointer(buffer, input, count); |
| 208 | buffer[count] = control; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 209 | return graph()->NewNode(phi_op, count + 1, buffer, true); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 210 | } |
| 211 | |
| 212 | |
| 213 | Node* StructuredGraphBuilder::MergeControl(Node* control, Node* other) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 214 | int inputs = control->op()->ControlInputCount() + 1; |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 215 | if (control->opcode() == IrOpcode::kLoop) { |
| 216 | // Control node for loop exists, add input. |
| 217 | const Operator* op = common()->Loop(inputs); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 218 | control->AppendInput(graph_zone(), other); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 219 | control->set_op(op); |
| 220 | } else if (control->opcode() == IrOpcode::kMerge) { |
| 221 | // Control node for merge exists, add input. |
| 222 | const Operator* op = common()->Merge(inputs); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 223 | control->AppendInput(graph_zone(), other); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 224 | control->set_op(op); |
| 225 | } else { |
| 226 | // Control node is a singleton, introduce a merge. |
| 227 | const Operator* op = common()->Merge(inputs); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 228 | Node* inputs[] = {control, other}; |
| 229 | control = graph()->NewNode(op, arraysize(inputs), inputs, true); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 230 | } |
| 231 | return control; |
| 232 | } |
| 233 | |
| 234 | |
| 235 | Node* StructuredGraphBuilder::MergeEffect(Node* value, Node* other, |
| 236 | Node* control) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 237 | int inputs = control->op()->ControlInputCount(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 238 | if (value->opcode() == IrOpcode::kEffectPhi && |
| 239 | NodeProperties::GetControlInput(value) == control) { |
| 240 | // Phi already exists, add input. |
| 241 | value->set_op(common()->EffectPhi(inputs)); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 242 | value->InsertInput(graph_zone(), inputs - 1, other); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 243 | } else if (value != other) { |
| 244 | // Phi does not exist yet, introduce one. |
| 245 | value = NewEffectPhi(inputs, value, control); |
| 246 | value->ReplaceInput(inputs - 1, other); |
| 247 | } |
| 248 | return value; |
| 249 | } |
| 250 | |
| 251 | |
| 252 | Node* StructuredGraphBuilder::MergeValue(Node* value, Node* other, |
| 253 | Node* control) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 254 | int inputs = control->op()->ControlInputCount(); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 255 | if (value->opcode() == IrOpcode::kPhi && |
| 256 | NodeProperties::GetControlInput(value) == control) { |
| 257 | // Phi already exists, add input. |
| 258 | value->set_op(common()->Phi(kMachAnyTagged, inputs)); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame^] | 259 | value->InsertInput(graph_zone(), inputs - 1, other); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 260 | } else if (value != other) { |
| 261 | // Phi does not exist yet, introduce one. |
| 262 | value = NewPhi(inputs, value, control); |
| 263 | value->ReplaceInput(inputs - 1, other); |
| 264 | } |
| 265 | return value; |
| 266 | } |
| 267 | |
| 268 | |
| 269 | Node* StructuredGraphBuilder::dead_control() { |
| 270 | if (!dead_control_.is_set()) { |
| 271 | Node* dead_node = graph()->NewNode(common_->Dead()); |
| 272 | dead_control_.set(dead_node); |
| 273 | return dead_node; |
| 274 | } |
| 275 | return dead_control_.get(); |
| 276 | } |
| 277 | } |
| 278 | } |
| 279 | } // namespace v8::internal::compiler |