[turbofan] Allow indexed access to node inputs/input_edges

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/compiler/types.h"
@@ skipping 28 matching lines @@
 // 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.
 class V8_EXPORT_PRIVATE Node final {
  public:
   static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count,
                    Node* const* inputs, bool has_extensible_inputs);
   static Node* Clone(Zone* zone, NodeId id, const Node* node);
 
-  bool IsDead() const { return InputCount() > 0 && !InputAt(0); }
+  inline bool IsDead() const;
   void Kill();
 
   const Operator* op() const { return op_; }
 
   IrOpcode::Value opcode() const {
     DCHECK(op_->opcode() <= IrOpcode::kLast);
     return static_cast<IrOpcode::Value>(op_->opcode());
   }
 
   NodeId id() const { return IdField::decode(bit_field_); }
@@ skipping 42 matching lines @@
   void AppendInput(Zone* zone, Node* new_to);
   void InsertInput(Zone* zone, int index, Node* new_to);
   void InsertInputs(Zone* zone, int index, int count);
   void RemoveInput(int index);
   void NullAllInputs();
   void TrimInputCount(int new_input_count);
 
   int UseCount() const;
   void ReplaceUses(Node* replace_to);
 
-  class InputEdges final {
-   public:
-    typedef Edge value_type;
+  class InputEdges;
+  inline InputEdges input_edges();
 
-    class iterator;
-    inline iterator begin() const;
-    inline iterator end() const;
-
-    bool empty() const;
-
-    explicit InputEdges(Node* node) : node_(node) {}
-
-   private:
-    Node* node_;
-  };
-
-  InputEdges input_edges() { return InputEdges(this); }
-
-  class V8_EXPORT_PRIVATE Inputs final {
-   public:
-    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) {}
-
-   private:
-    Node* node_;
-  };
-
-  Inputs inputs() { return Inputs(this); }
+  class Inputs;
+  inline Inputs inputs() const;
 
   class UseEdges final {
    public:
     typedef Edge value_type;
 
     class iterator;
     inline iterator begin() const;
     inline iterator end() const;
 
     bool empty() const;
@@ skipping 181 matching lines @@
 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());
 }
 
+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_;
+};
 
 // 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 use_->from(); }
   Node* to() const { return *input_ptr_; }
   int index() const {
     int const index = use_->input_index();
     DCHECK_LT(index, use_->from()->InputCount());
     return index;
   }
 
   bool operator==(const Edge& other) { return input_ptr_ == other.input_ptr_; }
   bool operator!=(const Edge& other) { return !(*this == other); }
 
   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;
   friend class Node::InputEdges::iterator;
 
   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::Use* use_;
   Node** input_ptr_;
 };
 
+bool Node::IsDead() const {
+  Node::Inputs inputs = this->inputs();
+  return inputs.count() > 0 && inputs[0] == nullptr;

[Jarin, 2017/01/10 10:53:39]

I actually think the original function will generate pretty much the same code.

[Leszek Swirski, 2017/01/10 12:03:38]

You'd be surprised! I checked the disassembled versions of ReduceTop (because of
inlining) with and without this patch, and the dead check changes from 68 to 44
bytes, 20 to 15 instructions, 5 to 4 loads, and 5 to 4 jumps. I think the
bitfield access to the inline count field may be confusing the compiler.

+}
+
+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_);
+  }
+}
 
 // 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 std::ptrdiff_t difference_type;
   typedef Edge value_type;
   typedef Edge* pointer;
   typedef Edge& reference;
 
   iterator() : use_(nullptr), input_ptr_(nullptr) {}
   iterator(const iterator& other)
       : use_(other.use_), input_ptr_(other.input_ptr_) {}
 
   Edge operator*() const { return Edge(use_, input_ptr_); }
   bool operator==(const iterator& other) const {
     return input_ptr_ == other.input_ptr_;
   }
   bool operator!=(const iterator& other) const { return !(*this == other); }
   iterator& operator++() {
     input_ptr_++;
     use_--;
     return *this;
   }
   iterator operator++(int);
   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 {
-    return static_cast<difference_type>(input_ptr_ - other.input_ptr_);
+    return input_ptr_ - other.input_ptr_;
   }
 
  private:
   friend class Node;
 
-  explicit iterator(Node* from, int index = 0)
-      : use_(from->GetUsePtr(index)), input_ptr_(from->GetInputPtr(index)) {}
-
   explicit iterator(Use* use, Node** input_ptr)
       : use_(use), input_ptr_(input_ptr) {}
 
   Use* use_;
   Node** input_ptr_;
 };
 
 
 Node::InputEdges::iterator Node::InputEdges::begin() const {
-  return Node::InputEdges::iterator(this->node_, 0);
+  return Node::InputEdges::iterator(use_root_, input_root_);
 }
 
 
 Node::InputEdges::iterator Node::InputEdges::end() const {
-  return Node::InputEdges::iterator(this->node_, this->node_->InputCount());
+  return Node::InputEdges::iterator(use_root_ - count_, input_root_ + count_);
 }
 
+Edge Node::InputEdges::operator[](int index) const {
+  return Edge(use_root_ + index, input_root_ + index);
+}
 
 // A forward iterator to visit the inputs of a node.
 class Node::Inputs::const_iterator final {
  public:
   typedef std::forward_iterator_tag iterator_category;
-  typedef int difference_type;
+  typedef std::ptrdiff_t difference_type;
   typedef Node* value_type;
-  typedef Node** pointer;
-  typedef Node*& reference;
+  typedef const value_type* pointer;
+  typedef value_type& reference;
 
-  const_iterator(const const_iterator& other) : iter_(other.iter_) {}
+  const_iterator(const const_iterator& other) : input_ptr_(other.input_ptr_) {}
 
-  Node* operator*() const { return (*iter_).to(); }
+  Node* operator*() const { return *input_ptr_; }
   bool operator==(const const_iterator& other) const {
-    return iter_ == other.iter_;
+    return input_ptr_ == other.input_ptr_;
   }
   bool operator!=(const const_iterator& other) const {
     return !(*this == other);
   }
   const_iterator& operator++() {
-    ++iter_;
+    ++input_ptr_;
     return *this;
   }
   const_iterator operator++(int);
   const_iterator& operator+=(difference_type offset) {
-    iter_ += offset;
+    input_ptr_ += offset;
     return *this;
   }
   const_iterator operator+(difference_type offset) const {
-    return const_iterator(iter_ + offset);
+    return const_iterator(input_ptr_ + offset);
   }
   difference_type operator-(const const_iterator& other) const {
-    return iter_ - other.iter_;
+    return input_ptr_ - other.input_ptr_;
   }
 
  private:
   friend class Node::Inputs;
 
-  const_iterator(Node* node, int index) : iter_(node, index) {}
+  explicit const_iterator(Node* const* input_ptr) : input_ptr_(input_ptr) {}
 
-  explicit const_iterator(Node::InputEdges::iterator iter) : iter_(iter) {}
-
-  Node::InputEdges::iterator iter_;
+  Node* const* input_ptr_;
 };
 
 
 Node::Inputs::const_iterator Node::Inputs::begin() const {
-  return const_iterator(this->node_, 0);
+  return const_iterator(input_root_);
 }
 
 
 Node::Inputs::const_iterator Node::Inputs::end() const {
-  return const_iterator(this->node_, this->node_->InputCount());
+  return const_iterator(input_root_ + count_);
 }
 
+Node* Node::Inputs::operator[](int index) const { return input_root_[index]; }
 
 // 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_, current_->input_ptr()); }
   bool operator==(const iterator& other) const {
     return current_ == other.current_;
@@ skipping 70 matching lines @@
 }
 
 
 Node::Uses::const_iterator Node::Uses::end() const { return const_iterator(); }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_NODE_H_