[turbofan] Initial attempt to cleanup Node and related classes.

src/compiler/node.h

Index: src/compiler/node.h
diff --git a/src/compiler/node.h b/src/compiler/node.h
index 9d3a2b039135dd66c7c1cdbfe5a4486128d6496d..f8b3329d039216dc46cad97a8f114e11813d47e3 100644
--- a/src/compiler/node.h
+++ b/src/compiler/node.h
@@ -5,14 +5,9 @@
 #ifndef V8_COMPILER_NODE_H_
 #define V8_COMPILER_NODE_H_
 
-#include <deque>
-#include <vector>
-
 #include "src/compiler/opcodes.h"
 #include "src/compiler/operator.h"
 #include "src/types-inl.h"
-#include "src/zone.h"
-#include "src/zone-allocator.h"
 #include "src/zone-containers.h"
 
 namespace v8 {
@@ -46,11 +41,11 @@ typedef int32_t NodeId;
 // by the Node's id.
 class Node FINAL {
  public:
-  bool IsDead() const { return InputCount() > 0 && InputAt(0) == NULL; }
-  void Kill();
+  static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count,
+                   Node** inputs, bool has_extensible_inputs);
 
-  void CollectProjections(ZoneVector<Node*>* projections);
-  Node* FindProjection(size_t projection_index);
+  bool IsDead() const { return InputCount() > 0 && !InputAt(0); }
+  void Kill();
 
   const Operator* op() const { return op_; }
   void set_op(const Operator* op) { op_ = op; }
@@ -64,25 +59,25 @@ class Node FINAL {
 
   int InputCount() const { return input_count(); }
   Node* InputAt(int index) const { return GetInputRecordPtr(index)->to; }
-  inline void ReplaceInput(int index, Node* new_input);
-  inline void AppendInput(Zone* zone, Node* new_input);
-  inline void InsertInput(Zone* zone, int index, Node* new_input);
-  inline void RemoveInput(int index);
+  inline void ReplaceInput(int index, Node* new_to);
+  void AppendInput(Zone* zone, Node* new_to);
+  void InsertInput(Zone* zone, int index, Node* new_to);
+  void RemoveInput(int index);
+  void RemoveAllInputs();
+  void TrimInputCount(int new_input_count);
 
   int UseCount() const;
   Node* UseAt(int index) const;
-  inline void ReplaceUses(Node* replace_to);
-  template <class UnaryPredicate>
-  inline void ReplaceUsesIf(UnaryPredicate pred, Node* replace_to);
-  inline void RemoveAllInputs();
-
-  inline void TrimInputCount(int input_count);
+  void ReplaceUses(Node* replace_to);
 
-  class InputEdges {
+  class InputEdges FINAL {
    public:
+    typedef Edge value_type;
+
     class iterator;
-    iterator begin() const;
-    iterator end() const;
+    inline iterator begin() const;
+    inline iterator end() const;
+
     bool empty() const;
 
     explicit InputEdges(Node* node) : node_(node) {}
@@ -91,11 +86,16 @@ class Node FINAL {
     Node* node_;
   };
 
-  class Inputs {
+  InputEdges input_edges() { return InputEdges(this); }
+
+  class Inputs FINAL {
    public:
-    class iterator;
-    iterator begin() const;
-    iterator end() const;
+    typedef Node* value_type;
+
+    class const_iterator;
+    inline const_iterator begin() const;
+    inline const_iterator end() const;
+
     bool empty() const;
 
     explicit Inputs(Node* node) : node_(node) {}
@@ -105,13 +105,15 @@ class Node FINAL {
   };
 
   Inputs inputs() { return Inputs(this); }
-  InputEdges input_edges() { return InputEdges(this); }
 
-  class UseEdges {
+  class UseEdges FINAL {
    public:
+    typedef Edge value_type;
+
     class iterator;
-    iterator begin() const;
-    iterator end() const;
+    inline iterator begin() const;
+    inline iterator end() const;
+
     bool empty() const;
 
     explicit UseEdges(Node* node) : node_(node) {}
@@ -120,11 +122,16 @@ class Node FINAL {
     Node* node_;
   };
 
-  class Uses {
+  UseEdges use_edges() { return UseEdges(this); }
+
+  class Uses FINAL {
    public:
-    class iterator;
-    iterator begin() const;
-    iterator end() const;
+    typedef Node* value_type;
+
+    class const_iterator;
+    inline const_iterator begin() const;
+    inline const_iterator end() const;
+
     bool empty() const;
 
     explicit Uses(Node* node) : node_(node) {}
@@ -134,26 +141,21 @@ class Node FINAL {
   };
 
   Uses uses() { return Uses(this); }
-  UseEdges use_edges() { return UseEdges(this); }
-
-  bool OwnedBy(Node* owner) const;
 
-  static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count,
-                   Node** inputs, bool has_extensible_inputs);
-
- protected:
-  friend class Graph;
-  friend class Edge;
+  // 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;
+  }
 
-  class Use : public ZoneObject {
-   public:
+ private:
+  struct Use FINAL : public ZoneObject {
     Node* from;
     Use* next;
     Use* prev;
     int input_index;
   };
 
-  class Input {
+  class Input FINAL {
    public:
     Node* to;
     Use* use;
@@ -161,7 +163,10 @@ class Node FINAL {
     void Update(Node* new_to);
   };
 
-  void EnsureAppendableInputs(Zone* zone);
+  inline Node(NodeId id, const Operator* op, int input_count,
+              int reserve_input_count);
+
+  inline void EnsureAppendableInputs(Zone* zone);
 
   Input* GetInputRecordPtr(int index) const {
     if (has_appendable_inputs()) {
@@ -171,20 +176,13 @@ class Node FINAL {
     }
   }
 
-  inline void AppendUse(Use* use);
-  inline void RemoveUse(Use* use);
+  inline void AppendUse(Use* const use);
+  inline void RemoveUse(Use* const use);
 
   void* operator new(size_t, void* location) { return location; }
 
- private:
-  inline Node(NodeId id, const Operator* op, int input_count,
-              int reserve_input_count);
-
   typedef ZoneDeque<Input> InputDeque;
 
-  friend class NodeMarkerBase;
-  friend class NodeProperties;
-
   // Only NodeProperties should manipulate the bounds.
   Bounds bounds() { return bounds_; }
   void set_bounds(Bounds b) { bounds_ = b; }
@@ -224,7 +222,7 @@ class Node FINAL {
   const Operator* op_;
   Bounds bounds_;
   Mark mark_;
-  NodeId id_;
+  NodeId const id_;
   unsigned bit_field_;
   union {
     // When a node is initially allocated, it uses a static buffer to hold its
@@ -237,20 +235,40 @@ class Node FINAL {
   Use* first_use_;
   Use* last_use_;
 
+  friend class Edge;
+  friend class NodeMarkerBase;
+  friend class NodeProperties;
+
   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 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 {
+class Edge FINAL {
  public:
   Node* from() const { return input_->use->from; }
   Node* to() const { return input_->to; }
   int index() const {
-    int index = input_->use->input_index;
-    DCHECK(index < input_->use->from->input_count());
+    int const index = input_->use->input_index;
+    DCHECK_LT(index, input_->use->from->input_count());
     return index;
   }
 
@@ -260,59 +278,51 @@ class Edge {
   void UpdateTo(Node* new_to) { input_->Update(new_to); }
 
  private:
-  friend class Node::Uses::iterator;
-  friend class Node::Inputs::iterator;
   friend class Node::UseEdges::iterator;
   friend class Node::InputEdges::iterator;
 
-  explicit Edge(Node::Input* input) : input_(input) {}
+  explicit Edge(Node::Input* input) : input_(input) { DCHECK_NOT_NULL(input); }
 
-  Node::Input* input_;
+  Node::Input* const input_;
 };
 
 
-// A forward iterator to visit the edges for the input dependencies of a node..
-class Node::InputEdges::iterator {
+// 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(const Node::InputEdges::iterator& other)  // NOLINT
-      : input_(other.input_) {}
-  iterator() : input_(NULL) {}
+
+  iterator() : input_(nullptr) {}
+  iterator(const iterator& other) : input_(other.input_) {}
 
   Edge operator*() const { return Edge(input_); }
-  bool operator==(const iterator& other) const { return Equals(other); }
-  bool operator!=(const iterator& other) const { return !Equals(other); }
+  bool operator==(const iterator& other) const {
+    return input_ == other.input_;
+  }
+  bool operator!=(const iterator& other) const { return !(*this == other); }
   iterator& operator++() {
-    DCHECK(input_ != NULL);
-    Edge edge(input_);
-    Node* from = edge.from();
-    SetInput(from, input_->use->input_index + 1);
+    SetInput(Edge(input_).from(), input_->use->input_index + 1);
     return *this;
   }
-  iterator operator++(int) {
-    iterator result(*this);
-    ++(*this);
-    return result;
-  }
+  iterator operator++(int);
 
  private:
   friend class Node;
 
-  explicit iterator(Node* from, int index = 0) : input_(NULL) {
+  explicit iterator(Node* from, int index = 0) : input_(nullptr) {
     SetInput(from, index);
   }
 
-  bool Equals(const iterator& other) const { return other.input_ == input_; }
   void SetInput(Node* from, int index) {
     DCHECK(index >= 0 && index <= from->InputCount());
     if (index < from->InputCount()) {
       input_ = from->GetInputRecordPtr(index);
     } else {
-      input_ = NULL;
+      input_ = nullptr;
     }
   }
 
@@ -320,8 +330,18 @@ class Node::InputEdges::iterator {
 };
 
 
+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());
+}
+
+
 // A forward iterator to visit the inputs of a node.
-class Node::Inputs::iterator {
+class Node::Inputs::const_iterator FINAL {
  public:
   typedef std::forward_iterator_tag iterator_category;
   typedef int difference_type;
@@ -329,319 +349,133 @@ class Node::Inputs::iterator {
   typedef Node** pointer;
   typedef Node*& reference;
 
-  iterator(const Node::Inputs::iterator& other)  // NOLINT
-      : iter_(other.iter_) {}
+  const_iterator(const const_iterator& other) : iter_(other.iter_) {}
 
   Node* operator*() const { return (*iter_).to(); }
-  bool operator==(const iterator& other) const { return Equals(other); }
-  bool operator!=(const iterator& other) const { return !Equals(other); }
-  iterator& operator++() {
+  bool operator==(const const_iterator& other) const {
+    return iter_ == other.iter_;
+  }
+  bool operator!=(const const_iterator& other) const {
+    return !(*this == other);
+  }
+  const_iterator& operator++() {
     ++iter_;
     return *this;
   }
-  iterator operator++(int) {
-    iterator result(*this);
-    ++(*this);
-    return result;
-  }
-
+  const_iterator operator++(int);
 
  private:
   friend class Node::Inputs;
 
-  explicit iterator(Node* node, int index) : iter_(node, index) {}
-
-  bool Equals(const iterator& other) const { return other.iter_ == iter_; }
+  const_iterator(Node* node, int index) : iter_(node, index) {}
 
   Node::InputEdges::iterator iter_;
 };
 
+
+Node::Inputs::const_iterator Node::Inputs::begin() const {
+  return const_iterator(this->node_, 0);
+}
+
+
+Node::Inputs::const_iterator Node::Inputs::end() const {
+  return const_iterator(this->node_, this->node_->InputCount());
+}
+
+
 // A forward iterator to visit the uses edges of a node. The edges are returned
 // in
 // the order in which they were added as inputs.
-class Node::UseEdges::iterator {
+class Node::UseEdges::iterator FINAL {
  public:
-  iterator(const Node::UseEdges::iterator& other)  // NOLINT
-      : current_(other.current_),
-        next_(other.next_) {}
+  iterator(const iterator& other)
+      : current_(other.current_), next_(other.next_) {}
 
-  Edge operator*() const { return Edge(CurrentInput()); }
+  Edge operator*() const {
+    return Edge(current_->from->GetInputRecordPtr(current_->input_index));
+  }
 
-  bool operator==(const iterator& other) { return Equals(other); }
-  bool operator!=(const iterator& other) { return !Equals(other); }
+  bool operator==(const iterator& other) const {
+    return current_ == other.current_;
+  }
+  bool operator!=(const iterator& other) const { return !(*this == other); }
   iterator& operator++() {
-    DCHECK(current_ != NULL);
+    DCHECK_NOT_NULL(current_);
     current_ = next_;
-    next_ = (current_ == NULL) ? NULL : current_->next;
+    next_ = current_ ? current_->next : nullptr;
     return *this;
   }
-  iterator operator++(int) {
-    iterator result(*this);
-    ++(*this);
-    return result;
-  }
+  iterator operator++(int);
 
  private:
   friend class Node::UseEdges;
 
-  iterator() : current_(NULL), next_(NULL) {}
+  iterator() : current_(nullptr), next_(nullptr) {}
   explicit iterator(Node* node)
       : current_(node->first_use_),
-        next_(current_ == NULL ? NULL : current_->next) {}
-
-  bool Equals(const iterator& other) const {
-    return other.current_ == current_;
-  }
-
-  Input* CurrentInput() const {
-    return current_->from->GetInputRecordPtr(current_->input_index);
-  }
+        next_(current_ ? current_->next : nullptr) {}
 
   Node::Use* current_;
   Node::Use* next_;
 };
 
 
-// A forward iterator to visit the uses of a node. The uses are returned in
-// the order in which they were added as inputs.
-class Node::Uses::iterator {
- public:
-  iterator(const Node::Uses::iterator& other)  // NOLINT
-      : current_(other.current_) {}
-
-  Node* operator*() { return current_->from; }
-
-  bool operator==(const iterator& other) { return other.current_ == current_; }
-  bool operator!=(const iterator& other) { return other.current_ != current_; }
-  iterator& operator++() {
-    DCHECK(current_ != NULL);
-    current_ = current_->next;
-    return *this;
-  }
-
- private:
-  friend class Node::Uses;
-
-  iterator() : current_(NULL) {}
-  explicit iterator(Node* node) : current_(node->first_use_) {}
-
-  Input* CurrentInput() const {
-    return current_->from->GetInputRecordPtr(current_->input_index);
-  }
-
-  Node::Use* current_;
-};
-
-
-std::ostream& operator<<(std::ostream& os, const Node& n);
-
-typedef ZoneDeque<Node*> NodeDeque;
-
-typedef ZoneVector<Node*> NodeVector;
-typedef NodeVector::iterator NodeVectorIter;
-typedef NodeVector::const_iterator NodeVectorConstIter;
-typedef NodeVector::reverse_iterator NodeVectorRIter;
-
-typedef ZoneVector<NodeVector> NodeVectorVector;
-typedef NodeVectorVector::iterator NodeVectorVectorIter;
-typedef NodeVectorVector::reverse_iterator NodeVectorVectorRIter;
-
-typedef Node::Uses::iterator UseIter;
-typedef Node::Inputs::iterator InputIter;
-
-// Helper to extract parameters from Operator1<*> nodes.
-template <typename T>
-static inline const T& OpParameter(const Node* node) {
-  return OpParameter<T>(node->op());
-}
-
-inline Node::InputEdges::iterator Node::InputEdges::begin() const {
-  return Node::InputEdges::iterator(this->node_, 0);
-}
-
-inline Node::InputEdges::iterator Node::InputEdges::end() const {
-  return Node::InputEdges::iterator(this->node_, this->node_->InputCount());
-}
-
-inline Node::Inputs::iterator Node::Inputs::begin() const {
-  return Node::Inputs::iterator(this->node_, 0);
-}
-
-inline Node::Inputs::iterator Node::Inputs::end() const {
-  return Node::Inputs::iterator(this->node_, this->node_->InputCount());
-}
-
-inline Node::UseEdges::iterator Node::UseEdges::begin() const {
+Node::UseEdges::iterator Node::UseEdges::begin() const {
   return Node::UseEdges::iterator(this->node_);
 }
 
-inline Node::UseEdges::iterator Node::UseEdges::end() const {
-  return Node::UseEdges::iterator();
-}
 
-inline Node::Uses::iterator Node::Uses::begin() const {
-  return Node::Uses::iterator(this->node_);
+Node::UseEdges::iterator Node::UseEdges::end() const {
+  return Node::UseEdges::iterator();
 }
 
-inline Node::Uses::iterator Node::Uses::end() const {
-  return Node::Uses::iterator();
-}
 
-inline bool Node::InputEdges::empty() const { return begin() == end(); }
-inline bool Node::Uses::empty() const { return begin() == end(); }
-inline bool Node::UseEdges::empty() const { return begin() == end(); }
-inline bool Node::Inputs::empty() const { return begin() == end(); }
+// A forward iterator to visit the uses of a node. The uses are returned in
+// the order in which they were added as inputs.
+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;
 
-inline void Node::ReplaceUses(Node* replace_to) {
-  for (Use* use = first_use_; use != NULL; use = use->next) {
-    use->from->GetInputRecordPtr(use->input_index)->to = replace_to;
-  }
-  if (replace_to->last_use_ == NULL) {
-    DCHECK_EQ(NULL, replace_to->first_use_);
-    replace_to->first_use_ = first_use_;
-    replace_to->last_use_ = last_use_;
-  } else if (first_use_ != NULL) {
-    DCHECK_NE(NULL, replace_to->first_use_);
-    replace_to->last_use_->next = first_use_;
-    first_use_->prev = replace_to->last_use_;
-    replace_to->last_use_ = last_use_;
-  }
-  first_use_ = NULL;
-  last_use_ = NULL;
-}
+  const_iterator(const const_iterator& other) : current_(other.current_) {}
 
-template <class UnaryPredicate>
-inline void Node::ReplaceUsesIf(UnaryPredicate pred, Node* replace_to) {
-  for (Use* use = first_use_; use != NULL;) {
-    Use* next = use->next;
-    if (pred(use->from)) {
-      RemoveUse(use);
-      replace_to->AppendUse(use);
-      use->from->GetInputRecordPtr(use->input_index)->to = replace_to;
-    }
-    use = next;
+  Node* operator*() const { return current_->from; }
+  bool operator==(const const_iterator& other) const {
+    return other.current_ == current_;
   }
-}
-
-inline void Node::RemoveAllInputs() {
-  for (Edge edge : input_edges()) {
-    edge.UpdateTo(NULL);
+  bool operator!=(const const_iterator& other) const {
+    return other.current_ != current_;
   }
-}
-
-inline void Node::TrimInputCount(int new_input_count) {
-  if (new_input_count == input_count()) return;  // Nothing to do.
-
-  DCHECK(new_input_count < input_count());
-
-  // Update inline inputs.
-  for (int i = new_input_count; i < input_count(); i++) {
-    Node::Input* input = GetInputRecordPtr(i);
-    input->Update(NULL);
+  const_iterator& operator++() {
+    DCHECK_NOT_NULL(current_);
+    current_ = current_->next;
+    return *this;
   }
-  set_input_count(new_input_count);
-}
+  const_iterator operator++(int);
 
-inline void Node::ReplaceInput(int index, Node* new_to) {
-  Input* input = GetInputRecordPtr(index);
-  input->Update(new_to);
-}
+ private:
+  friend class Node::Uses;
 
-inline void Node::Input::Update(Node* new_to) {
-  Node* old_to = this->to;
-  if (new_to == old_to) return;  // Nothing to do.
-  // Snip out the use from where it used to be
-  if (old_to != NULL) {
-    old_to->RemoveUse(use);
-  }
-  to = new_to;
-  // And put it into the new node's use list.
-  if (new_to != NULL) {
-    new_to->AppendUse(use);
-  } else {
-    use->next = NULL;
-    use->prev = NULL;
-  }
-}
+  const_iterator() : current_(nullptr) {}
+  explicit const_iterator(Node* node) : current_(node->first_use_) {}
 
-inline void Node::EnsureAppendableInputs(Zone* zone) {
-  if (!has_appendable_inputs()) {
-    void* deque_buffer = zone->New(sizeof(InputDeque));
-    InputDeque* deque = new (deque_buffer) InputDeque(zone);
-    for (int i = 0; i < input_count(); ++i) {
-      deque->push_back(inputs_.static_[i]);
-    }
-    inputs_.appendable_ = deque;
-    set_has_appendable_inputs(true);
-  }
-}
+  Node::Use* current_;
+};
 
-inline void Node::AppendInput(Zone* zone, Node* to_append) {
-  Use* new_use = new (zone) Use;
-  Input new_input;
-  new_input.to = to_append;
-  new_input.use = new_use;
-  if (reserved_input_count() > 0) {
-    DCHECK(!has_appendable_inputs());
-    set_reserved_input_count(reserved_input_count() - 1);
-    inputs_.static_[input_count()] = new_input;
-  } else {
-    EnsureAppendableInputs(zone);
-    inputs_.appendable_->push_back(new_input);
-  }
-  new_use->input_index = input_count();
-  new_use->from = this;
-  to_append->AppendUse(new_use);
-  set_input_count(input_count() + 1);
-}
 
-inline void Node::InsertInput(Zone* zone, int index, Node* to_insert) {
-  DCHECK(index >= 0 && index < InputCount());
-  // TODO(turbofan): Optimize this implementation!
-  AppendInput(zone, InputAt(InputCount() - 1));
-  for (int i = InputCount() - 1; i > index; --i) {
-    ReplaceInput(i, InputAt(i - 1));
-  }
-  ReplaceInput(index, to_insert);
+Node::Uses::const_iterator Node::Uses::begin() const {
+  return const_iterator(this->node_);
 }
 
-inline void Node::RemoveInput(int index) {
-  DCHECK(index >= 0 && index < InputCount());
-  // TODO(turbofan): Optimize this implementation!
-  for (; index < InputCount() - 1; ++index) {
-    ReplaceInput(index, InputAt(index + 1));
-  }
-  TrimInputCount(InputCount() - 1);
-}
 
-inline void Node::AppendUse(Use* use) {
-  use->next = NULL;
-  use->prev = last_use_;
-  if (last_use_ == NULL) {
-    first_use_ = use;
-  } else {
-    last_use_->next = use;
-  }
-  last_use_ = use;
-}
+Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
 
-inline void Node::RemoveUse(Use* use) {
-  if (last_use_ == use) {
-    last_use_ = use->prev;
-  }
-  if (use->prev != NULL) {
-    use->prev->next = use->next;
-  } else {
-    first_use_ = use->next;
-  }
-  if (use->next != NULL) {
-    use->next->prev = use->prev;
-  }
-}
 
-inline bool Node::OwnedBy(Node* owner) const {
-  return first_use_ != NULL && first_use_->from == owner &&
-         first_use_->next == NULL;
+void Node::ReplaceInput(int index, Node* new_to) {
+  GetInputRecordPtr(index)->Update(new_to);
 }
 
 }  // namespace compiler