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 FATAL("Node::New() Error: #%d:%s[%d] is nullptr", static_cast<int>(id), 64 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 void Node::Print() const { 300 StdoutStream os; 301 os << *this << std::endl; 302 for (Node* input : this->inputs()) { 303 os << " " << *input << std::endl; 304 } 305 } 306 307 std::ostream& operator<<(std::ostream& os, const Node& n) { 308 os << n.id() << ": " << *n.op(); 309 if (n.InputCount() > 0) { 310 os << "("; 311 for (int i = 0; i < n.InputCount(); ++i) { 312 if (i != 0) os << ", "; 313 if (n.InputAt(i)) { 314 os << n.InputAt(i)->id(); 315 } else { 316 os << "null"; 317 } 318 } 319 os << ")"; 320 } 321 return os; 322 } 323 324 Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity) 325 : op_(op), 326 mark_(0), 327 bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) | 328 InlineCapacityField::encode(inline_capacity)), 329 first_use_(nullptr) { 330 // Inputs must either be out of line or within the inline capacity. 331 DCHECK_GE(kMaxInlineCapacity, inline_capacity); 332 DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity); 333 } 334 335 336 void Node::AppendUse(Use* use) { 337 DCHECK(first_use_ == nullptr || first_use_->prev == nullptr); 338 DCHECK_EQ(this, *use->input_ptr()); 339 use->next = first_use_; 340 use->prev = nullptr; 341 if (first_use_) first_use_->prev = use; 342 first_use_ = use; 343 } 344 345 346 void Node::RemoveUse(Use* use) { 347 DCHECK(first_use_ == nullptr || first_use_->prev == nullptr); 348 if (use->prev) { 349 DCHECK_NE(first_use_, use); 350 use->prev->next = use->next; 351 } else { 352 DCHECK_EQ(first_use_, use); 353 first_use_ = use->next; 354 } 355 if (use->next) { 356 use->next->prev = use->prev; 357 } 358 } 359 360 361 #if DEBUG 362 void Node::Verify() { 363 // Check basic sanity of input data structures. 364 fflush(stdout); 365 int count = this->InputCount(); 366 // Avoid quadratic explosion for mega nodes; only verify if the input 367 // count is less than 200 or is a round number of 100s. 368 if (count > 200 && count % 100) return; 369 370 for (int i = 0; i < count; i++) { 371 DCHECK_EQ(i, this->GetUsePtr(i)->input_index()); 372 DCHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr()); 373 DCHECK_EQ(count, this->InputCount()); 374 } 375 { // Direct input iteration. 376 int index = 0; 377 for (Node* input : this->inputs()) { 378 DCHECK_EQ(this->InputAt(index), input); 379 index++; 380 } 381 DCHECK_EQ(count, index); 382 DCHECK_EQ(this->InputCount(), index); 383 } 384 { // Input edge iteration. 385 int index = 0; 386 for (Edge edge : this->input_edges()) { 387 DCHECK_EQ(edge.from(), this); 388 DCHECK_EQ(index, edge.index()); 389 DCHECK_EQ(this->InputAt(index), edge.to()); 390 index++; 391 } 392 DCHECK_EQ(count, index); 393 DCHECK_EQ(this->InputCount(), index); 394 } 395 } 396 #endif 397 398 Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) { 399 iterator result(*this); 400 ++(*this); 401 return result; 402 } 403 404 405 Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) { 406 const_iterator result(*this); 407 ++(*this); 408 return result; 409 } 410 411 412 Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) { 413 iterator result(*this); 414 ++(*this); 415 return result; 416 } 417 418 419 bool Node::UseEdges::empty() const { return begin() == end(); } 420 421 422 Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) { 423 const_iterator result(*this); 424 ++(*this); 425 return result; 426 } 427 428 429 bool Node::Uses::empty() const { return begin() == end(); } 430 431 } // namespace compiler 432 } // namespace internal 433 } // namespace v8 434