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/node.h" 6 7 namespace v8 { 8 namespace internal { 9 namespace compiler { 10 11 Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) { 12 size_t size = 13 sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use)); 14 intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size)); 15 Node::OutOfLineInputs* outline = 16 reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use)); 17 outline->capacity_ = capacity; 18 outline->count_ = 0; 19 return outline; 20 } 21 22 23 void Node::OutOfLineInputs::ExtractFrom(Use* old_use_ptr, Node** old_input_ptr, 24 int count) { 25 // Extract the inputs from the old use and input pointers and copy them 26 // to this out-of-line-storage. 27 Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1; 28 Node** new_input_ptr = inputs_; 29 for (int current = 0; current < count; current++) { 30 new_use_ptr->bit_field_ = 31 Use::InputIndexField::encode(current) | Use::InlineField::encode(false); 32 DCHECK_EQ(old_input_ptr, old_use_ptr->input_ptr()); 33 DCHECK_EQ(new_input_ptr, new_use_ptr->input_ptr()); 34 Node* old_to = *old_input_ptr; 35 if (old_to) { 36 *old_input_ptr = nullptr; 37 old_to->RemoveUse(old_use_ptr); 38 *new_input_ptr = old_to; 39 old_to->AppendUse(new_use_ptr); 40 } else { 41 *new_input_ptr = nullptr; 42 } 43 old_input_ptr++; 44 new_input_ptr++; 45 old_use_ptr--; 46 new_use_ptr--; 47 } 48 this->count_ = count; 49 } 50 51 52 Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count, 53 Node* const* inputs, bool has_extensible_inputs) { 54 Node** input_ptr; 55 Use* use_ptr; 56 Node* node; 57 bool is_inline; 58 59 #if DEBUG 60 // Verify that none of the inputs are {nullptr}. 61 for (int i = 0; i < input_count; i++) { 62 if (inputs[i] == nullptr) { 63 V8_Fatal(__FILE__, __LINE__, "Node::New() Error: #%d:%s[%d] is nullptr", 64 static_cast<int>(id), op->mnemonic(), i); 65 } 66 } 67 #endif 68 69 if (input_count > kMaxInlineCapacity) { 70 // Allocate out-of-line inputs. 71 int capacity = 72 has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count; 73 OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity); 74 75 // Allocate node. 76 void* node_buffer = zone->New(sizeof(Node)); 77 node = new (node_buffer) Node(id, op, kOutlineMarker, 0); 78 node->inputs_.outline_ = outline; 79 80 outline->node_ = node; 81 outline->count_ = input_count; 82 83 input_ptr = outline->inputs_; 84 use_ptr = reinterpret_cast<Use*>(outline); 85 is_inline = false; 86 } else { 87 // Allocate node with inline inputs. 88 int capacity = input_count; 89 if (has_extensible_inputs) { 90 const int max = kMaxInlineCapacity; 91 capacity = std::min(input_count + 3, max); 92 } 93 94 size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use)); 95 intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size)); 96 void* node_buffer = 97 reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use)); 98 99 node = new (node_buffer) Node(id, op, input_count, capacity); 100 input_ptr = node->inputs_.inline_; 101 use_ptr = reinterpret_cast<Use*>(node); 102 is_inline = true; 103 } 104 105 // Initialize the input pointers and the uses. 106 for (int current = 0; current < input_count; ++current) { 107 Node* to = *inputs++; 108 input_ptr[current] = to; 109 Use* use = use_ptr - 1 - current; 110 use->bit_field_ = Use::InputIndexField::encode(current) | 111 Use::InlineField::encode(is_inline); 112 to->AppendUse(use); 113 } 114 node->Verify(); 115 return node; 116 } 117 118 119 Node* Node::Clone(Zone* zone, NodeId id, const Node* node) { 120 int const input_count = node->InputCount(); 121 Node* const* const inputs = node->has_inline_inputs() 122 ? node->inputs_.inline_ 123 : node->inputs_.outline_->inputs_; 124 Node* const clone = New(zone, id, node->op(), input_count, inputs, false); 125 clone->set_type(node->type()); 126 return clone; 127 } 128 129 130 void Node::Kill() { 131 DCHECK_NOT_NULL(op()); 132 NullAllInputs(); 133 DCHECK(uses().empty()); 134 } 135 136 137 void Node::AppendInput(Zone* zone, Node* new_to) { 138 DCHECK_NOT_NULL(zone); 139 DCHECK_NOT_NULL(new_to); 140 141 int inline_count = InlineCountField::decode(bit_field_); 142 int inline_capacity = InlineCapacityField::decode(bit_field_); 143 if (inline_count < inline_capacity) { 144 // Append inline input. 145 bit_field_ = InlineCountField::update(bit_field_, inline_count + 1); 146 *GetInputPtr(inline_count) = new_to; 147 Use* use = GetUsePtr(inline_count); 148 use->bit_field_ = Use::InputIndexField::encode(inline_count) | 149 Use::InlineField::encode(true); 150 new_to->AppendUse(use); 151 } else { 152 // Append out-of-line input. 153 int input_count = InputCount(); 154 OutOfLineInputs* outline = nullptr; 155 if (inline_count != kOutlineMarker) { 156 // switch to out of line inputs. 157 outline = OutOfLineInputs::New(zone, input_count * 2 + 3); 158 outline->node_ = this; 159 outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count); 160 bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker); 161 inputs_.outline_ = outline; 162 } else { 163 // use current out of line inputs. 164 outline = inputs_.outline_; 165 if (input_count >= outline->capacity_) { 166 // out of space in out-of-line inputs. 167 outline = OutOfLineInputs::New(zone, input_count * 2 + 3); 168 outline->node_ = this; 169 outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count); 170 inputs_.outline_ = outline; 171 } 172 } 173 outline->count_++; 174 *GetInputPtr(input_count) = new_to; 175 Use* use = GetUsePtr(input_count); 176 use->bit_field_ = Use::InputIndexField::encode(input_count) | 177 Use::InlineField::encode(false); 178 new_to->AppendUse(use); 179 } 180 Verify(); 181 } 182 183 184 void Node::InsertInput(Zone* zone, int index, Node* new_to) { 185 DCHECK_NOT_NULL(zone); 186 DCHECK_LE(0, index); 187 DCHECK_LT(index, InputCount()); 188 AppendInput(zone, InputAt(InputCount() - 1)); 189 for (int i = InputCount() - 1; i > index; --i) { 190 ReplaceInput(i, InputAt(i - 1)); 191 } 192 ReplaceInput(index, new_to); 193 Verify(); 194 } 195 196 void Node::InsertInputs(Zone* zone, int index, int count) { 197 DCHECK_NOT_NULL(zone); 198 DCHECK_LE(0, index); 199 DCHECK_LT(0, count); 200 DCHECK_LT(index, InputCount()); 201 for (int i = 0; i < count; i++) { 202 AppendInput(zone, InputAt(Max(InputCount() - count, 0))); 203 } 204 for (int i = InputCount() - count - 1; i >= Max(index, count); --i) { 205 ReplaceInput(i, InputAt(i - count)); 206 } 207 for (int i = 0; i < count; i++) { 208 ReplaceInput(index + i, nullptr); 209 } 210 Verify(); 211 } 212 213 void Node::RemoveInput(int index) { 214 DCHECK_LE(0, index); 215 DCHECK_LT(index, InputCount()); 216 for (; index < InputCount() - 1; ++index) { 217 ReplaceInput(index, InputAt(index + 1)); 218 } 219 TrimInputCount(InputCount() - 1); 220 Verify(); 221 } 222 223 224 void Node::ClearInputs(int start, int count) { 225 Node** input_ptr = GetInputPtr(start); 226 Use* use_ptr = GetUsePtr(start); 227 while (count-- > 0) { 228 DCHECK_EQ(input_ptr, use_ptr->input_ptr()); 229 Node* input = *input_ptr; 230 *input_ptr = nullptr; 231 if (input) input->RemoveUse(use_ptr); 232 input_ptr++; 233 use_ptr--; 234 } 235 Verify(); 236 } 237 238 239 void Node::NullAllInputs() { ClearInputs(0, InputCount()); } 240 241 242 void Node::TrimInputCount(int new_input_count) { 243 int current_count = InputCount(); 244 DCHECK_LE(new_input_count, current_count); 245 if (new_input_count == current_count) return; // Nothing to do. 246 ClearInputs(new_input_count, current_count - new_input_count); 247 if (has_inline_inputs()) { 248 bit_field_ = InlineCountField::update(bit_field_, new_input_count); 249 } else { 250 inputs_.outline_->count_ = new_input_count; 251 } 252 } 253 254 255 int Node::UseCount() const { 256 int use_count = 0; 257 for (const Use* use = first_use_; use; use = use->next) { 258 ++use_count; 259 } 260 return use_count; 261 } 262 263 264 void Node::ReplaceUses(Node* that) { 265 DCHECK(this->first_use_ == nullptr || this->first_use_->prev == nullptr); 266 DCHECK(that->first_use_ == nullptr || that->first_use_->prev == nullptr); 267 268 // Update the pointers to {this} to point to {that}. 269 Use* last_use = nullptr; 270 for (Use* use = this->first_use_; use; use = use->next) { 271 *use->input_ptr() = that; 272 last_use = use; 273 } 274 if (last_use) { 275 // Concat the use list of {this} and {that}. 276 last_use->next = that->first_use_; 277 if (that->first_use_) that->first_use_->prev = last_use; 278 that->first_use_ = this->first_use_; 279 } 280 first_use_ = nullptr; 281 } 282 283 284 bool Node::OwnedBy(Node const* owner1, Node const* owner2) const { 285 unsigned mask = 0; 286 for (Use* use = first_use_; use; use = use->next) { 287 Node* from = use->from(); 288 if (from == owner1) { 289 mask |= 1; 290 } else if (from == owner2) { 291 mask |= 2; 292 } else { 293 return false; 294 } 295 } 296 return mask == 3; 297 } 298 299 300 void Node::Print() const { 301 OFStream os(stdout); 302 os << *this << std::endl; 303 } 304 305 306 Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity) 307 : op_(op), 308 type_(nullptr), 309 mark_(0), 310 bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) | 311 InlineCapacityField::encode(inline_capacity)), 312 first_use_(nullptr) { 313 // Inputs must either be out of line or within the inline capacity. 314 DCHECK(inline_capacity <= kMaxInlineCapacity); 315 DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity); 316 } 317 318 319 void Node::AppendUse(Use* use) { 320 DCHECK(first_use_ == nullptr || first_use_->prev == nullptr); 321 DCHECK_EQ(this, *use->input_ptr()); 322 use->next = first_use_; 323 use->prev = nullptr; 324 if (first_use_) first_use_->prev = use; 325 first_use_ = use; 326 } 327 328 329 void Node::RemoveUse(Use* use) { 330 DCHECK(first_use_ == nullptr || first_use_->prev == nullptr); 331 if (use->prev) { 332 DCHECK_NE(first_use_, use); 333 use->prev->next = use->next; 334 } else { 335 DCHECK_EQ(first_use_, use); 336 first_use_ = use->next; 337 } 338 if (use->next) { 339 use->next->prev = use->prev; 340 } 341 } 342 343 344 #if DEBUG 345 void Node::Verify() { 346 // Check basic sanity of input data structures. 347 fflush(stdout); 348 int count = this->InputCount(); 349 // Avoid quadratic explosion for mega nodes; only verify if the input 350 // count is less than 200 or is a round number of 100s. 351 if (count > 200 && count % 100) return; 352 353 for (int i = 0; i < count; i++) { 354 CHECK_EQ(i, this->GetUsePtr(i)->input_index()); 355 CHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr()); 356 CHECK_EQ(count, this->InputCount()); 357 } 358 { // Direct input iteration. 359 int index = 0; 360 for (Node* input : this->inputs()) { 361 CHECK_EQ(this->InputAt(index), input); 362 index++; 363 } 364 CHECK_EQ(count, index); 365 CHECK_EQ(this->InputCount(), index); 366 } 367 { // Input edge iteration. 368 int index = 0; 369 for (Edge edge : this->input_edges()) { 370 CHECK_EQ(edge.from(), this); 371 CHECK_EQ(index, edge.index()); 372 CHECK_EQ(this->InputAt(index), edge.to()); 373 index++; 374 } 375 CHECK_EQ(count, index); 376 CHECK_EQ(this->InputCount(), index); 377 } 378 } 379 #endif 380 381 382 std::ostream& operator<<(std::ostream& os, const Node& n) { 383 os << n.id() << ": " << *n.op(); 384 if (n.InputCount() > 0) { 385 os << "("; 386 for (int i = 0; i < n.InputCount(); ++i) { 387 if (i != 0) os << ", "; 388 if (n.InputAt(i)) { 389 os << n.InputAt(i)->id(); 390 } else { 391 os << "null"; 392 } 393 } 394 os << ")"; 395 } 396 return os; 397 } 398 399 400 Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) { 401 iterator result(*this); 402 ++(*this); 403 return result; 404 } 405 406 407 bool Node::InputEdges::empty() const { return begin() == end(); } 408 409 410 Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) { 411 const_iterator result(*this); 412 ++(*this); 413 return result; 414 } 415 416 417 bool Node::Inputs::empty() const { return begin() == end(); } 418 419 420 Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) { 421 iterator result(*this); 422 ++(*this); 423 return result; 424 } 425 426 427 bool Node::UseEdges::empty() const { return begin() == end(); } 428 429 430 Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) { 431 const_iterator result(*this); 432 ++(*this); 433 return result; 434 } 435 436 437 bool Node::Uses::empty() const { return begin() == end(); } 438 439 } // namespace compiler 440 } // namespace internal 441 } // namespace v8 442