node.h 20.9 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
#include "src/compiler/graph-zone-traits.h"
10 11
#include "src/compiler/opcodes.h"
#include "src/compiler/operator.h"
12
#include "src/compiler/types.h"
13
#include "src/zone/zone-containers.h"
14 15 16 17 18

namespace v8 {
namespace internal {
namespace compiler {

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

23

24 25 26
// 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.
27
using Mark = uint32_t;
28

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

33 34 35 36 37 38 39 40 41
// 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.
42
class V8_EXPORT_PRIVATE Node final {
43
 public:
44
  static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count,
45 46
                   Node* const* inputs, bool has_extensible_inputs);
  static Node* Clone(Zone* zone, NodeId id, const Node* node);
47

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

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

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

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

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

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

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

  void ReplaceInput(int index, Node* new_to) {
78 79
    CHECK_LE(0, index);
    CHECK_LT(index, InputCount());
80
    ZoneNodePtr* input_ptr = GetInputPtr(index);
81 82 83 84 85 86 87 88 89
    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);
    }
  }

90 91
  void AppendInput(Zone* zone, Node* new_to);
  void InsertInput(Zone* zone, int index, Node* new_to);
92
  void InsertInputs(Zone* zone, int index, int count);
93 94
  // Returns the removed input.
  Node* RemoveInput(int index);
95
  void NullAllInputs();
96
  void TrimInputCount(int new_input_count);
97 98
  // Can trim, extend by appending new inputs, or do nothing.
  void EnsureInputCount(Zone* zone, int new_input_count);
99

100
  int UseCount() const;
101
  void ReplaceUses(Node* replace_to);
102

103 104
  class InputEdges;
  inline InputEdges input_edges();
105

106 107
  class Inputs;
  inline Inputs inputs() const;
danno's avatar
danno committed
108

109
  class UseEdges final {
danno's avatar
danno committed
110
   public:
111
    using value_type = Edge;
112

danno's avatar
danno committed
113
    class iterator;
114 115 116
    inline iterator begin() const;
    inline iterator end() const;

danno's avatar
danno committed
117 118 119 120 121 122 123
    bool empty() const;

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

   private:
    Node* node_;
  };
124

125 126
  UseEdges use_edges() { return UseEdges(this); }

127
  class V8_EXPORT_PRIVATE Uses final {
128
   public:
129
    using value_type = Node*;
130 131 132 133 134

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

danno's avatar
danno committed
135
    bool empty() const;
136 137 138 139 140 141 142 143 144

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

   private:
    Node* node_;
  };

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

145
  // Returns true if {owner} is the only user of {this} node.
146
  bool OwnedBy(Node const* owner) const;
147

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

151 152
  void Print() const { Print(1); }
  void Print(int depth) const;
153
  void Print(std::ostream&, int depth = 1) const;
154

155
 private:
156 157 158 159 160
  template <typename NodePtrT>
  inline static Node* NewImpl(Zone* zone, NodeId id, const Operator* op,
                              int input_count, NodePtrT const* inputs,
                              bool has_extensible_inputs);

161
  struct Use;
162 163
  using ZoneUsePtr = GraphZoneTraits::Ptr<Use>;

164 165 166
  // Out of line storage for inputs when the number of inputs overflowed the
  // capacity of the inline-allocated space.
  struct OutOfLineInputs {
167
    ZoneNodePtr node_;
168 169
    int count_;
    int capacity_;
170 171

    // Inputs are allocated right behind the OutOfLineInputs instance.
172
    inline ZoneNodePtr* inputs();
173 174

    static OutOfLineInputs* New(Zone* zone, int capacity);
175
    void ExtractFrom(Use* use_ptr, ZoneNodePtr* input_ptr, int count);
176
  };
177
  using ZoneOutOfLineInputsPtr = GraphZoneTraits::Ptr<OutOfLineInputs>;
178 179 180 181

  // 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 {
182 183
    ZoneUsePtr next;
    ZoneUsePtr prev;
184 185 186 187
    uint32_t bit_field_;

    int input_index() const { return InputIndexField::decode(bit_field_); }
    bool is_inline_use() const { return InlineField::decode(bit_field_); }
188
    ZoneNodePtr* input_ptr() {
189 190
      int index = input_index();
      Use* start = this + 1 + index;
191 192
      ZoneNodePtr* inputs =
          is_inline_use() ? reinterpret_cast<Node*>(start)->inline_inputs()
193
                          : reinterpret_cast<OutOfLineInputs*>(start)->inputs();
194 195
      return &inputs[index];
    }
196

197 198 199 200 201
    Node* from() {
      Use* start = this + 1 + input_index();
      return is_inline_use() ? reinterpret_cast<Node*>(start)
                             : reinterpret_cast<OutOfLineInputs*>(start)->node_;
    }
202

203 204
    using InlineField = base::BitField<bool, 0, 1>;
    using InputIndexField = base::BitField<unsigned, 1, 31>;
205 206
  };

207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
  //============================================================================
  //== 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);

240 241
  inline Address inputs_location() const;

242 243
  ZoneNodePtr* inline_inputs() const {
    return reinterpret_cast<ZoneNodePtr*>(inputs_location());
244 245
  }
  OutOfLineInputs* outline_inputs() const {
246
    return *reinterpret_cast<ZoneOutOfLineInputsPtr*>(inputs_location());
247 248
  }
  void set_outline_inputs(OutOfLineInputs* outline) {
249
    *reinterpret_cast<ZoneOutOfLineInputsPtr*>(inputs_location()) = outline;
250 251
  }

252
  ZoneNodePtr const* GetInputPtrConst(int input_index) const {
253 254
    return has_inline_inputs() ? &(inline_inputs()[input_index])
                               : &(outline_inputs()->inputs()[input_index]);
255
  }
256
  ZoneNodePtr* GetInputPtr(int input_index) {
257 258
    return has_inline_inputs() ? &(inline_inputs()[input_index])
                               : &(outline_inputs()->inputs()[input_index]);
259 260 261
  }
  Use* GetUsePtr(int input_index) {
    Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this)
262
                                   : reinterpret_cast<Use*>(outline_inputs());
263
    return &ptr[-1 - input_index];
264 265
  }

266 267
  void AppendUse(Use* use);
  void RemoveUse(Use* use);
268 269 270

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

271 272 273
  // Only NodeProperties should manipulate the op.
  void set_op(const Operator* op) { op_ = op; }

274
  // Only NodeProperties should manipulate the type.
275 276
  Type type() const { return type_; }
  void set_type(Type type) { type_ = type; }
277 278

  // Only NodeMarkers should manipulate the marks on nodes.
279
  Mark mark() const { return mark_; }
280 281
  void set_mark(Mark mark) { mark_ = mark; }

282 283
  inline bool has_inline_inputs() const {
    return InlineCountField::decode(bit_field_) != kOutlineMarker;
284 285
  }

286
  void ClearInputs(int start, int count);
287

288 289 290
  using IdField = base::BitField<NodeId, 0, 24>;
  using InlineCountField = base::BitField<unsigned, 24, 4>;
  using InlineCapacityField = base::BitField<unsigned, 28, 4>;
291 292
  static const int kOutlineMarker = InlineCountField::kMax;
  static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
293

294
  const Operator* op_;
295
  Type type_;
296
  Mark mark_;
297
  uint32_t bit_field_;
298
  ZoneUsePtr first_use_;
299

300 301 302 303
  friend class Edge;
  friend class NodeMarkerBase;
  friend class NodeProperties;

304 305 306
  DISALLOW_COPY_AND_ASSIGN(Node);
};

307 308 309 310
Address Node::inputs_location() const {
  return reinterpret_cast<Address>(this) + sizeof(Node);
}

311 312 313
ZoneNodePtr* Node::OutOfLineInputs::inputs() {
  return reinterpret_cast<ZoneNodePtr*>(reinterpret_cast<Address>(this) +
                                        sizeof(Node::OutOfLineInputs));
314
}
315

316 317
std::ostream& operator<<(std::ostream& os, const Node& n);

318 319 320 321 322 323 324
// Base class for node wrappers.
class NodeWrapper {
 public:
  explicit constexpr NodeWrapper(Node* node) : node_(node) {}
  operator Node*() const { return node_; }
  Node* operator->() const { return node_; }

325 326 327 328 329 330 331
 protected:
  Node* node() const { return node_; }
  void set_node(Node* node) {
    DCHECK_NOT_NULL(node);
    node_ = node;
  }

332 333 334
 private:
  Node* node_;
};
335

336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
// Wrapper classes for special node/edge types (effect, control, frame states).

class Effect : public NodeWrapper {
 public:
  explicit constexpr Effect(Node* node) : NodeWrapper(node) {
    // TODO(jgruber): Remove the End special case.
    SLOW_DCHECK(node == nullptr || node->op()->opcode() == IrOpcode::kEnd ||
                node->op()->EffectOutputCount() > 0);
  }

  // Support the common `Node* x = effect = ...` pattern.
  Node* operator=(Node* value) {
    DCHECK_GT(value->op()->EffectOutputCount(), 0);
    set_node(value);
    return value;
  }
};

class Control : public NodeWrapper {
 public:
  explicit constexpr Control(Node* node) : NodeWrapper(node) {
    // TODO(jgruber): Remove the End special case.
    SLOW_DCHECK(node == nullptr || node->opcode() == IrOpcode::kEnd ||
                node->op()->ControlOutputCount() > 0);
  }

  // Support the common `Node* x = control = ...` pattern.
  Node* operator=(Node* value) {
    DCHECK_GT(value->op()->ControlOutputCount(), 0);
    set_node(value);
    return value;
  }
};

class FrameState : public NodeWrapper {
 public:
  explicit constexpr FrameState(Node* node) : NodeWrapper(node) {
    // TODO(jgruber): Disallow kStart (needed for PromiseConstructorBasic unit
    // test, among others).
    SLOW_DCHECK(node->opcode() == IrOpcode::kFrameState ||
                node->opcode() == IrOpcode::kStart);
  }

  // Duplicating here from frame-states.h for ease of access and to keep
  // header include-balls small. Equality of the two constants is
  // static-asserted elsewhere.
  static constexpr int kFrameStateOuterStateInput = 5;

  FrameState outer_frame_state() const {
    return FrameState{node()->InputAt(kFrameStateOuterStateInput)};
  }
};

389
// Typedefs to shorten commonly used Node containers.
390 391 392 393
using NodeDeque = ZoneDeque<Node*>;
using NodeSet = ZoneSet<Node*>;
using NodeVector = ZoneVector<Node*>;
using NodeVectorVector = ZoneVector<NodeVector>;
394

395 396
class Node::InputEdges final {
 public:
397
  using value_type = Edge;
398 399 400 401 402 403 404 405 406 407

  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;

408
  InputEdges(ZoneNodePtr* input_root, Use* use_root, int count)
409 410 411
      : input_root_(input_root), use_root_(use_root), count_(count) {}

 private:
412
  ZoneNodePtr* input_root_;
413 414 415 416 417 418
  Use* use_root_;
  int count_;
};

class V8_EXPORT_PRIVATE Node::Inputs final {
 public:
419
  using value_type = Node*;
420 421 422 423 424 425 426 427 428 429

  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;

430
  explicit Inputs(ZoneNodePtr const* input_root, int count)
431 432 433
      : input_root_(input_root), count_(count) {}

 private:
434
  ZoneNodePtr const* input_root_;
435 436
  int count_;
};
437

438 439
// 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
440
// the node having the input.
441
class Edge final {
442
 public:
443 444
  Node* from() const { return use_->from(); }
  Node* to() const { return *input_ptr_; }
445
  int index() const {
446 447
    int const index = use_->input_index();
    DCHECK_LT(index, use_->from()->InputCount());
448 449 450
    return index;
  }

451
  bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
danno's avatar
danno committed
452 453
  bool operator!=(const Edge& other) { return !(*this == other); }

454 455 456 457 458 459 460 461
  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
462

463
 private:
danno's avatar
danno committed
464
  friend class Node::UseEdges::iterator;
465
  friend class Node::InputEdges;
danno's avatar
danno committed
466
  friend class Node::InputEdges::iterator;
467

468 469
  Edge(Node::Use* use, ZoneNodePtr* input_ptr)
      : use_(use), input_ptr_(input_ptr) {
470 471 472 473
    DCHECK_NOT_NULL(use);
    DCHECK_NOT_NULL(input_ptr);
    DCHECK_EQ(input_ptr, use->input_ptr());
  }
474

475
  Node::Use* use_;
476
  ZoneNodePtr* input_ptr_;
477 478
};

479 480 481 482 483 484 485 486
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) {
487
    return InputEdges(inline_inputs(), reinterpret_cast<Use*>(this) - 1,
488 489
                      inline_count);
  } else {
490 491 492
    return InputEdges(outline_inputs()->inputs(),
                      reinterpret_cast<Use*>(outline_inputs()) - 1,
                      outline_inputs()->count_);
493 494 495 496 497 498
  }
}

Node::Inputs Node::inputs() const {
  int inline_count = InlineCountField::decode(bit_field_);
  if (inline_count != kOutlineMarker) {
499
    return Inputs(inline_inputs(), inline_count);
500
  } else {
501
    return Inputs(outline_inputs()->inputs(), outline_inputs()->count_);
502 503
  }
}
504

505
// A forward iterator to visit the edges for the input dependencies of a node.
506
class Node::InputEdges::iterator final {
danno's avatar
danno committed
507
 public:
508 509 510 511 512
  using iterator_category = std::forward_iterator_tag;
  using difference_type = std::ptrdiff_t;
  using value_type = Edge;
  using pointer = Edge*;
  using reference = Edge&;
513

514
  iterator() : use_(nullptr), input_ptr_(nullptr) {}
515
  iterator(const iterator& other) = default;
danno's avatar
danno committed
516

517
  Edge operator*() const { return Edge(use_, input_ptr_); }
518
  bool operator==(const iterator& other) const {
519
    return input_ptr_ == other.input_ptr_;
520 521
  }
  bool operator!=(const iterator& other) const { return !(*this == other); }
danno's avatar
danno committed
522
  iterator& operator++() {
523 524
    input_ptr_++;
    use_--;
danno's avatar
danno committed
525 526
    return *this;
  }
527
  iterator operator++(int);
528 529 530 531 532 533 534 535 536
  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 {
537
    return input_ptr_ - other.input_ptr_;
538
  }
danno's avatar
danno committed
539 540 541 542

 private:
  friend class Node;

543
  explicit iterator(Use* use, ZoneNodePtr* input_ptr)
544 545
      : use_(use), input_ptr_(input_ptr) {}

546
  Use* use_;
547
  ZoneNodePtr* input_ptr_;
danno's avatar
danno committed
548 549 550
};


551
Node::InputEdges::iterator Node::InputEdges::begin() const {
552
  return Node::InputEdges::iterator(use_root_, input_root_);
553 554 555 556
}


Node::InputEdges::iterator Node::InputEdges::end() const {
557
  return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
558 559
}

560 561 562
Edge Node::InputEdges::operator[](int index) const {
  return Edge(use_root_ + index, input_root_ + index);
}
563

danno's avatar
danno committed
564
// A forward iterator to visit the inputs of a node.
565
class Node::Inputs::const_iterator final {
566
 public:
567 568 569 570 571
  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
572

573
  const_iterator(const const_iterator& other) = default;
574

575
  Node* operator*() const { return *input_ptr_; }
576
  bool operator==(const const_iterator& other) const {
577
    return input_ptr_ == other.input_ptr_;
578 579 580 581 582
  }
  bool operator!=(const const_iterator& other) const {
    return !(*this == other);
  }
  const_iterator& operator++() {
583
    ++input_ptr_;
584 585
    return *this;
  }
586
  const_iterator operator++(int);
587
  const_iterator& operator+=(difference_type offset) {
588
    input_ptr_ += offset;
589 590 591
    return *this;
  }
  const_iterator operator+(difference_type offset) const {
592
    return const_iterator(input_ptr_ + offset);
593 594
  }
  difference_type operator-(const const_iterator& other) const {
595
    return input_ptr_ - other.input_ptr_;
596
  }
danno's avatar
danno committed
597 598 599 600

 private:
  friend class Node::Inputs;

601 602
  explicit const_iterator(ZoneNodePtr const* input_ptr)
      : input_ptr_(input_ptr) {}
603

604
  ZoneNodePtr const* input_ptr_;
danno's avatar
danno committed
605 606
};

607 608

Node::Inputs::const_iterator Node::Inputs::begin() const {
609
  return const_iterator(input_root_);
610 611 612 613
}


Node::Inputs::const_iterator Node::Inputs::end() const {
614
  return const_iterator(input_root_ + count_);
615 616
}

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

619
// A forward iterator to visit the uses edges of a node.
620
class Node::UseEdges::iterator final {
danno's avatar
danno committed
621
 public:
622
  iterator(const iterator& other) = default;
danno's avatar
danno committed
623

624
  Edge operator*() const { return Edge(current_, current_->input_ptr()); }
625 626 627 628
  bool operator==(const iterator& other) const {
    return current_ == other.current_;
  }
  bool operator!=(const iterator& other) const { return !(*this == other); }
danno's avatar
danno committed
629
  iterator& operator++() {
630
    DCHECK_NOT_NULL(current_);
danno's avatar
danno committed
631
    current_ = next_;
632
    next_ = current_ ? static_cast<Node::Use*>(current_->next) : nullptr;
633 634
    return *this;
  }
635
  iterator operator++(int);
636 637

 private:
danno's avatar
danno committed
638 639
  friend class Node::UseEdges;

640
  iterator() : current_(nullptr), next_(nullptr) {}
danno's avatar
danno committed
641 642
  explicit iterator(Node* node)
      : current_(node->first_use_),
643
        next_(current_ ? static_cast<Node::Use*>(current_->next) : nullptr) {}
644

danno's avatar
danno committed
645 646
  Node::Use* current_;
  Node::Use* next_;
647 648
};

649

650
Node::UseEdges::iterator Node::UseEdges::begin() const {
danno's avatar
danno committed
651 652 653 654
  return Node::UseEdges::iterator(this->node_);
}


655 656
Node::UseEdges::iterator Node::UseEdges::end() const {
  return Node::UseEdges::iterator();
657 658 659
}


660
// A forward iterator to visit the uses of a node.
661
class Node::Uses::const_iterator final {
662
 public:
663 664 665 666 667
  using iterator_category = std::forward_iterator_tag;
  using difference_type = int;
  using value_type = Node*;
  using pointer = Node**;
  using reference = Node*&;
668

669
  Node* operator*() const { return current_->from(); }
670 671
  bool operator==(const const_iterator& other) const {
    return other.current_ == current_;
672
  }
673 674
  bool operator!=(const const_iterator& other) const {
    return other.current_ != current_;
675
  }
676 677
  const_iterator& operator++() {
    DCHECK_NOT_NULL(current_);
678 679
    // Checking no use gets mutated while iterating through them, a potential
    // very tricky cause of bug.
680
    current_ = current_->next;
681 682 683 684
#ifdef DEBUG
    DCHECK_EQ(current_, next_);
    next_ = current_ ? current_->next : nullptr;
#endif
685
    return *this;
686
  }
687
  const_iterator operator++(int);
688

689 690
 private:
  friend class Node::Uses;
691

692
  const_iterator() : current_(nullptr) {}
693 694 695 696 697 698 699 700
  explicit const_iterator(Node* node)
      : current_(node->first_use_)
#ifdef DEBUG
        ,
        next_(current_ ? current_->next : nullptr)
#endif
  {
  }
701

702
  Node::Use* current_;
703 704 705
#ifdef DEBUG
  Node::Use* next_;
#endif
706
};
707 708


709 710
Node::Uses::const_iterator Node::Uses::begin() const {
  return const_iterator(this->node_);
711 712 713
}


714
Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
715

716 717 718
}  // namespace compiler
}  // namespace internal
}  // namespace v8
719 720

#endif  // V8_COMPILER_NODE_H_