[turbofan] Rework Node guts to save space.

src/compiler/node.h

 // 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"
 #include "src/types-inl.h"
@@ skipping 37 matching lines @@
   void Kill();
 
   const Operator* op() const { return op_; }
   void set_op(const Operator* op) { op_ = op; }
 
   IrOpcode::Value opcode() const {
     DCHECK(op_->opcode() <= IrOpcode::kLast);
     return static_cast<IrOpcode::Value>(op_->opcode());
   }
 
-  NodeId id() const { return id_; }
+  NodeId id() const { return IdField::decode(bit_field_); }
 
-  int InputCount() const { return input_count(); }
+  int InputCount() const {
+    return has_inline_inputs() ? InlineCountField::decode(bit_field_)
+                               : inputs_.outline_->count_;
+  }
+
+#if DEBUG
+#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
+#define BOUNDS_CHECK(index) \
+  do {                      \
+  } while (false)
+#endif
+
   Node* InputAt(int index) const {
-#if DEBUG
-    if (index < 0 || index >= InputCount()) {
-      V8_Fatal(__FILE__, __LINE__, "Node #%d:%s->InputAt(%d) out of bounds",
-               id(), op()->mnemonic(), index);
+    BOUNDS_CHECK(index);
+    return *GetInputPtrConst(index);
+  }
+
+  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);
     }
-#endif
-    return GetInputRecordPtr(index)->to;
   }
-  inline void ReplaceInput(int index, Node* new_to);
+

[Michael Starzinger, 2015/05/21 14:14:02]

nit: Maybe #undef BOUNDS_CHECK here again.

[titzer, 2015/05/21 15:11:19]

Done.

   void AppendInput(Zone* zone, Node* new_to);
   void InsertInput(Zone* zone, int index, Node* new_to);
   void RemoveInput(int index);
   void NullAllInputs();
   void TrimInputCount(int new_input_count);
 
   int UseCount() const;
   void ReplaceUses(Node* replace_to);
 
   class InputEdges final {
@@ skipping 63 matching lines @@
     explicit Uses(Node* node) : node_(node) {}
 
    private:
     Node* node_;
   };
 
   Uses uses() { return Uses(this); }
 
   // Returns true if {owner} is the user of {this} node.
   bool OwnedBy(Node* owner) const {
-    return first_use_ && first_use_->from == owner && !first_use_->next;
+    return first_use_ && first_use_->from() == owner && !first_use_->next;
   }
 
   // Returns true if {owner1} and {owner2} are the only users of {this} node.
   bool OwnedBy(Node const* owner1, Node const* owner2) const;
 
  private:
-  struct Use final : public ZoneObject {
-    Node* from;
+  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 {
     Use* next;
     Use* prev;
-    int input_index;
+    uint32_t bit_field_;
+
+    int input_index() const { return InputIndexField::decode(bit_field_); }
+    int output_index() const { return OutputIndexField::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];
+    }
+
+    Node* from() {
+      Use* start = this + 1 + input_index();
+      return is_inline_use() ? reinterpret_cast<Node*>(start)
+                             : reinterpret_cast<OutOfLineInputs*>(start)->node_;
+    }
+
+    typedef BitField<bool, 0, 1> InlineField;
+    typedef BitField<unsigned, 1, 17> InputIndexField;
+    typedef BitField<unsigned, 18, 14> OutputIndexField;
   };
 
-  class Input final {
-   public:
-    Node* to;
-    Use* use;
+  //============================================================================
+  //== 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.
 
-    void Update(Node* new_to);
-  };
+  Node(NodeId id, const Operator* op, int inline_count, int inline_capacity);
 
-  inline Node(NodeId id, const Operator* op, int input_count,
-              int reserve_input_count);
-
-  inline void EnsureAppendableInputs(Zone* zone);
-
-  Input* GetInputRecordPtr(int index) {
-    return has_appendable_inputs() ? &((*inputs_.appendable_)[index])
-                                   : &inputs_.static_[index];
+  Node* const* GetInputPtrConst(int input_index) const {
+    return has_inline_inputs() ? &(inputs_.inline_[input_index])
+                               : &inputs_.outline_->inputs_[input_index];
   }
-  const Input* GetInputRecordPtr(int index) const {
-    return has_appendable_inputs() ? &((*inputs_.appendable_)[index])
-                                   : &inputs_.static_[index];
+  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];
   }
 
-  inline void AppendUse(Use* const use);
-  inline void RemoveUse(Use* const use);
+  void AppendUse(Use* use);
+  void RemoveUse(Use* use);
 
   void* operator new(size_t, void* location) { return location; }
 
-  typedef ZoneDeque<Input> InputDeque;
-
   // Only NodeProperties should manipulate the bounds.
   Bounds bounds() { return bounds_; }
   void set_bounds(Bounds b) { bounds_ = b; }
 
   // Only NodeMarkers should manipulate the marks on nodes.
   Mark mark() { return mark_; }
   void set_mark(Mark mark) { mark_ = mark; }
 
-  int input_count() const { return InputCountField::decode(bit_field_); }
-  void set_input_count(int input_count) {
-    DCHECK_LE(0, input_count);
-    bit_field_ = InputCountField::update(bit_field_, input_count);
+  inline bool has_inline_inputs() const {
+    return InlineCountField::decode(bit_field_) != kOutlineMarker;
   }
 
-  int reserved_input_count() const {
-    return ReservedInputCountField::decode(bit_field_);
-  }
-  void set_reserved_input_count(int reserved_input_count) {
-    DCHECK_LE(0, reserved_input_count);
-    bit_field_ =
-        ReservedInputCountField::update(bit_field_, reserved_input_count);
-  }
+  void ClearInputs(int start, int count);
 
-  bool has_appendable_inputs() const {
-    return HasAppendableInputsField::decode(bit_field_);
-  }
-  void set_has_appendable_inputs(bool has_appendable_inputs) {
-    bit_field_ =
-        HasAppendableInputsField::update(bit_field_, has_appendable_inputs);
-  }
-
-  typedef BitField<unsigned, 0, 29> InputCountField;
-  typedef BitField<unsigned, 29, 2> ReservedInputCountField;
-  typedef BitField<unsigned, 31, 1> HasAppendableInputsField;
-  static const int kDefaultReservedInputs = ReservedInputCountField::kMax;
+  typedef BitField<NodeId, 0, 24> IdField;
+  typedef BitField<unsigned, 25, 4> InlineCountField;
+  typedef BitField<unsigned, 29, 4> InlineCapacityField;

[Michael Starzinger, 2015/05/21 14:14:02]

Looks like this is exceeding 32-bit here?

[titzer, 2015/05/21 15:11:19]

Finger math is best math!

+  static const int kOutlineMarker = InlineCountField::kMax;
+  static const int kMaxInlineCount = InlineCountField::kMax - 1;
+  static const int kMaxInlineCapacity = InlineCapacityField::kMax - 1;
 
   const Operator* op_;
   Bounds bounds_;
   Mark mark_;
-  NodeId const id_;
-  unsigned bit_field_;
+  uint32_t bit_field_;
   Use* first_use_;
   union {
-    // When a node is initially allocated, it uses a static buffer to hold its
-    // inputs under the assumption that the number of outputs will not increase.
-    // When the first input is appended, the static buffer is converted into a
-    // deque to allow for space-efficient growing.
-    Input static_[1];
-    InputDeque* appendable_;
+    // Inline storage for inputs or out-of-line storage.
+    Node* inline_[1];
+    OutOfLineInputs* outline_;
   } inputs_;
 
   friend class Edge;
   friend class NodeMarkerBase;
   friend class NodeProperties;
 
+#if DEBUG
+  static Node* Verify(Node* node);
+#define VERIFY(node) Verify(node)

[Michael Starzinger, 2015/05/21 14:14:02]

This macro probably cannot be undef'ed, because it's used in the .cc-file. So
can we move it into the .cc-file (or at least choose a slightly less ambiguous
name like VERIFY_NODE for it), because it would "leak" into many compilation
units.

[titzer, 2015/05/21 15:11:19]

Fixed this to be a regular function in debug mode, inline empty function in
release mode.

+#else
+#define VERIFY(node) \
+  do {               \
+  } while (false)
+#endif
+
   DISALLOW_COPY_AND_ASSIGN(Node);
 };
 
 
 std::ostream& operator<<(std::ostream& os, const Node& n);
 
 
 // Typedefs to shorten commonly used Node containers.
 typedef ZoneDeque<Node*> NodeDeque;
 typedef ZoneSet<Node*> NodeSet;
 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());
 }
 
 
 // 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
 // the node having the input.
 class Edge final {
  public:
-  Node* from() const { return input_->use->from; }
-  Node* to() const { return input_->to; }
+  Node* from() const { return use_->from(); }
+  Node* to() const { return *input_ptr_; }
   int index() const {
-    int const index = input_->use->input_index;
-    DCHECK_LT(index, input_->use->from->input_count());
+    int const index = use_->input_index();
+    DCHECK_LT(index, use_->from()->InputCount());
     return index;
   }
 
-  bool operator==(const Edge& other) { return input_ == other.input_; }
+  bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
   bool operator!=(const Edge& other) { return !(*this == other); }
 
-  void UpdateTo(Node* new_to) { input_->Update(new_to); }
+  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_);
+    }
+  }
 
  private:
   friend class Node::UseEdges::iterator;
   friend class Node::InputEdges::iterator;
 
-  explicit Edge(Node::Input* input) : input_(input) { DCHECK_NOT_NULL(input); }
+  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());
+  }
 
-  Node::Input* input_;
+  Node::Use* use_;
+  Node** input_ptr_;
 };
 
 
 // A forward iterator to visit the edges for the input dependencies of a node.
 class Node::InputEdges::iterator final {
  public:
   typedef std::forward_iterator_tag iterator_category;
   typedef int difference_type;
   typedef Edge value_type;
   typedef Edge* pointer;
   typedef Edge& reference;
 
-  iterator() : input_(nullptr) {}
-  iterator(const iterator& other) : input_(other.input_) {}
+  iterator() : use_(nullptr), input_ptr_(nullptr) {}
+  iterator(const iterator& other)
+      : use_(other.use_), input_ptr_(other.input_ptr_) {}
 
-  Edge operator*() const { return Edge(input_); }
+  Edge operator*() const { return Edge(use_, input_ptr_); }
   bool operator==(const iterator& other) const {
-    return input_ == other.input_;
+    return input_ptr_ == other.input_ptr_;
   }
   bool operator!=(const iterator& other) const { return !(*this == other); }
   iterator& operator++() {
-    SetInput(Edge(input_).from(), input_->use->input_index + 1);
+    input_ptr_++;
+    use_--;
     return *this;
   }
   iterator operator++(int);
 
  private:
   friend class Node;
 
-  explicit iterator(Node* from, int index = 0) : input_(nullptr) {
-    SetInput(from, index);
-  }
+  explicit iterator(Node* from, int index = 0)
+      : use_(from->GetUsePtr(index)), input_ptr_(from->GetInputPtr(index)) {}
 
-  void SetInput(Node* from, int index) {
-    DCHECK(index >= 0 && index <= from->InputCount());
-    if (index < from->InputCount()) {
-      input_ = from->GetInputRecordPtr(index);
-    } else {
-      input_ = nullptr;
-    }
-  }
-
-  Input* input_;
+  Use* use_;
+  Node** input_ptr_;
 };
 
 
 Node::InputEdges::iterator Node::InputEdges::begin() const {
   return Node::InputEdges::iterator(this->node_, 0);
 }
 
 
 Node::InputEdges::iterator Node::InputEdges::end() const {
   return Node::InputEdges::iterator(this->node_, this->node_->InputCount());
@@ skipping 42 matching lines @@
   return const_iterator(this->node_, this->node_->InputCount());
 }
 
 
 // A forward iterator to visit the uses edges of a node.
 class Node::UseEdges::iterator final {
  public:
   iterator(const iterator& other)
       : current_(other.current_), next_(other.next_) {}
 
-  Edge operator*() const {
-    return Edge(current_->from->GetInputRecordPtr(current_->input_index));
-  }
-
+  Edge operator*() const { return Edge(current_, current_->input_ptr()); }
   bool operator==(const iterator& other) const {
     return current_ == other.current_;
   }
   bool operator!=(const iterator& other) const { return !(*this == other); }
   iterator& operator++() {
     DCHECK_NOT_NULL(current_);
     current_ = next_;
     next_ = current_ ? current_->next : nullptr;
     return *this;
   }
@@ skipping 26 matching lines @@
 class Node::Uses::const_iterator final {
  public:
   typedef std::forward_iterator_tag iterator_category;
   typedef int difference_type;
   typedef Node* value_type;
   typedef Node** pointer;
   typedef Node*& reference;
 
   const_iterator(const const_iterator& other) : current_(other.current_) {}
 
-  Node* operator*() const { return current_->from; }
+  Node* operator*() const { return current_->from(); }
   bool operator==(const const_iterator& other) const {
     return other.current_ == current_;
   }
   bool operator!=(const const_iterator& other) const {
     return other.current_ != current_;
   }
   const_iterator& operator++() {
     DCHECK_NOT_NULL(current_);
     current_ = current_->next;
     return *this;
@@ skipping 10 matching lines @@
 };
 
 
 Node::Uses::const_iterator Node::Uses::begin() const {
   return const_iterator(this->node_);
 }
 
 
 Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
 
-
-void Node::ReplaceInput(int index, Node* new_to) {
-  GetInputRecordPtr(index)->Update(new_to);
-}
-
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_NODE_H_