node.cc 12.4 KB
Newer Older
1 2 3 4
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/compiler/node.h"
6

7 8 9 10
namespace v8 {
namespace internal {
namespace compiler {

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Node::OutOfLineInputs* Node::OutOfLineInputs::New(Zone* zone, int capacity) {
  size_t size =
      sizeof(OutOfLineInputs) + capacity * (sizeof(Node*) + sizeof(Use));
  intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
  Node::OutOfLineInputs* outline =
      reinterpret_cast<OutOfLineInputs*>(raw_buffer + capacity * sizeof(Use));
  outline->capacity_ = capacity;
  outline->count_ = 0;
  return outline;
}


void Node::OutOfLineInputs::ExtractFrom(Use* old_use_ptr, Node** old_input_ptr,
                                        int count) {
  // Extract the inputs from the old use and input pointers and copy them
  // to this out-of-line-storage.
  Use* new_use_ptr = reinterpret_cast<Use*>(this) - 1;
28
  Node** new_input_ptr = inputs();
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
  for (int current = 0; current < count; current++) {
    new_use_ptr->bit_field_ =
        Use::InputIndexField::encode(current) | Use::InlineField::encode(false);
    DCHECK_EQ(old_input_ptr, old_use_ptr->input_ptr());
    DCHECK_EQ(new_input_ptr, new_use_ptr->input_ptr());
    Node* old_to = *old_input_ptr;
    if (old_to) {
      *old_input_ptr = nullptr;
      old_to->RemoveUse(old_use_ptr);
      *new_input_ptr = old_to;
      old_to->AppendUse(new_use_ptr);
    } else {
      *new_input_ptr = nullptr;
    }
    old_input_ptr++;
    new_input_ptr++;
    old_use_ptr--;
    new_use_ptr--;
  }
  this->count_ = count;
}


52
Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count,
53
                Node* const* inputs, bool has_extensible_inputs) {
54 55 56 57 58
  Node** input_ptr;
  Use* use_ptr;
  Node* node;
  bool is_inline;

59 60 61
  // Verify that none of the inputs are {nullptr}.
  for (int i = 0; i < input_count; i++) {
    if (inputs[i] == nullptr) {
62 63
      FATAL("Node::New() Error: #%d:%s[%d] is nullptr", static_cast<int>(id),
            op->mnemonic(), i);
64 65 66
    }
  }

67 68 69 70 71 72
  if (input_count > kMaxInlineCapacity) {
    // Allocate out-of-line inputs.
    int capacity =
        has_extensible_inputs ? input_count + kMaxInlineCapacity : input_count;
    OutOfLineInputs* outline = OutOfLineInputs::New(zone, capacity);

73 74
    // Allocate node, with space for OutOfLineInputs pointer.
    void* node_buffer = zone->New(sizeof(Node) + sizeof(OutOfLineInputs*));
75
    node = new (node_buffer) Node(id, op, kOutlineMarker, 0);
76
    node->set_outline_inputs(outline);
77 78 79 80

    outline->node_ = node;
    outline->count_ = input_count;

81
    input_ptr = outline->inputs();
82 83 84
    use_ptr = reinterpret_cast<Use*>(outline);
    is_inline = false;
  } else {
85 86 87
    // Allocate node with inline inputs. Capacity must be at least 1 so that
    // an OutOfLineInputs pointer can be stored when inputs are added later.
    int capacity = std::max(1, input_count);
88 89 90 91 92 93 94 95 96
    if (has_extensible_inputs) {
      const int max = kMaxInlineCapacity;
      capacity = std::min(input_count + 3, max);
    }

    size_t size = sizeof(Node) + capacity * (sizeof(Node*) + sizeof(Use));
    intptr_t raw_buffer = reinterpret_cast<intptr_t>(zone->New(size));
    void* node_buffer =
        reinterpret_cast<void*>(raw_buffer + capacity * sizeof(Use));
97

98
    node = new (node_buffer) Node(id, op, input_count, capacity);
99
    input_ptr = node->inline_inputs();
100 101 102 103 104
    use_ptr = reinterpret_cast<Use*>(node);
    is_inline = true;
  }

  // Initialize the input pointers and the uses.
105 106
  for (int current = 0; current < input_count; ++current) {
    Node* to = *inputs++;
107 108 109 110
    input_ptr[current] = to;
    Use* use = use_ptr - 1 - current;
    use->bit_field_ = Use::InputIndexField::encode(current) |
                      Use::InlineField::encode(is_inline);
111 112
    to->AppendUse(use);
  }
113 114
  node->Verify();
  return node;
115 116 117
}


118 119 120
Node* Node::Clone(Zone* zone, NodeId id, const Node* node) {
  int const input_count = node->InputCount();
  Node* const* const inputs = node->has_inline_inputs()
121 122
                                  ? node->inline_inputs()
                                  : node->outline_inputs()->inputs();
123
  Node* const clone = New(zone, id, node->op(), input_count, inputs, false);
124
  clone->set_type(node->type());
125 126 127 128
  return clone;
}


129 130
void Node::Kill() {
  DCHECK_NOT_NULL(op());
131
  NullAllInputs();
132 133 134 135
  DCHECK(uses().empty());
}


136 137 138
void Node::AppendInput(Zone* zone, Node* new_to) {
  DCHECK_NOT_NULL(zone);
  DCHECK_NOT_NULL(new_to);
139 140 141 142 143 144 145 146 147 148 149

  int inline_count = InlineCountField::decode(bit_field_);
  int inline_capacity = InlineCapacityField::decode(bit_field_);
  if (inline_count < inline_capacity) {
    // Append inline input.
    bit_field_ = InlineCountField::update(bit_field_, inline_count + 1);
    *GetInputPtr(inline_count) = new_to;
    Use* use = GetUsePtr(inline_count);
    use->bit_field_ = Use::InputIndexField::encode(inline_count) |
                      Use::InlineField::encode(true);
    new_to->AppendUse(use);
150
  } else {
151 152 153 154 155 156 157 158 159
    // Append out-of-line input.
    int input_count = InputCount();
    OutOfLineInputs* outline = nullptr;
    if (inline_count != kOutlineMarker) {
      // switch to out of line inputs.
      outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
      outline->node_ = this;
      outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
      bit_field_ = InlineCountField::update(bit_field_, kOutlineMarker);
160
      set_outline_inputs(outline);
161 162
    } else {
      // use current out of line inputs.
163
      outline = outline_inputs();
164 165 166 167 168
      if (input_count >= outline->capacity_) {
        // out of space in out-of-line inputs.
        outline = OutOfLineInputs::New(zone, input_count * 2 + 3);
        outline->node_ = this;
        outline->ExtractFrom(GetUsePtr(0), GetInputPtr(0), input_count);
169
        set_outline_inputs(outline);
170 171 172 173 174 175 176 177
      }
    }
    outline->count_++;
    *GetInputPtr(input_count) = new_to;
    Use* use = GetUsePtr(input_count);
    use->bit_field_ = Use::InputIndexField::encode(input_count) |
                      Use::InlineField::encode(false);
    new_to->AppendUse(use);
178
  }
179
  Verify();
180 181 182 183 184 185 186 187 188 189
}


void Node::InsertInput(Zone* zone, int index, Node* new_to) {
  DCHECK_NOT_NULL(zone);
  DCHECK_LE(0, index);
  DCHECK_LT(index, InputCount());
  AppendInput(zone, InputAt(InputCount() - 1));
  for (int i = InputCount() - 1; i > index; --i) {
    ReplaceInput(i, InputAt(i - 1));
190
  }
191
  ReplaceInput(index, new_to);
192
  Verify();
193 194
}

195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
void Node::InsertInputs(Zone* zone, int index, int count) {
  DCHECK_NOT_NULL(zone);
  DCHECK_LE(0, index);
  DCHECK_LT(0, count);
  DCHECK_LT(index, InputCount());
  for (int i = 0; i < count; i++) {
    AppendInput(zone, InputAt(Max(InputCount() - count, 0)));
  }
  for (int i = InputCount() - count - 1; i >= Max(index, count); --i) {
    ReplaceInput(i, InputAt(i - count));
  }
  for (int i = 0; i < count; i++) {
    ReplaceInput(index + i, nullptr);
  }
  Verify();
}
211

212 213 214 215 216 217 218
void Node::RemoveInput(int index) {
  DCHECK_LE(0, index);
  DCHECK_LT(index, InputCount());
  for (; index < InputCount() - 1; ++index) {
    ReplaceInput(index, InputAt(index + 1));
  }
  TrimInputCount(InputCount() - 1);
219
  Verify();
220 221 222
}


223 224 225 226 227 228 229 230 231 232 233 234
void Node::ClearInputs(int start, int count) {
  Node** input_ptr = GetInputPtr(start);
  Use* use_ptr = GetUsePtr(start);
  while (count-- > 0) {
    DCHECK_EQ(input_ptr, use_ptr->input_ptr());
    Node* input = *input_ptr;
    *input_ptr = nullptr;
    if (input) input->RemoveUse(use_ptr);
    input_ptr++;
    use_ptr--;
  }
  Verify();
235 236 237
}


238 239 240
void Node::NullAllInputs() { ClearInputs(0, InputCount()); }


241
void Node::TrimInputCount(int new_input_count) {
242 243 244 245 246 247
  int current_count = InputCount();
  DCHECK_LE(new_input_count, current_count);
  if (new_input_count == current_count) return;  // Nothing to do.
  ClearInputs(new_input_count, current_count - new_input_count);
  if (has_inline_inputs()) {
    bit_field_ = InlineCountField::update(bit_field_, new_input_count);
248
  } else {
249
    outline_inputs()->count_ = new_input_count;
250 251 252 253
  }
}


254 255 256 257 258 259 260 261 262
int Node::UseCount() const {
  int use_count = 0;
  for (const Use* use = first_use_; use; use = use->next) {
    ++use_count;
  }
  return use_count;
}


263 264 265 266 267 268 269
void Node::ReplaceUses(Node* that) {
  DCHECK(this->first_use_ == nullptr || this->first_use_->prev == nullptr);
  DCHECK(that->first_use_ == nullptr || that->first_use_->prev == nullptr);

  // Update the pointers to {this} to point to {that}.
  Use* last_use = nullptr;
  for (Use* use = this->first_use_; use; use = use->next) {
270
    *use->input_ptr() = that;
271 272 273 274 275 276 277
    last_use = use;
  }
  if (last_use) {
    // Concat the use list of {this} and {that}.
    last_use->next = that->first_use_;
    if (that->first_use_) that->first_use_->prev = last_use;
    that->first_use_ = this->first_use_;
278 279 280 281 282
  }
  first_use_ = nullptr;
}


283 284 285
bool Node::OwnedBy(Node const* owner1, Node const* owner2) const {
  unsigned mask = 0;
  for (Use* use = first_use_; use; use = use->next) {
286 287
    Node* from = use->from();
    if (from == owner1) {
288
      mask |= 1;
289
    } else if (from == owner2) {
290 291 292 293 294 295 296 297
      mask |= 2;
    } else {
      return false;
    }
  }
  return mask == 3;
}

298
void Node::Print() const {
299
  StdoutStream os;
300 301 302 303
  Print(os);
}

void Node::Print(std::ostream& os) const {
304
  os << *this << std::endl;
305
  for (Node* input : this->inputs()) {
306 307 308 309 310 311 312
    os << "  ";
    if (input) {
      os << *input;
    } else {
      os << "(NULL)";
    }
    os << std::endl;
313
  }
314 315
}

316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331
std::ostream& operator<<(std::ostream& os, const Node& n) {
  os << n.id() << ": " << *n.op();
  if (n.InputCount() > 0) {
    os << "(";
    for (int i = 0; i < n.InputCount(); ++i) {
      if (i != 0) os << ", ";
      if (n.InputAt(i)) {
        os << n.InputAt(i)->id();
      } else {
        os << "null";
      }
    }
    os << ")";
  }
  return os;
}
332

333
Node::Node(NodeId id, const Operator* op, int inline_count, int inline_capacity)
334 335
    : op_(op),
      mark_(0),
336 337 338 339
      bit_field_(IdField::encode(id) | InlineCountField::encode(inline_count) |
                 InlineCapacityField::encode(inline_capacity)),
      first_use_(nullptr) {
  // Inputs must either be out of line or within the inline capacity.
340
  DCHECK_GE(kMaxInlineCapacity, inline_capacity);
341
  DCHECK(inline_count == kOutlineMarker || inline_count <= inline_capacity);
342 343 344
}


345
void Node::AppendUse(Use* use) {
346
  DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
347
  DCHECK_EQ(this, *use->input_ptr());
348 349 350 351
  use->next = first_use_;
  use->prev = nullptr;
  if (first_use_) first_use_->prev = use;
  first_use_ = use;
352 353 354
}


355
void Node::RemoveUse(Use* use) {
356
  DCHECK(first_use_ == nullptr || first_use_->prev == nullptr);
357
  if (use->prev) {
358
    DCHECK_NE(first_use_, use);
359 360
    use->prev->next = use->next;
  } else {
361
    DCHECK_EQ(first_use_, use);
362 363 364 365
    first_use_ = use->next;
  }
  if (use->next) {
    use->next->prev = use->prev;
366 367 368 369
  }
}


370 371 372 373 374 375 376 377 378 379
#if DEBUG
void Node::Verify() {
  // Check basic sanity of input data structures.
  fflush(stdout);
  int count = this->InputCount();
  // Avoid quadratic explosion for mega nodes; only verify if the input
  // count is less than 200 or is a round number of 100s.
  if (count > 200 && count % 100) return;

  for (int i = 0; i < count; i++) {
380 381 382
    DCHECK_EQ(i, this->GetUsePtr(i)->input_index());
    DCHECK_EQ(this->GetInputPtr(i), this->GetUsePtr(i)->input_ptr());
    DCHECK_EQ(count, this->InputCount());
383 384 385 386
  }
  {  // Direct input iteration.
    int index = 0;
    for (Node* input : this->inputs()) {
387
      DCHECK_EQ(this->InputAt(index), input);
388 389
      index++;
    }
390 391
    DCHECK_EQ(count, index);
    DCHECK_EQ(this->InputCount(), index);
392 393 394 395
  }
  {  // Input edge iteration.
    int index = 0;
    for (Edge edge : this->input_edges()) {
396 397 398
      DCHECK_EQ(edge.from(), this);
      DCHECK_EQ(index, edge.index());
      DCHECK_EQ(this->InputAt(index), edge.to());
399 400
      index++;
    }
401 402
    DCHECK_EQ(count, index);
    DCHECK_EQ(this->InputCount(), index);
403 404 405 406
  }
}
#endif

407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
Node::InputEdges::iterator Node::InputEdges::iterator::operator++(int n) {
  iterator result(*this);
  ++(*this);
  return result;
}


Node::Inputs::const_iterator Node::Inputs::const_iterator::operator++(int n) {
  const_iterator result(*this);
  ++(*this);
  return result;
}


Node::UseEdges::iterator Node::UseEdges::iterator::operator++(int n) {
  iterator result(*this);
  ++(*this);
  return result;
}


bool Node::UseEdges::empty() const { return begin() == end(); }


Node::Uses::const_iterator Node::Uses::const_iterator::operator++(int n) {
  const_iterator result(*this);
  ++(*this);
  return result;
}


bool Node::Uses::empty() const { return begin() == end(); }

440 441 442
}  // namespace compiler
}  // namespace internal
}  // namespace v8