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

#include "src/compiler/opcodes.h"
#include "src/compiler/operator.h"
10
#include "src/compiler/types.h"
11
#include "src/globals.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 26 27
// 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.
typedef uint32_t Mark;

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
typedef uint32_t NodeId;
32

33

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

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

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

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

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

  int InputCount() const {
    return has_inline_inputs() ? InlineCountField::decode(bit_field_)
                               : inputs_.outline_->count_;
  }
65

66
#ifdef DEBUG
67 68 69 70 71 72 73 74 75 76 77 78 79 80
  void Verify();
#define BOUNDS_CHECK(index)                                                  \
  do {                                                                       \
    if (index < 0 || index >= InputCount()) {                                \
      V8_Fatal(__FILE__, __LINE__, "Node #%d:%s->InputAt(%d) out of bounds", \
               id(), op()->mnemonic(), index);                               \
    }                                                                        \
  } while (false)
#else
  // No bounds checks or verification in release mode.
  inline void Verify() {}
#define BOUNDS_CHECK(index) \
  do {                      \
  } while (false)
81
#endif
82 83 84 85

  Node* InputAt(int index) const {
    BOUNDS_CHECK(index);
    return *GetInputPtrConst(index);
86
  }
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

  void ReplaceInput(int index, Node* new_to) {
    BOUNDS_CHECK(index);
    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);
    }
  }

#undef BOUNDS_CHECK

102 103
  void AppendInput(Zone* zone, Node* new_to);
  void InsertInput(Zone* zone, int index, Node* new_to);
104
  void InsertInputs(Zone* zone, int index, int count);
105
  void RemoveInput(int index);
106
  void NullAllInputs();
107
  void TrimInputCount(int new_input_count);
108

109
  int UseCount() const;
110
  void ReplaceUses(Node* replace_to);
111

112 113
  class InputEdges;
  inline InputEdges input_edges();
114

115 116
  class Inputs;
  inline Inputs inputs() const;
danno's avatar
danno committed
117

118
  class UseEdges final {
danno's avatar
danno committed
119
   public:
120 121
    typedef Edge value_type;

danno's avatar
danno committed
122
    class iterator;
123 124 125
    inline iterator begin() const;
    inline iterator end() const;

danno's avatar
danno committed
126 127 128 129 130 131 132
    bool empty() const;

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

   private:
    Node* node_;
  };
133

134 135
  UseEdges use_edges() { return UseEdges(this); }

136
  class V8_EXPORT_PRIVATE Uses final {
137
   public:
138 139 140 141 142 143
    typedef Node* value_type;

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

danno's avatar
danno committed
144
    bool empty() const;
145 146 147 148 149 150 151 152 153

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

   private:
    Node* node_;
  };

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

154 155
  // Returns true if {owner} is the user of {this} node.
  bool OwnedBy(Node* owner) const {
156
    return first_use_ && first_use_->from() == owner && !first_use_->next;
157
  }
158

159 160
  // Returns true if {owner1} and {owner2} are the only users of {this} node.
  bool OwnedBy(Node const* owner1, Node const* owner2) const;
161 162 163 164

  // Returns true if addressing related operands (such as load, store, lea)
  // are the only users of {this} node.
  bool OwnedByAddressingOperand() const;
165
  void Print() const;
166

167
 private:
168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183
  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_;
    Node* inputs_[1];

    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 {
184 185
    Use* next;
    Use* prev;
186 187 188 189 190 191 192 193 194 195 196 197
    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()
                          ? reinterpret_cast<Node*>(start)->inputs_.inline_
                          : reinterpret_cast<OutOfLineInputs*>(start)->inputs_;
      return &inputs[index];
    }
198

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

205 206
    typedef BitField<bool, 0, 1> InlineField;
    typedef BitField<unsigned, 1, 17> InputIndexField;
207 208
    // Leaving some space in the bitset in case we ever decide to record
    // the output index.
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 240 241 242 243 244 245 246
  //============================================================================
  //== 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);

  Node* const* GetInputPtrConst(int input_index) const {
    return has_inline_inputs() ? &(inputs_.inline_[input_index])
                               : &inputs_.outline_->inputs_[input_index];
247
  }
248 249 250 251 252 253 254 255
  Node** GetInputPtr(int input_index) {
    return has_inline_inputs() ? &(inputs_.inline_[input_index])
                               : &inputs_.outline_->inputs_[input_index];
  }
  Use* GetUsePtr(int input_index) {
    Use* ptr = has_inline_inputs() ? reinterpret_cast<Use*>(this)
                                   : reinterpret_cast<Use*>(inputs_.outline_);
    return &ptr[-1 - input_index];
256 257
  }

258 259
  void AppendUse(Use* use);
  void RemoveUse(Use* use);
260 261 262

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

263 264 265
  // Only NodeProperties should manipulate the op.
  void set_op(const Operator* op) { op_ = op; }

266 267 268
  // Only NodeProperties should manipulate the type.
  Type* type() const { return type_; }
  void set_type(Type* type) { type_ = type; }
269 270

  // Only NodeMarkers should manipulate the marks on nodes.
271
  Mark mark() const { return mark_; }
272 273
  void set_mark(Mark mark) { mark_ = mark; }

274 275
  inline bool has_inline_inputs() const {
    return InlineCountField::decode(bit_field_) != kOutlineMarker;
276 277
  }

278
  void ClearInputs(int start, int count);
279

280 281 282 283 284 285
  typedef BitField<NodeId, 0, 24> IdField;
  typedef BitField<unsigned, 24, 4> InlineCountField;
  typedef BitField<unsigned, 28, 4> InlineCapacityField;
  static const int kOutlineMarker = InlineCountField::kMax;
  static const int kMaxInlineCount = InlineCountField::kMax - 1;
  static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
286

287
  const Operator* op_;
288
  Type* type_;
289
  Mark mark_;
290
  uint32_t bit_field_;
291
  Use* first_use_;
292
  union {
293 294 295
    // Inline storage for inputs or out-of-line storage.
    Node* inline_[1];
    OutOfLineInputs* outline_;
296 297
  } inputs_;

298 299 300 301
  friend class Edge;
  friend class NodeMarkerBase;
  friend class NodeProperties;

302 303 304
  DISALLOW_COPY_AND_ASSIGN(Node);
};

305

306 307 308 309 310
std::ostream& operator<<(std::ostream& os, const Node& n);


// Typedefs to shorten commonly used Node containers.
typedef ZoneDeque<Node*> NodeDeque;
311
typedef ZoneSet<Node*> NodeSet;
312 313 314 315 316 317 318 319 320 321
typedef ZoneVector<Node*> NodeVector;
typedef ZoneVector<NodeVector> NodeVectorVector;


// Helper to extract parameters from Operator1<*> nodes.
template <typename T>
static inline const T& OpParameter(const Node* node) {
  return OpParameter<T>(node->op());
}

322 323 324 325 326 327 328 329 330 331 332 333 334 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
class Node::InputEdges final {
 public:
  typedef Edge value_type;

  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:
  typedef Node* value_type;

  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_;
};
364

365 366
// 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
367
// the node having the input.
368
class Edge final {
369
 public:
370 371
  Node* from() const { return use_->from(); }
  Node* to() const { return *input_ptr_; }
372
  int index() const {
373 374
    int const index = use_->input_index();
    DCHECK_LT(index, use_->from()->InputCount());
375 376 377
    return index;
  }

378
  bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
danno's avatar
danno committed
379 380
  bool operator!=(const Edge& other) { return !(*this == other); }

381 382 383 384 385 386 387 388
  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
389

390
 private:
danno's avatar
danno committed
391
  friend class Node::UseEdges::iterator;
392
  friend class Node::InputEdges;
danno's avatar
danno committed
393
  friend class Node::InputEdges::iterator;
394

395 396 397 398 399
  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());
  }
400

401 402
  Node::Use* use_;
  Node** input_ptr_;
403 404
};

405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
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) {
    return InputEdges(inputs_.inline_, reinterpret_cast<Use*>(this) - 1,
                      inline_count);
  } else {
    return InputEdges(inputs_.outline_->inputs_,
                      reinterpret_cast<Use*>(inputs_.outline_) - 1,
                      inputs_.outline_->count_);
  }
}

Node::Inputs Node::inputs() const {
  int inline_count = InlineCountField::decode(bit_field_);
  if (inline_count != kOutlineMarker) {
    return Inputs(inputs_.inline_, inline_count);
  } else {
    return Inputs(inputs_.outline_->inputs_, inputs_.outline_->count_);
  }
}
430

431
// A forward iterator to visit the edges for the input dependencies of a node.
432
class Node::InputEdges::iterator final {
danno's avatar
danno committed
433 434
 public:
  typedef std::forward_iterator_tag iterator_category;
435
  typedef std::ptrdiff_t difference_type;
danno's avatar
danno committed
436 437 438
  typedef Edge value_type;
  typedef Edge* pointer;
  typedef Edge& reference;
439

440 441 442
  iterator() : use_(nullptr), input_ptr_(nullptr) {}
  iterator(const iterator& other)
      : use_(other.use_), input_ptr_(other.input_ptr_) {}
danno's avatar
danno committed
443

444
  Edge operator*() const { return Edge(use_, input_ptr_); }
445
  bool operator==(const iterator& other) const {
446
    return input_ptr_ == other.input_ptr_;
447 448
  }
  bool operator!=(const iterator& other) const { return !(*this == other); }
danno's avatar
danno committed
449
  iterator& operator++() {
450 451
    input_ptr_++;
    use_--;
danno's avatar
danno committed
452 453
    return *this;
  }
454
  iterator operator++(int);
455 456 457 458 459 460 461 462 463
  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 {
464
    return input_ptr_ - other.input_ptr_;
465
  }
danno's avatar
danno committed
466 467 468 469

 private:
  friend class Node;

470 471 472
  explicit iterator(Use* use, Node** input_ptr)
      : use_(use), input_ptr_(input_ptr) {}

473 474
  Use* use_;
  Node** input_ptr_;
danno's avatar
danno committed
475 476 477
};


478
Node::InputEdges::iterator Node::InputEdges::begin() const {
479
  return Node::InputEdges::iterator(use_root_, input_root_);
480 481 482 483
}


Node::InputEdges::iterator Node::InputEdges::end() const {
484
  return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
485 486
}

487 488 489
Edge Node::InputEdges::operator[](int index) const {
  return Edge(use_root_ + index, input_root_ + index);
}
490

danno's avatar
danno committed
491
// A forward iterator to visit the inputs of a node.
492
class Node::Inputs::const_iterator final {
493
 public:
danno's avatar
danno committed
494
  typedef std::forward_iterator_tag iterator_category;
495
  typedef std::ptrdiff_t difference_type;
danno's avatar
danno committed
496
  typedef Node* value_type;
497 498
  typedef const value_type* pointer;
  typedef value_type& reference;
danno's avatar
danno committed
499

500
  const_iterator(const const_iterator& other) : input_ptr_(other.input_ptr_) {}
501

502
  Node* operator*() const { return *input_ptr_; }
503
  bool operator==(const const_iterator& other) const {
504
    return input_ptr_ == other.input_ptr_;
505 506 507 508 509
  }
  bool operator!=(const const_iterator& other) const {
    return !(*this == other);
  }
  const_iterator& operator++() {
510
    ++input_ptr_;
511 512
    return *this;
  }
513
  const_iterator operator++(int);
514
  const_iterator& operator+=(difference_type offset) {
515
    input_ptr_ += offset;
516 517 518
    return *this;
  }
  const_iterator operator+(difference_type offset) const {
519
    return const_iterator(input_ptr_ + offset);
520 521
  }
  difference_type operator-(const const_iterator& other) const {
522
    return input_ptr_ - other.input_ptr_;
523
  }
danno's avatar
danno committed
524 525 526 527

 private:
  friend class Node::Inputs;

528
  explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
529

530
  Node* const* input_ptr_;
danno's avatar
danno committed
531 532
};

533 534

Node::Inputs::const_iterator Node::Inputs::begin() const {
535
  return const_iterator(input_root_);
536 537 538 539
}


Node::Inputs::const_iterator Node::Inputs::end() const {
540
  return const_iterator(input_root_ + count_);
541 542
}

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

545
// A forward iterator to visit the uses edges of a node.
546
class Node::UseEdges::iterator final {
danno's avatar
danno committed
547
 public:
548 549
  iterator(const iterator& other)
      : current_(other.current_), next_(other.next_) {}
danno's avatar
danno committed
550

551
  Edge operator*() const { return Edge(current_, current_->input_ptr()); }
552 553 554 555
  bool operator==(const iterator& other) const {
    return current_ == other.current_;
  }
  bool operator!=(const iterator& other) const { return !(*this == other); }
danno's avatar
danno committed
556
  iterator& operator++() {
557
    DCHECK_NOT_NULL(current_);
danno's avatar
danno committed
558
    current_ = next_;
559
    next_ = current_ ? current_->next : nullptr;
560 561
    return *this;
  }
562
  iterator operator++(int);
563 564

 private:
danno's avatar
danno committed
565 566
  friend class Node::UseEdges;

567
  iterator() : current_(nullptr), next_(nullptr) {}
danno's avatar
danno committed
568 569
  explicit iterator(Node* node)
      : current_(node->first_use_),
570
        next_(current_ ? current_->next : nullptr) {}
571

danno's avatar
danno committed
572 573
  Node::Use* current_;
  Node::Use* next_;
574 575
};

576

577
Node::UseEdges::iterator Node::UseEdges::begin() const {
danno's avatar
danno committed
578 579 580 581
  return Node::UseEdges::iterator(this->node_);
}


582 583
Node::UseEdges::iterator Node::UseEdges::end() const {
  return Node::UseEdges::iterator();
584 585 586
}


587
// A forward iterator to visit the uses of a node.
588
class Node::Uses::const_iterator final {
589 590 591 592 593 594
 public:
  typedef std::forward_iterator_tag iterator_category;
  typedef int difference_type;
  typedef Node* value_type;
  typedef Node** pointer;
  typedef Node*& reference;
595

596 597 598 599 600 601 602 603
  const_iterator(const const_iterator& other)
      : current_(other.current_)
#ifdef DEBUG
        ,
        next_(other.next_)
#endif
  {
  }
604

605
  Node* operator*() const { return current_->from(); }
606 607
  bool operator==(const const_iterator& other) const {
    return other.current_ == current_;
608
  }
609 610
  bool operator!=(const const_iterator& other) const {
    return other.current_ != current_;
611
  }
612 613
  const_iterator& operator++() {
    DCHECK_NOT_NULL(current_);
614 615
    // Checking no use gets mutated while iterating through them, a potential
    // very tricky cause of bug.
616
    current_ = current_->next;
617 618 619 620
#ifdef DEBUG
    DCHECK_EQ(current_, next_);
    next_ = current_ ? current_->next : nullptr;
#endif
621
    return *this;
622
  }
623
  const_iterator operator++(int);
624

625 626
 private:
  friend class Node::Uses;
627

628
  const_iterator() : current_(nullptr) {}
629 630 631 632 633 634 635 636
  explicit const_iterator(Node* node)
      : current_(node->first_use_)
#ifdef DEBUG
        ,
        next_(current_ ? current_->next : nullptr)
#endif
  {
  }
637

638
  Node::Use* current_;
639 640 641
#ifdef DEBUG
  Node::Use* next_;
#endif
642
};
643 644


645 646
Node::Uses::const_iterator Node::Uses::begin() const {
  return const_iterator(this->node_);
647 648 649
}


650
Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
651

652 653 654
}  // namespace compiler
}  // namespace internal
}  // namespace v8
655 656

#endif  // V8_COMPILER_NODE_H_