deps/v8/src/compiler/node.h

   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 #ifndef V8_COMPILER_NODE_H_
   6 #define V8_COMPILER_NODE_H_
   7
   8 #include "src/compiler/opcodes.h"
   9 #include "src/compiler/operator.h"
  10 #include "src/types-inl.h"
  11 #include "src/zone-containers.h"
  12
  13 namespace v8 {
  14 namespace internal {
  15 namespace compiler {
  16
  17 // Forward declarations.
  18 class Edge;
  19 class Graph;
  20
  21
  22 // Marks are used during traversal of the graph to distinguish states of nodes.
  23 // Each node has a mark which is a monotonically increasing integer, and a
  24 // {NodeMarker} has a range of values that indicate states of a node.
  25 typedef uint32_t Mark;
  26
  27
  28 // NodeIds are identifying numbers for nodes that can be used to index auxiliary
  29 // out-of-line data associated with each node.
  30 typedef int32_t NodeId;
  31
  32
  33 // A Node is the basic primitive of graphs. Nodes are chained together by
  34 // input/use chains but by default otherwise contain only an identifying number
  35 // which specific applications of graphs and nodes can use to index auxiliary
  36 // out-of-line data, especially transient data.
  37 //
  38 // In addition Nodes only contain a mutable Operator that may change during
  39 // compilation, e.g. during lowering passes. Other information that needs to be
  40 // associated with Nodes during compilation must be stored out-of-line indexed
  41 // by the Node's id.
  42 class Node FINAL {
  43  public:
  44   static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count,
  45                    Node** inputs, bool has_extensible_inputs);
  46
  47   bool IsDead() const { return InputCount() > 0 && !InputAt(0); }
  48   void Kill();
  49
  50   const Operator* op() const { return op_; }
  51   void set_op(const Operator* op) { op_ = op; }
  52
  53   IrOpcode::Value opcode() const {
  54     DCHECK(op_->opcode() <= IrOpcode::kLast);
  55     return static_cast<IrOpcode::Value>(op_->opcode());
  56   }
  57
  58   NodeId id() const { return id_; }
  59
  60   int InputCount() const { return input_count(); }
  61   Node* InputAt(int index) const { return GetInputRecordPtr(index)->to; }
  62   inline void ReplaceInput(int index, Node* new_to);
  63   void AppendInput(Zone* zone, Node* new_to);
  64   void InsertInput(Zone* zone, int index, Node* new_to);
  65   void RemoveInput(int index);
  66   void RemoveAllInputs();
  67   void TrimInputCount(int new_input_count);
  68
  69   int UseCount() const;
  70   Node* UseAt(int index) const;
  71   void ReplaceUses(Node* replace_to);
  72
  73   class InputEdges FINAL {
  74    public:
  75     typedef Edge value_type;
  76
  77     class iterator;
  78     inline iterator begin() const;
  79     inline iterator end() const;
  80
  81     bool empty() const;
  82
  83     explicit InputEdges(Node* node) : node_(node) {}
  84
  85    private:
  86     Node* node_;
  87   };
  88
  89   InputEdges input_edges() { return InputEdges(this); }
  90
  91   class Inputs FINAL {
  92    public:
  93     typedef Node* value_type;
  94
  95     class const_iterator;
  96     inline const_iterator begin() const;
  97     inline const_iterator end() const;
  98
  99     bool empty() const;
 100
 101     explicit Inputs(Node* node) : node_(node) {}
 102
 103    private:
 104     Node* node_;
 105   };
 106
 107   Inputs inputs() { return Inputs(this); }
 108
 109   class UseEdges FINAL {
 110    public:
 111     typedef Edge value_type;
 112
 113     class iterator;
 114     inline iterator begin() const;
 115     inline iterator end() const;
 116
 117     bool empty() const;
 118
 119     explicit UseEdges(Node* node) : node_(node) {}
 120
 121    private:
 122     Node* node_;
 123   };
 124
 125   UseEdges use_edges() { return UseEdges(this); }
 126
 127   class Uses FINAL {
 128    public:
 129     typedef Node* value_type;
 130
 131     class const_iterator;
 132     inline const_iterator begin() const;
 133     inline const_iterator end() const;
 134
 135     bool empty() const;
 136
 137     explicit Uses(Node* node) : node_(node) {}
 138
 139    private:
 140     Node* node_;
 141   };
 142
 143   Uses uses() { return Uses(this); }
 144
 145   // Returns true if {owner} is the user of {this} node.
 146   bool OwnedBy(Node* owner) const {
 147     return first_use_ && first_use_->from == owner && !first_use_->next;
 148   }
 149
 150  private:
 151   struct Use FINAL : public ZoneObject {
 152     Node* from;
 153     Use* next;
 154     Use* prev;
 155     int input_index;
 156   };
 157
 158   class Input FINAL {
 159    public:
 160     Node* to;
 161     Use* use;
 162
 163     void Update(Node* new_to);
 164   };
 165
 166   inline Node(NodeId id, const Operator* op, int input_count,
 167               int reserve_input_count);
 168
 169   inline void EnsureAppendableInputs(Zone* zone);
 170
 171   Input* GetInputRecordPtr(int index) {
 172     return has_appendable_inputs() ? &((*inputs_.appendable_)[index])
 173                                    : &inputs_.static_[index];
 174   }
 175   const Input* GetInputRecordPtr(int index) const {
 176     return has_appendable_inputs() ? &((*inputs_.appendable_)[index])
 177                                    : &inputs_.static_[index];
 178   }
 179
 180   inline void AppendUse(Use* const use);
 181   inline void RemoveUse(Use* const use);
 182
 183   void* operator new(size_t, void* location) { return location; }
 184
 185   typedef ZoneDeque<Input> InputDeque;
 186
 187   // Only NodeProperties should manipulate the bounds.
 188   Bounds bounds() { return bounds_; }
 189   void set_bounds(Bounds b) { bounds_ = b; }
 190
 191   // Only NodeMarkers should manipulate the marks on nodes.
 192   Mark mark() { return mark_; }
 193   void set_mark(Mark mark) { mark_ = mark; }
 194
 195   int input_count() const { return InputCountField::decode(bit_field_); }
 196   void set_input_count(int input_count) {
 197     DCHECK_LE(0, input_count);
 198     bit_field_ = InputCountField::update(bit_field_, input_count);
 199   }
 200
 201   int reserved_input_count() const {
 202     return ReservedInputCountField::decode(bit_field_);
 203   }
 204   void set_reserved_input_count(int reserved_input_count) {
 205     DCHECK_LE(0, reserved_input_count);
 206     bit_field_ =
 207         ReservedInputCountField::update(bit_field_, reserved_input_count);
 208   }
 209
 210   bool has_appendable_inputs() const {
 211     return HasAppendableInputsField::decode(bit_field_);
 212   }
 213   void set_has_appendable_inputs(bool has_appendable_inputs) {
 214     bit_field_ =
 215         HasAppendableInputsField::update(bit_field_, has_appendable_inputs);
 216   }
 217
 218   typedef BitField<unsigned, 0, 29> InputCountField;
 219   typedef BitField<unsigned, 29, 2> ReservedInputCountField;
 220   typedef BitField<unsigned, 31, 1> HasAppendableInputsField;
 221   static const int kDefaultReservedInputs = ReservedInputCountField::kMax;
 222
 223   const Operator* op_;
 224   Bounds bounds_;
 225   Mark mark_;
 226   NodeId const id_;
 227   unsigned bit_field_;
 228   Use* first_use_;
 229   Use* last_use_;
 230   union {
 231     // When a node is initially allocated, it uses a static buffer to hold its
 232     // inputs under the assumption that the number of outputs will not increase.
 233     // When the first input is appended, the static buffer is converted into a
 234     // deque to allow for space-efficient growing.
 235     Input static_[1];
 236     InputDeque* appendable_;
 237   } inputs_;
 238
 239   friend class Edge;
 240   friend class NodeMarkerBase;
 241   friend class NodeProperties;
 242
 243   DISALLOW_COPY_AND_ASSIGN(Node);
 244 };
 245
 246
 247 std::ostream& operator<<(std::ostream& os, const Node& n);
 248
 249
 250 // Typedefs to shorten commonly used Node containers.
 251 typedef ZoneDeque<Node*> NodeDeque;
 252 typedef ZoneVector<Node*> NodeVector;
 253 typedef ZoneVector<NodeVector> NodeVectorVector;
 254
 255
 256 // Helper to extract parameters from Operator1<*> nodes.
 257 template <typename T>
 258 static inline const T& OpParameter(const Node* node) {
 259   return OpParameter<T>(node->op());
 260 }
 261
 262
 263 // An encapsulation for information associated with a single use of node as a
 264 // input from another node, allowing access to both the defining node and
 265 // the node having the input.
 266 class Edge FINAL {
 267  public:
 268   Node* from() const { return input_->use->from; }
 269   Node* to() const { return input_->to; }
 270   int index() const {
 271     int const index = input_->use->input_index;
 272     DCHECK_LT(index, input_->use->from->input_count());
 273     return index;
 274   }
 275
 276   bool operator==(const Edge& other) { return input_ == other.input_; }
 277   bool operator!=(const Edge& other) { return !(*this == other); }
 278
 279   void UpdateTo(Node* new_to) { input_->Update(new_to); }
 280
 281  private:
 282   friend class Node::UseEdges::iterator;
 283   friend class Node::InputEdges::iterator;
 284
 285   explicit Edge(Node::Input* input) : input_(input) { DCHECK_NOT_NULL(input); }
 286
 287   Node::Input* input_;
 288 };
 289
 290
 291 // A forward iterator to visit the edges for the input dependencies of a node.
 292 class Node::InputEdges::iterator FINAL {
 293  public:
 294   typedef std::forward_iterator_tag iterator_category;
 295   typedef int difference_type;
 296   typedef Edge value_type;
 297   typedef Edge* pointer;
 298   typedef Edge& reference;
 299
 300   iterator() : input_(nullptr) {}
 301   iterator(const iterator& other) : input_(other.input_) {}
 302
 303   Edge operator*() const { return Edge(input_); }
 304   bool operator==(const iterator& other) const {
 305     return input_ == other.input_;
 306   }
 307   bool operator!=(const iterator& other) const { return !(*this == other); }
 308   iterator& operator++() {
 309     SetInput(Edge(input_).from(), input_->use->input_index + 1);
 310     return *this;
 311   }
 312   iterator operator++(int);
 313
 314  private:
 315   friend class Node;
 316
 317   explicit iterator(Node* from, int index = 0) : input_(nullptr) {
 318     SetInput(from, index);
 319   }
 320
 321   void SetInput(Node* from, int index) {
 322     DCHECK(index >= 0 && index <= from->InputCount());
 323     if (index < from->InputCount()) {
 324       input_ = from->GetInputRecordPtr(index);
 325     } else {
 326       input_ = nullptr;
 327     }
 328   }
 329
 330   Input* input_;
 331 };
 332
 333
 334 Node::InputEdges::iterator Node::InputEdges::begin() const {
 335   return Node::InputEdges::iterator(this->node_, 0);
 336 }
 337
 338
 339 Node::InputEdges::iterator Node::InputEdges::end() const {
 340   return Node::InputEdges::iterator(this->node_, this->node_->InputCount());
 341 }
 342
 343
 344 // A forward iterator to visit the inputs of a node.
 345 class Node::Inputs::const_iterator FINAL {
 346  public:
 347   typedef std::forward_iterator_tag iterator_category;
 348   typedef int difference_type;
 349   typedef Node* value_type;
 350   typedef Node** pointer;
 351   typedef Node*& reference;
 352
 353   const_iterator(const const_iterator& other) : iter_(other.iter_) {}
 354
 355   Node* operator*() const { return (*iter_).to(); }
 356   bool operator==(const const_iterator& other) const {
 357     return iter_ == other.iter_;
 358   }
 359   bool operator!=(const const_iterator& other) const {
 360     return !(*this == other);
 361   }
 362   const_iterator& operator++() {
 363     ++iter_;
 364     return *this;
 365   }
 366   const_iterator operator++(int);
 367
 368  private:
 369   friend class Node::Inputs;
 370
 371   const_iterator(Node* node, int index) : iter_(node, index) {}
 372
 373   Node::InputEdges::iterator iter_;
 374 };
 375
 376
 377 Node::Inputs::const_iterator Node::Inputs::begin() const {
 378   return const_iterator(this->node_, 0);
 379 }
 380
 381
 382 Node::Inputs::const_iterator Node::Inputs::end() const {
 383   return const_iterator(this->node_, this->node_->InputCount());
 384 }
 385
 386
 387 // A forward iterator to visit the uses edges of a node. The edges are returned
 388 // in
 389 // the order in which they were added as inputs.
 390 class Node::UseEdges::iterator FINAL {
 391  public:
 392   iterator(const iterator& other)
 393       : current_(other.current_), next_(other.next_) {}
 394
 395   Edge operator*() const {
 396     return Edge(current_->from->GetInputRecordPtr(current_->input_index));
 397   }
 398
 399   bool operator==(const iterator& other) const {
 400     return current_ == other.current_;
 401   }
 402   bool operator!=(const iterator& other) const { return !(*this == other); }
 403   iterator& operator++() {
 404     DCHECK_NOT_NULL(current_);
 405     current_ = next_;
 406     next_ = current_ ? current_->next : nullptr;
 407     return *this;
 408   }
 409   iterator operator++(int);
 410
 411  private:
 412   friend class Node::UseEdges;
 413
 414   iterator() : current_(nullptr), next_(nullptr) {}
 415   explicit iterator(Node* node)
 416       : current_(node->first_use_),
 417         next_(current_ ? current_->next : nullptr) {}
 418
 419   Node::Use* current_;
 420   Node::Use* next_;
 421 };
 422
 423
 424 Node::UseEdges::iterator Node::UseEdges::begin() const {
 425   return Node::UseEdges::iterator(this->node_);
 426 }
 427
 428
 429 Node::UseEdges::iterator Node::UseEdges::end() const {
 430   return Node::UseEdges::iterator();
 431 }
 432
 433
 434 // A forward iterator to visit the uses of a node. The uses are returned in
 435 // the order in which they were added as inputs.
 436 class Node::Uses::const_iterator FINAL {
 437  public:
 438   typedef std::forward_iterator_tag iterator_category;
 439   typedef int difference_type;
 440   typedef Node* value_type;
 441   typedef Node** pointer;
 442   typedef Node*& reference;
 443
 444   const_iterator(const const_iterator& other) : current_(other.current_) {}
 445
 446   Node* operator*() const { return current_->from; }
 447   bool operator==(const const_iterator& other) const {
 448     return other.current_ == current_;
 449   }
 450   bool operator!=(const const_iterator& other) const {
 451     return other.current_ != current_;
 452   }
 453   const_iterator& operator++() {
 454     DCHECK_NOT_NULL(current_);
 455     current_ = current_->next;
 456     return *this;
 457   }
 458   const_iterator operator++(int);
 459
 460  private:
 461   friend class Node::Uses;
 462
 463   const_iterator() : current_(nullptr) {}
 464   explicit const_iterator(Node* node) : current_(node->first_use_) {}
 465
 466   Node::Use* current_;
 467 };
 468
 469
 470 Node::Uses::const_iterator Node::Uses::begin() const {
 471   return const_iterator(this->node_);
 472 }
 473
 474
 475 Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
 476
 477
 478 void Node::ReplaceInput(int index, Node* new_to) {
 479   GetInputRecordPtr(index)->Update(new_to);
 480 }
 481
 482 }  // namespace compiler
 483 }  // namespace internal
 484 }  // namespace v8
 485
 486 #endif  // V8_COMPILER_NODE_H_