node.h 18 KB
Newer Older
1 2 3 4 5 6 7
// 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.

#ifndef V8_COMPILER_NODE_H_
#define V8_COMPILER_NODE_H_

8
#include "src/common/globals.h"
9 10
#include "src/compiler/opcodes.h"
#include "src/compiler/operator.h"
11
#include "src/compiler/types.h"
12
#include "src/zone/zone-containers.h"
13 14 15 16 17

namespace v8 {
namespace internal {
namespace compiler {

18
// Forward declarations.
danno's avatar
danno committed
19
class Edge;
20 21
class Graph;

22

23 24 25
// Marks are used during traversal of the graph to distinguish states of nodes.
// Each node has a mark which is a monotonically increasing integer, and a
// {NodeMarker} has a range of values that indicate states of a node.
26
using Mark = uint32_t;
27

28 29
// NodeIds are identifying numbers for nodes that can be used to index auxiliary
// out-of-line data associated with each node.
30
using NodeId = uint32_t;
31

32 33 34 35 36 37 38 39 40
// A Node is the basic primitive of graphs. Nodes are chained together by
// input/use chains but by default otherwise contain only an identifying number
// which specific applications of graphs and nodes can use to index auxiliary
// out-of-line data, especially transient data.
//
// In addition Nodes only contain a mutable Operator that may change during
// compilation, e.g. during lowering passes. Other information that needs to be
// associated with Nodes during compilation must be stored out-of-line indexed
// by the Node's id.
41
class V8_EXPORT_PRIVATE Node final {
42
 public:
43
  static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count,
44 45
                   Node* const* inputs, bool has_extensible_inputs);
  static Node* Clone(Zone* zone, NodeId id, const Node* node);
46

47
  inline bool IsDead() const;
48
  void Kill();
49

50 51 52
  const Operator* op() const { return op_; }

  IrOpcode::Value opcode() const {
53
    DCHECK_GE(IrOpcode::kLast, op_->opcode());
54 55 56
    return static_cast<IrOpcode::Value>(op_->opcode());
  }

57 58 59 60
  NodeId id() const { return IdField::decode(bit_field_); }

  int InputCount() const {
    return has_inline_inputs() ? InlineCountField::decode(bit_field_)
61
                               : outline_inputs()->count_;
62
  }
63

64
#ifdef DEBUG
65 66 67
  void Verify();
#else
  inline void Verify() {}
68
#endif
69 70

  Node* InputAt(int index) const {
71 72
    CHECK_LE(0, index);
    CHECK_LT(index, InputCount());
73
    return *GetInputPtrConst(index);
74
  }
75 76

  void ReplaceInput(int index, Node* new_to) {
77 78
    CHECK_LE(0, index);
    CHECK_LT(index, InputCount());
79 80 81 82 83 84 85 86 87 88
    Node** input_ptr = GetInputPtr(index);
    Node* old_to = *input_ptr;
    if (old_to != new_to) {
      Use* use = GetUsePtr(index);
      if (old_to) old_to->RemoveUse(use);
      *input_ptr = new_to;
      if (new_to) new_to->AppendUse(use);
    }
  }

89 90
  void AppendInput(Zone* zone, Node* new_to);
  void InsertInput(Zone* zone, int index, Node* new_to);
91
  void InsertInputs(Zone* zone, int index, int count);
92
  void RemoveInput(int index);
93
  void NullAllInputs();
94
  void TrimInputCount(int new_input_count);
95

96
  int UseCount() const;
97
  void ReplaceUses(Node* replace_to);
98

99 100
  class InputEdges;
  inline InputEdges input_edges();
101

102 103
  class Inputs;
  inline Inputs inputs() const;
danno's avatar
danno committed
104

105
  class UseEdges final {
danno's avatar
danno committed
106
   public:
107
    using value_type = Edge;
108

danno's avatar
danno committed
109
    class iterator;
110 111 112
    inline iterator begin() const;
    inline iterator end() const;

danno's avatar
danno committed
113 114 115 116 117 118 119
    bool empty() const;

    explicit UseEdges(Node* node) : node_(node) {}

   private:
    Node* node_;
  };
120

121 122
  UseEdges use_edges() { return UseEdges(this); }

123
  class V8_EXPORT_PRIVATE Uses final {
124
   public:
125
    using value_type = Node*;
126 127 128 129 130

    class const_iterator;
    inline const_iterator begin() const;
    inline const_iterator end() const;

danno's avatar
danno committed
131
    bool empty() const;
132 133 134 135 136 137 138 139 140

    explicit Uses(Node* node) : node_(node) {}

   private:
    Node* node_;
  };

  Uses uses() { return Uses(this); }

141
  // Returns true if {owner} is the only user of {this} node.
142
  bool OwnedBy(Node const* owner) const;
143

144 145
  // Returns true if {owner1} and {owner2} are the only users of {this} node.
  bool OwnedBy(Node const* owner1, Node const* owner2) const;
146

147
  void Print() const;
148
  void Print(std::ostream&) const;
149

150
 private:
151 152 153 154 155 156 157
  struct Use;
  // Out of line storage for inputs when the number of inputs overflowed the
  // capacity of the inline-allocated space.
  struct OutOfLineInputs {
    Node* node_;
    int count_;
    int capacity_;
158 159 160

    // Inputs are allocated right behind the OutOfLineInputs instance.
    inline Node** inputs();
161 162 163 164 165 166 167 168

    static OutOfLineInputs* New(Zone* zone, int capacity);
    void ExtractFrom(Use* use_ptr, Node** input_ptr, int count);
  };

  // A link in the use chain for a node. Every input {i} to a node {n} has an
  // associated {Use} which is linked into the use chain of the {i} node.
  struct Use {
169 170
    Use* next;
    Use* prev;
171 172 173 174 175 176 177 178
    uint32_t bit_field_;

    int input_index() const { return InputIndexField::decode(bit_field_); }
    bool is_inline_use() const { return InlineField::decode(bit_field_); }
    Node** input_ptr() {
      int index = input_index();
      Use* start = this + 1 + index;
      Node** inputs = is_inline_use()
179 180
                          ? reinterpret_cast<Node*>(start)->inline_inputs()
                          : reinterpret_cast<OutOfLineInputs*>(start)->inputs();
181 182
      return &inputs[index];
    }
183

184 185 186 187 188
    Node* from() {
      Use* start = this + 1 + input_index();
      return is_inline_use() ? reinterpret_cast<Node*>(start)
                             : reinterpret_cast<OutOfLineInputs*>(start)->node_;
    }
189

190 191
    using InlineField = base::BitField<bool, 0, 1>;
    using InputIndexField = base::BitField<unsigned, 1, 31>;
192 193
  };

194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226
  //============================================================================
  //== Memory layout ===========================================================
  //============================================================================
  // Saving space for big graphs is important. We use a memory layout trick to
  // be able to map {Node} objects to {Use} objects and vice-versa in a
  // space-efficient manner.
  //
  // {Use} links are laid out in memory directly before a {Node}, followed by
  // direct pointers to input {Nodes}.
  //
  // inline case:
  // |Use #N  |Use #N-1|...|Use #1  |Use #0  |Node xxxx |I#0|I#1|...|I#N-1|I#N|
  //          ^                              ^                  ^
  //          + Use                          + Node             + Input
  //
  // Since every {Use} instance records its {input_index}, pointer arithmetic
  // can compute the {Node}.
  //
  // out-of-line case:
  //     |Node xxxx |
  //     ^       + outline ------------------+
  //     +----------------------------------------+
  //                                         |    |
  //                                         v    | node
  // |Use #N  |Use #N-1|...|Use #1  |Use #0  |OOL xxxxx |I#0|I#1|...|I#N-1|I#N|
  //          ^                                                 ^
  //          + Use                                             + Input
  //
  // Out-of-line storage of input lists is needed if appending an input to
  // a node exceeds the maximum inline capacity.

  Node(NodeId id, const Operator* op, int inline_count, int inline_capacity);

227 228 229 230 231 232 233 234 235 236 237 238
  inline Address inputs_location() const;

  Node** inline_inputs() const {
    return reinterpret_cast<Node**>(inputs_location());
  }
  OutOfLineInputs* outline_inputs() const {
    return *reinterpret_cast<OutOfLineInputs**>(inputs_location());
  }
  void set_outline_inputs(OutOfLineInputs* outline) {
    *reinterpret_cast<OutOfLineInputs**>(inputs_location()) = outline;
  }

239
  Node* const* GetInputPtrConst(int input_index) const {
240 241
    return has_inline_inputs() ? &(inline_inputs()[input_index])
                               : &(outline_inputs()->inputs()[input_index]);
242
  }
243
  Node** GetInputPtr(int input_index) {
244 245
    return has_inline_inputs() ? &(inline_inputs()[input_index])
                               : &(outline_inputs()->inputs()[input_index]);
246 247 248
  }
  Use* GetUsePtr(int input_index) {
    Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this)
249
                                   : reinterpret_cast<Use*>(outline_inputs());
250
    return &ptr[-1 - input_index];
251 252
  }

253 254
  void AppendUse(Use* use);
  void RemoveUse(Use* use);
255 256 257

  void* operator new(size_t, void* location) { return location; }

258 259 260
  // Only NodeProperties should manipulate the op.
  void set_op(const Operator* op) { op_ = op; }

261
  // Only NodeProperties should manipulate the type.
262 263
  Type type() const { return type_; }
  void set_type(Type type) { type_ = type; }
264 265

  // Only NodeMarkers should manipulate the marks on nodes.
266
  Mark mark() const { return mark_; }
267 268
  void set_mark(Mark mark) { mark_ = mark; }

269 270
  inline bool has_inline_inputs() const {
    return InlineCountField::decode(bit_field_) != kOutlineMarker;
271 272
  }

273
  void ClearInputs(int start, int count);
274

275 276 277
  using IdField = base::BitField<NodeId, 0, 24>;
  using InlineCountField = base::BitField<unsigned, 24, 4>;
  using InlineCapacityField = base::BitField<unsigned, 28, 4>;
278 279
  static const int kOutlineMarker = InlineCountField::kMax;
  static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
280

281
  const Operator* op_;
282
  Type type_;
283
  Mark mark_;
284
  uint32_t bit_field_;
285
  Use* first_use_;
286

287 288 289 290
  friend class Edge;
  friend class NodeMarkerBase;
  friend class NodeProperties;

291 292 293
  DISALLOW_COPY_AND_ASSIGN(Node);
};

294 295 296 297 298 299 300 301
Address Node::inputs_location() const {
  return reinterpret_cast<Address>(this) + sizeof(Node);
}

Node** Node::OutOfLineInputs::inputs() {
  return reinterpret_cast<Node**>(reinterpret_cast<Address>(this) +
                                  sizeof(Node::OutOfLineInputs));
}
302

303 304 305 306
std::ostream& operator<<(std::ostream& os, const Node& n);


// Typedefs to shorten commonly used Node containers.
307 308 309 310
using NodeDeque = ZoneDeque<Node*>;
using NodeSet = ZoneSet<Node*>;
using NodeVector = ZoneVector<Node*>;
using NodeVectorVector = ZoneVector<NodeVector>;
311

312 313
class Node::InputEdges final {
 public:
314
  using value_type = Edge;
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335

  class iterator;
  inline iterator begin() const;
  inline iterator end() const;

  bool empty() const { return count_ == 0; }
  int count() const { return count_; }

  inline value_type operator[](int index) const;

  InputEdges(Node** input_root, Use* use_root, int count)
      : input_root_(input_root), use_root_(use_root), count_(count) {}

 private:
  Node** input_root_;
  Use* use_root_;
  int count_;
};

class V8_EXPORT_PRIVATE Node::Inputs final {
 public:
336
  using value_type = Node*;
337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353

  class const_iterator;
  inline const_iterator begin() const;
  inline const_iterator end() const;

  bool empty() const { return count_ == 0; }
  int count() const { return count_; }

  inline value_type operator[](int index) const;

  explicit Inputs(Node* const* input_root, int count)
      : input_root_(input_root), count_(count) {}

 private:
  Node* const* input_root_;
  int count_;
};
354

355 356
// An encapsulation for information associated with a single use of node as a
// input from another node, allowing access to both the defining node and
danno's avatar
danno committed
357
// the node having the input.
358
class Edge final {
359
 public:
360 361
  Node* from() const { return use_->from(); }
  Node* to() const { return *input_ptr_; }
362
  int index() const {
363 364
    int const index = use_->input_index();
    DCHECK_LT(index, use_->from()->InputCount());
365 366 367
    return index;
  }

368
  bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
danno's avatar
danno committed
369 370
  bool operator!=(const Edge& other) { return !(*this == other); }

371 372 373 374 375 376 377 378
  void UpdateTo(Node* new_to) {
    Node* old_to = *input_ptr_;
    if (old_to != new_to) {
      if (old_to) old_to->RemoveUse(use_);
      *input_ptr_ = new_to;
      if (new_to) new_to->AppendUse(use_);
    }
  }
danno's avatar
danno committed
379

380
 private:
danno's avatar
danno committed
381
  friend class Node::UseEdges::iterator;
382
  friend class Node::InputEdges;
danno's avatar
danno committed
383
  friend class Node::InputEdges::iterator;
384

385 386 387 388 389
  Edge(Node::Use* use, Node** input_ptr) : use_(use), input_ptr_(input_ptr) {
    DCHECK_NOT_NULL(use);
    DCHECK_NOT_NULL(input_ptr);
    DCHECK_EQ(input_ptr, use->input_ptr());
  }
390

391 392
  Node::Use* use_;
  Node** input_ptr_;
393 394
};

395 396 397 398 399 400 401 402
bool Node::IsDead() const {
  Node::Inputs inputs = this->inputs();
  return inputs.count() > 0 && inputs[0] == nullptr;
}

Node::InputEdges Node::input_edges() {
  int inline_count = InlineCountField::decode(bit_field_);
  if (inline_count != kOutlineMarker) {
403
    return InputEdges(inline_inputs(), reinterpret_cast<Use*>(this) - 1,
404 405
                      inline_count);
  } else {
406 407 408
    return InputEdges(outline_inputs()->inputs(),
                      reinterpret_cast<Use*>(outline_inputs()) - 1,
                      outline_inputs()->count_);
409 410 411 412 413 414
  }
}

Node::Inputs Node::inputs() const {
  int inline_count = InlineCountField::decode(bit_field_);
  if (inline_count != kOutlineMarker) {
415
    return Inputs(inline_inputs(), inline_count);
416
  } else {
417
    return Inputs(outline_inputs()->inputs(), outline_inputs()->count_);
418 419
  }
}
420

421
// A forward iterator to visit the edges for the input dependencies of a node.
422
class Node::InputEdges::iterator final {
danno's avatar
danno committed
423
 public:
424 425 426 427 428
  using iterator_category = std::forward_iterator_tag;
  using difference_type = std::ptrdiff_t;
  using value_type = Edge;
  using pointer = Edge*;
  using reference = Edge&;
429

430
  iterator() : use_(nullptr), input_ptr_(nullptr) {}
431
  iterator(const iterator& other) = default;
danno's avatar
danno committed
432

433
  Edge operator*() const { return Edge(use_, input_ptr_); }
434
  bool operator==(const iterator& other) const {
435
    return input_ptr_ == other.input_ptr_;
436 437
  }
  bool operator!=(const iterator& other) const { return !(*this == other); }
danno's avatar
danno committed
438
  iterator& operator++() {
439 440
    input_ptr_++;
    use_--;
danno's avatar
danno committed
441 442
    return *this;
  }
443
  iterator operator++(int);
444 445 446 447 448 449 450 451 452
  iterator& operator+=(difference_type offset) {
    input_ptr_ += offset;
    use_ -= offset;
    return *this;
  }
  iterator operator+(difference_type offset) const {
    return iterator(use_ - offset, input_ptr_ + offset);
  }
  difference_type operator-(const iterator& other) const {
453
    return input_ptr_ - other.input_ptr_;
454
  }
danno's avatar
danno committed
455 456 457 458

 private:
  friend class Node;

459 460 461
  explicit iterator(Use* use, Node** input_ptr)
      : use_(use), input_ptr_(input_ptr) {}

462 463
  Use* use_;
  Node** input_ptr_;
danno's avatar
danno committed
464 465 466
};


467
Node::InputEdges::iterator Node::InputEdges::begin() const {
468
  return Node::InputEdges::iterator(use_root_, input_root_);
469 470 471 472
}


Node::InputEdges::iterator Node::InputEdges::end() const {
473
  return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
474 475
}

476 477 478
Edge Node::InputEdges::operator[](int index) const {
  return Edge(use_root_ + index, input_root_ + index);
}
479

danno's avatar
danno committed
480
// A forward iterator to visit the inputs of a node.
481
class Node::Inputs::const_iterator final {
482
 public:
483 484 485 486 487
  using iterator_category = std::forward_iterator_tag;
  using difference_type = std::ptrdiff_t;
  using value_type = Node*;
  using pointer = const value_type*;
  using reference = value_type&;
danno's avatar
danno committed
488

489
  const_iterator(const const_iterator& other) = default;
490

491
  Node* operator*() const { return *input_ptr_; }
492
  bool operator==(const const_iterator& other) const {
493
    return input_ptr_ == other.input_ptr_;
494 495 496 497 498
  }
  bool operator!=(const const_iterator& other) const {
    return !(*this == other);
  }
  const_iterator& operator++() {
499
    ++input_ptr_;
500 501
    return *this;
  }
502
  const_iterator operator++(int);
503
  const_iterator& operator+=(difference_type offset) {
504
    input_ptr_ += offset;
505 506 507
    return *this;
  }
  const_iterator operator+(difference_type offset) const {
508
    return const_iterator(input_ptr_ + offset);
509 510
  }
  difference_type operator-(const const_iterator& other) const {
511
    return input_ptr_ - other.input_ptr_;
512
  }
danno's avatar
danno committed
513 514 515 516

 private:
  friend class Node::Inputs;

517
  explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
518

519
  Node* const* input_ptr_;
danno's avatar
danno committed
520 521
};

522 523

Node::Inputs::const_iterator Node::Inputs::begin() const {
524
  return const_iterator(input_root_);
525 526 527 528
}


Node::Inputs::const_iterator Node::Inputs::end() const {
529
  return const_iterator(input_root_ + count_);
530 531
}

532
Node* Node::Inputs::operator[](int index) const { return input_root_[index]; }
533

534
// A forward iterator to visit the uses edges of a node.
535
class Node::UseEdges::iterator final {
danno's avatar
danno committed
536
 public:
537
  iterator(const iterator& other) = default;
danno's avatar
danno committed
538

539
  Edge operator*() const { return Edge(current_, current_->input_ptr()); }
540 541 542 543
  bool operator==(const iterator& other) const {
    return current_ == other.current_;
  }
  bool operator!=(const iterator& other) const { return !(*this == other); }
danno's avatar
danno committed
544
  iterator& operator++() {
545
    DCHECK_NOT_NULL(current_);
danno's avatar
danno committed
546
    current_ = next_;
547
    next_ = current_ ? current_->next : nullptr;
548 549
    return *this;
  }
550
  iterator operator++(int);
551 552

 private:
danno's avatar
danno committed
553 554
  friend class Node::UseEdges;

555
  iterator() : current_(nullptr), next_(nullptr) {}
danno's avatar
danno committed
556 557
  explicit iterator(Node* node)
      : current_(node->first_use_),
558
        next_(current_ ? current_->next : nullptr) {}
559

danno's avatar
danno committed
560 561
  Node::Use* current_;
  Node::Use* next_;
562 563
};

564

565
Node::UseEdges::iterator Node::UseEdges::begin() const {
danno's avatar
danno committed
566 567 568 569
  return Node::UseEdges::iterator(this->node_);
}


570 571
Node::UseEdges::iterator Node::UseEdges::end() const {
  return Node::UseEdges::iterator();
572 573 574
}


575
// A forward iterator to visit the uses of a node.
576
class Node::Uses::const_iterator final {
577
 public:
578 579 580 581 582
  using iterator_category = std::forward_iterator_tag;
  using difference_type = int;
  using value_type = Node*;
  using pointer = Node**;
  using reference = Node*&;
583

584
  Node* operator*() const { return current_->from(); }
585 586
  bool operator==(const const_iterator& other) const {
    return other.current_ == current_;
587
  }
588 589
  bool operator!=(const const_iterator& other) const {
    return other.current_ != current_;
590
  }
591 592
  const_iterator& operator++() {
    DCHECK_NOT_NULL(current_);
593 594
    // Checking no use gets mutated while iterating through them, a potential
    // very tricky cause of bug.
595
    current_ = current_->next;
596 597 598 599
#ifdef DEBUG
    DCHECK_EQ(current_, next_);
    next_ = current_ ? current_->next : nullptr;
#endif
600
    return *this;
601
  }
602
  const_iterator operator++(int);
603

604 605
 private:
  friend class Node::Uses;
606

607
  const_iterator() : current_(nullptr) {}
608 609 610 611 612 613 614 615
  explicit const_iterator(Node* node)
      : current_(node->first_use_)
#ifdef DEBUG
        ,
        next_(current_ ? current_->next : nullptr)
#endif
  {
  }
616

617
  Node::Use* current_;
618 619 620
#ifdef DEBUG
  Node::Use* next_;
#endif
621
};
622 623


624 625
Node::Uses::const_iterator Node::Uses::begin() const {
  return const_iterator(this->node_);
626 627 628
}


629
Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
630

631 632 633
}  // namespace compiler
}  // namespace internal
}  // namespace v8
634 635

#endif  // V8_COMPILER_NODE_H_