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